[Amath-seminars] Hongbo Dong - Tuesday April 22 at 4:00 - EEB 303
amjalali at u.washington.edu
Sun Apr 20 19:47:45 PDT 2014
Dear fellow optimizers,
Just a quick reminder: Hongbo Dong from the Department of Mathematics at
Washington State University will be giving the next TOPS talk.
April 22, 2014, 4:00pm
*Speaker: Hongbo Dong, Math-WSU*
*Title: **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
This work is based on our recent submission available here,
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Amath-seminars