Back to search

Georgia Institute of Technology

Sparse and Low-rank Constrained Optimization: Formulations, Theory, and Algorithms

Abstract

dc:description.abstract

Sparsity and low rank are fundamental concepts in data reduction. Sparse and low-rank constrained optimization has benefited various application areas by effectively managing the rapid growth of big data, including machine learning, finance, cloud computing, and healthcare. Despite its versatility, sparse and low-rank constrained optimization is known to be NP-hard. This thesis aims to mitigate this challenge by developing novel formulations, theory, and algorithms. This thesis's first part focuses on two classic sparse constrained optimization problems within the domains of optimization and interpretable machine learning. Both problems involve selecting a fixed-size subset of matrix rows and/or columns to maximize metrics like entropy or accuracy, aiming to minimize the gap relative to their non-sparse counterparts. The submatrix selection problem can be naturally formulated as discrete optimization since whether to select each candidate element corresponds to a binary variable. This motivates us to explore discrete algorithms and methods. First, we derive equivalent mixed-integer convex programming formulations for both sparse constrained optimization problems, which pave the way for designing efficient branch-and-cut algorithms to achieve optimality. In addition, we develop scalable approximation algorithms, analyze their first-known theoretical guarantees, and provide their efficient implementations for approximately solving sparse constrained optimization problems. In the second part of this thesis, we propose a general low-rank optimization framework. We show that various problems in optimization and machine learning fall into our framework, including quadratically constrained quadratic program, fair machine learning, and recommendation systems. The low-rank constrained optimization is generally NP-hard and not even mixed-integer convex representable. Hence, we leverage partial convexification to obtain a tractable convex relaxation of low-rank constrained optimization. While partial convexification is often practical, its solution quality lacks theoretical guarantees. We fill this gap by developing a new theory in convex geometry, which offers a geometric perspective to analyze the performance of partial convexification. Specifically, (i) we establish the necessary and sufficient condition under which partial convexification matches the original low-rank constrained optimization, and (ii) we derive an upper bound on the minimum rank among all the optimal solutions of partial convexification and prove its tightness. To efficiently solve partial convexification, we develop a column generation algorithm combined with a rank-reduction algorithm. This combination ensures that the output solution satisfies the theoretical guarantees.

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
  • Li, Yongchun
Advisor dc:contributor.advisor
  • Xie, Weijun
Committee members dc:contributor.committeemember
  • Cifuentes, Diego
  • Dey, Santanu
  • Singh, Mohit
  • Hildebrand, Robert

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Li, Yongchun. Sparse and Low-rank Constrained Optimization: Formulations, Theory, and Algorithms. Doctoral thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/75236