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

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

Activités de recherche : Semidefinite optimization

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
Pierre Andrieu - Agrégation de classements pour le
Thursday 21 October 2021 - 00:00
Salle : 435 - PCRI-N
.............................................

A counting argument for graph colouring
Graph Theory
Friday 08 October 2021 - 11:00
Salle : 445 - PCRI-N
Francois Pirot .............................................

Demographic reconstruction from paleogenomes of th
Thursday 25 February 2021 - 14:00
Salle : 435 - PCRI-N
Nina Marchi .............................................

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

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