We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. We also introduce novel branching variable selection strategies which can be used in conjunction with the quadratic relaxations investigated in this work. We integrate the proposed relaxation and branching techniques into the global optimization solver BARON, and test our implementation by conducting numerical experiments on a large collection of problems. Results demonstrate that the proposed implementation leads to very significant reductions in BARON's computational times to solve the test problems.

This is joint work with Carlos Nohra and Arvind Raghunathan.

Bio:
Nick Sahinidis is the John E. Swearingen Professor and Director of the Center for Advanced Process Decision-making at Carnegie Mellon University. He joined Carnegie Mellon in 2007 after a sixteen-year long career at the University of Illinois at Urbana, where he taught in Industrial Engineering and Chemical Engineering. His research has included the development of theory, algorithms, and the BARON software for global optimization of mixed-integer nonlinear programs. Professor Sahinidis’ research activities have been recognized by the INFORMS Computing Society Prize in 2004, the Beale-Orchard-Hays Prize from the Mathematical Programming Society in 2006, the Computing in Chemical Engineering Award in 2010, the Constantin Carathéodory Prize in 2015, and the National Award and Gold Medal from the Hellenic Operational Research Society in 2016. Professor Sahinidis is a fellow of INFORMS and AIChE. He is the Editor-in-Chief of Optimization and Engineering.