Portfolio optimisation - Non brute force solutions to optimisation problems

Recently I wrote a program in Python which extracts stock data for a designated period and frequency of the predetermined stocks and then optimises the portfolio using the Sharpe ratio. In order to generate the different kinds of weights, I wrote a generator that gives me all the possible weights (all weights are non-negative and have to sum to 100).

Now the problem with this is that while I can still confidently simulate a 5 stock portfolio (which takes about 5 minutes), simulating a 6 stock portfolio would take up to 10 hours on my machine, given all the possible distributions of weights (if I recall correctly it should be around 96 millions). I would want to push this as far as possible, optimally to a point where the gains from un-systematic risk reduction are minimal as a consequence of adding additional stocks.

Now my question is what are the "smart ways" to do this (obviously the way I am using is neat since you get all the possible outcomes, but cant be considered seriously given the resource and time intensity)? What kind of optimisation techniques would one use in order to make this process faster?

I am not searching for any single solution, but rather for an elaboration as to what optimization techniques exist out there, that could be used in order to approach this problem and what are their advantages or/and disadvantages.

Thank you for any suggestions!

• If you precisely define your problem, you are more likely to get clear answers. Eg. I'm minimizing object $f$ over variables $x, y$ etc... subject to constraitns $g_1$, $g_2$, etc.... – Matthew Gunn Jul 18 '17 at 16:41
• I think I did exactly that if you read my post. I am maximizing the Sharpe ratio (which is a well known ratio in finance), using n number of stocks which form a portfolio in which each stock has a non-negative weight (no short selling) and where the weights of all the stocks sum to 100, the risk / return profile of each stock is defined trough its price over a period of time. But I am also quote clear that I do not pursue a defined answerer but just an elaboration on the methods that exist in order to facilitate a more efficient optimization than the brute force method I am using. – Noir Jul 18 '17 at 19:07
• If one assumes you know the mean $\mu$ and covariance matrix $\Sigma$ for your $n$ securities, then you have a classic Markowitz portfolio optimization problem. It is a quadratic program with a well known analytical solution. @RPG provides the same answer below. That problem reduces to solving a linear system in $n$ variables which can be done about instantly. The problem is in estimating $\mu$ and $\Sigma$. – Matthew Gunn Jul 18 '17 at 19:14

There are a few commonly used solutions

1. Analytic solutions. These can be particularly effective when the objective function is linear/quadratic, and the constraints are all linear equality constraints (e.g. self-financing, zero beta, sector neutrality etc)

2. Quadratic optimization. This works well with linear/quadratic objective function, and linear equality or inequality constraints (all the above, plus turnover constraints, position limits, sector exposure limits etc)

3. Conic optimization. This extends the applicability of the above solutions to objective functions that can be non-linear/quadratic and constraints that can be non-linear, as long as the objective function and constraints can be transformed to either linear/quadratic or conic.

4. Non-linear optimization. Generic non-linear optimizers (e.g. interior point methods or Nelder-Mead) can sometimes give satisfactory solutions on a wide range of objective functions and constraints -- the only requirements generally being that the objective function/constraints are sufficiently smooth (no discontinuities). It helps if you can calculate an analytic gradient.

To optimize for the Sharpe ratio in cases 1 and 2, you generally have to consider a family of solutions $w_\lambda$ that maximise

$$\alpha^T w_\lambda - \lambda w_\lambda^T\Sigma w_\lambda$$

and chose the value of $\lambda$ that gives the highest Sharpe Ratio. In cases 3 and 4 you can optimize for the Sharpe ratio directly.

• Maybe I misunderstand what OP's asking, but I believe OP is asking about stock selection. Once you have the stock selected, it is trivial to get the weights/optimize/rebalance. But if you have 100 stocks and you want to get all possibile combinations and then optimize, you'd need to check $2^{100}-1$ portfolios, which I believe is what OP is asking. @Noir - please comment – rbm Jul 18 '17 at 11:26
• I am not 100% sure if I understood properly what you are suggesting that I am asking. Having read the answerer provided by @Chris Taylor, I do believe that it goes into the right direction (I am using the word "believe" only because I will have to do a bit of research on a few things he mentions). My question is centred around the issue as to how one should approach a portfolio optimization once a brute force method, becomes inefficient / unpractical. – Noir Jul 18 '17 at 11:45
• Understood, but I believe your brute force is only needed when you're trying to do stock selection. If you know what stocks you want to use for your portfolios, then optimizing is fairy simple (once you've chosen the method, e..g Markowitz). There are basic R packages which can do portfolio optimization, that include automatic weight calculation, based on your constrain (long-only, long-shorting, mean target, volatility target, etc). Look at R, packages mpo, PortfolioAnalytics and PerformanceAnalytics. – rbm Jul 18 '17 at 13:14
• Real-life example: we tried a portfolio optimization on 50 stocks, but it'd be impossible to try all combinations of 50 stocks ($2^{50}$) using our chosen method (we had a simple long-only constraint, with a goal of minimizing volatility). So we opted for portfolio with 5 stocks, which was much manageable as $C(50,5)=2118760$. – rbm Jul 18 '17 at 13:20
• @rbm I think that you misunderstand the question. The OP is currently doing portfolio optimization using brute force (by generating a grid of possible weights). They are asking for alternatives to brute force for portfolio optimization (what you describe as 'trivial' and later 'fairly simple' - presumably using the mathematician's definition of these terms!) – Chris Taylor Jul 18 '17 at 13:32

The maximum Sharpe portfolio has a closed form solution.

Let $w_i$ be the weight of asset $i$ so that $\sum_i w_i = 1$. The weights for the maximum Sharpe portfolio is then $$\bf{w} = \frac{\bf{\Sigma}^{-1}\bf{\mu}}{\bf{1}^T\bf{\Sigma}^{-1}\bf{\mu}},$$ where $\bf{\Sigma}$ is the return covariance matrix, $\mu$ is the excess return expectations, and $\bf{1}$ is a vector of ones.

• In theory yes. The obvious problem of course is that neither $\mu$ nor $\Sigma$ can be estimated precisely. Portfolio optimization can have big problems of garbage in, garbage out. – Matthew Gunn Jul 18 '17 at 16:40