Séminaire GERAD/ONDI : « A nasty cone with nice properties - new issues in copositive optimization »
514 340-6053, poste 6979
Site Web
2920, chemin de la Tour
Montréal, QC Canada
H3T 1N8
514 343-6111
Site Web | Itinéraire et carte
Consulté 791 fois
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, among them mixed-binary QPs or Standard QPs. Applications range from machine learning to several combinatorial optimization problems, including the maximum-clique problem or the maximum-cut problem.
The dual conic program, unlike the more popular SDP case, involves a different matrix cone, that of completely positive matrices (those which allow for a symmetric, possibly rectangular factorization with no negative entries). This conic optimization technique shifts complexity from global optimization towards sheer feasibility questions. Therefore it is of central importance to devise positive and negative certificates of copositivity and/or complete positivity.