YIP Data-driven analysis and design of mathematical optimization algorithms
Abstract
The goal of this project is to develop a principled data-driven framework for the analysis and design of large-scale optimization algorithms. Unfortunately, state-of-the-art algorithms for large-scale optimization, such as first-order methods, suffer from slow and unreliable convergence to high-quality solutions, which can lead to significant failures, particularly in critical applications. As an example, consider a resource allocation problem where we optimize the distribution of resources (e.g., bandwidth, materials, vessels, warfighters) in response to changing demands (e.g., information, capacities, military support). In case of a sudden change indemand in a critical setting such as a battlefield, we must be able to react and respond efficiently, sometimes in a fraction of a second. Unfortunately, current algorithm design frameworks rely on worst-case convergence guarantees, which are often very pessimistic, because they model generic classes of mathematical functions that are not representative of the problems encountered in practical applications. The key insight behind this proposal is that practical applications often require solving numerous similar parametric optimization problems. For example, in resource allocation problems we replan the allocation of resources in response to varying demands, thereby generating a large amount of data. The goal of this project is to harness the emerging power of data to develop a new theoretical framework and practical methods for data-driven performance analysis and automated design of large-scale optimization algorithms. We propose to leverage and extend ideas from robust optimization, operator theory, and statistical learning to achieve the following tightly-integrated objectives: i) We will develop practical tools to numerically analyze the performance of first-ordermethods in parametric optimization, by framing the analysis problem as an optimization problem. This approach combines operator theory and Wasserstein distributionally robust optimization to obtain finite-sample performance guarantees. ii) We will devise an automated framework for designing large-scale optimization algorithms with guaranteed performance, using insights from bilevel optimization and adversarial robust learning. This framework will learn crucial components, such as step-sizes, warm-starts, and acceleration schemes to enhance algorithm efficiency. iii) We will develop efficient software tools to streamline the design and analysis of custom optimizers for a specific application. We will also build a cutting-edge benchmark library for parametric optimization to accelerate future algorithm development. Our project vision is to develop the next-generation optimization tools for large-scale decision-making that will be task-dependent, trainable, and directly deployable on any computational device, from low-power to large-scale. Just as prediction models in artificial intelligence and data science are trained, tested, and deployed automatically, we expect the development of future optimization tools to be similarly automated. These advances have the potential to revolutionize a wide range of disciplines within engineering, applied mathematics, and computer science where optimization is not used because it is considered unsafe and computationally prohibitive, but real-time responsiveness and safety are required. As such, this project is closely aligned with the ONR#s Code 31 program #Mathematical and Resource Optimization,# and, more in general, with U.S. Navy#s vision of exploitthe emerging power of data to for enhanced insight, rapid decision making, and new mission capabilities.Approved for Public Release
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 12, 2025
- Source ID
- N000142512147
Entities
People
- Bartolomeo Stellato
Organizations
- Office of Naval Research
- Trustees of Princeton University
- United States Navy