In many cutting-edge paradigms that have been developed for joint optimization of multiple systems, it may be unrealistic to expect solutions that are guaranteed to be feasible with respect to all possible constraints of each system. This is particularly the case in systems that operate under dynamic environments and are subject to uncertain events such as terrorist attacks or natural disasters. Even when feasibility may be guaranteed, the resulting solutions could be overly conservative. In this project, we will consider one such paradigm for optimization, which we refer to as optimization problems with system choice (OPSC). This class of problems includes as special cases multiple-choice constrained optimization, optimization under sparsity constraints, linear programs with constraint selection, and chance-constrained programs. While convex conic optimization problems are efficiently solvable, the presence of nonconvexities, such as systems choice decisions, present significant new challenges and the state-of-the-art algorithms do not scale well. The prevailing approach to address related problems is to introduce additional binary variables to represent the constraint choice and use big-M formulations to enforce constraints that are chosen. Branch-and-bound solvers are used to solve the resulting mixed-integer representation, but it is well-known that the continuous relaxations of the big-M formulations are weak, which affects the performance of the branch-and-bound algorithm negatively. In special cases of this problem, there is some work to improve the relaxation bounds by deriving valid inequalities from individual constraints. However, when multiple constraints define a system, as in the general case of OPSC, ignoring the interactions between the constraints may lead to weak inequalities. The proposed foundational research will establish frameworks that overcome these challenges by exploiting valuable structural information in a unified manner. The main developments will address key trade-offs on relaxation quality and computational tractability.The proposed research aims to develop foundational theory to study the key properties of structured non-convex sets and design new efficient algorithms. The focus will be on development of new systemic techniques to generate classes of valid inequalities to improve the continuous relaxations (expressed in linear or conic form) that are effective and easy to incorporate into existing and/or novel algorithmic frameworks. Our primary focus will be deriving strong valid inequalities based on the polyhedral characterizations of the convex constraints. This research will introduce non-traditional paradigms for incorporating more information into the convexification process from different types of cones and multiple conic structures simultaneously present, by explicitly considering the interactions between multiple system constraints. The strength of the proposed inequalities, their separation, and computational complexity trade-offs will be rigorously quantified. Whenever possible, these developments will be supplemented with explicit results on convex hull characterizations and accompanied with efficient algorithms to further enhance the scalability of this approach.
|Effective start/end date||5/1/19 → 4/30/22|
- Office of Naval Research (N00014-19-1-2321)