Semidefinite programming

We have developed faster, provably correct algorithms for large-scale semidefinite programming (SDP), where the matrix variable has more than 10^13 entries, using two different approaches: sketching and complementarity. The latter, led by my student Lijun Ding, was honored by the INFORMS optimization society best student paper award. These methods handle nearly every useful SDP: Lijun and I showed the conditions required for these methods to succeed are generic and are necessary for any SDP solver to yield a useful solution given noisy problem data.

Talks

• Scalable Semidefinite Programming, E-NLA Seminar, 2021

• Sketchy Decisions: Convex Low Rank Matrix Optimization with Optimal Storage, Simons Institute, 2017 slides

Software

• SketchyCGAL, reproduces experiments from the paper Scalable Semidefinite Programming

Papers

A Strict Complementarity Approach to Error Bound and Sensitivity of Solution of Conic Programs
L. Ding and M. Udell
Optimization Letters, 2022
[arxiv][pdf][url][bib]

On the simplicity and conditioning of low rank semidefinite programs
L. Ding and M. Udell
SIAM Journal on Optimization (SIOPT), 2021
[arxiv][url][bib]

Scalable Semidefinite Programming
A. Yurtsever, J. Tropp, O. Fercoq, M. Udell, and V. Cevher
SIAM Journal on Mathematics of Data Science (SIMODS), 2021
[arxiv][pdf][bib]

An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity
L. Ding, A. Yurtsever, V. Cevher, J. Tropp, and M. Udell
SIAM Journal on Optimization (SIOPT), 2021
Winner of 2017 INFORMS Optimization Society student paper prize
[arxiv][pdf][slides][bib]

kFW: A Frank-Wolfe style algorithm with stronger subproblem oracles
L. Ding, J. Fan, and M. Udell
In revision at Computational Optimization and Applications, 2020
[arxiv][url][bib]

Frank-Wolfe Style Algorithms for Large Scale Optimization
L. Ding and M. Udell
Large-Scale and Distributed Optimization, 2018
[arxiv][pdf][bib]