Near-optimal Methods for Structured Nonconvex Constrained Optimization Problems and Nonconvex Decent
Abstract
This abstract is Approved for Public Release.Many tasks in Navy, such as resource management and object detection/tracking, can be f,ormulated into large-scale constrained optimization problems, which often involve a high-dimensional variable and/or a huge amount o,f data. Finding their solutions in an analytic way is in general impossible. Hence, efficient algorithms are needed to numerically c,ompute their solutions.This project focuses on nonconvex problems with affine-equality or nonlinear inequality constraints and also,on nonconvex decentralized optimization. The algorithms that we will design fall in the class of first-order methods (FOMs). Besides, certain simple operations like the projection onto a ball, an FOM only requires function value and first-order derivative informati,on of a problem. Compared to second or higher-order methods, FOMs often have much better scalability and require much less memory. W,e aim to design (near) optimal FOMs for solving nonconvex optimization withhard constraints and nonconvex decentralized optimization,, by exploiting various structures. Besides smoothness and/or weak-convexity, we will exploit coordinate-friendly structure, finite-,sum structure, few or many-constraint structure, and also certain regularity conditions of the constraints. We plan to investigate a, novel inexact proximal augmented Lagrangian method (ALM) for nonconvex problems with affine or convex nonlinear constraints. For pr,oblems with nonconvex constraints, we plan to investigate an inexact ALM. For affine-constrained problems, we plan to design a novel, inexact accelerated proximal gradient (iAPG) method to solve each proximal ALM subproblem. With the new iAPG, we can significantly,reduce the number of evaluations on the objective value and gradient, while maintaining the number of matrix-vector multiplications,at an order similar to the best-known result. For nonlinear constrained problems, we plan to design or apply certain variance-reduce,d randomized FOMs to solve each ALM or proximal ALM subproblem. This way, the overall complexity will have low-order dependence on a, target error tolerance and also the number of data samples. For decentralized optimization, we plan to explore multi-communication,based FOMs in order to reach complexity results that can nearly match certain lower-bound results and also to have fast practical co,nvergence for the cases with a poor-connected network. For either convex or nonconvex decentralized optimization, we plan to incorpo,rate a certain acceleration technique in the algorithmic design, such as heavy-ball or momentum-based variance-reduction technique f,or problems that involve streaming data or a huge amount of pre-collected data.If successful, the proposed research in this project,will significantly broaden the applicability ofFOMs for solving large-scale optimization problems. The FOMs that we will design can,efficiently solve complicated-constrained problems and decentralized optimization problems that arise from Navy?s missions, while ex,isting methods are not applicable or cannot solve them efficiently. With our new algorithms, Navy can highly increase its efficiency, and success rate in many tasks, such as resource management, real-time threat detection, object tracking, and data analytics.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 05, 2022
- Source ID
- N000142212573
Entities
People
- Yangyang Xu
Organizations
- Office of Naval Research
- Rensselaer Polytechnic Institute
- United States Navy