STIR: Scalable Computation of Sublevel Sets of Nonconvex Functions Using Approximate Convex Envelopes
Abstract
Although mathematical optimization algorithms typically focus on finding a single optimal solution, for many problems it is more valuable to also obtain the set of all near-optimal solutions. Specifically, it is valuable to find a subset of the input space that contains all solutions that maximize or almost maximize a function. Having such sublevel sets can help improve robustness, interpretability and implementation when using optimization algorithms for statistics and decision-making. However, the problem of computing these sublevel sets has received much less attention than other more traditional optimization problems. The current best method for computing sublevel sets uses a branch-and-bound approach and computes upper/lower bounds in each partition by decomposing the function into atomic parts, whose upper/lower bounds can be computed; then the bounds of the parts are aggregated together to yield bounds on the function. While this decomposition approach can yield tight bounds for functions with simple structure (e.g., a sum of univariate terms), these bounds are not always tight for more complex functions (e.g., products of univariate terms), which may limit the generalizability and scalability of this approach. Given the scale and complexity of modern datasets and models in statistics and decision making, there is currently a critical need for a general and scalable method for computing sublevel sets. The overall objective of our planned full-scale project is to develop a scalable method for computing sublevel sets of a nonconvex function. The central hypothesis is that using approximate convex/concave envelopes (ACEs) and relaxations to compute upper and lower bounds within a branch-and-bound strategy will result in a scalable method for computing the sublevel sets of such functions. The purpose of this STIR project is to measure the tightness of ACE-based bounds on lower-dimensional functions. Our initial hypothesis is that ACEs will provide tighter bounds than existing approaches for these functions. If this hypothesis proves true, then we will be in possession of strong evidence supporting the use of ACEs within a scalable method for computing sublevel sets of higher-dimensional functions, supporting the central hypothesis of our full-scale project. Our research group is well-prepared to succeed in the proposed STIR project due to our preliminary analysis as well as our experience in developing new models and algorithms for applied optimization problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 25, 2021
- Source ID
- W911NF2110079
Entities
People
- Hugh Medal
Organizations
- Army Contracting Command
- United States Army
- University of Tennessee