Session: Semidefinite programming and applications
Chair: Georgina Hall
Cluster: Conic and Semidefinite Optimization
Talk 1: A Matrix Generalization of the Goemans-Williamson Algorithm for Orthogonality Constrained Optimization Problems
Speaker: Ryan Cory-Wright
Abstract: A central research question in optimization concerns developing algorithms that solve non-convex problems to provable near optimality in a practically tractable amount of time. One popular two-step methodology called ``relax-and-round'' successfully addresses many well-behaved non-convex problems. In 1995, Goemans and Williamson proposed a polynomial-time relax-and-round algorithm for approximately solving Max-Cut problems by rounding their semidefinite relaxations. In this work, we propose a matrix generalization of their approach which applies to orthogonal matrices where U^\top U=I, as opposed to binary variables where z^2=1, and study the quality of this approach in both theory and practice. Our approach has applications in low-rank matrix completion and sparse PCA with multiple PC problems, among others.
Talk 2: Generalized Ellipsoids
Speaker: Cemil Dibek
Abstract: Ellipsoids are fundamental in applied and computational mathematics, featuring in optimization, control, convex geometry, and statistics due to their geometric and computational properties. In this talk, we introduce a new family of symmetric convex bodies called generalized ellipsoids of degree d (GE-ds), with ellipsoids corresponding to the case of d=0. Generalized ellipsoids (GEs) retain many geometric, algebraic, and algorithmic properties of ellipsoids, while also being tractable to search for and optimize over. We show that one can search for GEs of a given degree by solving a semidefinite program whose size grows only linearly with dimension, and that every GE has a semidefinite representation whose size depends linearly on both its dimension and degree. In terms of expressiveness, we demonstrate that every symmetric full-dimensional polytope and every intersection of co-centered ellipsoids can be represented exactly as a GE-d. Using this result, we show that every symmetric convex body can be approximated arbitrarily well by a GE-d. We also present applications of GEs in areas such as portfolio optimization, stability analysis of switched linear systems, and robust optimization.
Talk 3: TBD
Speaker: Georgina Hall
Abstract: TBD
