서브메뉴
검색
Sparse and Low-Rank Constrained Optimization: Formulations, Theory, and Algorithms
Sparse and Low-Rank Constrained Optimization: Formulations, Theory, and Algorithms
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202105557
- ISBN
- 9798265403667
- DDC
- 519.77
- 저자명
- Li, Yongchun.
- 서명/저자
- Sparse and Low-Rank Constrained Optimization: Formulations, Theory, and Algorithms
- 발행사항
- [Sl] : Georgia Institute of Technology, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 301 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-05, Section: B.
- 주기사항
- Advisor: Xie, Weijun.
- 학위논문주기
- Thesis (Ph.D.)--Georgia Institute of Technology, 2024.
- 초록/해제
- 요약Sparsity and low rank are fundamental concepts in data reduction. Sparse and low-rankconstrained optimization has benefited various application areas by effectively managingthe rapid growth of big data, including machine learning, finance, cloud computing, andhealthcare. Despite its versatility, sparse and low-rank constrained optimization is known tobe NP-hard. This thesis aims to mitigate this challenge by developing novel formulations,theory, and algorithms.This thesis's first part (Chapters 2 and 3) 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 nonsparse counterparts. The submatrix selection problem can be naturally formulated as discrete optimization since whether to select each candidate element corresponds to a binaryvariable. This motivates us to explore discrete algorithms and methods. First, we deriveequivalent mixed-integer convex programming formulations for both sparse constrainedoptimization 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 (Chapters 4 and 5) of this thesis, we propose a general low-rank optimization framework. We show that various problems in optimization and machine learningfall into our framework, including quadratically constrained quadratic program, fair machine learning, and recommendation systems. The low-rank constrained optimization isgenerally NP-hard and not even mixed-integer convex representable. Hence, we leverage partial convexification to obtain a tractable convex relaxation of low-rank constrainedoptimization. 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 partialconvexification matches the original low-rank constrained optimization, and (ii) we derivean 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 acolumn generation algorithm combined with a rank-reduction algorithm. This combinationensures that the output solution satisfies the theoretical guarantees.
- 일반주제명
- Integer programming
- 일반주제명
- Linear programming
- 기본자료저록
- Dissertations Abstracts International. 87-05B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2024 us c eng d■001000017360628
■00520260202105557
■006m o d
■007cr#unu||||||||
■020 ▼a9798265403667
■035 ▼a(MiAaPQ)AAI32315915
■035 ▼a(MiAaPQ)GeorgiaTech75236
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a519.77
■1001 ▼aLi, Yongchun.
■24510▼aSparse and Low-Rank Constrained Optimization: Formulations, Theory, and Algorithms
■260 ▼a[Sl]▼bGeorgia Institute of Technology▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a301 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-05, Section: B.
■500 ▼aAdvisor: Xie, Weijun.
■5021 ▼aThesis (Ph.D.)--Georgia Institute of Technology, 2024.
■520 ▼aSparsity and low rank are fundamental concepts in data reduction. Sparse and low-rankconstrained optimization has benefited various application areas by effectively managingthe rapid growth of big data, including machine learning, finance, cloud computing, andhealthcare. Despite its versatility, sparse and low-rank constrained optimization is known tobe NP-hard. This thesis aims to mitigate this challenge by developing novel formulations,theory, and algorithms.This thesis's first part (Chapters 2 and 3) 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 nonsparse counterparts. The submatrix selection problem can be naturally formulated as discrete optimization since whether to select each candidate element corresponds to a binaryvariable. This motivates us to explore discrete algorithms and methods. First, we deriveequivalent mixed-integer convex programming formulations for both sparse constrainedoptimization 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 (Chapters 4 and 5) of this thesis, we propose a general low-rank optimization framework. We show that various problems in optimization and machine learningfall into our framework, including quadratically constrained quadratic program, fair machine learning, and recommendation systems. The low-rank constrained optimization isgenerally NP-hard and not even mixed-integer convex representable. Hence, we leverage partial convexification to obtain a tractable convex relaxation of low-rank constrainedoptimization. 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 partialconvexification matches the original low-rank constrained optimization, and (ii) we derivean 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 acolumn generation algorithm combined with a rank-reduction algorithm. This combinationensures that the output solution satisfies the theoretical guarantees.
■590 ▼aSchool code: 0078.
■650 4▼aInteger programming
■650 4▼aLinear programming
■690 ▼a0800
■71020▼aGeorgia Institute of Technology.
■7730 ▼tDissertations Abstracts International▼g87-05B.
■790 ▼a0078
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360628▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
