On the exactness of sum-of-squares approximations for the cone of 5 5 copositive matrices

DOI10.1016/J.LAA.2022.06.015MaRDI QIDQ2158273zbMATH OpenOpenAlexWikidataFDO

Authors Monique Laurent, Luis Felipe Vargas

Publication date 26 July 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2205.05381

zbMATH Keywords

sum-of-squares polynomialscopositive coneHorn matrix

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22) Sums of squares and representations by other particular quadratic forms (11E25) Polynomial optimization (90C23)

Abstract: We investigate the hierarchy of conic inner approximations $mathcal{K}_n^{(r)}$ ($rinmathbbN$) for the copositive cone $ext{COP}_n$, introduced by Parrilo (Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD Thesis, California Institute of Technology, 2001). It is known that $ext{COP}_4=mathcal{K}_4^{(0)}$ and that, while the union of the cones $mathcal{K}_n^{(r)}$ covers the interior of $ext{COP}_n$, it does not cover the full cone $ext{COP}_n$ if $ngeq6$. Here we investigate the remaining case $n=5$, where all extreme rays have been fully characterized by Hildebrand (The extreme rays of the 5 $imes$ 5 copositive cone. Linear Algebra and its Applications, 437(7):1538--1547, 2012). We show that the Horn matrix $H$ and its positive diagonal scalings play an exceptional role among the extreme rays of $ext{COP}_5$. We show that equality $$ holds if and only if any positive diagonal scaling of $H$ belongs to $mathcal{K}_5^{(r)}$ for some $rinmathbbN$. As a main ingredient for the proof, we introduce new Lasserre-type conic inner approximations for $ext{COP}_n$, based on sums of squares of polynomials. We show their links to the cones $mathcal{K}_n^{(r)}$, and we use an optimization approach that permits to exploit finite convergence results on Lasserre hierarchy to show membership in the new cones.

Recommendations

• Scaling relationship between the copositive cone and Parrilo's first level approximation
• New approximations for the cone of copositive matrices and its dual
• Approximation of copositive programming via linear programming using second order sum of square decomposition
• The extreme rays of the \(5 \times 5\) copositive cone
• Faces of the \(5\times 5\) completely positive cone

Cites work

• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 3176168 (Why is no real title available?)
• scientific article; zbMATH DE number 527343 (Why is no real title available?)
• Approximation of the stability number of a graph via copositive programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
• Finite convergence of sum-of-squares hierarchies for the stability number of a graph
• Generating irreducible copositive matrices using the stable set problem
• Global optimization with polynomials and the problem of moments
• Irreducible elements of the copositive cone
• LMI Approximations for Cones of Positive Semidefinite Forms
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On copositive programming and standard quadratic optimization problems
• On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Optimality conditions and finite convergence of Lasserre's hierarchy
• Optimization of Polynomial Functions
• Scaling relationship between the copositive cone and Parrilo's first level approximation
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• Some NP-complete problems in quadratic and nonlinear programming
• Sums of squares, moment matrices and optimization over polynomials
• The extreme rays of the \(5 \times 5\) copositive cone
• Uniform denominators in Hilbert's seventeenth problem

Cited in

(8)

• Exactness of sums of squares relaxations involving \(3\times 3\) matrices and Lorentz cones
• A random copositive matrix is completely positive with positive probability
• A Sum of Squares Characterization of Perfect Graphs
• On the structure of the $6 \times 6$ copositive cone
• Sum-of-squares certificates for copositivity via test states
• Scaling relationship between the copositive cone and Parrilo's first level approximation
• New approximations for the cone of copositive matrices and its dual
• Approximation hierarchies for copositive cone over symmetric cone and their comparison

This page was built for publication: On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2158273)