Strong Convexification of Constrained Nonconvex Optimization: Theory and Algorithms
Abstract
The PI#s primary research goal is to investigate Constrained Nonconvex Optimization (CNO), study the exactness and approximation guarantees of its strong convex relaxations, and develop efficient solution algorithms. Through exploring theoretical properties and exploiting optimization structures of CNO, the scope of this YIP proposal is to develop theoretically sound and computationally efficient solution algorithms under cutting-edge applications. Many modern optimization, machine learning, and statistics problems are highly nonconvex, such as integer programs, Quadratically Constrained Quadratic Programs (QCQPs), matrix completion, fair principal component analysis, and sparse regression, many of which have direct relevance to defense-related problems. Albeit important, CNO exhibits the following theoretical and algorithmic challenges: (i) Nonconvexity. The nonconvexity in CNO severely impacts the generalizability of existing convex optimization approaches to solve CNO problems. Hence, it calls for novel solution approaches to solve CNO to (near-)optimality; (ii) Lacking Exactness. Many existing approaches focus on approximate CNO to be an alternative convex optimization. However, it lacks a theoretical understanding of the strength of such approximations; and (iii) Large Scale. Many CNO problem instances are often large scale and existing methods are often unable to scale to solve these real-world instances. To address thesechallenges, we will establish novel optimization frameworks for CNO problems. Specifically, the objectives of this proposal are: (i) to study strong relaxations of CNO through structural exploration and the convexification of a subsystem of the CNO feasible set, referred to as #CNO-R;# (ii) to establish necessary and sufficient conditions under which the relaxations are exact and develop exact algorithms for solving CNO by harvesting the strength of relaxations; and (iii) to investigate effective decomposition solution schemes for solving large-scale CNO problems or its strong relaxations that are computationally efficient and have attractive convergent properties. This research project, if successful, will broaden the research scope on the interface among optimization, statistics, and engineering. The outcomes from this project will be a set of efficient exact solution algorithms as well as approximation algorithms with provable performance guarantees. These algorithms can be incorporated into modeling and solution software, offering effective means to enhance the modeling, analysis, and prediction capabilities of complex systems, aligning with the missions of the ONRMathematical and Resource Optimization program. Approved for Public Release.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Dec 15, 2023
- Source ID
- N000142412066
Entities
People
- Weijun Xie
Organizations
- Georgia Tech Research Corporation
- Office of Naval Research
- United States Navy