Dear faculty members and fellow students,

You are cordially invited to attend my thesis defense.

Title: Fast First-Order Methods for Large-Scale Nonconvex Optimization and Semidefinite Programming

Committee:

Dr. Renato D.C. Monteiro (Advisor), H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Arkadi Nemirovski, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Alexander Shapiro, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Diego Cifuentes, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Samuel Burer, Tippie College of Business, The University of Iowa

Date and Time: Wednesday, July 10th, 2024, 1:00 PM (EST)

Meeting Link and Location: Microsoft Teams. Link: Join the meeting now

Meeting ID: 233 121 228 762

Passcode: Vdgkqf

Abstract:

This dissertation develops fast and scalable algorithms with theoretical complexity guarantees for solving important optimization problem classes including semidefinite programming, nonconvex constrained optimization, and unconstrained composite optimization. Many important real-world problems can be modelled as optimization problems that fit into such problem classes. Examples include phase retrieval, matrix completion, sparse PCA, and finding the maximum stable set of a graph. We display that the methods developed in this thesis are faster than other existing state-of-the art methods on many huge or ill-conditioned instances of such important and relevant problem classes.

Chapter 2 develops adaptive FISTA and inexact proximal point type methods for unconstrained convex, strongly convex, and nonconvex composite optimization problems. We display through extensive computational experiments that our methods are roughly 5-10 times faster on several problem classes. Unlike several of the best-performing state-of-the-art methods which are based on heuristic schemes (with no convergence proof), our methods have theoretical complexity guarantees. Another nice feature of our methods is that they are parameter-free in the sense that they require no knowledge of objective function curvatures.

Chapter 3 presents an adaptive superfast proximal augmented Lagrangian (AS-PAL) method for solving linearly-constrained smooth nonconvex composite optimization problems. Each iteration of AS-PAL inexactly solves a possibly nonconvex proximal augmented Lagrangian (AL) subproblem obtained by an aggressive/adaptive choice of prox stepsize with the aim of substantially improving its computational performance followed by a full Lagrangian multiplier update. A major advantage of AS-PAL compared to other AL methods is that it requires no knowledge of parameters (e.g., size of constraint matrix, objective function curvatures, etc) associated with the optimization problem, due to its adaptive nature not only in choosing the prox stepsize but also in using a crucial adaptive FISTA variant (developed in chapter 2) to solve the proximal AL subproblems. The speed and efficiency of AS-PAL is demonstrated through extensive computational experiments on important classes of problems such as sparse PCA and matrix completion. The experiments show that our method is over ten times faster than other state-of-the-art penalty and AL methods, particularly when high accuracy is required.

Chapter 4 develops a new first-order method named HALLaR for solving huge SDPs with bounded domain. It is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a hybrid low-rank method that uses a mix of the Frank-Wolfe method, low-rank factorization, and the nonconvex optimization solver developed in chapter 2. In contrast to the classical low-rank method developed by Burer and Monteiro, our method HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on many 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 21 minutes, our method can solve a maximum stable set SDP with 1 million vertices and 10 million edges within 1e-10 relative accuracy. HALLaR has also been able to solve, on a personal laptop, a maximum stable set SDP with 17 million vertices and 201 million edges in roughly just 15 hours.