Back to search

Georgia Institute of Technology

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

Abstract

dc:description.abstract

This thesis presents fast and efficient first-order methods, with provable complexity bounds, for solving unconstrained convex/strongly convex composite optimization problems, linearly-constrained nonconvex composite optimization problems, and semidefinite programs. We show through extensive computational experiments that the algorithms developed in this thesis are anywhere from 5 to 100 times faster than other existing state-of-the-art codes on important classes of optimization problems such as phase retrieval, matrix completion, sparse PCA, and logistic regression. In the context of semidefinite programming, the algorithm developed in this thesis, namely HALLaR, can also solve (to high accuracy) large-scale problems that have never been solved before due to its low-memory requirements and efficient and highly accurate inner solver. For example, in less than 20 minutes, HALLaR can solve a maximum stable set SDP with 1 million vertices and 10 million edges within 1e-5 relative accuracy while the second-best performing method is unable to find such a solution in 4 hours.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Sujanani, Arnesh M.
Advisor dc:contributor.advisor
  • Monteiro, Renato D. C.
Committee members dc:contributor.committeemember
  • Nemirovski, Arkadi
  • Shapiro, Alexander
  • Cifuentes, Diego
  • Burer, Samuel

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/75696

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Sujanani, Arnesh M.. Fast First-Order Methods for Large-Scale Nonconvex Optimization and Semidefinite Programming. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75696