Scalable semidefinite programming
Volkan Cevher (EPFL)
Abstract: This talk first introduces new convex optimization methods based on linear minimization oracles to obtain numerical solutions to semidefinite programs with a low-rank matrix streaming model. This streaming model provides us an opportunity to integrate sketching as a new tool for developing storage optimal convex optimization methods that can solve semidefinite programs (SDP) efficiently within space required to write down the problem and its solution.
In particular, for SDP formulations, we obtain an approximate solution within an $\epsilon$-error region in the objective residual and distance to feasible set, after a total of $\texttt{Const}\cdot \epsilon^{-5/2}\log(n/\epsilon)$ matrix vector multiplications for the linear minimization oracle (approximate eigenvalue calculation), and an additional $\mathcal{O}(\max(n,d)/\epsilon^2)$ arithmetic operations for the remaining arithmetics. $\texttt{Const}$ is problem independent.
We then discuss a practical inexact augmented Lagrangian method for non-convex problems with nonlinear constraints and contrast this approach to the convex one for solving SDPs. We characterize the total computational complexity of the non-convex method subject to a verifiable geometric condition, followed by numerical demonstrations that include, max-cut, unsupervised clustering, and quadratic assignment problems.
The talk is based on joint work with several collaborators, including Alp Yurtsever, Olivier Fercoq, Joel A. Tropp, Madeleine Udell, Fatih Sahin, Armin Eftekhari, and Ahmet Alacaoglu.
optimization and control
Audience: researchers in the topic
Comments: the address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk
One World Optimization seminar
Series comments: Description: Online seminar on optimization and related areas
The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk
Organizers: | Sorin-Mihai Grad*, Radu Ioan BoČ›, Shoham Sabach, Mathias Staudigl |
*contact for this listing |