Abstract
A disadvantage of the SDP (semidefinite programming) relaxation method for quadratic and/or combinatorial optimization problems lies in its expensive computational cost. This paper proposes a SOCP (second-order-cone programming) relaxation method, which strengthens the lift-and-project LP (linear programming) relaxation method by adding convex quadratic valid inequalities for the positive semidefinite cone involved in the SDP relaxation. Numerical experiments show that our SOCP relaxation is a reasonable compromise between the effectiveness of the SDP relaxation and the low computational cost of the lift-and-project LP relaxation.
| Original language | English |
|---|---|
| Pages (from-to) | 201-224 |
| Number of pages | 24 |
| Journal | Optimization Methods and Software |
| Volume | 15 |
| Issue number | 3-4 |
| State | Published - 2001 |
Keywords
- Global optimization
- Lift-and-project convex relaxation method
- Nonconvex quadratic program
- Primal-dual interior-point method
- Second-order-cone program