Copositive optimization -- recent developments and applications (Q421783): Difference between revisions

An interesting overview on the copositive optimization is presented pointing the diversity of its formulations: continuous, discrete, deterministic, stochastic. Some ideas of approximation hierarchies are sketched, together with some complexity issues. The study of the role of copositivity for local and global optimality conditions reveal new particular results in the case of quadratic optimization. The author pays attention to recursive procedures and to decomposition and adaptive approaches to the copositivity detection. The presentation of the copositive optimization concludes with some interesting success applications: the role of copositivity in the convex underestimation in quadratic optimization problems, finding Lyapunov functions for switched dynamical systems in optimal control, strengthening bounds for a maximum clique problem, finding the best known asymptotic bound for crossing numbers.

0 references

reviewed by

Gabriela Cristescu

0 references

zbMATH Keywords

clique number

0 references

completely positive matrix

0 references

convexity gap

0 references

robust optimization

0 references

standard quadratic optimization

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.ejor.2011.04.026

0 references

cites work

Copositivity and constrained fractional quadratic problems

0 references

Q4353530

0 references

A time-stepping method for stiff multibody dynamics with contact and friction

0 references

Computable representations for convex hulls of low-dimensional quadratic forms

0 references

Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints

0 references

The complexity of approximating a nonlinear program

0 references

Q4405832

0 references

Remarks on the recursive structure of copositivity

0 references

Q4942383

0 references

Detecting all evolutionarily stable strategies

0 references

Block pivoting and shortcut strategies for detecting copositivity

0 references

On standard quadratic optimization problems

0 references

Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality

0 references

Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects

0 references

Perron-Frobenius property of copositive matrices, and a block copositivity criterion

0 references

Global Optimization: A Quadratic Programming Perspective

0 references

Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming

0 references

On copositive programming and standard quadratic optimization problems

0 references

Copositivity detection by difference-of-convex decomposition and $\omega $-subdivision

0 references

Copositivity cuts for improving SDP bounds on the clique number

0 references

A note on Burer's copositive representation of mixed-binary QPs

0 references

Quadratic factorization heuristics for copositive programming

0 references

Q3569180

0 references

Multi-standard quadratic optimization: Interior point methods and cone programming reformulation

0 references

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

0 references

Necessary and sufficient conditions for quadratic minimality

0 references

Four applications of majorization to convexity in the calculus of variations

0 references

Algorithmic copositivity detection by simplicial partition

0 references

An Adaptive Linear Approximation Algorithm for Copositive Programs

0 references

Copositive Lyapunov functions for switched systems over cones

0 references

On the copositive representation of binary and continuous nonconvex quadratic programs

0 references

Copositive Programming

0 references

The difference between $5\times 5$ doubly nonnegative and completely positive matrices

0 references

Q4821606

0 references

An interior Newton method for quadratic programming

0 references

Une caractérisation complete des minima locaux en programmation quadratique

0 references

Q5625366

0 references

Necessary and sufficient conditions for strong ellipticity of isotropic functions in any dimension

0 references

Q3198800

0 references

Using copositivity for global optimality criteria in concave quadratic programming problems

0 references

The complexity of optimizing over a simplex, hypercube or sphere: a short survey

0 references

Numerical block diagonalization of matrix $\ast$-algebras with application to semidefinite programming

0 references

Improved Bounds for the Crossing Numbers of Km,n and Kn

0 references

Approximation of the Stability Number of a Graph via Copositive Programming

0 references

A linear programming reformulation of the standard quadratic optimization problem

0 references

Reduction of symmetric semidefinite programs using the regular $\ast$-representation

0 references

Q3843714

0 references

A note on ``$5\times 5$ completely positive matrices''

0 references

Copositive programming motivated bounds on the stability and the chromatic numbers

0 references

Q5503714

0 references

Q2903231

0 references

Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem

0 references

Finite-Dimensional Variational Inequalities and Complementarity Problems

0 references

Finite-Dimensional Variational Inequalities and Complementarity Problems

0 references

Q3928936

0 references

Q4739659

0 references

Critical angles in polyhedral convex cones: Numerical and statistical considerations

0 references

The Operator $\Psi$ for the Chromatic Number of a Graph

0 references

On copositive matrices

0 references

Copositive matrices and Simpson's paradox

0 references

Permitted and Forbidden Sets in Symmetric Threshold-Linear Networks

0 references

Q5328177

0 references

Clique is hard to approximate within $n^{1-\epsilon}$

0 references

Two remarks on copositive matrices

0 references

A Variational Approach to Copositive Matrices

0 references

The Delay of Open Markovian Queueing Networks: Uniform Functional Bounds, Heavy Traffic Pole Multiplicities, and Stability

0 references

Q5316981

0 references

Conditionally definite matrices

0 references

Searching for critical angles in a convex cone

0 references

Extension of linear-quadratic control, optimization and matrix theory

0 references

Spectral theory of copositive matrices

0 references

The eigenvalue complementarity problem

0 references

Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies

0 references

Global Optimization with Polynomials and the Problem of Moments

0 references

Q5292090

0 references

Q3661322

0 references

On the Shannon capacity of a graph

0 references

Cones of Matrices and Set-Functions and 0–1 Optimization

0 references

Optimality conditions for quadratic programming

0 references

Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints

0 references

An application of Lemke's method to a class of Markov decision problems

0 references

Q4194987

0 references

Q4945444

0 references

New linear program performance bounds for queueing networks

0 references

New linear program performance bounds for closed queueing networks

0 references

Maxima for Graphs and a New Proof of a Theorem of Turán

0 references

Q4039868

0 references

Some NP-complete problems in quadratic and nonlinear programming

0 references

Nonnegativity of bivariate quadratic functions on a triangle

0 references

On the crossing number of $K_{m,n}$

0 references

Existence of global minima for constrained optimization

0 references

Semidefinite programming relaxations for semialgebraic problems

0 references

Computing the Stability Number of a Graph Via Linear and Semidefinite Programming

0 references

Cone-constrained eigenvalue problems: Theory and algorithms

0 references

A Copositive Programming Approach to Graph Partitioning

0 references

Copositive and semidefinite relaxations of the quadratic assignment problem

0 references

Copositivity and the Minimization of Quadratic Functions with Nonnegativity and Quadratic Equality Constraints

0 references

Q4285035

0 references

An approach to robust stability of matrix polytopes through copositive homogeneous polynomials

0 references

Copositive realxation for genera quadratic programming

0 references

A Conic Duality Frank–Wolfe-Type Theorem via Exact Penalization in Quadratic Optimization

0 references

The $K$-moment problem for compact semi-algebraic sets

0 references

A comparison of the Delsarte and Lovász bounds

0 references

A Nullstellensatz and a Positivstellensatz in semialgebraic geometry

0 references

Global optimization of mixed-integer nonlinear programs: a theoretical and computational study

0 references

Testing the definiteness of matrices on polyhedral cones

0 references

Generalized Chebyshev Bounds via Semidefinite Programming

0 references

Q5641059

0 references

On a problem of P. Turan concerning graphs

0 references

Depth-first simplicial partition for copositivity detection, with an application to MaxClique

0 references

Identifiers

zbMATH Open document ID

1262.90129

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

10.1016/J.EJOR.2011.04.026

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:421783

@@ Property / DOI @@
-.1016/j.ejor.2011.04.026
@@ Property / DOI: 10.1016/j.ejor.2011.04.026 / rank @@
-Normal rank
@@ Property / cites work @@
+Copositivity and constrained fractional quadratic problems
+Normal rank
@@ Property / cites work @@
+Q4353530
@@ Property / cites work: Q4353530 / rank @@
+Normal rank
@@ Property / cites work @@
+A time-stepping method for stiff multibody dynamics with contact and friction
+Normal rank
@@ Property / cites work @@
+Computable representations for convex hulls of low-dimensional quadratic forms
+Normal rank
@@ Property / cites work @@
+Optimal Hoffman-type estimates in eigenvalue and semidefinite inequality constraints
+Normal rank
@@ Property / cites work @@
+The complexity of approximating a nonlinear program
+Normal rank
@@ Property / cites work @@
+Q4405832
@@ Property / cites work: Q4405832 / rank @@
+Normal rank
@@ Property / cites work @@
+Remarks on the recursive structure of copositivity
+Normal rank
@@ Property / cites work @@
+Q4942383
@@ Property / cites work: Q4942383 / rank @@
+Normal rank
@@ Property / cites work @@
+Detecting all evolutionarily stable strategies
@@ Property / cites work: Detecting all evolutionarily stable strategies / rank @@
+Normal rank
@@ Property / cites work @@
+Block pivoting and shortcut strategies for detecting copositivity
+Normal rank
@@ Property / cites work @@
+On standard quadratic optimization problems
@@ Property / cites work: On standard quadratic optimization problems / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
+Normal rank
@@ Property / cites work @@
+Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
+Normal rank
@@ Property / cites work @@
+Perron-Frobenius property of copositive matrices, and a block copositivity criterion
+Normal rank
@@ Property / cites work @@
+Global Optimization: A Quadratic Programming Perspective
+Normal rank
@@ Property / cites work @@
+Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
+Normal rank
@@ Property / cites work @@
+On copositive programming and standard quadratic optimization problems
+Normal rank
@@ Property / cites work @@
+Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
+Normal rank
@@ Property / cites work @@
+Copositivity cuts for improving SDP bounds on the clique number
+Normal rank
@@ Property / cites work @@
+A note on Burer's copositive representation of mixed-binary QPs
+Normal rank
@@ Property / cites work @@
+Quadratic factorization heuristics for copositive programming
+Normal rank
@@ Property / cites work @@
+Q3569180
@@ Property / cites work: Q3569180 / rank @@
+Normal rank
@@ Property / cites work @@
+Multi-standard quadratic optimization: Interior point methods and cone programming reformulation
+Normal rank
@@ Property / cites work @@
+Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
+Normal rank
@@ Property / cites work @@
+Necessary and sufficient conditions for quadratic minimality
+Normal rank
@@ Property / cites work @@
+Four applications of majorization to convexity in the calculus of variations
+Normal rank
@@ Property / cites work @@
+Algorithmic copositivity detection by simplicial partition
+Normal rank
@@ Property / cites work @@
+An Adaptive Linear Approximation Algorithm for Copositive Programs
+Normal rank
@@ Property / cites work @@
+Copositive Lyapunov functions for switched systems over cones
+Normal rank
@@ Property / cites work @@
+On the copositive representation of binary and continuous nonconvex quadratic programs
+Normal rank
@@ Property / cites work @@
+Copositive Programming
@@ Property / cites work: Copositive Programming / rank @@
+Normal rank
@@ Property / cites work @@
+The difference between \(5\times 5\) doubly nonnegative and completely positive matrices
+Normal rank
@@ Property / cites work @@
+Q4821606
@@ Property / cites work: Q4821606 / rank @@
+Normal rank
@@ Property / cites work @@
+An interior Newton method for quadratic programming
+Normal rank
@@ Property / cites work @@
+Une caractérisation complete des minima locaux en programmation quadratique
+Normal rank
@@ Property / cites work @@
+Q5625366
@@ Property / cites work: Q5625366 / rank @@
+Normal rank
@@ Property / cites work @@
+Necessary and sufficient conditions for strong ellipticity of isotropic functions in any dimension
+Normal rank
@@ Property / cites work @@
+Q3198800
@@ Property / cites work: Q3198800 / rank @@
+Normal rank
@@ Property / cites work @@
+Using copositivity for global optimality criteria in concave quadratic programming problems
+Normal rank
@@ Property / cites work @@
+The complexity of optimizing over a simplex, hypercube or sphere: a short survey
+Normal rank
@@ Property / cites work @@
+Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming
+Normal rank
@@ Property / cites work @@
+Improved Bounds for the Crossing Numbers of Km,n and Kn
+Normal rank
@@ Property / cites work @@
+Approximation of the Stability Number of a Graph via Copositive Programming
+Normal rank
@@ Property / cites work @@
+A linear programming reformulation of the standard quadratic optimization problem
+Normal rank
@@ Property / cites work @@
+Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
+Normal rank
@@ Property / cites work @@
+Q3843714
@@ Property / cites work: Q3843714 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on ``\(5\times 5\) completely positive matrices''
+Normal rank
@@ Property / cites work @@
+Copositive programming motivated bounds on the stability and the chromatic numbers
+Normal rank
@@ Property / cites work @@
+Q5503714
@@ Property / cites work: Q5503714 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2903231
@@ Property / cites work: Q2903231 / rank @@
+Normal rank
@@ Property / cites work @@
+Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
+Normal rank
@@ Property / cites work @@
+Finite-Dimensional Variational Inequalities and Complementarity Problems
+Normal rank
@@ Property / cites work @@
+Finite-Dimensional Variational Inequalities and Complementarity Problems
+Normal rank
@@ Property / cites work @@
+Q3928936
@@ Property / cites work: Q3928936 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4739659
@@ Property / cites work: Q4739659 / rank @@
+Normal rank
@@ Property / cites work @@
+Critical angles in polyhedral convex cones: Numerical and statistical considerations
+Normal rank
@@ Property / cites work @@
+The Operator $\Psi$ for the Chromatic Number of a Graph
+Normal rank
@@ Property / cites work @@
+On copositive matrices
@@ Property / cites work: On copositive matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Copositive matrices and Simpson's paradox
@@ Property / cites work: Copositive matrices and Simpson's paradox / rank @@
+Normal rank
@@ Property / cites work @@
+Permitted and Forbidden Sets in Symmetric Threshold-Linear Networks
+Normal rank
@@ Property / cites work @@
+Q5328177
@@ Property / cites work: Q5328177 / rank @@
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Two remarks on copositive matrices
@@ Property / cites work: Two remarks on copositive matrices / rank @@
+Normal rank
@@ Property / cites work @@
+A Variational Approach to Copositive Matrices
@@ Property / cites work: A Variational Approach to Copositive Matrices / rank @@
+Normal rank
@@ Property / cites work @@
+The Delay of Open Markovian Queueing Networks: Uniform Functional Bounds, Heavy Traffic Pole Multiplicities, and Stability
+Normal rank
@@ Property / cites work @@
+Q5316981
@@ Property / cites work: Q5316981 / rank @@
+Normal rank
@@ Property / cites work @@
+Conditionally definite matrices
@@ Property / cites work: Conditionally definite matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Searching for critical angles in a convex cone
@@ Property / cites work: Searching for critical angles in a convex cone / rank @@
+Normal rank
@@ Property / cites work @@
+Extension of linear-quadratic control, optimization and matrix theory
+Normal rank
@@ Property / cites work @@
+Spectral theory of copositive matrices
@@ Property / cites work: Spectral theory of copositive matrices / rank @@
+Normal rank
@@ Property / cites work @@
+The eigenvalue complementarity problem
@@ Property / cites work: The eigenvalue complementarity problem / rank @@
+Normal rank
@@ Property / cites work @@
+Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies
+Normal rank
@@ Property / cites work @@
+Global Optimization with Polynomials and the Problem of Moments
+Normal rank
@@ Property / cites work @@
+Q5292090
@@ Property / cites work: Q5292090 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3661322
@@ Property / cites work: Q3661322 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Shannon capacity of a graph
@@ Property / cites work: On the Shannon capacity of a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+Optimality conditions for quadratic programming
@@ Property / cites work: Optimality conditions for quadratic programming / rank @@
+Normal rank
@@ Property / cites work @@
+Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints
+Normal rank
@@ Property / cites work @@
+An application of Lemke's method to a class of Markov decision problems
+Normal rank
@@ Property / cites work @@
+Q4194987
@@ Property / cites work: Q4194987 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4945444
@@ Property / cites work: Q4945444 / rank @@
+Normal rank
@@ Property / cites work @@
+New linear program performance bounds for queueing networks
+Normal rank
@@ Property / cites work @@
+New linear program performance bounds for closed queueing networks
+Normal rank
@@ Property / cites work @@
+Maxima for Graphs and a New Proof of a Theorem of Turán
+Normal rank
@@ Property / cites work @@
+Q4039868
@@ Property / cites work: Q4039868 / rank @@
+Normal rank
@@ Property / cites work @@
+Some NP-complete problems in quadratic and nonlinear programming
+Normal rank
@@ Property / cites work @@
+Nonnegativity of bivariate quadratic functions on a triangle
+Normal rank
@@ Property / cites work @@
+On the crossing number of \(K_{m,n}\)
@@ Property / cites work: On the crossing number of \(K_{m,n}\) / rank @@
+Normal rank
@@ Property / cites work @@
+Existence of global minima for constrained optimization
+Normal rank
@@ Property / cites work @@
+Semidefinite programming relaxations for semialgebraic problems
+Normal rank
@@ Property / cites work @@
+Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
+Normal rank
@@ Property / cites work @@
+Cone-constrained eigenvalue problems: Theory and algorithms
+Normal rank
@@ Property / cites work @@
+A Copositive Programming Approach to Graph Partitioning
+Normal rank
@@ Property / cites work @@
+Copositive and semidefinite relaxations of the quadratic assignment problem
+Normal rank
@@ Property / cites work @@
+Copositivity and the Minimization of Quadratic Functions with Nonnegativity and Quadratic Equality Constraints
+Normal rank
@@ Property / cites work @@
+Q4285035
@@ Property / cites work: Q4285035 / rank @@
+Normal rank
@@ Property / cites work @@
+An approach to robust stability of matrix polytopes through copositive homogeneous polynomials
+Normal rank
@@ Property / cites work @@
+Copositive realxation for genera quadratic programming
+Normal rank
@@ Property / cites work @@
+A Conic Duality Frank–Wolfe-Type Theorem via Exact Penalization in Quadratic Optimization
+Normal rank
@@ Property / cites work @@
+The \(K\)-moment problem for compact semi-algebraic sets
+Normal rank
@@ Property / cites work @@
+A comparison of the Delsarte and Lovász bounds
@@ Property / cites work: A comparison of the Delsarte and Lovász bounds / rank @@
+Normal rank
@@ Property / cites work @@
+A Nullstellensatz and a Positivstellensatz in semialgebraic geometry
+Normal rank
@@ Property / cites work @@
+Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
+Normal rank
@@ Property / cites work @@
+Testing the definiteness of matrices on polyhedral cones
+Normal rank
@@ Property / cites work @@
+Generalized Chebyshev Bounds via Semidefinite Programming
+Normal rank
@@ Property / cites work @@
+Q5641059
@@ Property / cites work: Q5641059 / rank @@
+Normal rank
@@ Property / cites work @@
+On a problem of P. Turan concerning graphs
@@ Property / cites work: On a problem of P. Turan concerning graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Depth-first simplicial partition for copositivity detection, with an application to MaxClique
+Normal rank
@@ Property / DOI @@
+.1016/J.EJOR.2011.04.026
@@ Property / DOI: 10.1016/J.EJOR.2011.04.026 / rank @@
+Normal rank