Algorithms for Large Scale Nuclear Norm Minimization and Convex Quadratic Semidefinite Programming Problems

Abstract

In this thesis, we focus on designing efficient algorithms for solving large scale nuclear norm minimization and convex quadratic semidefinite programming (QSDP) problems. We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner sub-problems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semi-smoothness property of the singular value soft thresholding operator. To solve convex QSDP problems, we extend the accelerated proximal gradient method to the inexact setting where the sub-problems need only be solved with progressively better accuracy, and show that it enjoys the same superior worst-case iteration complexity as the exact counterpart. Numerical experiments on a variety of large scale nuclear norm minimization and convex QSDP problems show that the proposed algorithms are very efficient and robust.