[Amath-seminars] Hongbo Dong - Tuesday April 22 at 4:00 - EEB 303

Amin Jalali 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.

TOPS organizers
April 22, 2014, 4:00pm
EEB 303

*Speaker: Hongbo Dong, Math-WSU*

*Title: **A New Approach to Relax Nonconvex Quadratics*

*Abstract: *In many areas of engi­neer­ing and com­puter sci­ences,
opti­miza­tion mod­els with non­con­vex qua­dratic func­tions nat­u­rally
arise, such as var­i­ous mod­els related to process net­works in Chem­i­cal
Engi­neer­ing, com­pu­ta­tional geom­e­try, as well as cut­ting and
par­ti­tion­ing of graphs. Tractable con­vex relax­ations are often
cru­cial when the global opti­mal solu­tion or a good approx­i­mate
solu­tion is of inter­ests. How­ever, most cur­rent relax­ation meth­ods
based on lifting/linearization are bot­tle­necked by the huge amount of
addi­tional vari­ables intro­duced, espe­cially when there are dense
qua­drat­ics with a mod­er­ate num­ber of vari­ables (n >= 70).

In this talk, we will first describe a few sce­nar­ios where non­con­vex
qua­drat­ics nat­u­rally arise. Then we will briefly overview some
state-of-the-art relax­ation meth­ods based on poly­he­dral as well as
semi­def­i­nite tech­niques. Finally I will intro­duce a novel cut­ting
sur­face approach to derive con­vex qua­dratic relax­ations. Our approach
uses diag­o­nal per­tur­ba­tions of the qua­drat­ics as cut­ting sur­faces
that are iter­a­tively added into relax­ations. We devise a spe­cial­ized
heuris­tic algo­rithm to search for good cut­ting sur­faces, where each
iter­a­tion needs only O(n^2) flops. Com­pu­ta­tional results show promises
of our new approach, espe­cially when large dense qua­drat­ics are present.
We show that on a model with one non­con­vex qua­dratic func­tion, only a
small num­ber of cut­ting sur­faces are needed to cap­ture the most
strength of a semi­def­i­nite relax­ation, while our approach is much more
scal­able. We also com­pare with another approach that gen­er­ates con­vex
cut­ting sur­faces pro­posed by (Sax­ena, Bonami and Lee, 2011). We obtain
slightly weaker bounds but in 1–2 orders of mag­ni­tude shorter time.
Finally, we also dis­cuss how to incor­po­rate our meth­ods into a gen­eral
branch-and-bound solver for mixed-integer qua­drat­i­cally con­strained
pro­grams (MIQCP).

This work is based on our recent sub­mis­sion avail­able here,
http://www.optimization-online.org/DB_HTML/2014/03/4274.html .
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman13.u.washington.edu/pipermail/amath-seminars/attachments/20140420/65de6074/attachment.html>

More information about the Amath-seminars mailing list