# Fastest solver possible for portfolio optimization

I am using quadprog in MATLAB for very simple mean-variance optimization, with less than 100 assets.

It is quite fast but if I run a strategy with daily rebalancing, the execution time can add up very quickly.

Does anyone know any faster solver, particularly in MATLAB?

-
How long does it take now to optimize? For daily mean-variance rebalancing you shouldn't need more than the standard optimizer I guess, even with 100 assets. In short, define better your problem (the size of your constraint set and the optimizing method you use, ..), we might help you from there already. – SRKX Sep 27 '12 at 18:52
The optimization itself is very simple, just standard mean-variance optimization with standard nonnegativity and full investment constraints. The only problem is that I need to do this daily for say 30 different portfolios each with 100 assets. So it could take hours in aggregate. I have been using quadprog in Matlab with interior-point-convex algorithm. It is very possible that there is nothing I can do to speed it up, but I thought I tried my luck by asking here. – ezbentley Sep 27 '12 at 19:29
I take it you mean you want to do a backtest that looks over the past n years using 30 different strategies. You might want to look to parallel processing. That tends to work well in this sort of situation. – John Sep 27 '12 at 19:59
I forgot to mention that I was already using parallel processing. I ran the profiler on my code an quadprog is the one taking the most time simply because it gets called so many times. So anything to speed it up will be very valuable. – ezbentley Sep 27 '12 at 22:06
How long does a single mean-variance run take in Matlab on 100 assets? – Marc Shivers Sep 28 '12 at 2:21

I believe there are several ways you can tackle your problems.

First, you mentioned that your perform several optimizations. One solution that comes to mind instead of speeding up the optimization itself is to perform the optimizations in parallel, so you could look at Mathwork's Parallel Computing Toolbox.

Second, providing the optimizer with a good initial guess reduces the execution time, by how much depends on the problem. In this case the optimal weights for the previous day can be such a guess.

Third, if you want to speed up the optimization, you have basically two approaches.

Either you can use the same method but with a package that is implement in a more optimal fashion, and you could look at packages such as NAG's.

Otherwise, you believe that there is another method that would be better at finding a solution. I've seen people use Conic Optimization for this kind of problems and I know that MOSEK have a MATLAB package for that method. You can also have a look at their white paper for more details about this approach.

For more theory on numerical optimizations such as quadratic programming you could take a look at Numerical Optimization by Nocedal and Wright.

-
I don't know whether this applies in this scenario but another idea is seeding the solver with a good initial guess. In this case a good guess could be obtained by using the portfolio weights of the previous day. – Bob Jansen Sep 28 '12 at 5:31
@BobJansen oh yeah I forgot about that, although if it is convex it should quickly converge shouldn't it? – SRKX Sep 28 '12 at 15:13

I had the problem of creating a portfolio from 10000 time series. So I used greedy optimisation principle. 1. select best Sharpe ratio time series 2. select next time series that in combination creates best Sharpe ratio 3. add one more time series that creates best portfolio Sharpe ratio 4. continue adding one by one till you reach 100 or so 5. divide weights by 100 and you get weights to sum up to 1

you can add restrictions inside the main loop - i.e. do not add more than 10% of the same type. results are similar to quadprog but much faster.

-

Note that you should run only one server and one or more workers in different computers.