Copositive optimization -- recent developments and applications

DOI10.1016/j.ejor.2011.04.026zbMath1262.90129OpenAlexW2025776604MaRDI QIDQ421783

Immanuel M. Bomze

Publication date: 14 May 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2011.04.026

zbMATH Keywords

clique numberrobust optimizationcompletely positive matrixstandard quadratic optimizationconvexity gap

Mathematics Subject Classification ID

Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

On the number of CP factorizations of a completely positive matrix ⋮ On equivalent representations and properties of faces of the cone of copositive matrices ⋮ Distributionally robust mixed integer linear programs: persistency models with applications ⋮ On distributional robust probability functions and their computations ⋮ Computing the distance between the linear matrix pencil and the completely positive cone ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ SPN graphs: when copositive = SPN ⋮ Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming ⋮ Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems ⋮ Feasibility problems with complementarity constraints ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ On strong duality in linear copositive programming ⋮ Triangle-free graphs and completely positive matrices ⋮ Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ LP-based tractable subcones of the semidefinite plus nonnegative cone ⋮ A variational approach of the rank function ⋮ Testing copositivity with the help of difference-of-convex optimization ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ Interplay of non-convex quadratically constrained problems with adjustable robust optimization ⋮ A factorization method for completely positive matrices ⋮ Immobile indices and CQ-free optimality criteria for linear copositive programming problems ⋮ Necessary and sufficient conditions for copositive tensors ⋮ New results on the cp-rank and related properties of co(mpletely )positive matrices ⋮ An exact completely positive programming formulation for the discrete ordered median problem: an extended version ⋮ Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems ⋮ Moment approximations for set-semidefinite polynomials ⋮ 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 ⋮ From seven to eleven: completely positive matrices with high cp-rank ⋮ The boosted DC algorithm for linearly constrained DC programming ⋮ Copositivity and constrained fractional quadratic problems ⋮ An exact explicit dual for the linear copositive programming problem ⋮ Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems ⋮ Dehomogenization for completely positive tensors ⋮ Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming ⋮ Optimization under uncertainty and risk: quadratic and copositive approaches ⋮ Interiors of completely positive cones ⋮ Performance comparison of two recently proposed copositivity tests ⋮ Global quadratic minimization over bivalent constraints: necessary and sufficient global optimality condition ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ An improved algorithm to test copositivity ⋮ Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision ⋮ Conic formulation of QPCCs applied to truly sparse QPs ⋮ Factorization and cutting planes for completely positive matrices by copositive projection ⋮ Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the computational complexity of membership problems for the completely positive cone and its dual ⋮ A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints ⋮ New approximations for the cone of copositive matrices and its dual ⋮ Exceptional family and solvability of copositive complementarity problems ⋮ Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017 ⋮ On the algebraic structure of the copositive cone ⋮ The structure of completely positive matrices according to their CP-rank and CP-plus-rank ⋮ Copositivity and sparsity relations using spectral properties ⋮ An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints ⋮ Completely positive matrices: real, rational, and integral ⋮ Analytical expressions of copositivity for fourth-order symmetric tensors ⋮ Convexifiability of continuous and discrete nonnegative quadratic programs for gap-free duality ⋮ The extreme rays of the \(6\times 6\) copositive cone ⋮ Extremal copositive matrices with minimal zero supports of cardinality two ⋮ A MAX-CUT formulation of 0/1 programs ⋮ A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors ⋮ Building a completely positive factorization ⋮ Unnamed Item ⋮ Copositivity tests based on the linear complementarity problem ⋮ Optimality conditions for linear copositive programming problems with isolated immobile indices ⋮ A polynomial-time interior-point method for circular cone programming based on kernel functions ⋮ The integer cp-rank of \(2 \times 2\) matrices ⋮ Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction ⋮ Unnamed Item ⋮ Pairwise Completely Positive Matrices and Conjugate Local Diagonal Unitary Invariant Quantum States ⋮ Completely Positive Tensors: Properties, Easily Checkable Subclasses, and Tractable Relaxations ⋮ Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization ⋮ Two-stage stochastic standard quadratic optimization ⋮ Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems ⋮ On an extension of Pólya's Positivstellensatz ⋮ A gentle, geometric introduction to copositive optimization ⋮ Sign patterns of inverse doubly nonnegative matrices and inverse completely positive matrices ⋮ A note on completely positive relaxations of quadratic problems in a multiobjective framework ⋮ Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme ⋮ Mathematical optimization ideas for biodiversity conservation

Cites Work

• A Copositive Programming Approach to Graph Partitioning
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Optimality conditions for quadratic programming
• On a problem of P. Turan concerning graphs
• On copositive programming and standard quadratic optimization problems
• Necessary and sufficient conditions for strong ellipticity of isotropic functions in any dimension
• 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
• Copositivity and constrained fractional quadratic problems
• Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
• Quadratic factorization heuristics for copositive programming
• Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
• 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 of global minima for constrained optimization
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• A linear programming reformulation of the standard quadratic optimization problem
• Perron-Frobenius property of copositive matrices, and a block copositivity criterion
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Four applications of majorization to convexity in the calculus of variations
• 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
• Testing the definiteness of matrices on polyhedral cones
• 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
• The \(K\)-moment problem for compact semi-algebraic sets
• Nonnegativity of bivariate quadratic functions on a triangle
• On standard quadratic optimization problems
• New linear program performance bounds for queueing networks
• Using copositivity for global optimality criteria in concave quadratic programming problems
• Detecting all evolutionarily stable strategies
• Copositive matrices and Simpson's paradox
• On the crossing number of \(K_{m,n}\)
• Semidefinite programming relaxations for semialgebraic problems
• Conditionally definite matrices
• An interior Newton method for quadratic programming
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• An application of Lemke's method to a class of Markov decision problems
• Spectral theory of copositive matrices
• Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• On copositive matrices
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• The complexity of approximating a nonlinear program
• Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
• A note on Burer's copositive representation of mixed-binary QPs
• Cone-constrained eigenvalue problems: Theory and algorithms
• 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
• Algorithmic copositivity detection by simplicial partition
• Two remarks on copositive matrices
• A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
• Block pivoting and shortcut strategies for detecting copositivity
• Computable representations for convex hulls of low-dimensional quadratic forms
• Copositivity cuts for improving SDP bounds on the clique number
• The eigenvalue complementarity problem
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Copositive Programming
• A Variational Approach to Copositive Matrices
• Depth-first simplicial partition for copositivity detection, with an application to MaxClique
• 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
• Generalized Chebyshev Bounds via Semidefinite Programming
• Global Optimization: A Quadratic Programming Perspective
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Remarks on the recursive structure of copositivity
• Some NP-complete problems in quadratic and nonlinear programming
• A comparison of the Delsarte and Lovász bounds
• An approach to robust stability of matrix polytopes through copositive homogeneous polynomials
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• The Delay of Open Markovian Queueing Networks: Uniform Functional Bounds, Heavy Traffic Pole Multiplicities, and Stability
• Copositive realxation for genera 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
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Permitted and Forbidden Sets in Symmetric Threshold-Linear Networks
• Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies
• 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
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming