Invited Session Tue.2.H 3004

Tuesday, 13:15 - 14:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Cone factorizations and lifts of convex sets


Chair: Pablo A. Parrilo and Rekha Thomas



Tuesday, 13:15 - 13:40 h, Room: H 3004, Talk 1

Stephen A. Vavasis
Identifying k large submatrices using convex programming

Coauthors: Venkat Chandrasekaran, Xuan Vinh Doan


We consider the problem of identifying k large approximately rank-one submatrices of a nonnegative data matrix. Stated in a certain manner, this problem is NP-hard, but has important applications in data mining. In particular it is a version of the well-known nonnegative matrix factorization, which has been applied to document classification, image decomposition, and analysis of biochemical experiments. We prove that if the data is constructed according to a certain randomized model, then the k blocks can be recovered in polynomial time via convex relaxation.



Tuesday, 13:45 - 14:10 h, Room: H 3004, Talk 2

João Gouveia
Semidefinite lifts of polytopes

Coauthors: Richard Z. Robinson, Rekha R. Thomas


Recently, there has been a renewed interest in understanding the
existence of small linear or semidefinite representations for
polytopes. These representations, which are obtained by adding extra variables, are deeply connected to certain special factorizations of the slack matrix of the polytopes.
In this talk, we explore this connection to present some results on the size of semidefinite lifts of polytopes, with focus on examples, surveying what is known in the area.



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

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.


  cash advance . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.