A simplex algorithm for rational cp-factorization

DOI10.1007/S10107-020-01467-4MaRDI QIDQ2020599zbMATH OpenOpenAlexFDO

Authors Achill Schürmann, Frank Vallentin, Mathieu Dutour Sikirić

Publication date 23 April 2021

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

matrix factorizationcomplete positivitycopositive programmingcopositive minimum

Mathematics Subject Classification ID

Quadratic programming (90C20) Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Minima of forms (11H50)

Abstract: In this paper we provide an algorithm, similar to the simplex algorithm, which determines a rational cp-factorization of a given matrix, whenever the matrix allows such a factorization. This algorithm can be used to show that every integral completely positive $2imes2$ matrix has an integral cp-factorization.

Recommendations

• Factorization of cp-rank-\(3\) completely positive matrices.
• scientific article; zbMATH DE number 5613138
• A note on the computation of the CP-rank
• On the number of CP factorizations of a completely positive matrix
• A polynomial-time algorithm for computing low CP-rank decompositions

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 192896 (Why is no real title available?)
• scientific article; zbMATH DE number 1859030 (Why is no real title available?)
• scientific article; zbMATH DE number 7300556 (Why is no real title available?)
• A factorization method for completely positive matrices
• A note on the computation of the CP-rank
• Algorithmic copositivity detection by simplicial partition
• An improved characterisation of the interior of the completely positive cone
• Classification of eight-dimensional perfect forms
• Completely positive matrices: real, rational, and integral
• Computational geometry of positive definite quadratic forms. Polyhedral reduction theories, algorithms, and applications
• Dual Cones and the Voronoi Algorithm
• Factorization and cutting planes for completely positive matrices by copositive projection
• GitHub
• Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
• Integer completely positive matrices of order two
• Interior points of the completely positive cone
• Linear inequalities and quadratic forms
• Matrix product constraints by projection methods
• On the accuracy of uniform polyhedral approximations of the copositive cone
• On the computation of \(C^*\) certificates
• On the computational complexity of membership problems for the completely positive cone and its dual
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Rational factorizations of completely positive matrices
• Some NP-complete problems in quadratic and nonlinear programming
• The \(\mathcal A\)-truncated \(K\)-moment problem
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization

Cited in

(6)

• Completely positive factorization by a Riemannian smoothing method
• Perfect copositive matrices
• Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
• Bounding the separable rank via polynomial optimization
• An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix
• A polynomial-time algorithm for computing low CP-rank decompositions

Describes a project that uses

Uses Software

• GitHub

This page was built for publication: A simplex algorithm for rational cp-factorization

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