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

Friday, October 24, 2014
UTA 7.532

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.


Assistant Professor
University of Texas at Austin

Dr. Aida Khajavirad is an Assistant Professor at The University of Texas at Austin in the graduate program in Operations Research and Industrial Engineering within the Department of Mechanical
Engineering. She completed her Ph.D. in mechanical engineering at Carnegie Mellon University in August 2011, where she was affiliated with the Center for Advanced Process Decision-making. Prior to joining The University of Texas at Austin, Aida worked as a research staff member in the mathematical programming group at IBM T.J. Watson research center for two years. Aida's research interest lies at the interface of convex analysis and nonconvex optimization. Her current work is focused on both theoretical and algorithmic aspects of global optimization of nonconvex mixed-integer nonlinear optimization problems.