[Mat10] Meghívó a BME Optimalizálási Szemináriumára - 05.22 10:15

[Zsófia Tardos]

Kedves Érdeklődők!

Szeretnénk meghívni Önöket a BME Optimalizálási Szemináriumára, ahol Immanuel
M. Bomze tart előadást "*Copositive relaxation beats Lagrangian dual bounds
in quadratically and linearly constrained QPs" *cĂ­mmel mĂĄjus 22-ĂŠn
csĂźtĂśrtĂśkĂśn a H306-os teremben 10:15-Ăśs kezdettel.

Minden érdeklődőt szeretettel várunk!

*Copositive relaxation beats Lagrangian dual bounds in quadratically and
linearly constrained QPs*

*Immanuel M. Bomze, ISOR, University of Vienna*

For all-quadratic problems (without any linear constraints), it is well
known that the semidefinite relaxation coincides basically with the
Lagrangian dual problem. Here we study a more general case where the
constraints can be either quadratic or linear. To be more precise, we
include explicit sign constraints on the problem variables, and study both
the full Lagrangian dual as well as the Semi-Lagrangian relaxation. We show
that the stronger Semi-Lagrangian dual bounds coincide with the ones
resulting from copositive relaxation. This way, we arrive at a full
hierarchy of tractable conic bounds stronger than the usual Lagrangian dual
(and thus than the SDP) bounds. We also specify sufficient conditions for
tightness of the Semi-Lagrangian (i.e.
copositive) relaxation and show that copositivity of the slack matrix
guarantees global optimality for KKT points of this problem.

A symmetric matrix is called copositive, if it generates a quadratic form
taking no negative values over the positive orthant. Contrasting to
positive-semidefiniteness, checking copositivity is NP-hard. In a
copositive optimization problem, we have to minimize a linear function of a
symmetric matrix over the copositive cone subject to linear constraints.
This convex program has no non-global local solutions. On the other hand,
there are several hard non-convex programs which can be formulated as
copositive programs. This optimization technique shifts complexity from
global optimization towards sheer feasibility questions. Approximation
hierarchies offer a way to obtain approximate solutions by tractable conic
(e.g., semidefinite) optimization techniques.

A szemináriumról további információkat illetve az elhangzott előadások
diĂĄit itt talĂĄlhatjĂĄk:

http://www.math.bme.hu/~diffe/szeminarium/opt.shtml#m


TovĂĄbbi informĂĄciĂł vagy hĂ­rlevĂŠlre valĂł feliratkozĂĄs kĂŠrĂŠse esetĂŠn
írjanak a következő címre: *tardoszs at gmail.com <tardoszs at gmail.com>*

Üdvözlettel,

Tardos ZsĂłfia
--------- következő rész ---------
Egy csatolt HTML ĂĄllomĂĄny ĂĄt lett konvertĂĄlva...
URL: http://lists.math.bme.hu/pipermail/mat10/attachments/20140518/db40814d/attachment.htm