Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization

DOI10.1007/s10898-011-9749-3zbMath1268.90051OpenAlexW1991347066MaRDI QIDQ427378

Werner Schachinger, Immanuel M. Bomze, Gabriele Danninger

Publication date: 13 June 2012

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-011-9749-3

zbMATH Keywords

queueinggame theoryreliabilitySchur complementHadamard productrelaxationcopositive matrixtrafficrobust optimizationcongruencetensor productfeasibilitycompletely positive matrixconic optimizationswitched systemattainabilityposynomialconic dualitycopositive reformulationfriction and contact problemnetwork stability

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26)

Related Items

On equivalent representations and properties of faces of the cone of copositive matrices ⋮ Completely positive rooted matrices ⋮ Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ Copositive matrices with circulant zero support set ⋮ Completely positive factorizations associated with Euclidean distance matrices corresponding to an arithmetic progression ⋮ New results on the cp-rank and related properties of co(mpletely )positive matrices ⋮ Generating irreducible copositive matrices using the stable set problem ⋮ Completely positive reformulations of polynomial optimization problems with linear constraints ⋮ A fresh CP look at mixed-binary QPs: new formulations and relaxations ⋮ Completely positive factorization by a Riemannian smoothing method ⋮ A new certificate for copositivity ⋮ Minimal zeros of copositive matrices ⋮ From seven to eleven: completely positive matrices with high cp-rank ⋮ Copositivity and constrained fractional quadratic problems ⋮ Optimization under uncertainty and risk: quadratic and copositive approaches ⋮ (Global) optimization: historical notes and recent developments ⋮ Hermitian completely positive matrices ⋮ Copositive optimization -- recent developments and applications ⋮ Bad Semidefinite Programs: They All Look the Same ⋮ Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision ⋮ Copositive programming via semi-infinite optimization ⋮ Conic formulation of QPCCs applied to truly sparse QPs ⋮ Factorization and cutting planes for completely positive matrices by copositive projection ⋮ On the computational complexity of membership problems for the completely positive cone and its dual ⋮ New approximations for the cone of copositive matrices and its dual ⋮ Testing copositivity via mixed-integer linear programming ⋮ On the algebraic structure of the copositive cone ⋮ Copositivity and sparsity relations using spectral properties ⋮ Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches ⋮ A simplex algorithm for rational cp-factorization ⋮ The extreme rays of the \(6\times 6\) copositive cone ⋮ Completely positive cones: are they facially exposed? ⋮ Copositivity tests based on the linear complementarity problem ⋮ Considering copositivity locally ⋮ Optimality conditions for linear copositive programming problems with isolated immobile indices ⋮ Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices ⋮ The integer cp-rank of \(2 \times 2\) matrices ⋮ Unnamed Item ⋮ A gentle, geometric introduction to copositive optimization

Cites Work

• Copositivity and constrained fractional quadratic problems
• Copositive optimization -- recent developments and applications
• An LPCC approach to nonconvex quadratic programs
• On the computational complexity of membership problems for the completely positive cone and its dual
• Geometry of the copositive and completely positive cones
• Axiomatization of the index of pointedness for closed convex cones
• Quadratic factorization heuristics for copositive programming
• On nonnegative factorization of matrices
• On copositive matrices and strong ellipticity for isotropic elastic materials
• Branch-and-bound approaches to standard quadratic optimization problems
• Characterization of completely positive graphs
• A copositive Q-matrix which is not \(R_ 0\)
• Burer's key assumption for semidefinite and doubly nonnegative relaxations
• Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
• Linear inequalities and quadratic forms
• Conjugate cone characterization of positive definite and semidefinite matrices
• Copositive and semidefinite relaxations of the quadratic assignment problem
• The difference between \(5\times 5\) doubly nonnegative and completely positive matrices
• Copositive programming motivated bounds on the stability and the chromatic numbers
• Critical angles in polyhedral convex cones: Numerical and statistical considerations
• Existence theorems for linear complementarity problems on solid closed convex cones
• A note on the computation of the CP-rank
• The copositive completion problem: unspecified diagonal entries
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• A linear programming reformulation of the standard quadratic optimization problem
• On a subproblem of trust region algorithms for constrained optimization
• On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm
• Perron-Frobenius property of copositive matrices, and a block copositivity criterion
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Four applications of majorization to convexity in the calculus of variations
• Algorithms for determining the copositivity of a given symmetric matrix
• A note on algorithms for determining the copositivity of a given symmetric matrix
• A field guide to the matrix classes found in the literature of the linear complementarity problem
• A note on ``\(5\times 5\) completely positive matrices
• Copositive Lyapunov functions for switched systems over cones
• Searching for critical angles in a convex cone
• Algorithms and applications for approximate nonnegative matrix factorization
• Numerical resolution of cone-constrained eigenvalue problems
• On the computation of \(C^*\) certificates
• Criteria for copositive matrices
• Combinatorial results on completely positive matrices
• Testing the definiteness of matrices on polyhedral cones
• Complete positivity
• Pseudomonotone and copositive star matrices
• Almost copositive matrices
• Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions
• Une caractérisation complete des minima locaux en programmation quadratique
• Extension of linear-quadratic control, optimization and matrix theory
• Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints
• Finite criteria for conditional definiteness of quadratic forms
• Theory of cones
• On a decomposition of conditionally positive-semidefinite matrices
• Copositive-plus Lemke algorithm solves polymatrix games
• Game theoretical foundations of evolutionary stability
• Nonnegativity of bivariate quadratic functions on a triangle
• Completely positive matrices and positivity of least squares solutions
• Positive operators on the \(n\)-dimensional ice cream cone
• Necessary and sufficient conditions for a quadratic form to be positive whenever a set of homogeneous linear constraints is satisfied
• On standard quadratic optimization problems
• Decreasing diagonal elements in completely positive matrices
• New linear program performance bounds for queueing networks
• Fully copositive matrices
• Some optimization reformulations of the extended linear complementarity problem
• A finite algorithm for solving general quadratic problems
• Criteria for copositive matrices of order four
• Using copositivity for global optimality criteria in concave quadratic programming problems
• Detecting all evolutionarily stable strategies
• Role of copositivity in optimality criteria for nonconvex optimization problems
• An alternative theorem for quadratic forms and extensions
• Evolution towards the maximum clique
• Stationary points of bound constrained minimization reformulations of complementarity problems
• Global escape strategies for maximizing quadratic forms over a simplex
• Copositive matrices and Simpson's paradox
• Notes on completely positive matrices
• Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems
• Multiset graph partitioning
• On eigenvalues induced by a cone constraint.
• Semidefinite programming relaxations for semialgebraic problems
• Factorization index for completely positive graphs
• On completely copositive and decomposable linear transformations
• Conditionally definite matrices
• A test for copositive matrices
• A matrix-splitting method for symmetric affine second-order cone complementarity problems
• Spectral theory of copositive matrices
• Building a completely positive factorization
• Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Quadratic-programming criteria for copositive matrices
• Extrémales du cône des matrices de type non négatif, à coefficients positifs ou nuls
• On copositive matrices
• The maximal cp-rank of rank \(k\) completely positive matrices
• CP rank of completely positive matrices of order 5
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• Criteria for copositive matrices using simplices and barycentric coordinates
• Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
• A note on Burer's copositive representation of mixed-binary QPs
• Nonnegative rank factorization -- a heuristic approach via rank reduction
• On copositive matrices with -1, 9, 1 entries
• Cone-constrained eigenvalue problems: Theory and algorithms
• Local minima of quadratic forms on convex cones
• Angular analysis of two classes of non-polyhedral convex cones: the point of view of optimization theory
• Multi-standard quadratic optimization: Interior point methods and cone programming reformulation
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
• Improved SDP bounds for minimizing quadratic functions over the \(\ell^{1}\)-ball
• Normality and modulability indices. I: Convex cones in normed spaces
• Algorithmic copositivity detection by simplicial partition
• Extreme copositive quadratic forms
• Two remarks on copositive matrices
• Extreme copositive quadratic forms. II
• On classes of copositive matrices
• Boundedness relations for linear constraint sets
• Matrix-theoretic criteria for the quasi-convexity and pseudo-convexity of quadratic functions
• Cones, matrices and mathematical programming
• Block pivoting and shortcut strategies for detecting copositivity
• The copositive completion problem
• Quartic formulation of standard quadratic optimization problems
• On pairs of vectors achieving the maximal angle of a convex cone
• D.C. versus copositive bounds for standard QP
• Computable representations for convex hulls of low-dimensional quadratic forms
• Copositivity cuts for improving SDP bounds on the clique number
• The eigenvalue complementarity problem
• Positive Subdefinite Matrices, Generalized Monotonicity, and Linear Complementarity Problems
• Global Optimization with Polynomials and the Problem of Moments
• Minimal CP rank
• Approximation of the Stability Number of a Graph via Copositive Programming
• On the accuracy of uniform polyhedral approximations of the copositive cone
• A semidefinite programming approach to the hypergraph minimum bisection problem
• A Variational Approach to Copositive Matrices
• An improved characterisation of the interior of the completely positive cone
• Depth-first simplicial partition for copositivity detection, with an application to MaxClique
• Mixed 0-1 Linear Programs Under Objective Uncertainty: A Completely Positive Representation
• On generalized bisection of 𝑛-simplices
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• A Conic Duality Frank–Wolfe-Type Theorem via Exact Penalization in Quadratic Optimization
• Constructing copositive matrices from interior matrices
• On the Stability of Isolated and Interconnected Input-Queueing Switches Under Multiclass Traffic
• Global Optimization: A Quadratic Programming Perspective
• Scaling of symmetric matrices by positive diagonal congruence
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
• A conjugate decomposition of the Euclidean space
• Remarks on the recursive structure of copositivity
• Some NP-complete problems in quadratic and nonlinear programming
• A refinement of an inequality of Johnson, Loewy and London on nonnegative matrices and some applications
• On the Matrix Equation X′X = A
• Conditional Positivity of Quadratic Forms in Hilbert Space
• A note on the Talman, Van der Heyden linear complementarity algorithm
• On the Identification of Local Minimizers in Inertia-Controlling Methods for Quadratic Programming
• An approach to robust stability of matrix polytopes through copositive homogeneous polynomials
• Cones of Matrices and Set-Functions and 0–1 Optimization
• A Global Optimization Algorithm for Concave Quadratic Programming Problems
• A General Framework of Continuation Methods for Complementarity Problems
• On the number of local maxima of a constrained quadratic form
• Completely positive matrices associated withM-matrices
• A new proof for the criss-cross method for quadratic programming
• The Delay of Open Markovian Queueing Networks: Uniform Functional Bounds, Heavy Traffic Pole Multiplicities, and Stability
• Copositive realxation for genera quadratic programming
• A Class of Linear Positive Maps in Matrix Algebras
• A Spectral Bundle Method for Semidefinite Programming
• A Class of Linear Positive Maps in Matrix Algebras II
• On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
• Stability of queueing networks and scheduling policies
• Graph Partitioning and Continuous Quadratic Programming
• Necessary and sufficient conditions for quadratic minimality
• A time-stepping method for stiff multibody dynamics with contact and friction
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• The symmetric eigenvalue complementarity problem
• Permitted and Forbidden Sets in Symmetric Threshold-Linear Networks
• Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies
• Semidefinite Programming
• Copositivity and the Minimization of Quadratic Functions with Nonnegativity and Quadratic Equality Constraints
• Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
• An Adaptive Linear Approximation Algorithm for Copositive Programs
• Stability and Instability Matrices for Linear Evolution Variational Inequalities
• Optimal Inequalities in Probability Theory: A Convex Optimization Approach
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• A Copositive Programming Approach to Graph Partitioning
• Measuring the degree of pointedness of a closed convex cone: a metric approach
• LMI Approximations for Cones of Positive Semidefinite Forms
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Extreme copositive quadratic forms
• Optimality conditions for quadratic programming
• Computing Stationary Nash Equilibria of Undiscounted Single-Controller Stochastic Games
• On Cones of Nonnegative Quadratic Functions
• A Survey of the S-Lemma
• On convex cones with infinitely many critical angles
• On the classes of fully copositive and fully semimonotone matrices
• On copositive programming and standard quadratic optimization problems
• Necessary and sufficient conditions for strong ellipticity of isotropic functions in any dimension
• A copositivity probe
• New linear program performance bounds for closed queueing networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item