Penalty method for the sparse portfolio optimization problem

Hongxin Zhao; Lingchen Kong

doi:10.3934/jimo.2024031

Article Contents

2024, Volume 20, Issue 9: 2864-2884. Doi: 10.3934/jimo.2024031

This issue Previous Article A scalar Hessian estimation with a sparse nonmonotone line search technique for the sparse recovery problem Next Article Tsallis entropy of uncertain sets and its application to portfolio allocation

Penalty method for the sparse portfolio optimization problem

Hongxin Zhao^1, and
Lingchen Kong^1, ,

1.
School of Mathematics and Statistics, Beijing Jiaotong University, Beijing, China

^*Corresponding author: Lingchen Kong
^*Corresponding author: Lingchen Kong

Received: August 2023

Revised: February 2024

Early access: March 4, 2024

Published online: March 4, 2024

The work was partially supported by Beijing Natural Science Foundation (Z220001) and the National Natural Science Foundation of China (12371322).

Abstract / Introduction Full Text(HTML) Figure(4) / Table(4) Related Papers Cited by

Abstract

The sparse portfolio optimization problem aims to select a subset of assets from a given set of investment options in order to maximize portfolio returns while minimizing risk. In this paper, we study a class of portfolio problem with the feasible set being the intersection of a polyhedral set and a sparse set. To solve this constrained problem, one efficient approach is the penalty method. We put the sparse constraint on the objective function to get the penalized formulation. We study the $ \epsilon $-optimality and establish an exact penalty result under some mild conditions. Moreover, we reveal the equivalent form of the sparse constraint can be further expressed as the $ \ell_1 $-projection onto the sparse set. Based on this result, an efficient MM-ADMM algorithm is designed by combining majorization-minimization methodology with alternating direction method of multipliers. Extensive numerical experiments demonstrate the efficiency of our model for producing the higher Sharpe ratio when compared with several existing models on six real-world data sets.

Keywords:

Mathematics Subject Classification: Primary: 90C90, 90C26; Secondary: 91G10.

Citation:

Full Text(HTML)

Figure 1. Selected asset wight

Download: Full-size image PowerPoint slide

Figure 2. Portfolio wight and objective function value

Download: Full-size image PowerPoint slide

Figure 3. Sharpe ratio

Download: Full-size image PowerPoint slide

Figure 4. Cumulative return

Download: Full-size image PowerPoint slide

Table 1. List of portfolio strategies considered

Group	Model	$ Abbr. $	$ Refer. $
(0)	Sparse Portfolio
	MVP with the sparse constraint	L0	this paper

(1)	Norm-regular Portfolio
	MVP with the $ \ell_{12} $ regularization	L12	[35]
	MVP with $ \ell_{1} $-regularization	L1	[3]
	MVP with the Elastic Net regularization	EN	[33]

(2)	Benchmarks Portfolio
	MVP with shortsale-constrained	SC	[20]
	MVP with shortsale-unconstrained	SU	[20]
	Equally-weighted (1/N) portfolio	EW	[10]

(3)	Shrinkage of Covariance
	Mixture of sample covariance and identity matrix	SCID	[24]
	Mixture of sample covariance and 1-factor matrix	SC1F	[23]

| Show Table

DownLoad: CSV

Table 2. Information of the six real data sets

$ \# $	Dataset	Stocks	Time period	Source	Frequency
1	DJIA30	29	01/04/2015-30/10/2022	Yahoo finance	Weekly
2	NASDAQ100	95	01/04/2015-30/10/2022	Yahoo finance	Weekly
3	SP500	336	01/04/2015-30/10/2022	Yahoo finance	Weekly
4	Russell2000	1340	01/04/2015-30/10/2022	Yahoo finance	Weekly
5	Russell3000	2166	01/04/2015-30/10/2022	Yahoo finance	Weekly
6	FF100	100	11/1978-06/2022	K.French	Monthly

| Show Table

DownLoad: CSV

Table 3. Four OOS performance ($ \widehat{\sigma}^{2}(\%^2) $, $ \widehat{SR} $, $ TO $, $ ASP $) of L0, L12, L1, EN, EW, SC, SU, SCID and SC1F on six data sets

		DJIA	NASDAQ	SP500	R2000	R3000	FF100
		N=29	N=95	N=336	N=1340	N=2166	N=100
	$ \widehat{\sigma}^{2} $	2.5493	2.6441	1.7298	2.0437	1.5994	5.0968
L0	$ \widehat{SR} $	0.2470	0.1892	0.2135	0.2304	0.2863	0.7337
	$ TO $	0.1673	0.2124	0.3852	1.5348	1.7263	0.6207
	$ ASP $	0.0011	0.0252	0.0878	0.4957	0.6067	0.4234
	$ \widehat{\sigma}^{2} $	3.0045	4.0312	2.7287	3.2294	2.6874	10.8475
L12	$ \widehat{SR} $	0.2277	0.2211	0.1542	0.1777	0.2009	0.4862
	$ TO $	0.015	0.0237	0.0244	0.0504	0.0462	0.0653
	$ ASP $	-7.61E-05	1.02E-04	3.12E-05	2.27E-04	2.11E-04	3.29E-04
	$ \widehat{\sigma}^{2} $	2.4748	2.8808	1.9075	2.1428	1.8526	6.7314
L1	$ \widehat{SR} $	0.2619	0.2364	0.1911	0.2513	0.2552	0.6492
	$ TO $	0.0702	0.1549	0.1013	0.1449	0.1524	0.2058
	$ ASP $	2.62E-06	1.37E-04	1.24E-04	2.18E-04	1.97E-04	1.42E-04
	$ \widehat{\sigma}^{2} $	2.9527	3.4946	2.1594	2.372	1.9566	8.5071
EN	$ \widehat{SR} $	0.2313	0.2274	0.1816	0.2294	0.2406	0.5551
	$ TO $	0.0162	0.0374	0.0532	0.1223	0.1235	0.0958
	$ ASP $	9.45E-05	2.06E-04	1.25E-04	2.15E-04	2.14E-04	3.18E-04
	$ \widehat{\sigma}^{2} $	3.0502	4.3269	3.0474	4.0637	3.5171	12.385
EW	$ \widehat{SR} $	0.2251	0.2187	0.1414	0.1683	0.1846	0.4558
	$ TO $	0.0147	0.0217	0.0207	0.0305	0.0271	0.0181
	$ ASP $	1.12E-16	1.12E-16	-1.11E-16	4.48E-16	-3.36E-16	0
	$ \widehat{\sigma}^{2} $	2.5098	2.5622	1.7653	1.9918	1.5767	6.0162
SC	$ \widehat{SR} $	0.2575	0.1341	0.1814	0.3855	0.3454	0.7533
	$ TO $	0.1641	0.1947	0.3108	0.4704	0.5049	0.1797
	$ ASP $	1.11E-10	-4.27E-13	-9.92E-13	1.15E-12	1.15E-12	1.13E-12
	$ \widehat{\sigma}^{2} $	3.8426	4.4823	2.1135	3.3557	2.6337	10.162
SU	$ \widehat{SR} $	0.2618	0.1012	0.2183	0.1443	0.1727	0.5894
	$ TO $	0.7164	2.1896	0.6387	0.3014	0.2773	5.0389
	$ ASP $	1.2239	1.9652	0.8731	0.3479	0.3559	5.2745
	$ \widehat{\sigma}^{2} $	2.7159	2.9801	1.5719	1.6259	1.2838	13.998
SCID	$ \widehat{SR} $	0.3306	0.1901	0.2419	0.2309	0.2893	0.4953
	$ TO $	0.2809	0.6930	0.4781	0.2437	0.2281	2.0935
	$ ASP $	0.4838	1.2255	0.9967	0.4926	0.4913	4.1532
	$ \widehat{\sigma}^{2} $	2.5324	2.6633	1.5715	1.6233	1.2833	10.788
SCIF	$ \widehat{SR} $	0.3309	0.2026	0.2439	0.2304	0.2891	0.5279
	$ TO $	0.2001	0.7913	0.5332	0.2587	0.2395	2.6103
	$ ASP $	0.3306	0.9515	0.9396	0.4920	0.4908	3.3615

| Show Table

DownLoad: CSV

Table 4. Four OOS performance ($ \widehat{\sigma}^{2}(\%^2) $, $ \widehat{SR} $, $ TO $, $ ASP $) of L0, L12, L1, EN, EW, SC, SU, SCID and SC1F on six data sets

		DJIA	NASDAQ	SP500	R2000	R3000	FF100
		N=29	N=95	N=336	N=1340	N=2166	N=100
	$ \widehat{\sigma}^{2} $	4.2750	4.9032	12.3449	7.7311	5.4219	14.516
L0	$ \widehat{SR} $	0.1832	0.1548	0.0634	0.1271	0.1203	0.2685
	$ TO $	0.0652	0.1923	0.0293	2.1782	2.1298	0.4935
	$ ASP $	0.0034	0.0498	5.32E-04	0.5909	0.6234	0.2134
	$ \widehat{\sigma}^{2} $	4.9964	4.7616	12.1218	5.2520	4.5668	23.888
L12	$ \widehat{SR} $	0.1221	0.1142	0.0657	0.0941	0.1067	0.2187
	$ TO $	0.0226	0.0333	0.0289	0.0954	0.1027	0.0578
	$ ASP $	-1.83E-04	2.53E-04	0.0011	2.05E-04	2.24E-04	2.94E-04
	$ \widehat{\sigma}^{2} $	3.7206	4.7563	11.3104	4.4145	3.6472	18.747
L1	$ \widehat{SR} $	0.1867	0.1012	0.0756	0.1229	0.1352	0.2440
	$ TO $	0.1285	0.1754	0.0542	0.1993	0.1979	0.2661
	$ ASP $	-2.75E-06	1.35E-04	6.96E-04	2.21E-04	2.20E-04	1.72E-04
	$ \widehat{\sigma}^{2} $	4.5370	4.6409	10.9986	4.5102	3.7296	21.192
EN	$ \widehat{SR} $	0.1422	0.1021	0.0733	0.1148	0.1337	0.2322
	$ TO $	0.0304	0.0608	0.0559	0.1709	0.1748	0.1092
	$ ASP $	2.67E-04	2.58E-04	7.68E-04	2.22E-04	2.24E-04	2.86E-04
	$ \widehat{\sigma}^{2} $	6.4740	5.1432	12.7871	7.8861	6.9559	29.144
EW	$ \widehat{SR} $	0.0805	0.1278	0.0602	0.0865	0.0956	0.2041
	$ TO $	0.0210	0.0253	0.0298	0.034	0.0301	0.0228
	$ ASP $	1.16E-16	1.16E-16	-1.16E-16	4.45E-16	-3.34E-16	0
	$ \widehat{\sigma}^{2} $	3.9798	5.2190	3.1752	5.4868	4.6523	15.901
SC	$ \widehat{SR} $	0.2015	0.2174	-0.0539	0.1936	0.1581	0.2503
	$ TO $	0.1282	0.2188	0.2143	0.4866	0.4776	0.2332
	$ ASP $	9.62E-11	-4.04E-12	5.42E-13	-3.09E-13	6.61E-14	1.08E-12
	$ \widehat{\sigma}^{2} $	5.66E+02	6.1397	8.9327	6.535	5.4722	11.864
SU	$ \widehat{SR} $	-0.0908	0.1808	0.0943	0.0483	0.0621	0.1033
	$ TO $	1.29E+02	1.2898	0.9638	0.3275	0.3163	2.2901
	$ ASP $	12.4048	1.2403	1.2338	0.2546	0.2570	2.2785
	$ \widehat{\sigma}^{2} $	6.5846	6.5168	3.7389	3.6023	2.9769	10.408
SCID	$ \widehat{SR} $	0.4598	0.0652	0.2480	0.1011	0.1312	0.3379
	$ TO $	0.8728	0.8798	0.583	0.2625	0.2598	1.3237
	$ ASP $	1.3851	1.5091	1.1280	0.3192	0.3357	2.3725
	$ \widehat{\sigma}^{2} $	5.1236	6.1740	3.7488	3.6004	2.9824	9.9189
SCIF	$ \widehat{SR} $	0.444	0.0799	0.2097	0.102	0.1313	0.3418
	$ TO $	0.5808	0.8756	0.5974	0.2722	0.2711	1.4382
	$ ASP $	1.0701	1.3942	1.1166	0.3196	0.3361	2.2401

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Beck, First-Order Methods in Optimization, SIAM, 2017. doi: 10.1137/1.9781611974997.ch1.
[2]	D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74 (1996), 121-140. doi: 10.1016/0025-5610(96)00044-5.
[3]	J. Brodie, I. Daubechies, C. De Mol, D. Giannone and I. Loris, Sparse and stable Markowitz portfolios, Proceedings of the National Academy of Sciences, 106 (2009), 12267-12272.
[4]	T.-J. Chang, N. Meade, J. E. Beasley and Y. M. Sharaiha, Computers and Operations Research, 27 (2000), 1271-1302.,
[5]	C. Chen, X. Li, C. Tolman, S. Wang and Y. Ye, Sparse portfolio selection via quasi-norm regularization, preprint arXiv: 1312.6350, 2013.
[6]	X. Chen, D. Ge, Z. Wang and Y. Ye, Complexity of unconstrained $\ell_2-\ell_p$ minimization, Mathematical Programming, 143 (2014), 371-383. doi: 10.1007/s10107-012-0613-0.
[7]	X. Chen, Z. Lu and T.-K. Pong, Penalty methods for a class of non-Lipschitz optimization problems, SIAM Journal on Optimization, 26 (2016), 1465-1492. doi: 10.1137/15M1028054.
[8]	S. Corsaro and V. De Simone, Adaptive $\ell_1$-regularization for short-selling control in portfolio selection, Computational Optimization and Applications, 72 (2019), 457-478. doi: 10.1007/s10589-018-0049-4.
[9]	V. DeMiguel, L. Garlappi, F. J. Nogales and R. Uppal, A generalized approach to portfolio optimization: Improving performance by constraining portfolio norms, Management Science, 55 (2009), 798-812.
[10]	V. DeMiguel, L. Garlappi and R. Uppal, Optimal versus naive diversification: How inefficient is the 1/N portfolio strategy?, The Review of Financial Studies, 22 (2009), 1915-1953. 2009.
[11]	J. Fan, H. Weng and Y. Zhou, Optimal estimation of functionals of high-dimensional mean and covariance matrix, preprint, arXiv: 1908.07460, 2019.
[12]	J. Fan, J. Zhang and K. Yu, Vast portfolio selection with gross-exposure constraints, Journal of the American Statistical Association, 107 (2012), 592-606. doi: 10.1080/01621459.2012.682825.
[13]	B. Fastrich, S. Paterlini and P. Winker, Cardinality versus q-norm constraints for index tracking, Quantitative Finance, 14 (2014), 2019-2032. doi: 10.1080/14697688.2012.691986.
[14]	J. Gao and D. Li, Optimal cardinality constrained portfolio selection, Operations Research, 61 (2013), 745-761. doi: 10.1287/opre.2013.1170.
[15]	Y. Gao and D. Sun, A majorized penalty approach for calibrating rank constrained correlation matrix problems, 2010.
[16]	M. Giuzio, Genetic algorithm versus classical methods in sparse index tracking, Decisions in Economics and Finance, 40 (2017), 243-256. doi: 10.1007/s10203-017-0191-y.
[17]	J. Gotoh, A. Takeda and K. Tono, DC formulations and algorithms for sparse optimization problems, Mathematical Programming, 169 (2018), 141-176. doi: 10.1007/s10107-017-1181-0.
[18]	H. Hazimeh and R. Mazumder, Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms, Operations Research, 68 (2020), 1517-1537.
[19]	N. L. Jacob, A limited-diversification portfolio selection model for the small investor, The Journal of Finance, 29 (1974), 847-856.
[20]	R. Jagannathan and T. Ma, Risk reduction in large portfolios: Why imposing the wrong constraints helps, The Journal of Finance, 58 (2003), 1651-1683.
[21]	P. J. Kremer, S. Lee, M. Bogdan and S. Paterlini, Sparse portfolio selection via the sorted $\ell_1$-norm, Journal of Banking and Finance, 110 (2020), 105687.
[22]	H. A. Le Thi, T. Pham Dinh, H. M. Le and X. T. Vo, DC approximation approaches for sparse optimization, European Journal of Operational Research, 244 (2015), 26-46. doi: 10.1016/j.ejor.2014.11.031.
[23]	O. Ledoit and M. Wolf, Improved estimation of the covariance matrix of stock returns with an application to portfolio selection, Journal of Empirical Finance, 10 (2003), 603-621.
[24]	O. Ledoit and M. Wolf, A well-conditioned estimator for large-dimensional covariance matrices, Journal of Multivariate Analysis, 88 (2004), 365-411. doi: 10.1016/S0047-259X(03)00096-4.
[25]	Z. Lu and X. Li, Sparse recovery via partial regularization: Models, theory, and algorithms, Mathematics of Operations Research, 43 (2018), 1290-1316. doi: 10.1287/moor.2017.0905.
[26]	R. Moral-Escudero, R. Ruiz-Torrubiano and A. Suárez, Selection of optimal investment portfolios with cardinality constraints, In 2006 IEEE International Conference on Evolutionary Computation, (2006), 2382-2388.
[27]	W. F. Sharpe, The Sharpe ratio, Streetwise–the Best of the Journal of Portfolio Management, 3 (1998), 169-185.
[28]	W. Shen, J. Wang and S. Ma, Doubly regularized portfolio with risk minimization, In Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014.
[29]	Q. Wang and H. Sun, Sparse markowitz portfolio selection by using stochastic linear complementarity approach, Journal of Industrial and Management Optimization, 14 (2018), 541-559. doi: 10.3934/jimo.2017059.
[30]	M. Woodside-Oriakhi, C. Lucas and J. E. Beasley, Heuristic algorithms for the cardinality constrained efficient frontier, European Journal of Operational Research, 213 (2011), 538-550. doi: 10.1016/j.ejor.2011.03.030.
[31]	F. Xu, Z. Lu and Z. Xu, An efficient optimization approach for a cardinality-constrained index tracking problem, Optimization Methods and Software, 31 (2016), 258-271. doi: 10.1080/10556788.2015.1062891.
[32]	Z. Xu, X. Chang, F. Xu and H. Zhang, $\ell_{\frac 12}$ regularization: A thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems, 23 (2012), 1013-1027.
[33]	Y.-M. Yen and T.-J. Yen, Solving norm constrained portfolio optimization via coordinate-wise descent algorithms, Computational Statistics and Data Analysis, 76 (2014), 737-759. doi: 10.1016/j.csda.2013.07.010.
[34]	C. Zhao, N. Xiu, H. Qi and Z. Luo, A Lagrange-Newton algorithm for sparse nonlinear programming, Mathematical Programming, 195 (2022), 903-928. doi: 10.1007/s10107-021-01719-x.
[35]	H. Zhao, L. Kong and H.-D. Qi, Optimal portfolio selections via $\ell_{1, 2}$-norm regularization, Computational Optimization and Applications, 80 (2021), 853-881. doi: 10.1007/s10589-021-00312-4.
[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]	X. Zheng, X. Sun, D. Li and J. Sun, Successive convex approximations to cardinality-constrained convex programs: A piecewise-linear DC approach, Computational Optimization and Applications, 59 (2014), 379-397. doi: 10.1007/s10589-013-9582-3.
[38]	S. Zhou, N. Xiu and H.-D. Qi, A fast matrix majorization-projection method for penalized stress minimization with box constraints, IEEE Transactions on Signal Processing, 66 (2018), 4331-4346. doi: 10.1109/TSP.2018.2849734.
[39]	S. Zhou, N. Xiu and H.-D. Qi, Global and quadratic convergence of Newton hard-thresholding pursuit, J. Mach. Learn. Res., 22 (2021), 1-45.