Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) ROCS
Copositive relaxation beats Lagrangian dual bounds in quadratically and linearly constrained QPs
Professeur Manuel Bomze

08 November 2013, 10h30 - 08 November 2013, 11h30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Optimisation semidéfinie positive

Résumé :
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.

Pour en savoir plus : http://homepage.univie.ac.at/immanuel.bomze/index.htmlwww.
Séminaires
Quantum at LRI
Calcul quantique
Tuesday 04 February 2020 - 09h00
Salle : 465 - PCRI-N
.............................................

Progressive Data Analysis: a new computation parad
Gestion de données du Web
Friday 24 January 2020 - 14h00
Salle : 435 - PCRI-N
Jean-Daniel Fekete .............................................

Jeux d’instructions : des extensions SIMD aux exte
Architectures parallèles
Tuesday 21 January 2020 - 10h30
Salle : 465 - PCRI-N
Daniel Etiemble .............................................

Forum dev-LRI
Tuesday 14 January 2020 - 14h00
Salle : 445 - PCRI-N
Erik Bray .............................................

La transformation du travail, un analyseur des tra
Wednesday 18 December 2019 - 10h00
Salle : 475 - PCRI-N
Raquel Becerril-Ortega .............................................