Financiometrics Inc.'s QP Algorithm

Overview

The quadratic programming algorithm used in the Quadratic Optimization System portfolio optimization software has been developed specially for solving large-scale portfolio optimization problems. The special structure of these problems lends itself to fast solution by the active set method for quadratic programming. This design of the QP algorithm results in a dramatic increase in the speed of portfolio optimization when compared with a general purpose QP algorithm.

The optimization system is designed to work in two phases. Phase 1 performs a linear optimization to construct a feasible solution for the given set of linear constraints, i.e., it constructs a portfolio which satisfies all of the individual asset holding, portfolio attribute and asset-group constraints. Phase 2 performs the quadratic optimization which determines the global optimal portfolio.

Phase 1 is similar to the traditional Phase 1 Simplex Method of Linear Programming, but it is different in one important way: it keeps as many assets at their initial holdings as is possible. Since the holdings in many assets in the optimal portfolio will not change from their initial values (because of the transactions costs of trading), keeping as many assets as possible at their initial holdings in Phase 1 makes the quadratic optimization in Phase 2 much more efficient.

When a feasible solution is generated by Phase 1, the system moves on to Phase 2 for the quadratic optimization. Each successive iteration of the QP algorithm generates a new portfolio which is closer to the optimal portfolio. Each new portfolio can be described in terms of active constraints. If an asset is at its upper bound, then that upper bound constraint is active. If an asset is at its lower bound, then that lower bound constraint is active. If an asset is at its initial holding, because the cost of transacting that asset is higher than the benefit from the transaction, then an implicit initial holding constraint is active for that asset. The set of active constraints is called the active set. Variables that are not associated with active constraints are called basic variables, or as in our application basic assets.

When the optimization system is used regularly to rebalance a portfolio, the optimal portfolio holdings are usually not very different from the initial portfolio holdings. As a result the number of basic assets is usually much smaller than the total number of assets in the universe. This reduces the size of the optimization problem substantially, which in turn leads to a dramatic increase in the speed of the optimization.

Starting with the feasible solution generated by Phase 1, the QP algorithm in Phase 2 progresses from one iteration to the next by making one of the following changes to the active set:

Drop a constraint,

Add a constraint,

Drop one constraint and add another.

In addition, it is sometimes necessary to perform a Newton step which determines the optimal portfolio in the intersection of the presently active constraints.

Each new portfolio (x_new) is obtained from the previous one (x_old) according to the iterative relation

x_new = x_old - (b . s)

where s is an n-dimensional search direction, n is the number of assets and b is a scalar step-size. The algorithm terminates when the Karush-Kuhn-Tucker optimality conditions are satisfied. The final portfolio is a true global optimum.

A theoretical comparison of the speed of our algorithm relative to the speed of a general purpose quadratic programming algorithm, will illustrate the superiority of our algorithm for portfolio optimization. Let n denote the number of variables in the QP. It is known that most QP algorithms generate exactly the same sequence of points when applied to the same problem with the same initial conditions. To compare the numerical efficiency of the algorithms, we need only compare the number of calculations required per iteration.

When transactions costs are not included, one iteration for a good general purpose QP method (Best and Ritter, 1988) requires updating a matrix with a minimum dimension of (n x n), where n is the number of assets in the universe. That would require about

n²

arithmetic operations per iteration. By contrast, when the number of group constraints is small relative to the number of assets in the universe, our method updates a much smaller matrix of dimension (p x p) where

p = number of basic assets + number of portfolio attribute and asset-group constraints

The value of p varies from iteration to iteration as the number of basic assets changes, but for portfolio optimization problems p is small relative to n when the system is used regularly to rebalance a portfolio. For n = 100, when the only linear constraint (other than bounds on individual assets), is a budget constraint, p may be about 20. Similarly, for n = 500, p may be about 50.

The ratio of the execution time for our algorithm to the execution time for a general purpose algorithm is

p² / n².

For p = 20 and n = 100, this ratio is about 4%. For this case, if a general purpose algorithm takes 10 minutes to solve the QP problem, our algorithm will take about 24 seconds. For p = 50 and n = 500 this ratio is about 1%.

When transactions costs are included, the setup for a general purpose QP algorithm requires the introduction of two new vectors of decision variables, the sale and purchase vectors. The total number of variables seen by the QP algorithm is then 3n, and matrix updates are performed on a (3n x 3n) matrix. This requires approximately

9n²

arithmetic operations per iteration. By comparison, our algorithm handles transaction costs implicitly. It does not require any new decision variables. The number of basic assets, p, is even smaller than before since transactions costs increase the effective number of active constraints. The ratio of the execution time for our algorithm to the execution time for a general purpose algorithm is now

p² / 9n².

For p = 10 and n = 100, this ratio is about 0.11%. For p = 25 and n = 500 it is about 0.03%, i.e., our algorithm is over 3,000 times faster.

The timing comparisons above are an illustration of the magnitude of the improvement in optimization speed that is possible with our QP algorithm. The realized improvement will vary from case to case.

Another advantage of our QP algorithm is that it can handle a semi-definite Hessian matrix. That gives it the capability to accommodate risk-free asssets and solve linear optimization problems.

References

Michael Best and Jivendra Kale, "Quadratic Programming for Large-Scale Portfolio Optimization," Financial Services Information Systems, edited by Jessica Keyes, Auerbach Publications, CRC Press, pp 513-529, 2000.
Michael Best and Jaroslava Hlouskova, "An Algorithm for Portfolio Optimization with Transaction Costs," Management Science, Vol. 51, No. 11, November 2005, pp 1676-1688.
Michael Best and Klaus Ritter, "A Quadratic Programming Algorithm," Zeitschrift fur Operations Research, Volume 32, No. 5, pp 271-297, 1988.