Optimising performance of quadratic programming problems

We have been working on an exciting new project where we are trying to automate some aspects of portfolio construction. In this case, we are trying to create a portfolio to closely track some sort of benchmark. The core of the portfolio construction algorithm will be an optimisation problem that needs solving numerically. In the early development of the algorithm, we have found that computation time can be problematically slow, and that there will be a need to speed this up substantially, especially given that we foresee a need to scale up the number of portfolios to be constructed in the future. In this post, I want to give some background to the problem, identify the areas where we can increase performance, and share some of our experiences so far.

From benchmark to quadratic programming

Tracking a benchmark means constructing a portfolio that not only closely approximates the value of the benchmark but is also expected to follow the benchmark as market conditions change. To understand how the benchmark and portfolio changes with market conditions, we need to determine their sensitivity to a set of risk factors. These risk factors depend on what kind of benchmark you are tracking. For instance, for general investment portfolios, the risk factors may follow from a factor model framework. For fixed income portfolios, the risk factors may be key durations and credit spreads. The approach outlined here could apply to any of them. I will use a little bit of matrix algebra to set out the optimisation problem.

Assume that your benchmark has sensitivities to M different risk factors, captured in a vector b. Now also assume that you have N potential assets you can invest in, each with their own sensitivities to the risk factors, captured in a matrix of M rows and N columns, where each column expresses the sensitivities of a single asset. If we are able to find a portfolio that matches the benchmark’s sensitivity to each risk factor, we ensure that the portfolio perfectly tracks the benchmark. Mathematically, this corresponds to finding a weight vector x consisting of weightings of each potential investment asset, such that it solves the matrix equation Ax = b.

We may be able to find weights x to solve this equation as long as there are sufficiently ‘different’ assets we can invest in [1]. However, in some cases we want to restrict the number of selected assets, for instance to control transaction cost. In that case there may no longer be an exact solution to the matrix equation, and the best we can hope for is that the left side of closely approximates the right side. Put differently, if we subtract b from both sides, we obtain Ax - b = c, where we would like the vector c to be as close to a vector of zeroes as possible. This can form the basis of an optimisation algorithm. However, we would like to focus the minimisation of the differences to those selected assets with the highest impact, which is why we left multiply both sides by the weights vector x, to get x’Ax - x’b = x’c, where x’ indicates the transpose of x. Both sides of this equation are now a single number, and therefore easily taken as the target value to minimise. In optimisation terms, this is the objective function of the algorithm. This type of optimisation problem is called a quadratic programming (QP) problem, as the left hand side of the equation varies quadratically with x.

Where are the performance issues?

The quadratic programming problem is a common type of problem in optimisation and consequently there are many mathematical packages available that solve it. We need to specify A and b, as well as some constraints on the solution, for instance a maximum weighting in any single asset to get some diversification. However, many of them only calculate the optimal weightings given that you have selected to assets to invest in. As mentioned above, the reasonable number of invested assets may be (a lot) smaller than the number of potential assets. Our problem is then not just to determine the optimal weightings of our investments, but also which combination of investments gives the best (i.e. minimal value of the objective function) result.

Keeping in mind that we did not want to optimize for performance too early, our initial approach was to take a ‘brute force’ approach to solving the second issue. We determine all possible combinations of investment assets, and evaluate each one of them to see if they satisfy our constraints and how well they score on the objective function. The winning solution is the one from all successful solutions that minimises the objective function value. The number of different combinations of assets can quickly explode[2], so this is where our performance concerns are coming from.

We see broadly two ways in which we can increase performance:

• Ensure, through whatever means, that the brute force approach converges to a solution faster.
• Rewrite the problem so that we pass the selection of the optimal combination of assets to the optimisation package.

We decided to focus on the former first. The reason is that the second approach leads to a much more complex problem that is harder to solve[3]. Even then we have a few choices:

• Parallellize the problem as much as possible to benefit from multi core performance.
• Select an optimisation package that provides the best performance for each QP problem iteration.
• Distribute the calculation of different branches of the algorithm to different machines, likely in the cloud.

So far we have achieved substantial improvements by focussing on the first two. We have not starting a distributed approach yet, so I can’t share any experiences on it yet.

Performance optimisation results

The implementation of our portfolio construction algorithm is in C#, mostly because it relies heavily on an in-house quantitative analytics library that is written in C#. We make use here of the Task Parallel Library (TPL), first shipped with .Net 4.0, to parallellise the loop that is running the brute force algorithm. There is very little effort here to obtain much better performance. However, we found that we needed to rewrite parts of the code to get optimal benefit from TPL. In particular, we get the best results when everything within the loop is related to the specific loop variable, i.e. the combination of assets being optimised for. Everything that is shared between loops, like the risk factors of the benchmark, should be pulled out. This lead us to pulling apart some calculations that are closely related, just so that we don’t duplicate calculations anymore. The result is code that is slightly less readible and elegant, but much more performant. It did underline the use of the mantra of not prematurely optimising for performance, as there is often a compromise in readability. In thise case, we feel this compromise is worth it.

After this round of improvements, we set about trying alternative optimisation packages for the QP calculations. We are still looking at different packages so we don’t have a winner yet, but already we are finding that there are some decisions you can take that make this process easier. I would recommend making sure you have a wide ranging set of benchmarking tests to base your comparisons on. This will make sure you make like for like comparisons. We also made a decision early on, when we were implementing the algorithm with our initial package, that we would abstract away from it through an adapter like pattern. Consequently there is only one class that depends on the optmisation package, and this class implements an interface for a Solve method. Putting different packages in amounts to adding a new class implementing that interface and passing that into your algorithm code. No other code needs to change. The tricky bit is to actually implement this class. Different optimisation packages have very different APIs, so you end up spending most of your time consulting their documentation to find out how to specify your A and b, your constraints, your starting point etc. For this, you need a good understanding of the nature of the optimisation problem.

When we finish this optimisation step and we still have performance concerns, we will move on to parallellising across different machines in the cloud. Only if this does not prove sufficient, will we consider reformulating the problem completely. We will keep you posted in future updates!

Footnotes

[1] Even if we are able to find a set of weights to perfectly replicate the risk factor sensitivities of the benchmark, we will need to continuously adjust these weights over time. As market moves, the sensitivities to the risk factors change as well, and the exact solution to the matrix equation changes accordingly. Again, in practice, considerations around transaction costs will put a limit of how often to adjust our portfolio weightings.

[2] There are n!/(k!(n-k)!) different ways to choose k items out of a set of n items. For k = 10 and n = 25, this number is already 3268760.

[3] We would need to add binary variables to the problem to represent the choice to invest (or not) in a certain asset. We then obtain a mixed integer linear programming problem, which is much more difficult to solve than quadratic programming problems.