LP-based tractable subcones of the semidefinite plus nonnegative cone

DOI10.1007/S10479-017-2720-ZMaRDI QIDQ1657406zbMATH OpenOpenAlexFDO

Authors Akihiro Tanaka, Akiko Yoshise

Publication date 13 August 2018

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

linear programmingmatrix decompositionmaximum clique problemcopositive conedoubly nonnegative conequadratic optimization problemsemidefinite basissemidefinite plus nonnegative cone

Mathematics Subject Classification ID

Linear programming (90C05)

Abstract: The authors in a previous paper devised certain subcones of the semidefinite plus nonnegative cone and showed that satisfaction of the requirements for membership of those subcones can be detected by solving linear optimization problems (LPs) with $O(n)$ variables and $O(n^2)$ constraints. They also devised LP-based algorithms for testing copositivity using the subcones. In this paper, they investigate the properties of the subcones in more detail and explore larger subcones of the positive semidefinite plus nonnegative cone whose satisfaction of the requirements for membership can be detected by solving LPs. They introduce a {em semidefinite basis (SD basis)} that is a basis of the space of $nimesn$ symmetric matrices consisting of $n(n+1)/2$ symmetric semidefinite matrices. Using the SD basis, they devise two new subcones for which detection can be done by solving LPs with $O(n^2)$ variables and $O(n^2)$ constraints. The new subcones are larger than the ones in the previous paper and inherit their nice properties. The authors also examine the efficiency of those subcones in numerical experiments. The results show that the subcones are promising for testing copositivity as a useful application.

Recommendations

• Cone-LP's and semidefinite programs: geometry and a simplex-type method
• On Cones of Nonnegative Quadratic Functions
• Optimization over structured subsets of positive semidefinite matrices via column generation
• Detection of a copositive matrix over a \(p\)-th order cone
• Linear optimization with cones of moments and nonnegative polynomials

Cites work

• scientific article; zbMATH DE number 3176168 (Why is no real title available?)
• scientific article; zbMATH DE number 715155 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• scientific article; zbMATH DE number 3212891 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 3084780 (Why is no real title available?)
• A Copositive Programming Approach to Graph Partitioning
• Algorithmic copositivity detection by simplicial partition
• An LP-based algorithm to test copositivity
• An improved algorithm to test copositivity
• An introduction to formally real Jordan algebras and their applications in optimization
• Approximation of the stability number of a graph via copositive programming
• Block pivoting and shortcut strategies for detecting copositivity
• Cones of diagonally dominant matrices
• Constructing copositive matrices from interior matrices
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Copositive matrices, copositive programming, and applications
• Copositive optimization -- recent developments and applications
• Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
• Depth-first simplicial partition for copositivity detection, with an application to MaxClique
• Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme
• Geometry of the copositive and completely positive cones
• Matrix Analysis
• On copositive programming and standard quadratic optimization problems
• On generalized bisection of 𝑛-simplices
• On the computation of \(C^*\) certificates
• On the computational complexity of membership problems for the completely positive cone and its dual
• On the copositive representation of binary and continuous nonconvex quadratic programs
• On the exhaustivity of simplicial partitioning
• Optimization over structured subsets of positive semidefinite matrices via column generation
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Some NP-complete problems in quadratic and nonlinear programming
• Testing copositivity with the help of difference-of-convex optimization
• Variational Analysis

Cited in

(2)

• Polyhedral approximations of the semidefinite cone and their application
• Parametric conic optimization problems over semidefinite plus nonnegative cone

This page was built for publication: LP-based tractable subcones of the semidefinite plus nonnegative cone

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