Algorithm for cardinality-constrained quadratic optimization

被引:172
作者
Bertsimas, Dimitris [2 ,3 ]
Shioda, Romy [1 ]
机构
[1] Univ Waterloo, Dept Combinator & Optimizat, Fac Math, Waterloo, ON N2L 3G1, Canada
[2] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA
[3] MIT, Ctr Operat Res, Cambridge, MA 02139 USA
基金
加拿大自然科学与工程研究理事会;
关键词
Mixed-integer quadratic programming; Branch-and-bound; Lemke's method; Subset selection; Portfolio selection; PORTFOLIO SELECTION; TRANSACTION COSTS; EQUILIBRIUM POINTS; VARIABLES;
D O I
10.1007/s10589-007-9126-9
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper describes an algorithm for cardinality-constrained quadratic optimization problems, which are convex quadratic programming problems with a limit on the number of non-zeros in the optimal solution. In particular, we consider problems of subset selection in regression and portfolio selection in asset management and propose branch-and-bound based algorithms that take advantage of the special structure of these problems. We compare our tailored methods against CPLEX's quadratic mixed-integer solver and conclude that the proposed algorithms have practical advantages for the special class of problems we consider.
引用
收藏
页码:1 / 22
页数:22
相关论文
共 25 条
[1]  
Arthanari T.S., 1993, Mathematical Programming in Statistics
[2]  
BEALE EML, 1967, BIOMETRIKA, V54, P357
[3]   Portfolio construction through mixed-integer programming at Grantham, Mayo, Van Otterloo and Company [J].
Bertsimas, D ;
Darnell, C ;
Soucy, R .
INTERFACES, 1999, 29 (01) :49-66
[4]   Computational study of a family of mixed-integer quadratic programming problems [J].
Bienstock, D .
MATHEMATICAL PROGRAMMING, 1996, 74 (02) :121-140
[5]   THE OPTIMAL SELECTION OF SMALL PORTFOLIOS [J].
BLOG, B ;
VANDERHOEK, G ;
KAN, AHGR ;
TIMMER, GT .
MANAGEMENT SCIENCE, 1983, 29 (07) :792-798
[6]   Heuristics for cardinality constrained portfolio optimisation [J].
Chang, TJ ;
Meade, N ;
Beasley, JE ;
Sharaiha, YM .
COMPUTERS & OPERATIONS RESEARCH, 2000, 27 (13) :1271-1302
[7]  
Cottle R.W., 1992, The Linear Complementarity Problem
[8]   REGRESSIONS BY LEAPS AND BOUNDS [J].
FURNIVAL, GM ;
WILSON, RW .
TECHNOMETRICS, 1974, 16 (04) :499-511
[9]   SELECTION OF BEST SUBSET IN REGRESSION ANALYSIS [J].
HOCKING, RR ;
LESLIE, RN .
TECHNOMETRICS, 1967, 9 (04) :531-&
[10]  
*ILOG CPLEX DIV, 2002, ILOG CPLEX 8 1 US MA