EFFICIENT ALGORITHMS FOR LEAST SQUARES SEMIDEFINITE PROGRAMMING AND SEMIDEFINITE PROGRAMMING WITH A LARGE NUMBER OF CONSTRAINTS

Abstract

This thesis focuses on designing efficient algorithms for solving large scale least squares semidefinite programming (LSSDP) and linear semidefinite programming (SDP). We first propose an inexact accelerated block coordinate descent (ABCD) method for solving LSSDP via its dual, which has the attractive O(1/k^2) iteration complexity if the subproblems are solved progressively more accurately. Next we design a convergent semi-proximal alternating direction method of multipliers for convex programming problems having three separable blocks in the objective function with the third part being linear. In the last part, we present a majorized semismooth Newton-CG augmented Lagrangian method, called SDPNAL+, for SDP with partial or full nonnegative constraints on the matrix variable. Numerical results for various large scale LSSDPs and SDPs show that the proposed three method is not only fast but also robust in obtaining accurate solutions. They outperform, by a significant margin, other competitive first order methods.