Hongbo Dong; A New Approach to Relax Nonconvex Quadratics

April 22, 2014, 4:00pm
EEB 303
Hongbo Dong, Depart­ment of Mathematics, Washington State University. 
A New Approach to Relax Nonconvex Quadratics

Abstract: In many areas of engineering and computer sciences, optimization models with nonconvex quadratic functions naturally arise, such as various models related to process networks in Chemical Engineering, computational geometry, as well as cutting and partitioning of graphs. Tractable convex relaxations are often crucial when the global optimal solution or a good approximate solution is of interests. However, most current relaxation methods based on lifting/linearization are bottlenecked by the huge amount of additional variables introduced, especially when there are dense quadratics with a moderate number of variables (n >= 70).

In this talk, we will first describe a few scenarios where nonconvex quadratics naturally arise. Then we will briefly overview some state-of-the-art relaxation methods based on polyhedral as well as semidefinite techniques. Finally I will introduce a novel cutting surface approach to derive convex quadratic relaxations. Our approach uses diagonal perturbations of the quadratics as cutting surfaces that are iteratively added into relaxations. We devise a specialized heuristic algorithm to search for good cutting surfaces, where each iteration needs only O(n^2) flops. Computational results show promises of our new approach, especially when large dense quadratics are present. We show that on a model with one nonconvex quadratic function, only a small number of cutting surfaces are needed to capture the most strength of a semidefinite relaxation, while our approach is much more scalable. We also compare with another approach that generates convex cutting surfaces proposed by (Saxena, Bonami and Lee, 2011). We obtain slightly weaker bounds but in 1-2 orders of magnitude shorter time. Finally, we also discuss how to incorporate our methods into a general branch-and-bound solver for mixed-integer quadratically constrained programs (MIQCP).

This work is based on our recent submission available here.

Leave a Reply

Your email address will not be published. Required fields are marked *