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 & 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.  doi: 10.1007/s10589-007-9126-9.  Google Scholar

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[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.  doi: 10.3934/jimo.2009.5.33.  Google Scholar

[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.  doi: 10.1007/s10898-012-9842-2.  Google Scholar

[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.  doi: 10.1016/j.ejor.2013.02.031.  Google Scholar

[10]

E. Elton and M. Gruber, Modern Portfolio Theory and Investment Analysis,, 2nd edition, (1984).   Google Scholar

[11]

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

[12]

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

[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.  doi: 10.1016/j.orl.2009.02.003.  Google Scholar

[14]

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

[15]

M. Grant and S. Boyd, CVX: matlab software for disciplined programming, version 1.2,, , (2010).   Google Scholar

[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.  doi: 10.1007/s40305-013-0009-8.  Google Scholar

[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.  doi: 10.1088/1469-7688/1/5/301.  Google Scholar

[18]

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

[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.  doi: 10.1016/j.ejor.2012.04.003.  Google Scholar

[20]

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

[21]

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

[22]

H. Markowitz, Portfolio selection,, Journal of Finance, 7 (1952), 77.   Google Scholar

[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.  doi: 10.1057/palgrave.jam.2250079.  Google Scholar

[24]

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

[25]

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

[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.  doi: 10.1007/BF01299454.  Google Scholar

[27]

R. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[28]

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

[29]

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

[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.  doi: 10.1007/s40305-013-0004-0.  Google Scholar

[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.  doi: 10.3934/jimo.2013.9.703.  Google Scholar

[32]

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

[33]

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

[34]

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

[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.  doi: 10.3934/jimo.2010.6.483.  Google Scholar

[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.  doi: 10.1287/ijoc.2014.0592.  Google Scholar

[37]

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

show all references

References:
[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[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.  doi: 10.3934/jimo.2009.5.33.  Google Scholar

[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.  doi: 10.1007/s10898-012-9842-2.  Google Scholar

[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.  doi: 10.1016/j.ejor.2013.02.031.  Google Scholar

[10]

E. Elton and M. Gruber, Modern Portfolio Theory and Investment Analysis,, 2nd edition, (1984).   Google Scholar

[11]

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

[12]

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

[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.  doi: 10.1016/j.orl.2009.02.003.  Google Scholar

[14]

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

[15]

M. Grant and S. Boyd, CVX: matlab software for disciplined programming, version 1.2,, , (2010).   Google Scholar

[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.  doi: 10.1007/s40305-013-0009-8.  Google Scholar

[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.  doi: 10.1088/1469-7688/1/5/301.  Google Scholar

[18]

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

[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.  doi: 10.1016/j.ejor.2012.04.003.  Google Scholar

[20]

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

[21]

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

[22]

H. Markowitz, Portfolio selection,, Journal of Finance, 7 (1952), 77.   Google Scholar

[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.  doi: 10.1057/palgrave.jam.2250079.  Google Scholar

[24]

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

[25]

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

[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.  doi: 10.1007/BF01299454.  Google Scholar

[27]

R. Rockafellar, Convex Analysis,, Princeton University Press, (1970).   Google Scholar

[28]

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

[29]

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

[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.  doi: 10.1007/s40305-013-0004-0.  Google Scholar

[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.  doi: 10.3934/jimo.2013.9.703.  Google Scholar

[32]

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

[33]

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

[34]

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

[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.  doi: 10.3934/jimo.2010.6.483.  Google Scholar

[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.  doi: 10.1287/ijoc.2014.0592.  Google Scholar

[37]

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

[1]

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

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[4]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027
[5]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[6]

Horst R. Thieme. Remarks on resolvent positive operators and their perturbation. Discrete & Continuous Dynamical Systems - A, 1998, 4 (1) : 73-90. doi: 10.3934/dcds.1998.4.73
[7]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[8]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[9]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[10]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[11]

Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810
[12]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[13]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044
[14]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401
[15]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151
[16]

Gloria Paoli, Gianpaolo Piscitelli, Rossanno Sannipoli. A stability result for the Steklov Laplacian Eigenvalue Problem with a spherical obstacle. Communications on Pure & Applied Analysis, 2021, 20 (1) : 145-158. doi: 10.3934/cpaa.2020261
[17]

Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $ \Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109
[18]

Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995
[19]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090
[20]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (154)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences