A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors

DOI10.1137/17M115308XzbMath1406.15026arXiv1711.03704WikidataQ114074312 ScholiaQ114074312MaRDI QIDQ4687245

Jia-Wang Nie, Xinzhen Zhang, Zi Yang

Publication date: 11 October 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

tensorcopositive matrixsymmetric matrixsemidefinite relaxation

Mathematics Subject Classification ID

Related Items (23)

Further results on eigenvalues of symmetric decomposable tensors from multilinear dynamical systems ⋮ On monotonicity and search strategies in face-based copositivity detection algorithms ⋮ An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix ⋮ Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints ⋮ Homogenization for polynomial optimization with unbounded sets ⋮ Copositivity of Three-Dimensional Symmetric Tensors ⋮ The boosted DC algorithm for linearly constrained DC programming ⋮ Dehomogenization for completely positive tensors ⋮ A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization ⋮ Generalized truncated moment problems with unbounded sets ⋮ Copositive tensor optimization problem and its applications to hypergraphs ⋮ Testing copositivity via mixed-integer linear programming ⋮ Hypergraph characterizations of copositive tensors ⋮ Analytical expressions of copositivity for fourth-order symmetric tensors ⋮ An SDP method for copositivity of partially symmetric tensors ⋮ A semidefinite relaxation method for second-order cone tensor eigenvalue complementarity problems ⋮ Best Nonnegative Rank-One Approximations of Tensors ⋮ On copositiveness identification of partially symmetric rectangular tensors ⋮ A semidefinite relaxation method for second-order cone polynomial complementarity problems ⋮ SDP relaxation algorithms for \(\mathbf{P(P}_0)\)-tensor detection ⋮ Copositivity for 3rd-order symmetric tensors and applications ⋮ Copositivity for a class of fourth-order symmetric tensors given by scalar dark matter ⋮ An SDP relaxation method for Perron pairs of a nonnegative tensor

Uses Software

• SeDuMi
• GloptiPoly

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Positive-definite tensors to nonlinear complementarity problems
• Tensor complementarity problem and semi-positive tensors
• Testing copositivity with the help of difference-of-convex optimization
• Symmetric nonnegative tensors and copositive tensors
• Scaling relationship between the copositive cone and Parrilo's first level approximation
• Copositive optimization -- recent developments and applications
• An improved algorithm to test copositivity
• The extreme rays of the \(5 \times 5\) copositive cone
• On the computational complexity of membership problems for the completely positive cone and its dual
• The \(\mathcal A\)-truncated \(K\)-moment problem
• Copositive tensor detection and its applications in physics and hypergraphs
• Linear inequalities and quadratic forms
• Copositive programming motivated bounds on the stability and the chromatic numbers
• A linear programming reformulation of the standard quadratic optimization problem
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Geometric algorithms and combinatorial optimization
• On the complexity of semidefinite programs
• A test for copositive matrices
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Copositivity detection of tensors: theory and algorithm
• Criteria for copositive matrices using simplices and barycentric coordinates
• Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
• On copositive matrices with -1, 9, 1 entries
• Completely positive reformulations for polynomial optimization
• Exploiting symmetry in copositive programs via semidefinite hierarchies
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Certifying convergence of Lasserre's hierarchy via flat truncation
• A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
• Algorithmic copositivity detection by simplicial partition
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Exact Algorithms for Linear Matrix Inequalities
• $M$-Tensors and Some Applications
• Necessary and sufficient conditions for copositive tensors
• A Variational Approach to Copositive Matrices
• GloptiPoly 3: moments, optimization and semidefinite programming
• Semidefinite optimization
• Open problems in the theory of completely positive and copositive matrices
• Some NP-complete problems in quadratic and nonlinear programming
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Properties of Tensor Complementarity Problem and Some Classes of Structured Tensors
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
• All Real Eigenvalues of Symmetric Tensors
• On Linear Copositive Lyapunov Functions and the Stability of Switched Positive Linear Systems
• Optimization of Polynomials on Compact Semialgebraic Sets
• Maxima for Graphs and a New Proof of a Theorem of Turán

This page was built for publication: A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors