Tuesday, 14:15 - 14:40 h, Room: H 3004


Francois Glineur
Compact polyhedral approximations for convex sets defined by polynomials


Ben-Tal and Nemirovski proposed in 2001 a way to approximate second-order cone optimization with linear optimization. Their technique relies on a clever linear extended formulation for the two-dimensional regular 2k-gon. Since these polygons approximate the two-dimensional disc, polyhedral approximations for any second-order cone optimization problem can be derived. These approximations are compact in the sense that they feature a number of vertices that is exponential in the size of their extended formulation.
In this talk, we present a generalization of this construction that provides new polyhedral approximations for a large class of convex sets defined by convex univariate polynomial inequalities. It relies on a compact extended formulation for a polyhedral approximation of a specific spectrahedron, namely the convex hull of the moment curve. This construction features links with cyclic polytopes and the trigonometric moment curve. We also report on numerical experiments demonstrating usefulness of this technique.


Talk 3 of the invited session Tue.2.H 3004
"Cone factorizations and lifts of convex sets" [...]
Cluster 2
"Combinatorial optimization" [...]


  Payday Loans In Indiana. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.