Noa Elad, Satyen Kale and Joseph (Seffi) Naor
Proceedings of 43rd International Colloquium on Automata, Languages and Programming (ICALP), 2016

We consider semidefinite programming through the lens of online algorithms – what happens if not all input is given at once, but rather iteratively? In what way does it make sense for a semidefinite program to be revealed? We answer these questions by defining a model for online semidefinite programming. This model can be viewed as a generalization of online covering-packing linear programs, and it also captures interesting problems from quantum information theory. We design an online algorithm for semidefinite programming,
utilizing the online primal-dual method, achieving a competitive ratio of $$O\left(\log n\right)$$, where $$n$$ is the number of matrices in the primal semidefinite program. We also design an algorithm for semidefinite programming with box constraints, achieving a competitive ratio of $$O\left(\log F^{\ast}\right)$$, where $$F^{\ast}$$ is a sparsity
measure of the semidefinite program. We conclude with an online randomized rounding procedure.