## 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**

**Abstract:**

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**

**Abstract:**

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

**Abstract:**

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 *2*^{k}-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.