1
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Hi: you can use integer programming for something like this where you define $X_i = 0$ if the ith stock is not held and 1 if its held. Then you'd add a constraint like $\sum_{i} {X_{i}}$ greater than or equal to M. I'm not sure if this could be transformed in some way to a more standard linear program. $\endgroup$
    – mark leeds
    Mar 19 at 4:24
  • $\begingroup$ Hi: in the realm of heuristics, you might consider ranking the asset by their return $r_i$ and attempting a solution using only the most high return assets. $\endgroup$
    – nbbo2
    Mar 19 at 9:35
  • $\begingroup$ @markleeds That's true, but wouldn't that be significantly more difficult than LP? Slow optimisation with unstable solution. $\endgroup$
    – jam123
    Mar 19 at 9:52
  • $\begingroup$ @nbbo2 Yes that heuristic should be a baseline, but hard to say if it's optimal enough without implementing the constrained LP for a comparison. Do you know if it's been done in the literature? $\endgroup$
    – jam123
    Mar 19 at 9:54
  • $\begingroup$ Hi jam123: The speed of course would depend on the size of the problem. As far as stability, I don't have a feel for why a solution would be unstable. As far as difficulty, R has many packages for optimization problems and also packages that allow for interfaces to optimization libraries. So I don't think it should be terribly difficult to implement. You didn't say whether you were incorporating a covariance matrix. If you aren't, then nbbo2's suggestion is good. If you are ( and I assumed that to be the case ), then what nbbo2 suggested is not going to necessarily be close to optimal. $\endgroup$
    – mark leeds
    Mar 19 at 18:05

1 Answer 1

Reset to default
3
$\begingroup$

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.

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.

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.

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.

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you, great review. I can see that even in these recent articles, the running time is not trivial - it would take a long time to run a daily historical backtest. This motivates finding quicker heuristics for preliminary results. $\endgroup$
    – jam123
    Mar 19 at 20:15
  • $\begingroup$ As noted in the comments, the suggestion by @nbbo2 is a good initial approach. The most popular method is probably the $l_1$-approximation that is also noted in the first article I linked to. A general overview can be found here: web.stanford.edu/class/ee364b/lectures/l1_methods_slides.pdf $\endgroup$
    – Hans-Peter Schrei
    Mar 19 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.