Optimization Online


Simplified semidefinite and completely positive relaxations

Felix Lieder (lieder***at***opt.uni-duesseldorf.de)

Abstract: This paper is concerned with completely positive and semidefinite relaxations of quadratic programs with linear constraints and binary variables as presented by Burer. It observes that all constraints of the relaxation associated with linear constraints of the original problem can be accumulated in a single linear constraint without changing the feasible set of either the completely positive or the semidefinite approximation. It also shows that a tightening of the semidefinite relaxation proposed by Burer is equivalent to the original relaxation.

Keywords: Semidefinite relaxation, completely positive relaxation

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Integer Programming (0-1 Programming )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Lieder, F. (2015). Simplified semidefinite and completely positive relaxations. Operations Research Letters, 43(6), 579-580.


Entry Submitted: 07/18/2015
Entry Accepted: 07/25/2015
Entry Last Modified: 11/14/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society