A Frankfurt Darmstadt Afternoon on Optimization

A Frankfurt-Darmstadt Afternoon on Optimization

June 24, 2022, 16:00 s.t.

Goethe-Universität Frankfurt am Main, Campus Bockenheim

Robert-Mayer-Str. 8, Hilbertraum (3rd floor, 302)

Abstracts:

Venkat Chandrasekaran (California Institute of Technology): Fitting Tractable Convex Sets to Support Function Data

The geometric problem of estimating an unknown compact convex set from evaluations of its support function arises in a range of scientific and engineering applications. Traditional approaches typically rely on estimators that minimize the error over all possible compact convex sets; in particular, these methods do not allow for much incorporation of prior structural information about the underlying set and the resulting estimates become increasingly more complicated to describe as the number of measurements available grows. We address both of these shortcomings by describing a framework for estimating tractably specified convex sets from support function evaluations. Building on the literature in convex optimization, our approach is based on estimators that minimize the error over structured families of convex sets that are specified as linear images of concisely described sets - such as the simplex or the spectraplex - in a higher-dimensional space that is not much larger than the ambient space.

Convex sets parametrized in this manner are significant from a computational perspective as one can optimize linear functionals over such sets efficiently; they serve a different purpose in the inferential context of the present topic, namely, that of incorporating regularization in the reconstruction while still offering considerable expressive power. We provide a geometric characterization of the asymptotic behavior of our estimators, with the analysis relying on the property that certain sets which admit semialgebraic descriptions are Vapnik-Chervonenkis (VC) classes.

Along the way, we also present new bounds on how well arbitrary convex bodies can be approximated by elements from structured non-polyhedral families of convex sets.pine numerical experiments highlight the utility of our framework over previous approaches in settings in which the measurements available are noisy or small in number as well as those in which the underlying set to be reconstructed is non-polyhedral. (Joint work with Yong Sheng Soh and Eliza O'Reilly.)

Max Klimm (TU Berlin): Optimal Information Design for Congested Networks

We consider a network with load-dependent and stochastic travel times. Large mobility services have an informational advantage over single network users as they are able to learn traffic conditions from data. A benevolent mobility service may use this informational advantage in order to steer the traffic equilibrium into a favorable direction. The resulting optimization problem is a task commonly referred to as Bayesian persuasion. We tightly characterize the class of networks in which full information revelation is always an optimal signaling strategy. Moreover, we construct a reduction from optimal signaling to computing an optimal collection of support vectors for the Wardrop equilibrium.

For two states, this insight can be used to compute an optimal signaling scheme. The algorithm runs in polynomial time whenever the number of different supports resulting from any signal distribution is bounded to a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multi-commodity parallel link networks with a constant number of commodities, even when we have a constant number of different states of nature. (Joint work with Svenja M. Griesbach, Martin Hoefer, and Tim Koglin.)