Scalable semidefinite programming

Volkan Cevher (EPFL)

08-Jun-2020, 13:00-14:00 (4 years ago)

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

Export talk to