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.
Many problems in engineering design, logistics, manufacturing, and the chemical and biological sciences require finding minima or maxima of cost functions with multiple hills and valleys. Many of these problems are beyond the capabilities of current optimization algorithms and software. To make such problems solvable, researchers have been interested in devising ways to construct smooth envelopes of ragged functions. However, finding envelopes is an exceptionally difficult mathematical task. Non-polyhedral envelopes were known for only about half a dozen types of functions when we began this project. Under this project, we developed novel techniques to derive closed-form expressions for non-polyhedral envelopes for many functional classes that appear frequently in applications. Using these techniques, we obtained the envelopes of roughly 30% of functions that appear in standard engineering design and operational problems. The proposed envelopes promise to increase the size and complexity of nonlinear optimization problems that can be solved to guaranteed global optimality. Some of our envelopes have already been implemened in widely distributed global optimization software systems that are used by a very diverse group of scientists and engineers. Computational results presented in the literature confirm our hypothesis that the envelopes we have obtained facilitate the solution of difficult optimization problems for the first time.
