Optimization methods & software · 1998 · 64 citations · 28 references
Natural SciencesComputer ScienceMathematicsOptimizationQuantum ComputingTheory Of ComputationCombinatorial OptimizationConstrained OptimizationConvex OptimizationDiscrete OptimizationOptimization TheoryQuadratic ProgrammingConvex Quadratic ProgrammingConvex RelaxationsLinear ConstraintsNonconvex Quadratic ProgrammingQuadratic Programming RelaxationsSemidefinite ProgrammingSemidefinite Programming RelaxationSemidefinite Relaxation
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.
28
Nonlinear programming: theory and algorithms
Computers & Operations Research · 1993 · 5.8K citations
Lieven Vandenberghe, Stephen Boyd · SIAM Review · 1996 · 4.1K citations