Branch-and-Bound Based Algorithms for Global Optimization of Nonconvex Nonlinear Optimization Problems

Several general-purpose deterministic global optimization algorithms have been developed for mixed-integer nonlinear optimization problems over the past two decades. Central to the efficiency of such methods is their ability to construct sharp convex relaxations. Current global solvers rely on factorable programming techniques to iteratively decompose nonconvex factorable functions, until each intermediate expression can be outer-approximated by a convex feasible set. While it is easy to automate, this factorable programming technique often leads to weak relaxations.

In this talk, UT Austin Prof. Aida Khajavirad presents a number of new techniques for convexification of nonconvex NLPs.  Namely, she discusses the theory of convex envelopes and present closed-form expressions for the envelopes of various types of functions that are the building blocks of nonconvex problems.  In the second part of the talk, Prof. Khajavirad will focus on computational implications of the proposed relaxation techniques. She will start by giving a brief overview of the global solver BARON and, subsequently present several new developments along with extensive numerical results on a number of standard test libraries.