New Theory and Algorithms for Convex Optimization with Non-Standard Structures

Optimization models and algorithms have long played central and indispensable roles in the advancement of science and engineering. In recent years, first-order methods have played important roles in tackling applications arising in machine learning and data science, due to their simplicity, reasonab...

Full description

Bibliographic Details
Main Author: Zhao, Renbo
Other Authors: Freund, Robert M.
Format: Thesis
Published: Massachusetts Institute of Technology 2023
Online Access:https://hdl.handle.net/1721.1/151475
https://orcid.org/0000-0002-8226-9243
_version_ 1826203056636690432
author Zhao, Renbo
author2 Freund, Robert M.
author_facet Freund, Robert M.
Zhao, Renbo
author_sort Zhao, Renbo
collection MIT
description Optimization models and algorithms have long played central and indispensable roles in the advancement of science and engineering. In recent years, first-order methods have played important roles in tackling applications arising in machine learning and data science, due to their simplicity, reasonably fast convergence rate, and low periteration computational cost. However, there exist many important applications that violate the fundamental assumptions on which existing first-order methods are based — specifically, the objective function, despite being convex, is neither Lipschitz nor has Lipschitz-gradient on the feasible region. The purpose of this thesis is to propose new optimization models for these “non-standard” problems, develop new first-order methods to solve these models, and analyze the convergence rate of these methods. In the first chapter, we present and analyze a new generalized Frank-Wolfe method for the composite convex optimization problem min𝑥∈R𝑛𝑓(A𝑥) + ℎ(𝑥), where 𝑓 is a 𝜃-logarithmically-homogeneous self-concordant barrier, A is a linear operator and the function ℎ has a bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires 𝑂((𝛿0 + 𝜃 + 𝑅ℎ) ln(𝛿0) + (𝜃 + 𝑅ℎ)2/𝜀) iterations to produce an 𝜀-approximate solution, where 𝛿0 denotes the initial optimality gap and 𝑅ℎ is the variation of ℎ on its domain. This result establishes certain intrinsic connections between 𝜃-logarithmically homogeneous barriers and the Frank-Wolfe method. When specialized to the 𝐷-optimal design problem, we essentially recover the complexity obtained by Khachiyan (1996) using the Frank-Wolfe method with exact line-search. In the second chapter, we present and analyze a new away-step Frank-Wolfe method for the convex optimization problem min𝑥∈𝒳 𝑓(A𝑥) + ⟨𝑐, 𝑥⟩, where 𝑓 is a 𝜃-logarithmically-homogeneous self-concordant barrier, A is a linear operator, ⟨𝑐, ·⟩ is a linear function and 𝒳 is a nonempty polytope. We establish the global linear convergence rate of our Frank-Wolfe method in terms of both the objective gap and the Frank-Wolfe gap. This, in particular, settles the question raised in Ahipasaoglu, 3 Sun and Todd (2008) on the global linear convergence of the away-step Frank-Wolfe method specialized to the D-optimal design problem. In the third chapter, we propose a generalized multiplicative gradient (MG) method for a class of convex optimization problems, which, roughly speaking, involves minimizing a 1-logarithmically-homogeneous function over a “slice” of symmetric cone. This problem class includes several important applications, including positron emission tomography, D-optimal design, quantum state tomography, and Nesterov’s relaxation of boolean quadratic optimization. We show, via the machinery of Euclidean Jordan algebra, that this generalized MG method converges with rate 𝑂(ln(𝑛)/𝑘), where 𝑛 denotes the rank of the symmetric cone.
first_indexed 2024-09-23T12:30:59Z
format Thesis
id mit-1721.1/151475
institution Massachusetts Institute of Technology
last_indexed 2024-09-23T12:30:59Z
publishDate 2023
publisher Massachusetts Institute of Technology
record_format dspace
spelling mit-1721.1/1514752023-08-01T03:45:10Z New Theory and Algorithms for Convex Optimization with Non-Standard Structures Zhao, Renbo Freund, Robert M. Massachusetts Institute of Technology. Operations Research Center Optimization models and algorithms have long played central and indispensable roles in the advancement of science and engineering. In recent years, first-order methods have played important roles in tackling applications arising in machine learning and data science, due to their simplicity, reasonably fast convergence rate, and low periteration computational cost. However, there exist many important applications that violate the fundamental assumptions on which existing first-order methods are based — specifically, the objective function, despite being convex, is neither Lipschitz nor has Lipschitz-gradient on the feasible region. The purpose of this thesis is to propose new optimization models for these “non-standard” problems, develop new first-order methods to solve these models, and analyze the convergence rate of these methods. In the first chapter, we present and analyze a new generalized Frank-Wolfe method for the composite convex optimization problem min𝑥∈R𝑛𝑓(A𝑥) + ℎ(𝑥), where 𝑓 is a 𝜃-logarithmically-homogeneous self-concordant barrier, A is a linear operator and the function ℎ has a bounded domain but is possibly non-smooth. We show that our generalized Frank-Wolfe method requires 𝑂((𝛿0 + 𝜃 + 𝑅ℎ) ln(𝛿0) + (𝜃 + 𝑅ℎ)2/𝜀) iterations to produce an 𝜀-approximate solution, where 𝛿0 denotes the initial optimality gap and 𝑅ℎ is the variation of ℎ on its domain. This result establishes certain intrinsic connections between 𝜃-logarithmically homogeneous barriers and the Frank-Wolfe method. When specialized to the 𝐷-optimal design problem, we essentially recover the complexity obtained by Khachiyan (1996) using the Frank-Wolfe method with exact line-search. In the second chapter, we present and analyze a new away-step Frank-Wolfe method for the convex optimization problem min𝑥∈𝒳 𝑓(A𝑥) + ⟨𝑐, 𝑥⟩, where 𝑓 is a 𝜃-logarithmically-homogeneous self-concordant barrier, A is a linear operator, ⟨𝑐, ·⟩ is a linear function and 𝒳 is a nonempty polytope. We establish the global linear convergence rate of our Frank-Wolfe method in terms of both the objective gap and the Frank-Wolfe gap. This, in particular, settles the question raised in Ahipasaoglu, 3 Sun and Todd (2008) on the global linear convergence of the away-step Frank-Wolfe method specialized to the D-optimal design problem. In the third chapter, we propose a generalized multiplicative gradient (MG) method for a class of convex optimization problems, which, roughly speaking, involves minimizing a 1-logarithmically-homogeneous function over a “slice” of symmetric cone. This problem class includes several important applications, including positron emission tomography, D-optimal design, quantum state tomography, and Nesterov’s relaxation of boolean quadratic optimization. We show, via the machinery of Euclidean Jordan algebra, that this generalized MG method converges with rate 𝑂(ln(𝑛)/𝑘), where 𝑛 denotes the rank of the symmetric cone. Ph.D. 2023-07-31T19:42:37Z 2023-07-31T19:42:37Z 2023-06 2023-07-13T16:04:11.848Z Thesis https://hdl.handle.net/1721.1/151475 https://orcid.org/0000-0002-8226-9243 In Copyright - Educational Use Permitted Copyright retained by author(s) https://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology
spellingShingle Zhao, Renbo
New Theory and Algorithms for Convex Optimization with Non-Standard Structures
title New Theory and Algorithms for Convex Optimization with Non-Standard Structures
title_full New Theory and Algorithms for Convex Optimization with Non-Standard Structures
title_fullStr New Theory and Algorithms for Convex Optimization with Non-Standard Structures
title_full_unstemmed New Theory and Algorithms for Convex Optimization with Non-Standard Structures
title_short New Theory and Algorithms for Convex Optimization with Non-Standard Structures
title_sort new theory and algorithms for convex optimization with non standard structures
url https://hdl.handle.net/1721.1/151475
https://orcid.org/0000-0002-8226-9243
work_keys_str_mv AT zhaorenbo newtheoryandalgorithmsforconvexoptimizationwithnonstandardstructures