Loading...
Please wait, while we are loading the content...
Second order cone programming relaxation of nonconvex quadratic optimization problems
| Content Provider | CiteSeerX |
|---|---|
| Author | Kim, Sunyoung Kojima, Masakazu |
| Abstract | 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 compro-mise between the effectiveness of the SDP relaxation and the low computational cost of the lift-and-project LP relaxation. Key words. second-order-cone program, lift-and-project convex relaxation method, non-convex quadratic program, global optimization, primal-dual interior-point method |
| File Format | |
| Journal | Optimization Methods and Software |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Relaxation Method Second Order Cone Nonconvex Quadratic Optimization Problem Sdp Relaxation Linear Programming Reasonable Compro-mise Global Optimization Lift-and-project Lp Relaxation Positive Semidefinite Cone Lift-and-project Convex Relaxation Method Second-order-cone Programming Semidefinite Programming Lift-and-project Lp Combinatorial Optimization Problem Low Computational Cost Socp Relaxation Convex Quadratic Valid Inequality Non-convex Quadratic Program Second-order-cone Program Primal-dual Interior-point Method Numerical Experiment Key Word Expensive Computational Cost |
| Content Type | Text |
| Resource Type | Article |
