Efficient second-order methods for continuous nonlinear conic optimization with special structure-23-000004767
Abstract
Numerical optimization has been an essential tool in engineering, research, economics, and othersections of society for many years, including applications relevant to national security. Highly sophisticated optimization software packages are used by practitioners on a daily basis, but limitations remain that prevent the utilization of nonlinear optimization to its full potential. This proposal addresses two of them. The first research thrust pushes the size limitation for an important class of nonlinear nonconvex problemby orders of magnitude beyond the state-of-the-art, and the second aims at accelerating the solution of second-order cone problems in certain cases where a rapid successive application of method is necessary. In both thrusts, the emphasis is on practical and implementable methods with provable convergence guarantees and sophisticated software implementations.A common theme is the use of second-order derivative information to accelerate the methods and enable them to compute highly accurate solutions, and the exploitation of specific problem structures.The first research thrust tackles bi-level nonlinear optimization problems. These exhibit a highly complicated nonconvex structure and no practical algorithms for large-scale instances exist to date.Problems of this type arise in important settings where a leader makes decisions and needs to consider followers# responses to the leader#s decisions. Besides Stackelberg games modeling markets, also important national security questions can be modeled this way, such as interdiction scenarios where one wants to limit the damage an attacker can cause to a vulnerable system. Often, data is unknown, and to capture the uncertaintywell, a large number of scenarios must be included, resulting in very large instances.This research will produce the first paralleldecomposition framework for nonlinear bi-level problems. It utilizes a novel smoothing technique that makes it possible use second-order informationandto incorporate existing and reliable optimization software. A new concept of local minima for nonconvex bi-linear problems will be developed as part of this research. Rigorous theoreticalconvergence guarantees will be established, including fast local convergence to highly accurate solutions by facilitated by second-order information and new extrapolation steps. The research will also investigate spurious nonconvexities that are induced by the smoothing approach and that have been recently discovered bythe PI. Eventually, an efficient open-source C++ software implementation of the framework will be made publicly available.The second thrust is concerned with two important aspects of problems with second-order cone constraints. Problems of this type arise, for example, in financial applications such as portfolio optimization, as a modeling tool in robust optimization, or as convex relaxationsof nonconvex problems. The first part of this research concerns the fundamental open question whether efficient active-set methods exist for this problem class and under which circumstances they outperform state-of-the-art interior-point methods, which are currently the only practical approach. We expect that the new method has a strong potential for small or medium-sized instances, or when instances are solved in quick succession, as in real-time optimal control. Two different active-set approaches will be explored and analyzed, and their practical performance will be compared with state-of-theart interior-point solvers.The second part of this research thrust extends these methods to nonlinear nonconvex instances, significantly broadening the scope of models that a practitioner can use when linear models are not sufficient to accurately represent nonlinear phenomena. The outcome of this project will be a prototype implementation of the algorithm, together with mathematical convergence theory.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Nov 09, 2024
- Source ID
- N000142412658
Entities
People
- Andreas Waechter
Organizations
- Northwestern University
- Office of Naval Research
- United States Navy