On the computational complexity of membership problems for the completely positive cone and its dual

DOI10.1007/s10589-013-9594-zzbMath1330.90103OpenAlexW2126138717MaRDI QIDQ461444

Peter J. C. Dickinson, Luuk Gijben

Publication date: 10 October 2014

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-013-9594-z

zbMATH Keywords

stable setcompletely positiveNP-hardcopositive

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Related Items (76)

Off-diagonal symmetric nonnegative matrix factorization ⋮ Cutting planes for semidefinite relaxations based on triangle-free subgraphs ⋮ On the number of CP factorizations of a completely positive matrix ⋮ Tensors in computations ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ On standard quadratic programs with exact and inexact doubly nonnegative relaxations ⋮ Computing the distance between the linear matrix pencil and the completely positive cone ⋮ Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank ⋮ On conic QPCCs, conic QCQPs and completely positive programs ⋮ Completely positive tensor recovery with minimal nuclear value ⋮ Duality of sum of nonnegative circuit polynomials and optimal SONC bounds ⋮ A polynomial-time algorithm for computing low CP-rank decompositions ⋮ LP-based tractable subcones of the semidefinite plus nonnegative cone ⋮ Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositions ⋮ An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix ⋮ A factorization method for completely positive matrices ⋮ Copositivity detection of tensors: theory and algorithm ⋮ Moment approximations for set-semidefinite polynomials ⋮ A fresh CP look at mixed-binary QPs: new formulations and relaxations ⋮ Completely positive factorization by a Riemannian smoothing method ⋮ Completely positive completely positive maps (and a resource theory for non-negativity of quantum amplitudes) ⋮ Partially positive matrices ⋮ Copositivity and constrained fractional quadratic problems ⋮ Dehomogenization for completely positive tensors ⋮ Optimization under uncertainty and risk: quadratic and copositive approaches ⋮ Interiors of completely positive cones ⋮ Completely Positive Binary Tensors ⋮ Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems ⋮ Approximation hierarchies for copositive cone over symmetric cone and their comparison ⋮ Exploiting ideal-sparsity in the generalized moment problem with application to matrix factorization ranks ⋮ Hermitian completely positive matrices ⋮ Completely positive tensors in the complex field ⋮ A difference-of-convex approach for split feasibility with applications to matrix factorizations and outlier detection ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ A Positivstellensatz for Sums of Nonnegative Circuit Polynomials ⋮ Factorization and cutting planes for completely positive matrices by copositive projection ⋮ Unbounded convex sets for non-convex mixed-integer quadratic programming ⋮ The infinite extendibility problem for exchangeable real-valued random vectors ⋮ Sum of squares basis pursuit with linear and second order cone programming ⋮ Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming ⋮ Convex and concave envelopes: revisited and new perspectives ⋮ Testing copositivity via mixed-integer linear programming ⋮ Exploiting partial correlations in distributionally robust optimization ⋮ Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017 ⋮ The \(\mathcal A\)-truncated \(K\)-moment problem ⋮ Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations ⋮ Analysis of copositive optimization based linear programming bounds on standard quadratic optimization ⋮ Approximation hierarchies for the cone of flow matrices ⋮ On reduced semidefinite programs for second order moment bounds with applications ⋮ Semidefinite approximations of conical hulls of measured sets ⋮ A semidefinite algorithm for completely positive tensor decomposition ⋮ Copositive tensor detection and its applications in physics and hypergraphs ⋮ On cones of nonnegative quartic forms ⋮ Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches ⋮ A simplex algorithm for rational cp-factorization ⋮ Nonconvex min-max fractional quadratic problems under quadratic constraints: copositive relaxations ⋮ A hierarchy of semidefinite relaxations for completely positive tensor optimization problems ⋮ The CP-Matrix Approximation Problem ⋮ Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations ⋮ Polyhedral approximations of the semidefinite cone and their application ⋮ A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors ⋮ Best Nonnegative Rank-One Approximations of Tensors ⋮ Lower Bounds for Polynomials with Simplex Newton Polytopes Based on Geometric Programming ⋮ Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction ⋮ Unnamed Item ⋮ A semidefinite relaxation algorithm for checking completely positive separable matrices ⋮ Pairwise Completely Positive Matrices and Conjugate Local Diagonal Unitary Invariant Quantum States ⋮ The Computational Complexity of Duality ⋮ Linear mappings preserving the copositive cone ⋮ Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems ⋮ The complete positivity of symmetric tridiagonal and pentadiagonal matrices ⋮ Narrowing the difficulty gap for the Celis-Dennis-Tapia problem ⋮ On Degenerate Doubly Nonnegative Projection Problems ⋮ Linear mappings preserving the completely positive rank ⋮ Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem ⋮ A note on completely positive relaxations of quadratic problems in a multiobjective framework

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Copositive optimization -- recent developments and applications
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• Quadratic factorization heuristics for copositive programming
• On nonnegative factorization of matrices
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• On the computation of \(C^*\) certificates
• Geometric algorithms and combinatorial optimization
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Approximation of the Stability Number of a Graph via Copositive Programming
• Copositive Programming
• A Variational Approach to Copositive Matrices
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Some NP-complete problems in quadratic and nonlinear programming
• Linear-Time Complete Positivity Detection and Decomposition of Sparse Matrices
• An Adaptive Linear Approximation Algorithm for Copositive Programs

This page was built for publication: On the computational complexity of membership problems for the completely positive cone and its dual