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
Demographic reconstruction from paleogenomes of th
Thursday 25 February 2021 - 14h00
Salle : 435 - PCRI-N
Nina Marchi .............................................

A Graph-based Similarity Approach to Classify Recu
Thursday 18 February 2021 - 14h00
Salle : 435 - PCRI-N
Coline Gianfrotta .............................................

"Answer Set Programming for computing constraints-
Thursday 04 February 2021 - 14h00
Salle : 435 - PCRI-N
Maxime Mahout .............................................

"Pandæsim: An Epidemic Spreading Stochastic Simula
Thursday 14 January 2021 - 14h00
Salle : 435 - PCRI-N
Patrick Amar .............................................

Disentangling the role of selection on the evoluti
Friday 02 October 2020 - 17h30
Salle : 455 - PCRI-N
Fanny Pouyet .............................................