BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:Global Solutions of Nonconvex Standard Quadratic P
rograms via Mixed Integer Linear Programming Formu
lations - Emre Alper Yildirim (Koc University\, T
urkey)
DTSTART:20181213T120000Z
DTEND:20181213T130000Z
UID:TALK3413AT
URL:/talk/index/3413
DESCRIPTION:A standard quadratic program is an optimization pr
oblem that consists of minimizing a (nonconvex) qu
adratic form over the unit simplex. We focus on re
formulating a standard quadratic program as a mixe
d integer linear programming problem. We propose t
wo alternative mixed integer linear programming fo
rmulations. Our first formulation is based on cast
ing a standard quadratic program as a linear progr
am with complementarity constraints. We then emplo
y binary variables to linearize the complementarit
y constraints. For the second formulation\, we fir
st derive an overestimating function of the object
ive function and establish its tightness at any gl
obal minimizer. We then linearize the overestimati
ng function using binary variables and obtain our
second formulation. For both formulations\, we pro
pose a set of valid inequalities. Our extensive co
mputational results illustrate that the proposed m
ixed integer linear programming reformulations sig
nificantly outperform other global solution approa
ches. On larger instances\, we usually observe imp
rovements of orders of magnitude.\n\nThis is joint
work with Jacek Gondzio.
LOCATION:Nuffield G13
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR