"Sujanani, Arnesh M"


Poster Title:
HALLaR: A New Solver for Solving Huge SDPs

Poster Abstract: 
This poster presents a new first-order method for solving large-scale
semidefinite programs (SDPs) with bounded domain. It is an inexact augmented
Lagrangian (AL) method where the AL subproblems are solved by a hybrid low-rank
method. In contrast to the classical low-rank method, the new method finds a
near-optimal solution (with provable complexity bounds) of SDP instances
satisfying strong duality. Computational results comparing the new method to
state-of-the-art solvers on several large SDP instances show that the former
finds higher accurate solutions in substantially less CPU time than the latter
ones. For example, in less than 20 minutes, our method can solve (on a personal
laptop) a maximum stable set SDP with 1 million vertices and 10 million edges
within 1e-5 relative accuracy. This is joint work with Renato D.C. Monteiro and
Diego Cifuentes.