TARU PUBLICATIONS
Journal of Information and Optimization Sciences cover

Journal of Information and Optimization Sciences

(Since 1980)
Hybrid ·Peer-reviewed·ISSN (Online): 2169-0103·ISSN (Print): 0252-2667

WoS  JIF 2026 : 0.4 (Q4)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research on topics in information and optimization sciences.

Issues up to 2022 co-published with and available at:Taylor & Francis
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Information and Optimization Sciences
Open Access Research Article

A tight semidefinite relaxation for portfolio optimization problem with cardinality constraint

* ,

* Corresponding author · click or hover a name for details

pp. 1–20Online FirstMay 2026DOI: 10.47974/JIOS-1841XML
Received:
01 Nov 2023
Published Online:
13 May 2026
Article type:
Research Article
Language:
EN
Article no.:
JIOS-1841
Pages:
1–20

Abstract

We consider the use of mean-variance (MV) portfolio optimization for investors with the risk preference parameter and some real-life trading constraints, such as the cardinality constraint. For the selection of portfolios, semidefinite relaxation (SDR) is used to increase the sparsity as well as to obtain a tight lower bound. Generally, to solve the cardinality constrained portfolio optimization (CCPO), which is NP-hard in nature, one can reformulate it as a mixed-integer quadratic programming problem (MIQP) and solve it with several existing global solvers. During SDR, the substitution leads to a nonconvex rank-one constraint. Many authors dropped it to reduce it to a convex problem, which may sometimes produce a significant discrepancy between the original problem’s optimal values and the relaxed problem. In this paper, we propose two SDR models for the MIQP model and a direct SDR model by convexifying the rank-one constraint, which increases the sparsity and provides a tight lower bound. The effectiveness of the proposed model is demonstrated via numerical analysis of historical stock returns. 

Keywords

Portfolio optimizationCardinality constraintMIQPSemidefinite relaxationRank-one relaxation

Subject Classifications

90C1190C2090C22

References

[1] H. Markowitz, “Portfolio selection j. finance,” (1952).
[2] H. Markowitz, “Portfolio selection,” (1959).
[3] H. Konno and H. Yamazaki, “Mean-absolute deviation portfolio optimization model and its applications to tokyo stock market,” Management science, vol. 37, no. 5, pp. 519–531 (1991).
[4] W. F. Sharpe, “Mutual fund performance,” The Journal of business, vol. 39, no. 1, pp. 119–138 (1966).
[5] A. E. Bernardo and O. Ledoit, “Gain, loss, and asset pricing,” Journal of political economy, vol. 108, no. 1, pp. 144–172 (2000).
[6] E. J. Elton, M. J. Gruber, S. J. Brown, and W. N. Goetzmann, Modern portfolio theory and investment analysis. John Wiley & Sons (2009).
[7] A. F. Perold, “Large-scale portfolio optimization,” Management science, vol. 30, no. 10, pp. 1143–1160 (1984).
[8] M. Sasaki, A. Laamrani, and M. Yamashiro, “An interactive genetic algorithm for portfolio optimization considering the decision maker’s preference,” Journal of Information and Optimization Sciences, vol. 39, no. 4, pp. 989–1008 (2018).
[9] R. Jagannathan and T. Ma, “Risk reduction in large portfolios: Why imposing the wrong constraints helps,” The Journal of Finance, vol. 58, no. 4, pp. 1651–1683 (2003).
[10] L. Mencarelli and C. d’Ambrosio, “Complex portfolio selection via convex mixed-integer quadratic programming: a survey,” International Transactions in Operational Research, vol. 26, no. 2, pp. 389–414 (2019).
[11] D. Bienstock, “Computational study of a family of mixed-integer quadratic programming problems,” Mathematical programming, vol. 74, no. 2, pp. 121–140 (1996).
[12] C. Chen, X. Li, C. Tolman, S. Wang, and Y. Ye, “Sparse portfolio selection via quasi-norm regularization,” arXiv preprint arXiv:1312.6350 (2013).
[13] J. Gao and D. Li, “Cardinality constrained linear-quadratic optimal control,” IEEE Transactions on Automatic Control, vol. 56, no. 8, pp. 1936–1941 (2011).
[14] D. Li, X. Sun, and J. Wang, “Optimal lot solution to cardinality constrained mean–variance formulation for portfolio selection,” Mathematical Finance: An International Journal of Mathematics, Statistics and Financial Economics, vol. 16, no. 1, pp. 83–101 (2006).
[15] 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, vol. 1, no. 1, pp. 55–77 (2013).
[16] J. Xie, S. He, and S. Zhang, “Randomized portfolio selection with constraints,” Pacific Journal of Optimization, vol. 4, no. 1, pp. 89–112 (2008).
[17] 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, vol. 26, no. 4, pp. 690–703 (2014).
[18] D. X. Shaw, S. Liu, and L. Kopman, “Lagrangian relaxation procedure for cardinality-constrained portfolio optimization,” Optimisation Methods & Software, vol. 23, no. 3, pp. 411–420 (2008).
[19] D. Bertsimas and R. Shioda, “Algorithm for cardinality-constrained quadratic optimization,” Computational Optimization and Applications, vol. 43, no. 1, pp. 1–22 (2009).
[20] A. Frangioni and C. Gentile, “Perspective cuts for a class of convex 0–1 mixed integer programs,” Mathematical Programming, vol. 106, no. 2, pp. 225–236 (2006).
[21] A. Frangioni and C. Gentile, “Sdp diagonalizations and perspective cuts for a class of nonseparable miqp,” Operations Research Letters, vol. 35, no. 2, pp. 181–185 (2007).
[22] J. Gao and D. Li, “Optimal cardinality constrained portfolio selection,” Operations research, vol. 61, no. 3, pp. 745–761 (2013).
[23] Y. Tian, S. Fang, Z. Deng, and Q. Jin, “Cardinality constrained portfolio selection problem: A completely positive programming approach,” Journal of Industrial & Management Optimization, vol. 12, no. 3, p. 1041 (2016).
[24] O. P. Burdakov, C. Kanzow, and A. Schwartz, “Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method,” SIAM Journal on Optimization, vol. 26, no. 1, pp. 397–425 (2016).
[25] N. D. Hardoroudi, A. Keshvari, M. Kallio, and P. Korhonen, “Solving cardinality constrained mean-variance portfolio problems via milp,” Annals of Operations Research, vol. 254, no. 1, pp. 47–59 (2017).
[26] A. Wiegele and S. Zhao, “Tight sdp relaxations for cardinalityconstrained problems,” in International Conference on Operations Research. Springer, pp. 167–172 (2021).
[27] A. Frangioni, F. Furini, and C. Gentile, “Improving the approximated projected perspective reformulation by dual information,” Operations Research Letters, vol. 45, no. 5, pp. 519–524 (2017).
[28] X. Cui, X. Zheng, S. Zhu, and X. Sun, “Convex relaxations and miqcqp reformulations for a class of cardinality-constrained portfolio selection problems,” Journal of Global Optimization, vol. 56, no. 4, pp. 1409–1423 (2013).
[29] H. C. Jimbo, I. S. Ngongo, N. G. Andjiga, T. Suzuki, and C. A. Onana, “Portfolio optimization under cardinality constraints: A comparative study,” Open Journal of Statistics, vol. 7, no. 4, pp. 731–742 (2017).
[30] J. Miroforidis, “Bounds on efficient outcomes for large-scale cardinalityconstrained markowitz problems,” Journal of Global Optimization, vol. 80, no. 3, pp. 617–634 (2021).
[31] A. M. Tillmann, D. Bienstock, A. Lodi, and A. Schwartz, “Cardinality minimization, constraints, and regularization: A survey,” arXiv preprint arXiv:2106.09606 (2021).
[32] A. d’Aspremont, L. El Ghaoui, M. I. Jordan, and G. R. Lanckriet, “A direct formulation for sparse pca using semidefinite programming,” SIAM review, vol. 49, no. 3, pp. 434–448 (2007).
[33] M. J. Kim, Y. Lee, J. H. Kim, and W. C. Kim, “Sparse tangent portfolio selection via semi-definite relaxation,” Operations Research Letters, vol. 44, no. 4, pp. 540–543 (2016).
[34] Y. Lee, M. J. Kim, J. H. Kim, J. R. Jang, and W. Chang Kim, “Sparse and robust portfolio selection via semi-definite relaxation,” Journal of the Operational Research Society, vol. 71, no. 5, pp. 687–699 (2020).
[35] F. J. Fabozzi, P. N. Kolm, D. A. Pachamanova, and S. M. Focardi, Robust portfolio optimization and management. John Wiley & Sons (2007).
[36] S. Liu and R. Xu, “The effects of risk aversion on optimization, february 2010,” MSCI Barra Research Paper, no. 2010-06 (2010).
[37] M. R. Garey and D. S. Johnson, Computers and intractability. freeman San Francisco, vol. 174 (1979).
[38] Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” (2023). [Online]. Available: https://www.gurobi.com
[39] I. I. Cplex, “V12. 1: User’s manual for cplex,” International Business Machines Corporation, vol. 46, no. 53, p. 157 (2009).
[40] X. Zheng, X. Sun, D. Li, and X. Cui, “Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs,” European Journal of Operational Research, vol. 221, no. 1, pp. 38–48 (2012).
[41] E. F. Fama and K. R. French, “Industry costs of equity,” Journal of financial economics, vol. 43, no. 2, pp. 153–193 (1997).
[42] M. Grant and S. Boyd, “Graph implementations for nonsmooth convex programs,” in Recent Advances in Learning and Control, ser. Lecture Notes in Control and Information Sciences, V. Blondel, S. Boyd, and H. Kimura, Eds. Springer-Verlag Limited, pp. 95–110 (2008), http: //stanford.edu/~boyd/graph dcp.html.
[43] Michael Grant and Stephen Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
[44] M. ApS, The MOSEK optimization toolbox for MATLAB manual. Version 9.0. (2019). [Online]. Available: http://docs.mosek.com/9.0/ toolbox/index.html
[45] E. D. Dolan and J. J. Mor´e, “Benchmarking optimization software with performance profiles,” Mathematical programming, vol. 91, no. 2, pp. 201–213 (2002).

Views: 173Downloads: 81Citations: 0