BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:A Multigrid approach to SDP relaxations of sparse
polynomial optimization problems - Panos Parpas\,
Imperial Colledge\, London
DTSTART:20161208T120000Z
DTEND:20161208T130000Z
UID:TALK2243AT
URL:/talk/index/2243
DESCRIPTION:We propose a multigrid approach for the global opt
imization of a class of polynomial optimization pr
oblems with sparse support. The problems we consid
er arise from the discretization of infinite dimen
sional optimization problems\, such as PDE optimiz
ation problems\, boundary value problems and some
global optimization applications. In many of these
applications\, the level of discretization can be
used to obtain a hierarchy of optimization models
that captures the underlying infinite dimensional
problem at different degrees of fidelity. This ap
proach\, inspired by multigrid methods\, has been
successfully used for decades to solve large syste
ms of linear equations. However\, it has not been
adapted to SDP relaxations of polynomial optimiza
tion problems. The main difficulty is that the geo
metric information between grids is lost when the
original problem is approximated via an SDP relaxa
tion. Despite the loss of geometric information\,
we show how a multigrid approach can be applied by
developing projection operators to relate the pri
mal and dual variables of the SDP relaxation betwe
en lower and higher levels in the hierarchy of dis
cretizations. We develop sufficient conditions for
the operators to be useful in applications. Our c
onditions are easy to verify in practice\, and we
discuss how they can be used to reduce the complex
ity of infeasible interior point methods. Our prel
iminary results highlight two promising advantages
of following a multigrid approach in contrast wit
h a pure interior point method: the percentage of
problems that can be solved to a high accuracy is
much higher\, and the time necessary to find a sol
ution can be reduced significantly\, especially fo
r large scale problems.\n\n
LOCATION:University House\, room 108
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR