Novel Relaxations for Global Optimization

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Software implementing general-purpose deterministic global optimization algorithms for nonconvex nonlinear programs (NLPs) and mixed-integer nonlinear programs (MINLPs) became available for the first time over the past two decades. By building upon results from convex analysis, combinatorial optimization, and convex programming, these algorithms and software have already had a transformative impact in operations research, computer science, engineering design, and computational biology. Yet, there exist vast classes of important applications that these tools are unable to address at the moment. The primary goal of this project is to address the problem that lies at the heart of global optimization algorithms, i.e., the construction of sharp relaxations. Current algorithms iteratively decompose nonconvex functions, through the introduction of variables and constraints for intermediate functional expressions, until the intermediate expressions can be outer-approximated by a convex feasible set. While it is easy to automate, this factorable programming technique often leads to weak relaxations. This project pursues and systematically applies an innovative technique for relaxation construction that generates convex and concave envelopes of nonconvex functions while minimizing, or even entirely eliminating, the steps of this factorable decomposition. The technique relies on ideas from convex analysis with a careful exploitation of properties to derive closed-form solutions for convex optimization problems that characterize convex and concave envelopes of nonconvex functions. The project will develop analytical expressions for the envelopes of a variety of functions that appear in diverse application areas. The project will also investigate the computational implications of using these envelopes in branch-and-cut algorithms for NLPs and MINLPs. If successful, the results of this research will lay the foundations of a new generation of algorithms and software for global optimization capable of solving large-scale nonconvex NLPs and MINLPs that are ubiquitous in engineering design, manufacturing, logistics, and the chemical and biological sciences.