Next Generation Algorithms for Stochastic Optimization with Constraints
Abstract
The objective of this project is to significantly advance the state-of-the-art in terms of the design, analysis, and implementation of algorithms for solving stochastic optimization problems with constraints. In particular, the project focuses on problems involving deterministic constraint functions, but objectivefunctions that are defined by an expectation, or by a large finite sum, in which case stochastic optimization approaches can be computationally beneficial. Such problems, which can arise in numerous important c relatively little attention in the optimization community due to the challenges that arise in designing eective algorithms for solving them. Indeed, in the sparse research in this area, the focus has been on straightforward adaptations of classical optimization techniques from the deterministic to the stochastic setting. These adaptations, which have been superseded by more modern techniques in the deterministic regime, are unlikely to be eective for solving a broad range of cutting edge problems, bothnow and in the ft have been made in the design of constrained optimization algorithms, and build upon modern techniques for stochastic optimization that have born out from the immense recent interest in machine learning, and deep learning in particular. Our eorts will focus on the design, analysis, and implementation of a class of sequential quadratic optimization methods (commonly known as SQP methods), about which our investigators have well-established expertise. Ourresearch team has completed preliminary work on an algorithm for solving problems with general nonlinear equality constraints, and have shown that the proposed approach achieves strong theoretical convergence guarantees, and oers practical performance that is significantly and consistently better than that oered by a state-of-the-art algorithm. The investigators will build upon this work in various ways to design next generation algorithms for solving cutting edge problems, such as by addressing problems that only satisfy weaker assumptions and that involve inequality constraints. They will also design algorithms that allow the use of iterative linear algebra techniques for solving the subproblems that arise within the algorithms, and that allow for these subproblems to be solved inexactly. These advances will oer the utmost compibility such that large-scale problems can be solved efficiently. The project will also answer various related open questions, such as how to handle adaptive algorithm parameters, identify active constraints, and compute accurate Lagrange multipliers in stochastic settings. Theoretical analyses will oer convergence guarantees in expectation and/or with high probability, as well as global convergence rates (i.e., worst-case complexity bounds). A comprehensive software package will be written that encapsulates all of the proposed techniques, and the algorithms will be evaluated using a test suite of synthetic and real-world problems that is to be compiled as part of the project. Our new algorithms, corresponding theory, and software will allow users of mathematical optimization to solve challenging problems that are beyond the reach of state-of-the-art solvers. The proposed project charters a new course in the design of algorithms for solving next generation stochastic optimization problems with constraints. Our work addresses various areas of interest of ONRs Mathematics, Computer and Information Sciences (MCIS) Division, specifically within the Mathematical and Resource Optimization program, due to our focus on the design, analysis, and implementation of algorithms for solving large-scale, stoch
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 09, 2021
- Source ID
- N000142112532
Entities
People
- Frank E. Curtis
Organizations
- Lehigh University
- Office of Naval Research
- United States Navy