Title:  A two-phase proximal augmented Lagrangian method for convex quadratic semidefinite programming

Speaker: Defeng Sun, National University of Singapore

Abstract: In machine learning, finance, statistics, and other areas, numerous interesting problems can be modelled into the form of convex composite quadratic conic programming.  In this talk, we use the  convex quadratic semidefinite programming (QSDP)  problem  as an example to introduce a two-phase proximal augmented Lagrangian method, called QSDPNAL, for solving convex composite quadratic conic programming problems with constraints consisting of a large number  of linear equality, inequality constraints, a simple convex polyhedral set constraint, and a closed convex cone constraint.  As the cornerstone of QSDPNAL, we first introduce the powerful and elegant inexact symmetric Gauss-Seidel (sGS) decomposition technique for solving a convex minimization problem whose objective is the sum of a multi-block (non-separable) quadratic function and a non-smooth function involving only the first block. A first order algorithm which takes advantage of our inexact sGS decomposition technique is adopted in our QSDPNAL-Phase I to generate a reasonably good initial point. Then, in QSDPNAL-Phase II, we design a proximal augmented Lagrangian method (ALM) where the inner sub-problem in each iteration is solved via the inexact accelerated block coordinate descent (ABCD) method, which again relies on our inexact sGS decomposition technique, together with the intelligent incorporation of the semi-smooth Newton-CG algorithm. Moreover, under certain suitable conditions, we are able to analyze the rate of convergence of the proposed algorithm.  We further discuss the important numerical issues in the implementation of QSDPNAL. Extensive numerical results for various large scale QSDPs show that our two-phase framework is not only fast but also robust in obtaining accurate solutions.  [This talk is based on a joint work with Xudong Li and Kim-Chuan Toh].