Numerical Analysis and Scientific Computing Seminar

Convexification Techniques for Global Optimization of Mixed-Integer Nonlinear Optimization Problems

Speaker: Aida Khajavirad

Location: Warren Weaver Hall 1302

Date: Oct. 27, 2017, 10 a.m.

Synopsis:

Several general-purpose deterministic global optimization algorithms have been developed for nonconvex 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, I present a number of new techniques for convexification of nonconvex MINLPs by using ideas from convex analysis, generalized convexity and mixed-integer linear programming.  In the second part of the talk, I will focus on computational implications of the proposed relaxation techniques. I will start by giving a brief overview of the global solver BARON and, subsequently present several new developments along with numerical results on a number of standard test libraries.