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

DOI10.1016/J.LAA.2022.06.015zbMATH Open1493.90127arXiv2205.05381OpenAlexW4282914742WikidataQ114151386 ScholiaQ114151386MaRDI QIDQ2158273FDOQ2158273

Authors: Monique Laurent, Luis Felipe Vargas 

Publication date: 26 July 2022

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

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.

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

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

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)

Cites Work

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

Cited In (8)

• A random copositive matrix is completely positive with positive probability
• A Sum of Squares Characterization of Perfect Graphs
• Exactness of sums of squares relaxations involving \(3\times 3\) matrices and Lorentz cones
• 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)