NSF Award: Efficiently Computable Convex Approximation Methods for Non-Convex Optimization Problems

A recent NSF Award is given to Luis Zuluaga on Computable Convex Approximation Methods for Non-Convex Optimization Problems.

This research project takes on the challenge of closing the large gap between the current ability to solve convex or integer-linear optimization problems and the capacity to solve non-convex optimization problems by introducing novel methodologies to solve this class of problems using polynomial optimization techniques. In particular, the research will be focused on the following three main directions. The first direction is the introduction of new polynomial optimization techniques that instead of solving non-convex problems exhaustively, do so dynamically. The second one is the introduction and effective use of polynomial optimization results that beyond semidefinite programming tools make full use of the powerful convex optimization toolkit. The third one is the use of polynomial optimization results, related to the convex reformulation of low-dimensional or low-degree non-convex problems, as the foundation to obtain better reformulations for general non-convex problems. This project's practically oriented research is aimed at solving key and difficult decision-making problems that are now regularly faced in the communications, healthcare, electricity, and oil and gas industries. Many times, the difficulty to solve these problems arises from the use of polynomials to closely model the behavior of real-world systems. Modeling real-world systems more accurately is an overarching need in today's competitive and resource-constrained environment.
The results of this research will substantially improve computer-based solvers for this class of problems. The software developed to achieve this goal will use open source software tools that will be made available to the public. The corresponding positive impact on profits, safety, resource management, client satisfaction, etc., will further broaden the practical successes that make Operations Research the "Science of the Better". Furthermore, the challenging nature of this research will provide ample opportunity to the participating graduate students to excel, and its results will be incorporated into appropriate graduate level courses.