American Institute of Mathematical Sciences

Advanced
July  2016, 12(3): 1041-1056. doi: 10.3934/jimo.2016.12.1041

Cardinality constrained portfolio selection problem: A completely positive programming approach

Ye Tian 1, , Shucherng Fang 2, , Zhibin Deng 3, and  Qingwei Jin 4,

1. 

School of Business Administration, Southwestern University of Finance and Economics, Chengdu, 611130
2. 

Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606, United States
3. 

School of Management, University of Chinese Academy of Sciences, Beijing, 100190
4. 

Department of Management Science and Engineering, Zhejiang University, Hangzhou, Zhejiang 310058

Received  March 2014 Revised  May 2015 Published  September 2015

In this paper, we propose a completely positive programming reformulation of the cardinality constrained portfolio selection problem. By constructing a sequence of computable cones of nonnegative quadratic forms over a union of second-order cones, an $\epsilon$-optimal solution of the original problem can be found in finite iterations using semidefinite programming techniques. In order to obtain a good lower bound efficiently, an adaptive scheme is adopted in our approximation algorithm. The numerical results show that the proposed algorithm can find better approximate and feasible solutions than other known methods in the literature.
Keywords: Cardinality constrained portfolio selection problem, adaptive approximation., completely positive programming, second-order cone.
Mathematics Subject Classification: Primary: 90C26, 90C59, 90C22; Secondary: 30E1.
Citation: Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041
References:
[1]

D. Bertsimas and R. Shioda, Algorithm for cardinality-constrained quadratic optimization, Computational Optimization and Applications, 43 (2009), 1-22. doi: 10.1007/s10589-007-9126-9.

[2]

D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), 121-140. doi: 10.1007/BF02592208.

[3]

P. Bonami and M. Lejeune, An exact solution approach for portfolio optimization problems under stochastic and integer constraints, Operations Research, 57 (2009), 650-670. doi: 10.1287/opre.1080.0599.

[4]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.

[5]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495. doi: 10.1007/s10107-008-0223-z.

[6]

T. Chang, N. Meade, J. Beasley and Y. Sharaiha, Heuristics for cardinality constrained portfolio optimization, Computational Operations Research, 27 (2000), 1271-1302.

[7]

X. Cui, X. Sun and D. Sha, An empirical study on discrete optimization models for portfolio selection, Journal of Industrial and Managment Optimization, 5 (2009), 33-46. doi: 10.3934/jimo.2009.5.33.

[8]

X. Cui, X. Zheng, S. Zhu and X. Sun, Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio slection problems, Journal of Global Optimization, 56 (2013), 1409-1423. doi: 10.1007/s10898-012-9842-2.

[9]

Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, European Journal of Operational Research, 229 (2013), 21-28. doi: 10.1016/j.ejor.2013.02.031.

[10]

E. Elton and M. Gruber, Modern Portfolio Theory and Investment Analysis, 2nd edition, John Wiley & Sons, Inc, Hoboken, 1984.

[11]

A. Frangioni and C. Gentile, Perspective cuts for a class of convex 0-1 mixed integer programs, Mathematical Programming, 106 (2006), 225-236. doi: 10.1007/s10107-005-0594-3.

[12]

A. Frangioni and C. Gentile, SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Operations Research Letters, 35 (2007), 181-185. doi: 10.1016/j.orl.2006.03.008.

[13]

A. Frangioni and C. Gentile, A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes, Operations Research Letters, 37 (2009), 206-210. doi: 10.1016/j.orl.2009.02.003.

[14]

J. Gao and D. Li, Optimal cardinality constrained portfolio selecton, Operations Research, 61 (2013), 745-761. doi: 10.1287/opre.2013.1170.

[15]

M. Grant and S. Boyd, CVX: matlab software for disciplined programming, version 1.2, http://cvxr.com/cvx, 2010.

[16]

Q. Jin, Y. Tian, Z. Deng, S.-C. Fang and W. Xing, Exact computable representation of some second-order cone constrained quadratic programming problems, Journal of the Operations Research Society of China, 1 (2013), 107-134. doi: 10.1007/s40305-013-0009-8.

[17]

N. Jobst, M. Horniman, C. Luca and G. Mitra, Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints, Quantitative Finance, 1 (2001), 489-501. doi: 10.1088/1469-7688/1/5/301.

[18]

H. Konno and H. Yamazaki, Mean-absolute deviation portfolio optimization model and its applications to Tokyo stock market, Management Science, 37 (1991), 519-531. doi: 10.1287/mnsc.37.5.519.

[19]

P. Leung, H. Ng and W. Wong, An improved estimation to make Markowitz's portfolio optimization theory users friendly and estimation accurate with application on the US stock market investment, European Journal of Operational Research, 222 (2012), 85-95. doi: 10.1016/j.ejor.2012.04.003.

[20]

P. Lin, Portfolo optimization and risk measurement based on non-dominated sorting genetic algorithm, Journal of Industrial and Management Optimization, 8 (2012), 549-564. doi: 10.3934/jimo.2012.8.549.

[21]

D. Maringer and H. Kellerer, Optimization of cardinality constrained portfolios with a hybrid local search algorithm, OR Spectrum, 25 (2003), 481-495. doi: 10.1007/s00291-003-0139-1.

[22]

H. Markowitz, Portfolio selection, Journal of Finance, 7 (1952), 77-91.

[23]

G. Mitra, F. Ellison and A. Scowcroft, Quadratic programming for portfolio planning: Insights into algorithmic and computational issues. Part II: Processing of portfolio planning models with discrete constraints, Journal of Asset Management, 8 (2007), 249-258. doi: 10.1057/palgrave.jam.2250079.

[24]

K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), 117-129. doi: 10.1007/BF02592948.

[25]

P. Pardalos and G. Rodgers, Computing aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144. doi: 10.1007/BF02247879.

[26]

P. Pardalos and M. Sandström and C. Zopounidis, On the use of optimization models for portfolio selection: A review and some computational results, Computational Economics, 7 (1994), 227-244. doi: 10.1007/BF01299454.

[27]

R. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.

[28]

D. Shaw, S. Liu and L. Kopman, Lagrangian relaxation procedure for cardinality-constrained portfolio optimization, Optimization Methods and Software, 23 (2008), 411-420. doi: 10.1080/10556780701722542.

[29]

J. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267. doi: 10.1287/moor.28.2.246.14485.

[30]

X. Sun, X. Zheng and D. Li, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, Journal of the Operations Research Society of China, 1 (2013), 55-77. doi: 10.1007/s40305-013-0004-0.

[31]

Y. Tian, S.-C. Fang, Z. Deng and W. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming, Journal of Industrial and Management Optimization, 9 (2013), 703-721. doi: 10.3934/jimo.2013.9.703.

[32]

J. Xie, S. He and S. Zhang, Randomized portfolio selection with constraints, Pacific Journal of Optimization, 4 (2008), 87-112.

[33]

Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267. doi: 10.1137/S105262340139001X.

[34]

M. Young, A minimax portfolio selction rule with linear programming solution, Management Science, 44 (1998), 673-683.

[35]

Y. Zeng, Z. Li and J. Liu, Optimal strategies of benchmark and mean-variance portfolo selection problems for insurers, Journal of Industral and Management Optimization, 6 (2010), 483-496. doi: 10.3934/jimo.2010.6.483.

[36]

X. Zheng, X. Sun and D. Li, Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach, INFORMS Journal on Computing, 26 (2014), 690-703. doi: 10.1287/ijoc.2014.0592.

[37]

S. Zymler, B. Rustem and D. Kuhn, Robust portfolio optimization with derivative insurance guarantees, European Journal of Operational Research, 210 (2011), 410-424. doi: 10.1016/j.ejor.2010.09.027.

show all references

References:
[1]

D. Bertsimas and R. Shioda, Algorithm for cardinality-constrained quadratic optimization, Computational Optimization and Applications, 43 (2009), 1-22. doi: 10.1007/s10589-007-9126-9.

[2]

D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), 121-140. doi: 10.1007/BF02592208.

[3]

P. Bonami and M. Lejeune, An exact solution approach for portfolio optimization problems under stochastic and integer constraints, Operations Research, 57 (2009), 650-670. doi: 10.1287/opre.1080.0599.

[4]

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. doi: 10.1017/CBO9780511804441.

[5]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs, Mathematical Programming, 120 (2009), 479-495. doi: 10.1007/s10107-008-0223-z.

[6]

T. Chang, N. Meade, J. Beasley and Y. Sharaiha, Heuristics for cardinality constrained portfolio optimization, Computational Operations Research, 27 (2000), 1271-1302.

[7]

X. Cui, X. Sun and D. Sha, An empirical study on discrete optimization models for portfolio selection, Journal of Industrial and Managment Optimization, 5 (2009), 33-46. doi: 10.3934/jimo.2009.5.33.

[8]

X. Cui, X. Zheng, S. Zhu and X. Sun, Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio slection problems, Journal of Global Optimization, 56 (2013), 1409-1423. doi: 10.1007/s10898-012-9842-2.

[9]

Z. Deng, S.-C. Fang, Q. Jin and W. Xing, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, European Journal of Operational Research, 229 (2013), 21-28. doi: 10.1016/j.ejor.2013.02.031.

[10]

E. Elton and M. Gruber, Modern Portfolio Theory and Investment Analysis, 2nd edition, John Wiley & Sons, Inc, Hoboken, 1984.

[11]

A. Frangioni and C. Gentile, Perspective cuts for a class of convex 0-1 mixed integer programs, Mathematical Programming, 106 (2006), 225-236. doi: 10.1007/s10107-005-0594-3.

[12]

A. Frangioni and C. Gentile, SDP diagonalizations and perspective cuts for a class of nonseparable MIQP, Operations Research Letters, 35 (2007), 181-185. doi: 10.1016/j.orl.2006.03.008.

[13]

A. Frangioni and C. Gentile, A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes, Operations Research Letters, 37 (2009), 206-210. doi: 10.1016/j.orl.2009.02.003.

[14]

J. Gao and D. Li, Optimal cardinality constrained portfolio selecton, Operations Research, 61 (2013), 745-761. doi: 10.1287/opre.2013.1170.

[15]

M. Grant and S. Boyd, CVX: matlab software for disciplined programming, version 1.2, http://cvxr.com/cvx, 2010.

[16]

Q. Jin, Y. Tian, Z. Deng, S.-C. Fang and W. Xing, Exact computable representation of some second-order cone constrained quadratic programming problems, Journal of the Operations Research Society of China, 1 (2013), 107-134. doi: 10.1007/s40305-013-0009-8.

[17]

N. Jobst, M. Horniman, C. Luca and G. Mitra, Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints, Quantitative Finance, 1 (2001), 489-501. doi: 10.1088/1469-7688/1/5/301.

[18]

H. Konno and H. Yamazaki, Mean-absolute deviation portfolio optimization model and its applications to Tokyo stock market, Management Science, 37 (1991), 519-531. doi: 10.1287/mnsc.37.5.519.

[19]

P. Leung, H. Ng and W. Wong, An improved estimation to make Markowitz's portfolio optimization theory users friendly and estimation accurate with application on the US stock market investment, European Journal of Operational Research, 222 (2012), 85-95. doi: 10.1016/j.ejor.2012.04.003.

[20]

P. Lin, Portfolo optimization and risk measurement based on non-dominated sorting genetic algorithm, Journal of Industrial and Management Optimization, 8 (2012), 549-564. doi: 10.3934/jimo.2012.8.549.

[21]

D. Maringer and H. Kellerer, Optimization of cardinality constrained portfolios with a hybrid local search algorithm, OR Spectrum, 25 (2003), 481-495. doi: 10.1007/s00291-003-0139-1.

[22]

H. Markowitz, Portfolio selection, Journal of Finance, 7 (1952), 77-91.

[23]

G. Mitra, F. Ellison and A. Scowcroft, Quadratic programming for portfolio planning: Insights into algorithmic and computational issues. Part II: Processing of portfolio planning models with discrete constraints, Journal of Asset Management, 8 (2007), 249-258. doi: 10.1057/palgrave.jam.2250079.

[24]

K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39 (1987), 117-129. doi: 10.1007/BF02592948.

[25]

P. Pardalos and G. Rodgers, Computing aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, 45 (1990), 131-144. doi: 10.1007/BF02247879.

[26]

P. Pardalos and M. Sandström and C. Zopounidis, On the use of optimization models for portfolio selection: A review and some computational results, Computational Economics, 7 (1994), 227-244. doi: 10.1007/BF01299454.

[27]

R. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.

[28]

D. Shaw, S. Liu and L. Kopman, Lagrangian relaxation procedure for cardinality-constrained portfolio optimization, Optimization Methods and Software, 23 (2008), 411-420. doi: 10.1080/10556780701722542.

[29]

J. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267. doi: 10.1287/moor.28.2.246.14485.

[30]

X. Sun, X. Zheng and D. Li, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, Journal of the Operations Research Society of China, 1 (2013), 55-77. doi: 10.1007/s40305-013-0004-0.

[31]

Y. Tian, S.-C. Fang, Z. Deng and W. Xing, Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming, Journal of Industrial and Management Optimization, 9 (2013), 703-721. doi: 10.3934/jimo.2013.9.703.

[32]

J. Xie, S. He and S. Zhang, Randomized portfolio selection with constraints, Pacific Journal of Optimization, 4 (2008), 87-112.

[33]

Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267. doi: 10.1137/S105262340139001X.

[34]

M. Young, A minimax portfolio selction rule with linear programming solution, Management Science, 44 (1998), 673-683.

[35]

Y. Zeng, Z. Li and J. Liu, Optimal strategies of benchmark and mean-variance portfolo selection problems for insurers, Journal of Industral and Management Optimization, 6 (2010), 483-496. doi: 10.3934/jimo.2010.6.483.

[36]

X. Zheng, X. Sun and D. Li, Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: A semidefinite program approach, INFORMS Journal on Computing, 26 (2014), 690-703. doi: 10.1287/ijoc.2014.0592.

[37]

S. Zymler, B. Rustem and D. Kuhn, Robust portfolio optimization with derivative insurance guarantees, European Journal of Operational Research, 210 (2011), 410-424. doi: 10.1016/j.ejor.2010.09.027.

[1]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[2]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[3]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[4]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[5]

Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[6]

Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108
[7]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[8]

Nguyen Thi Hoai. Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 495-512. doi: 10.3934/naco.2020040
[9]

Xi-De Zhu, Li-Ping Pang, Gui-Hua Lin. Two approaches for solving mathematical programs with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2015, 11 (3) : 951-968. doi: 10.3934/jimo.2015.11.951
[10]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1
[11]

Li Chu, Bo Wang, Jie Zhang, Hong-Wei Zhang. Convergence analysis of a smoothing SAA method for a stochastic mathematical program with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1863-1886. doi: 10.3934/jimo.2020050
[12]

Xin-He Miao, Kai Yao, Ching-Yu Yang, Jein-Shan Chen. Levenberg-Marquardt method for absolute value equation associated with second-order cone. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 47-61. doi: 10.3934/naco.2021050
[13]

Lin Zhu, Xinzhen Zhang. Semidefinite relaxation method for polynomial optimization with second-order cone complementarity constraints. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1505-1517. doi: 10.3934/jimo.2021030
[14]

Liu Yang, Xiaojiao Tong, Yao Xiong, Feifei Shen. A smoothing SAA algorithm for a portfolio choice model based on second-order stochastic dominance measures. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1171-1185. doi: 10.3934/jimo.2018198
[15]

Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021032
[16]

Leonardo Colombo. Second-order constrained variational problems on Lie algebroids: Applications to Optimal Control. Journal of Geometric Mechanics, 2017, 9 (1) : 1-45. doi: 10.3934/jgm.2017001
[17]

Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
[18]

Johnny Henderson, Rodica Luca. Existence of positive solutions for a system of nonlinear second-order integral boundary value problems. Conference Publications, 2015, 2015 (special) : 596-604. doi: 10.3934/proc.2015.0596
[19]

Kaizhi Wang, Yong Li. Existence and monotonicity property of minimizers of a nonconvex variational problem with a second-order Lagrangian. Discrete and Continuous Dynamical Systems, 2009, 25 (2) : 687-699. doi: 10.3934/dcds.2009.25.687
[20]

Hancheng Guo, Jie Xiong. A second-order stochastic maximum principle for generalized mean-field singular control problem. Mathematical Control and Related Fields, 2018, 8 (2) : 451-473. doi: 10.3934/mcrf.2018018

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (459)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy