A Scalable Optimization Framework for Convex Minimization with Hard Constraints
Abstract
Constrained convex optimization is a powerful tool to solve numerous applications in different domains, including operations research, military, transportation, networks, computer science, machine learning, statistics, and engineering. Constraints in these applications can be classified into soft constraints and hard constraints. Whereas soft constraints allow some degrees of violation and can be handled by penalty and relaxation methods, hard constraints must not be violated, which creates fundamental challenges for existing numerical optimization methods to guarantee their feasibility. Hard constraints are present in various convex optimization applications, especially in military, space exploration, and navigation, where safety conditions become vital. State-of-the-art optimization methods such as penalty and primal-dual schemes often fail to handle the strict feasibility of such constraints due to their naturally approximate termination criteria. The interior-point (IP) method is perhaps the best (if not the only) candidate that can provably handle strict feasibility by means of interior barriers. Unfortunately, existing IP algorithms face a fundamental drawback: scalability, making them less applicable to large-scale applications.This proposal seeks completely new approaches to develop novel algorithms for solving structural convex optimization problems, especially problems with hard constraints. The proposed research is divided into three work packages (WPs). WP1 develops a class of homotopy proximal variable metric algorithms that play a core step in the proximal IP methods. This WP focuses on global convergence rates of the proposed methods under different smooth structures of the objective function. WP2 introduces a proximal IP framework to unify both the proximal-point and interior-point methods and studies its theoretical aspects such as convergence guarantees and complexity estimates. WP3 focuses on three representative applications: convex problems with hard conic constraints, convex relaxations of nonconvex problems, and matrix optimization involving log-determinants. Intellectual merit: This proposal is built on several novel ideas and combinations of advanced techniques in optimization. The homotopy parameterization strategy is key to develop a new class of proximal variable metric algorithms with global convergence rates where existing methods are notefficient or do not have theoretical guarantees. The unification of proximal-point and interior-point methods is novel and has just been recently initiated in the PI~s on-going work. The proposed framework is expected to inherit the robustness and reliability of interior-point methods, while flexibly handlingnonsmooth terms as in proximal-based algorithms. Besides these central ideas and techniques, the PI also proposes a set of new ideas and combines them with the proposed algorithms to efficiently solve three representative applications that potentially have various applications in military and defense.Broader impact: The success of this proposal will create new opportunities to tackle complex large-scale optimization applications, both existing and new models, especially problems with safety constraints and nonsmooth regularizers. The new algorithms from WP1 are expected to address a class ofcomposite convex problems widely used in manufacturing, machine learning, and complex data analysis. The methods proposed in WP2 provide promising tools to deal with problems in robotics, manufacturing, and medical science, where handling safety conditions is crucial. This research program also providesan excellent source to create new research topics for doctoral, master, and undergraduate students.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 17, 2020
- Source ID
- N000142012088
Entities
People
- Quoc Tran-Dinh
Organizations
- Office of Naval Research
- United States Navy
- University of North Carolina at Chapel Hill