Past Event: Oden Institute Seminar

Convexification techniques for global optimization of nonconvex nonlinear optimization problems

Aida Khajavirad, Assistant Professor, Operations Research and Industrial Engineering Program, Department of Mechanical Engineering, UT Austin

Abstract

Several general-purpose deterministic global optimization algorithms have been developed for nonconvex 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 NLPs. Namely, I discuss 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, 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 extensive numerical results on a number of standard test libraries. Bio 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.