Cardinality-Constrained Portfolio Optimization with Linear Constraints

# Portfolio optimization on a subset of assets


# Portfolio optimization on a subset of assets












My objective is a portfolio optimization of the type: given $N$ assets with expected returns $r_i$ and a fixed portfolio size $M$, with $M < N$, find weights $w_i$ (positive or negative) maximizing $$ \max_w \sum_{i=1}^M w_i r_i $$ (simplifying the notation - this over all $M$ size subsets of weights) with a gross constraint $$ \sum_{i=1}^M |w_i| = 1 $$ and some linear constraints, for example hedging with market beta of zero $$ \sum_{i=1}^M \beta_i w_i = 0 $$

If $M=N$ this would be a standard Linear Programming - quick solvers exist. However, in equities there may be $N=10000$ assets and it may not be practical to hold all assets hence the fixed number of assets $M$. But with the fixed number of assets constraint $M < N$, this is a more difficult Integer Programming. (Consider a backtest over 20 years - that's 5000 optimisations so each optimisation needs to be fast.)

I am looking for papers or textbook references treating this, or heuristics to avoid solving an Integer Programming. If I solve the original LP with $M=N$ (no integer constraints), threshold by selecting the top $M$ weights and then rescale, the beta constraint wouldn't be satisfied.

## Answer by Hans-Peter Schrei (score 3)

https://quant.stackexchange.com/a/74966

The term under which this problems is usually known is cardinality-constrained portfolio optimization. This is a broad and active field of research, with new approaches coming out continuously. In general, research is done in the direction of complex methods using simulated annealing, particle swarm optimizations and genetic algorithms, your mileage may vary using these in practice. Depending on your hardware and on your time to implement techniques, I should caution that $N=10 000$ might be ambitious.

In the following I am listing a few approaches that might be of interest. The articles should also give you a good sense of which computation times and values for $N$ are achievable.

- A comparative study of heuristic methods for cardinality constrained portfolio optimization by Lei Fu, Jun Li, Shanwen Pu (2022). High-Confidence Computing, 100097. ISSN 2667-2952. doi: 10.1016/j.hcc.2022.100097

In this paper, the authors propose several heuristic methods: the continuous-relaxation-based method (Heuristic 1), the $l_1$-norm-based solution (Heuristic 2), the integer programming-based solution (Heuristic 3), and the SDP-based solution (Heuristic 4). Utilizing real-life stock data and simulated data sets, the paper assesses the efficiency and accuracy of the proposed techniques. The computational experiments reveal that their SDP-based solution effectively generates high-quality outcomes, outperforming the commercial MIQP solver when time is limited. These methods have apparently been adopted in practice.

- An Efficient Optimization Approach for a Cardinality-Constrained Index Tracking Problem, arXiv:1506.05866 [math.OC]

This paper examines such a cardinality-constrained index tracking model and introduces an efficient nonmonotone projected gradient (NPG) method to address the problem. Typically, this method solves multiple projected gradient subproblems at each iteration, with each subproblem having a closed-form solution that can be computed in linear time. Under appropriate assumptions, it is established that any accumulation point of the sequence generated by the NPG method is a local minimizer of the cardinality-constrained index tracking issue. The authors also perform empirical tests comparing their approach with the hybrid evolutionary algorithm and the hybrid half thresholding algorithm for index tracking. The results show that their method generally yields sparse portfolios with reduced out-of-sample tracking errors and improved consistency between in-sample and out-of-sample tracking errors.

- Bounds on efficient outcomes for large-scale cardinality-constrained Markowitz problems by Miroforidis, J. (2021). J Glob Optim 80, 617–634. doi: 10.1007/s10898-021-01022-1

When addressing large-scale cardinality-constrained Markowitz mean-variance portfolio investment problems, exact solvers may struggle to determine some efficient portfolios within a reasonable time frame. In these instances, information regarding the distance between the best feasible solution found before the optimization process halts and the true efficient solution is not available. In this article, the authors showcase how to provide such information to a decision-maker. Their goal is to employ the concept of lower and upper bounds on objective function values of an efficient portfolio, as developed in their previous works. They demonstrate the proposed approach using a large-scale dataset based on real data. They tackle cases where a top-tier commercial mixed-integer quadratic programming solver fails to deliver efficient portfolios attempted to be derived by Chebyshev scalarization of the bi-objective optimization problem within a given time limit. In this situation, they suggest transforming purely technical information provided by the solver into information that can be utilized in navigating the efficient frontier of the cardinality-constrained Markowitz mean-variance portfolio investment problem.

- Efficient Cardinality/Mean-Variance Portfolios, November 2014. IFIP Advances in Information and Communication Technology 443:52-73. DOI: 10.1007/978-3-662-45504-3_6. In book: System Modeling and Optimization (pp.52-73). Edition: IFIP Advances in Information and Communication Technology. Chapter: 6. Publisher: Springer

The authors propose an innovative approach to address cardinality in portfolio selection by introducing a biobjective cardinality/mean-variance problem. This allows investors to analyze the efficient tradeoff between return-risk and the number of active positions. Recent advancements in multiobjective optimization without derivatives enable them to robustly compute (in-sample) the entire cardinality/mean-variance efficient frontier for various datasets and mean-variance models. Their findings indicate that a significant number of efficient cardinality/mean-variance portfolios can outperform (out-of-sample) the naive strategy while maintaining relatively low transaction costs.