ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Plenary Talks

Mon 09:15–10:00, Auditorium Max Weber, Chair: Peter Å emrl
Convex sets, matrix factorizations and positive semidefinite rank
Pablo A. Parrilo (Massachusetts Institute of Technology)

In optimization one often represents convex sets in terms of convex cones. Such representations or 'lifts' of a convex set are especially useful if the cone admits efficient algorithms for linear optimization over its affine slices, as in the classical cases of linear and semidefinite programming. In this lecture we discuss the relationship between conic representations of convex sets, and a special "conic" factorization of an operator associated to the convex set, generalizing earlier results of Yannakakis on polyhedral lifts of polytopes and nonnegative factorizations. When the cones live in a family, our results lead to the definition of the rank of a convex set with respect to this family (e.g., the positive semidefinite rank of a convex set), as well as techniques for lower bounding these ranks. We will provide a gentle introduction to these techniques, emphasizing geometric intuition, open questions as well as recent results. Based on joint work with Joao Gouveia, Hamza Fawzi, James Saunderson and Rekha Thomas.

  1. G. Blekherman, P. A. Parrilo, and R. R. Thomas, editors. Semidefinite optimization and convex algebraic geometry, volume 13 of MOS-SIAM Series on Optimization. SIAM, 2012.
  2. H. Fawzi, J. Gouveia P. A. Parrilo, R. Z. Robinson, and R. R. Thomas. Positive semidefinite rank. Mathematical Programming, 153(1):133–177, 2015.
  3. J. Gouveia, P. A. Parrilo, and R. R. Thomas. Lifts of convex sets and cone factorizations. Mathematics of Operations Research, 38(2):248–264, 2013.