Optimality Tracking Principle: A Novel and Provable Framework for Optimization and Minimax Problems
Abstract
This proposal aims at introducing a new optimality tracking (OT) priciple which presents as a unified framework to develop highly efficient and provable optimization algorithms for wide classes of optimization and minimax problems arising from data-driven applications. The pro- posed research is divided into four topics ranging from theoretical foundations and algorithms to concrete applications. More specifically, Topic 1 plans to develop the foundation of the proposed OT principle with two major steps. The first one reformulates or parameterizes the underlying problem into a suitable parametric generalized equation, while the second step establishesbounds of solution variation which characterize the variation of a solution trajectory along the parameter horizon. Topic 2 focuseson constructing a class of homotopy generalized Newton-type methods based on the OT principle for generalized equations and applying them to both convex and noncon- vex optimization problems. Topic 3 is devoted to designing efficient OT algorithms for minimax problems. Topic 4 will deal with two key applications: nonlinear model predictive model (NMPC) and adversarial training problems, whichhave a plethora of applications in military operations.Intellectual merit: This proposal advances several techniques, both old and new, to develop a principle approach for designing fast, reliable, and provable optimization algorithms to solve dif- ferent problems. The leading idea is the optimality tracking principle inspired by homotopy and path-following methods in scientific computing. This principle is combined with other recent tools such as smoothing techniques, [generalized] self-concordant structures, and sensitivity analysis to create various combinations for developing new algorithms. These algorithms not only have bet- ter convergence rates and complexity bounds but also possess other advantages such as reliability due to the use of analytical rules, and simple computational operations (e.g., closed form proximal operators and matrix-vector multiplications). Along with the central OT framework, other new ideas will also be exploited in this proposal, including efficient randomized and stochastic variants for minimax problems, and general metrics and Lyapunov functions for characterizing optimality tracking bounds. In particular, new asymptotic stability guarantee bounds for real-time iteration schemes are expected to solve a long-standing (approximately two decades) problem in NMPC.Broader impacts: Due to the rigorously theoretical foundation of the proposed OT framework, new algorithms obtained from this proposal are general, reliable, and efficient. They are expected to make broader impacts in military operations and interdisciplinary researchacross optimization and control, engineering, machine learning, and operations research. A comprehensive integration between the research of this proposal and training activities as well as a new data science lab initiative will bring significant impacts to the new data science programs at the PI#s institution. The two applications in Topic 4 will also have the potential to make great impact in practice, including military applications, where NMPC and adversarial training problems are used.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 29, 2023
- Source ID
- N000142312588
Entities
People
- Quoc Tran-Dinh
Organizations
- Office of Naval Research
- United States Navy
- University of North Carolina at Chapel Hill