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
Knowledge Graph Refinement based on Triplet BERT-N
Gestion de données du Web
Monday 29 November 2021 - 13h00
Salle : 455 - PCRI-N
Armita Khajeh Nassiri .............................................

A Hyper-graph Approach for Computing EL+-Ontology
Raisonnement automatique
Monday 15 November 2021 - 13h00
Salle : 445 - PCRI-N
Hui Yang .............................................

Semantic approaches to predict the presence of asb
Intégration de données et de connaissances
Monday 08 November 2021 - 13h00
Salle : 455 - PCRI-N
Thamer Mecharnia .............................................

Pierre Andrieu - Agrégation de classements pour le
Thursday 21 October 2021 - 00h00
Salle : 435 - PCRI-N
.............................................

A counting argument for graph colouring
Théorie des graphes
Friday 08 October 2021 - 11h00
Salle : 445 - PCRI-N
Francois Pirot .............................................