Copositive realxation for genera quadratic programming
- 1 January 1998
- journal article
- other
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 9 (1) , 185-208
- https://doi.org/10.1080/10556789808805692
Abstract
We consider general, typically nonconvex, Quadratic programming Problem. The Semidefinite relaxation proposed by Shor provides bounds on the optimal solution, but it does not always provide sufficiently strong bounds if linear constraintare also involved. To get rid of the linear side-constraints, another, stronger convex relaxation is derved. This relaxation uses copositive matrices. Special cases are dicussed for which both relaxations are equal. At end of the paper, the complexity and solvablility of the relaxation are discussed.Keywords
This publication has 22 references indexed in Scilit:
- Block pivoting and shortcut strategies for detecting copositivityLinear Algebra and its Applications, 1996
- A recipe for semidefinite relaxation for (0,1)-quadratic programmingJournal of Global Optimization, 1995
- A finite algorithm for solving general quadratic problemsJournal of Global Optimization, 1994
- A Global Optimization Algorithm for Concave Quadratic Programming ProblemsSIAM Journal on Optimization, 1993
- Cones of Matrices and Set-Functions and 0–1 OptimizationSIAM Journal on Optimization, 1991
- Some NP-complete problems in quadratic and nonlinear programmingMathematical Programming, 1987
- On copositive matricesLinear Algebra and its Applications, 1983
- Finite criteria for conditional definiteness of quadratic formsLinear Algebra and its Applications, 1981
- Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraintsLinear Algebra and its Applications, 1981
- On the asymptotic integer algorithmLinear Algebra and its Applications, 1970