Vortrag: Augmented Lagrangian Approaches for Solving Doubly Nonnegative Progra...
Stammdaten
Titel: | Augmented Lagrangian Approaches for Solving Doubly Nonnegative Programs |
Beschreibung: | Augmented Lagrangian methods are among the most popular first-order approaches to handle large-scale semidefinite programs (SDP). Alternating direction method of multipliers (ADMM) is a variant of the augmented Lagrangian scheme that performs consecutive updates on certain blocks of the dual variables. We present an ADMM where we investigate the possibility of eliminating the positive semidefinite constraint on the dual matrix by employing a factorization. A description on how to deal with the resulting unconstrained maximization of the augmented Lagrangian is given. In particular, we look at doubly nonnegative programs (DNN), these are semidefinite programs where the elements of the matrix variable are constrained to be nonnegative. In an ADMM, these constraints can be handled efficiently since this simply amounts in projections onto the non-negative orthant. Whenever the SDP or DNN is a relaxation of a combinatorial optimization problem, one is interested in using its solution within a branch-and-bound framework. ADMM typically does not yield solutions with a high precision. Having solutions of moderate precision only, the obtained optimum of the SDP or DNN might not be a valid bound for the underlying combinatorial optimization problem. We present a post-processing to obtain valid bounds from the solution of the ADMM. This valid bound can be computed at low cost and the numerical results demonstrate that this procedure does not weaken the bound significantly. This is joint work with Martina Cerulli, Marianna De Santis, Elisabeth Gaar and Franz Rendl. |
Schlagworte: | Conic Optimization, Copositive Optimization |
Typ: | Vortrag auf Einladung |
Homepage: | https://www.ricam.oeaw.ac.at/specsem/specsem2019/workshop6/ |
Veranstaltung: | RICAM Special Semester Optimization (Linz, Johann Radon Institute for Computational and Applied Mathematics) |
Datum: | 10.12.2019 |
Vortragsstatus: |
Beteiligte
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Vortragsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
TeilnehmerInnenkreis |
|
Publiziert? |
|
Keynote-Speaker |
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Organisation | Adresse | ||
---|---|---|---|
Johann Radon Institute for Computational and Applied Mathematics (RICAM)
|
AT
|
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte | Keine verknüpften Projekte vorhanden |
Publikationen | Keine verknüpften Publikationen vorhanden |
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |