We will present new primal-dual algorithms for convex optimization problems in conic form. On the one hand, our algorithms have desired properties for conic optimization problems at least as general as hyperbolic programming problems. On the other hand, when specialized to certain sparse matrix spaces, our algorithms have the potential of solving extremely large instances of semidefinite programming problems efficiently and robustly.

Our algorithms have many desired properties including polynomial-time iteration-complexity for computing an approximate solution (for well-posed instances). In the special case of dense SDPs (as well as for symmetric cone programming problems with self-scaled barriers), our algorithms specialize to Nesterov-Todd algorithm. However, for certain sparse SDPs, our algorithms are new and have additional desired properties.

The talk is based on joint work with Lieven Vandenberghe.