ncku-talk2011-03-24

NCTS(South)/ NCKU Math Colloquium

DATE 2011-03-24　16:10-17:00

PLACE R204, 2F, NCTS, NCKU

SPEAKER Professor Xiaoling Sun（Fudan University）

TITLE SDP Relaxation and MIQP Reformulation for Cardinality Constrained Quadratic Programming

ABSTRACT In this talk, we consider cardinality constrained quadratic programming problems arising from various applications such as portfolio selection and subset selection in regression.
The problem can be described as a convex quadratic program with additional constraints on the number of nonzero variables in the feasible solution and lower bounds for positive variables.
The problem can be formulated as a mixed‐integer quadratic program (MIQP). We first investigate how to get tight convex relaxations to this special classes of mixed integer QP. We show that the dual problem via Lagrangian decomposition can be reduced to a semidefinite program (SDP). In particular, we derive a second‐order cone programming (SOCP) relaxation to the original problem which is tighter than the continuous relaxation of the standard MIQP.
We also propose a new reformulation of the cardinality constrained QP whose continuous relaxation is exactly the SOCP relaxation. This reformulation is more efficient than the standard MIQP when branch‐and bound method is used to solve the problem. Computational results are reported to demonstrate the tightness of the SOCP bound and the effectiveness of the new MIQP reformulation.

NCTS(South)/ NCKU Math Colloquium

DATE	2011-03-24　16:10-17:00

PLACE	R204, 2F, NCTS, NCKU

SPEAKER	Professor Xiaoling Sun（Fudan University）

TITLE	SDP Relaxation and MIQP Reformulation for Cardinality Constrained Quadratic Programming

ABSTRACT	In this talk, we consider cardinality constrained quadratic programming problems arising from various applications such as portfolio selection and subset selection in regression. The problem can be described as a convex quadratic program with additional constraints on the number of nonzero variables in the feasible solution and lower bounds for positive variables. The problem can be formulated as a mixed‐integer quadratic program (MIQP). We first investigate how to get tight convex relaxations to this special classes of mixed integer QP. We show that the dual problem via Lagrangian decomposition can be reduced to a semidefinite program (SDP). In particular, we derive a second‐order cone programming (SOCP) relaxation to the original problem which is tighter than the continuous relaxation of the standard MIQP. We also propose a new reformulation of the cardinality constrained QP whose continuous relaxation is exactly the SOCP relaxation. This reformulation is more efficient than the standard MIQP when branch‐and bound method is used to solve the problem. Computational results are reported to demonstrate the tightness of the SOCP bound and the effectiveness of the new MIQP reformulation.