Testing copositivity via mixed-integer linear programming

DOI10.1016/J.LAA.2020.09.002MaRDI QIDQ2226458zbMATH OpenOpenAlexWikidataFDO

Authors Kurt M. Anstreicher

Publication date 12 February 2021

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

Full work available at URL https://doi.org/10.1016/j.laa.2020.09.002

zbMATH Keywords

mixed integer linear programmingcopositive programmingcopositive matrix

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Positive matrices and their generalizations; cones of matrices (15B48) Mixed integer programming (90C11)

Recommendations

• Copositivity tests based on the linear complementarity problem
• An LP-based algorithm to test copositivity
• Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
• An improved algorithm to test copositivity
• Criteria for copositive matrices

Cites work

• A branch-and-cut algorithm for nonconvex quadratic programs with box constraints
• A complete semidefinite algorithm for detecting copositive matrices and tensors
• A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
• A gentle, geometric introduction to copositive optimization
• A new certificate for copositivity
• A variational approach to copositive matrices
• Algorithmic copositivity detection by simplicial partition
• Almost copositive matrices
• An improved algorithm to test copositivity
• Approximation of the stability number of a graph via copositive programming
• Cliques in random graphs
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Copositive matrices with circulant zero support set
• Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On copositive matrices
• 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
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Some NP-complete problems in quadratic and nonlinear programming
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization

Cited in

(8)

• Gradient projection method on the sphere, complementarity problems and copositivity
• The positive edge criterion within COIN-OR's CLP
• An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
• scientific article; zbMATH DE number 4204116 (Why is no real title available?)
• A copositive framework for analysis of hybrid Ising-classical algorithms
• Conic formulation of QPCCs applied to truly sparse QPs
• Performance comparison of two recently proposed copositivity tests
• Copositivity tests based on the linear complementarity problem

Describes a project that uses

Uses Software

• quadprogIP

This page was built for publication: Testing copositivity via mixed-integer linear programming

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