Trade Cost Optimisation II: Tracking Error and the Cutting Plane Algorithm

29 May 2019  |  Dr. Malte Kurz
TCO II cutting plane dark
Measuring the distance between two portfolios can be achieved with different metrics, like turnover or tracking error. We show how a tracking-error-based trade cost optimisation can be implemented using the cutting plane algorithm to solve mixed integer quadratic programs (MIQPs).

DisclaimerThe views and opinions expressed in this blog are those of the author and do not necessarily reflect the views of Scalable Capital GmbH or its subsidiaries. Further information can be found at the end of this article.

Summary

  • This blog article builds on our first blog article about trade cost optimisation approaches. We discuss some weaknesses of the simple approach presented in the first article and make suggestions for extending and improving the trade cost optimisation towards a more sophisticated and powerful algorithm.
  • Distances between portfolios can be measured with different metrics: We compare turnover and tracking error as distance measures.
  • Drawbacks of turnover-based trade cost optimisations in terms of indifferences and suboptimalities are explained and illustrated.
  • An extended and more sophisticated trade cost optimisation using tracking error is introduced and formulated in terms of a mixed integer quadratic program (MIQP).
  • We explain how the cutting plane algorithm can be used to solve mixed integer quadratic programs (MIQPs) sequentially with solvers for mixed integer linear programs (MILPs).
  • The superiority of the tracking-error-based trade cost optimisation is shown by revisiting the momentum strategy backtest from the first trade cost optimisation blog article and we provide comparative results.

1. Measuring the Distance Between Weight Vectors: Turnover vs. Tracking Error

In the last blog article, we already got to know different measures for the distance of two portfolio weight vectors:
Trade count

TC(x,x~):=i=1n1{xix~i>0}TC(
bm{x},
tilde{
bm{x}})
{:=}
sum_{i=1}^{n} 1_{
lbrace |x_i -
tilde{x}_i| > 0
rbrace}

and turnover

TO(x,x~):=12i=1nxix~i.TO(
bm{x},
tilde{
bm{x}}) {:=}
frac{1}{2}
sum_{i=1}^{n} |x_i -
tilde{x}_i|.

Both measures have a direct link to some kind of transaction costs, i.e., fixed costs and variable costs, respectively. In the context of a trade cost optimisation, distance measures for portfolios are relevant at multiple occasions. The main purpose of a trade cost optimisation is to handle the trade-off between cost efficiency and optimality of a portfolio with respect to an ideal target portfolio. In this sense, the optimality also has to be measured in terms of the distance of two portfolio weight vectors. However, the turnover is not necessarily a well-suited similarity measure for the proximity of a portfolio to its target portfolio.

1.1. Turnover vs. Tracking Error

In the following, we will demonstrate the suboptimality of turnover as distance measure using a simple example of three assets. We consider the bond ETF TLT and the two equity ETFs IWM and EEM. Let us assume that we hold an equal-weights portfolio x0=(13,13,13)
bm{x}_0 = (
frac{1}{3},
frac{1}{3},
frac{1}{3})'
and consider three different target portfolios

x~1=(00.50.5),x~2=(0.500.5),x~3=(0.50.50).
tilde{
bm{x}}_1 =
left(
begin{matrix}0

0.5

0.5
end{matrix}
right),

quad

tilde{
bm{x}}_2 =
left(
begin{matrix}0.5

0

0.5
end{matrix}
right),

quad

tilde{
bm{x}}_3 =
left(
begin{matrix}0.5

0.5

0
end{matrix}
right).

The turnover distances are all equal, i.e.,

TO(x0,x~1)=TO(x0,x~2)=TO(x0,x~3)=0.3333.TO(
bm{x}_0,
tilde{
bm{x}}_1) = TO(
bm{x}_0,
tilde{
bm{x}}_2)
= TO(
bm{x}_0,
tilde{
bm{x}}_3) = 0.3333.

Even measuring exactly the same distance, it is rather unlikely that an investor or portfolio manager would assign the same utility to all three portfolio distances. To give an impression, we consider an investor holding the four different portfolios with fixed weights (i.e., daily rebalancing to the fixed weights) and analyse the differences of realised portfolio returns. The studied sample period is the same as in the previous blog article, i.e., from Jan-2008 till Dec-2018. Denoting the portfolio return corresponding to weight x
bm{x}
by rxr_{
bm{x}}
, we obtain the following sample volatilities (standard deviations) for daily percentage return differences:

σ^(rx0rx~1)=0.7320,σ^(rx0rx~2)=0.3950,σ^(rx0rx~3)=0.5385.
begin{aligned}

hat{
sigma}(r_{
bm{x}_0} - r_{
tilde{
bm{x}}_{1}}) &= 0.7320,



hat{
sigma}(r_{
bm{x}_0} - r_{
tilde{
bm{x}}_{2}}) &= 0.3950,



hat{
sigma}(r_{
bm{x}_0} - r_{
tilde{
bm{x}}_{3}}) &= 0.5385.

end{aligned}

These volatilities are often called tracking error. The tracking-error as volatility of the return differences provides a measure for the dispersion of two portfolios in terms of performance differences. In contrast to the turnover, which is not distinguishing between weight differences in different assets, the tracking error is a dispersion measure which is sensitive with respect to weight differences in different assets. Therefore, tracking error is better suited for measuring the distance of a portfolio from its ideal target.

Tracking error can also be written as a quadratic form in the variance-covariance matrix of the assets, i.e.,

Var(rx0rx~1)=Var(x0rx~1r)=(x0x~1)Σ(x0x~1),
text{Var}(r_{
bm{x}_0} - r_{
tilde{
bm{x}}_{1}})
=
text{Var}({
bm{x}_0}'
bm{r} -
tilde{
bm{x}}_{1}'
bm{r})
= (
bm{x}_0 -
tilde{
bm{x}}_{1})'
Sigma (
bm{x}_0 -
tilde{
bm{x}}_{1}),

with Cov(r)=Σ
text{Cov}(
bm{r}) =
bm{
Sigma}
and r
bm{r}
denoting the vector of asset returns. Therefore, a definition of tracking error TE(,)TE(
cdot,
cdot)
as distance between two portfolios in terms of weight vectors is given by

TE(x,x~):=(Var(xrx~r))12=((xx~)Σ(xx~))12.TE(
bm{x},
tilde{
bm{x}})
:=
left(
text{Var}(
bm{x}'
bm{r} -
tilde{
bm{x}}'
bm{r})
right)^{
frac{1}{2}}
=
left((
bm{x} -
tilde{
bm{x}})'
bm{
Sigma} (
bm{x} -
tilde{
bm{x}})
right)^{
frac{1}{2}}.

1.2. Relative Tracking Error

Let us consider another portfolio weight vector x~4=(0.59,0,0.41)
tilde{
bm{x}}_4 = (0.59, 0, 0.41)
for which TO(x0,x~4)=0.3333TO(
bm{x}_0,
tilde{
bm{x}}_4) = 0.3333
and σ^(rx0rx~4)=0.5413
hat{
sigma}(r_{
bm{x}_{0}} - r_{
tilde{
bm{x}}_{4}}) = 0.5413
. So it has equal turnover distance compared to the one between x0
bm{x}_0
and x~3
tilde{
bm{x}}_3
and almost equal tracking error distance. However, the target portfolios have empirical volatilities of σ^(rx~3)=0.7001
hat{
sigma}(r_{
tilde{
bm{x}}_{3}}) = 0.7001
and σ^(rx~4)=0.7840
hat{
sigma}(r_{
tilde{
bm{x}}_{4}}) = 0.7840
. Therefore, while the absolute dispersion in terms of tracking error from the current portfolio, x0
bm{x}_0
, is very similar, it might be more sensible to consider the tracking error distance relative to the volatility of the target portfolio. This gives rise to the definition of relative tracking error TErel(,)TE_{rel}(
cdot,
cdot)

TErel(x,x~):=(Var(xrx~r)Var(x~r))12=((xx~)Σ(xx~)x~Σx~)12.TE_{rel}(
bm{x},
tilde{
bm{x}})
:=
left(
frac{
text{Var}(
bm{x}'
bm{r} -
tilde{
bm{x}}'
bm{r})}{
text{Var}(
tilde{
bm{x}}'
bm{r})}
right)^{
frac{1}{2}}
=
left(
frac{(
bm{x} -
tilde{
bm{x}})'
bm{
Sigma} (
bm{x} -
tilde{
bm{x}})}{
tilde{
bm{x}}'
bm{
Sigma}
tilde{
bm{x}}}
right)^{
frac{1}{2}}.

For the exemplary portfolio vectors that are considered we get the following relative tracking error distances

TE^rel(x0,x~1)=0.4430,TE^rel(x0,x~2)=0.4319,TE^rel(x0,x~3)=0.7682,TE^rel(x0,x~4)=0.6905,
begin{aligned}

hat{TE}_{rel}(
bm{x}_0,
tilde{
bm{x}}_{1}) &= 0.4430,



hat{TE}_{rel}(
bm{x}_0,
tilde{
bm{x}}_{2}) &= 0.4319,



hat{TE}_{rel}(
bm{x}_0,
tilde{
bm{x}}_{3}) &= 0.7682,



hat{TE}_{rel}(
bm{x}_0,
tilde{
bm{x}}_{4}) &= 0.6905,

end{aligned}

where TE^rel(,)
hat{TE}_{rel}(
cdot,
cdot)
denotes the ex-post observed tracking error based on the empirical variance-covariance matrix Σ^
hat{
Sigma}
. We can see that in terms of relative tracking error the distances of x0
bm{x}_0
to x~3
tilde{
bm{x}}_3
and x0
bm{x}_0
to x~4
tilde{
bm{x}}_4
are no longer evaluated approximately the same. At the same time it is also interesting to note that in terms of relative tracking error, the distances of x0
bm{x}_0
to x~1
tilde{
bm{x}}_1
and x0
bm{x}_0
to x~2
tilde{
bm{x}}_2
are quite similar, which is caused by the differences in the volatility of the target portfolios. It is important to point out that this relative assessment of distances is not symmetric, i.e., it matters which of the two portfolios is the target portfolio and in general we have TErel(x,x~)TE_{rel}(
bm{x},
tilde{
bm{x}})
TErel(x~,x)TE_{rel}(
tilde{
bm{x}},
bm{x})
.

2. On Turnover-Based Trade Cost Optimisation

In our first blog article about trade cost optimisation, we introduced the optimisation problem

minxC(x0,x)s.t.TO(x,x~)γ,
min
limits_{
bm{x}} C(
bm{x}_0,
bm{x})

qquad
text{s.t.}
qquad
TO(
bm{x},
tilde{
bm{x}})
leq
gamma,

where C(x0,x)C(
bm{x}_0,
bm{x})
are the costs to trade from x0
bm{x}_0
to x
bm{x}
and TO(x,x~)TO(
bm{x},
tilde{
bm{x}})
is the turnover distance of the post-trade weights, x
bm{x}
, to the ideal weights, x~
tilde{
bm{x}}
. In this approach, the trade-off between cost efficiency and optimality of the new portfolio is handled by enforcing an upper bound for the turnover distance to the ideal portfolio x~
tilde{
bm{x}}
and at the same time trading costs are minimised. While this approach performs very well in implementing systematic portfolio strategies cost-efficiently, it also comes at some drawbacks that we would like to discuss in the following sections.

2.1. Indifferences Between Different Optimal Solutions

One problem of turnover distance is its indifference with respect to different assets, i.e., for turnover distance it does not really matter in which asset a weight difference occurs. As a result, it can happen that there exist multiple non-unique solutions to the trade cost optimisation problem. As an illustration, we again use the three-asset case and for the current portfolio weight we assume x0=(0.4,0.3,0.3)
bm{x}_0 = (0.4, 0.3, 0.3)'
and as target portfolio weight x~=(0.5,0.25,0.25)
tilde{
bm{x}} = (0.5, 0.25, 0.25)'
. For γ=0.025
gamma = 0.025
optimal solutions of the optimisation problem are

x1=(0.47500.25000.2750),x2=(0.47500.27500.2500),x3=(0.47500.26250.2625),
bm{x}_1 =
left(
begin{matrix}0.4750

0.2500

0.2750
end{matrix}
right),

quad

bm{x}_2 =
left(
begin{matrix}0.4750

0.2750

0.2500
end{matrix}
right),

quad

bm{x}_3 =
left(
begin{matrix}0.4750

0.2625

0.2625
end{matrix}
right),

with

TO(x1,x~)=TO(x2,x~)=TO(x3,x~)=0.025,C(x0,x1)=C(x0,x2)=C(x0,x3)=cfix3+PPF2cvar0.15.
begin{aligned}
TO(
bm{x}_1,
tilde{
bm{x}})
&= TO(
bm{x}_2,
tilde{
bm{x}}) = TO(
bm{x}_3,
tilde{
bm{x}}) = 0.025,


C(
bm{x}_0,
bm{x}_1) &= C(
bm{x}_0,
bm{x}_2) = C(
bm{x}_0,
bm{x}_3)
= c_{fix}
cdot 3 + P_{PF}
cdot 2
cdot c_{var}
cdot 0.15.

end{aligned}

We see that all these solutions have the same fit value and there even exists an infinite number of solutions with this fit value. Two issues arise: First, even providing the same fit, investors and portfolio managers might not be indifferent to the choice between the different solutions of the optimisation problem. Second, from a numerical optimisation point of view stability issues can arise when solving an optimisation problem with an infinite number of optimal solutions. Depending on the algorithm used for solving the optimisation problem, different solutions can be obtained if computations are repeated or done on different machines. The non-uniqueness can make it difficult or impossible to obtain reproducible results. Both issues can be tackled by using tracking error instead of turnover to measure the distance to the target portfolio. While indifferences are very likely with turnover, they are only possible in edge cases with tracking error.

2.2. Suboptimal Solutions to the Multi-Objective Optimisation Problem

Theoretically, investors face a multi-objective problem when handling the trade-off between cost efficiency and optimality. In combination with turnover as a metric, we could even face the situation where the trade cost optimisation problem has multiple non-unique solutions with the same fit value (in terms of costs) but different turnover distances to the target portfolio. If we set cvar=0c_{var} = 0 and reconsider the example above, it holds

C(x0,x1)=C(x0,x2)=C(x0,x3)=C(x0,x~)=cfix3.C(
bm{x}_0,
bm{x}_1) = C(
bm{x}_0,
bm{x}_2) = C(
bm{x}_0,
bm{x}_3)
= C(
bm{x}_0,
tilde{
bm{x}})
= c_{fix}
cdot 3.

This means that we can even achieve a turnover distance of TO(x~,x~)=0TO(
tilde{
bm{x}},
tilde{
bm{x}}) = 0
with the same fit value, i.e. costs, as the other three stated solutions with TO(xi,x~)=0.025TO(
bm{x}_{i},
tilde{
bm{x}}) = 0.025
, i=1,2,3i = 1,2,3. Due to the fact that the distance to the ideal portfolio is not part of the objective function, one of the indifferent solutions will be arbitrarily chosen by solvers for the optimisation problem. To tackle this issue directly, we would need to translate the trade-off into a utility function that is directly relating both distances in some way. This utility can then either be used as objective function or is made a part of the constraints.

2.3. A Two-Step Trade Cost Optimisation

As an alternative to the construction of a utility function we can use a two-step approach which saves us the formalisation of the trade-off in terms of utility. The basic idea behind it is:

  1. Use a trading threshold to determine the need for rebalancing.
  2. Use a first trade cost optimisation to find the costs that need to be spent in order to get close enough to the target portfolio.
  3. Use another trade cost optimisation to spend the determined costs as efficient as possible.

As trading threshold, we use the relative tracking error

TErel(x0,x~)>ϕ.TE_{rel}(
bm{x}_0,
tilde{
bm{x}}) >
phi.

Then we apply our standard trade cost optimisation to find

x^=argminxC(x0,x)s.t.TO(x,x~)γ,
hat{
bm{x}} =
arg
min
limits_{
bm{x}} C(
bm{x}_0,
bm{x})

qquad
text{s.t.}
qquad
TO(
bm{x},
tilde{
bm{x}})
leq
gamma,

determining our trade count limit ψ=TC1(x0,x^)
psi = TC_{1}(
bm{x}_0,
hat{
bm{x}})
. The final weight vector, x
bm{x}
, is then obtained by solving the optimisation problem

minxTErel(x,x~)s.t.TC1(x0,x)ψ.
min
limits_{
bm{x}} TE_{rel}(
bm{x},
tilde{
bm{x}})

qquad
text{s.t.}
qquad
TC_{1}(
bm{x}_0,
bm{x})
leq
psi.

The two-step approach can be summarised as follows: The first optimisation is used to determine an optimal trade count budget and the second optimisation tries to optimally use those trades in order to minimise the tracking-error distance to the target portfolio. Indifferences are also possible in the second step but of a different kind, i.e., there might now be a solution with the same distance to the target as the optimal solution, but with lower costs. There is, however, never the situation that a smaller distance could be achievable with same costs as the optimal solution. If the budget is chosen with care, e.g., by restricting the number of trades to a low number, this indifference might be less severe. In our case the budget is not fixed over time, but determined by the first-step trade cost optimisation.

3. Applications: The Cost-Efficient Implementation of a Relative Strength Momentum Strategy

Like in our first blog article about trade cost optimisation, we would like to showcase the benefits of the presented trade cost optimisation using a backtest of a systematic portfolio strategy. To allow for direct comparison, we again consider the relative strength momentum strategy (Faber 2010) for a US investor rotating across asset classes using the following ETFs: SHY, TLT, RWR, IWM, IWB, GLD, EFA, EEM, DBC. Our ten-year sample period spans from Jan-2008 to Dec-2018.

TCO II perf
Figure 1: Relative Strength Momentum Strategy with Trade Cost Optimisation

In the first article, we evaluated and compared the effectiveness of the different trade cost optimisation settings by computing ex-post average daily turnover distances to the target portfolio weights. Similarly, we can compute the ex-post relative tracking error distances of the realised portfolio returns after application of trade cost optimisation to the realised portfolio returns of the target strategy. For the studied TOTO-based trade cost optimisation settings, we observe average turnover distances of 5.94% and 9.59% for the two considered parameter settings γ=0.025
gamma = 0.025
, δ=0.1
delta=0.1
and γ=0.05
gamma = 0.05
, δ=0.15
delta=0.15
, respectively. The observed ex-post relative tracking error distances are 9.66% and 14.00%.

In contrast to the TOTO-based trade cost optimisation, we now use relative tracking error as trading trigger as well as in the objective function of the trade cost optimisation. To do so, we need to specify a trading trigger parameter ϕ
phi
and again a turnover parameter γ
gamma
. We consider two settings: γ=0.025
gamma = 0.025
, ϕ=0.1
phi=0.1
and γ=0.05
gamma = 0.05
, ϕ=0.15
phi=0.15
. Moreover, for computation of relative tracking errors within the trade cost optimisation, we need an estimate of the variance-covariance matrix for the asset universe at hand based on past data. For simplicity, we use the sample variance-covariance matrix based on daily data with a moving-window-length of 252 days, i.e. roughly one year of data.

In Figure 1 we present the resulting backtest performance. The first plot corresponds to the TOTO-based trade cost optimisation and the second plot to the TErelTE_{rel}-based one. We clearly see that the TErelTE_{rel}-based trade cost optimisation is capable of producing a performance which is even closer to the ideal strategy performance than for the TOTO-based approach. Note that we use a log-scaled y-axis to make it easier to compare relative performance and differences of relative performance over time.

Table 1 summarises the results. We can see that the ex-post relative tracking error can be substantially reduced with the more sophisticated trade cost optimisation approach, attending a minimum of 5.95% for the parameter setting γ=0.025
gamma = 0.025
, ϕ=0.1
phi=0.1
. At the same time, we also observe that the improved tracking in terms of more similar returns comes at a cost. First, the average daily turnover distances increase, meaning that investors looking at the portfolio weights see larger differences to the target weights than before. However, the dispersion of realised portfolio returns, measured in terms of relative tracking error, becomes smaller. Secondly, the costs of implementation are slightly higher than for the TOTO-based trade cost optimisation, but still very low with an average number of 40 and 66 trades per year for the two different parameter settings.

Parameters & metrics No trade cost optimisation TO
bm{TO}
-based: Setting 1
TO
bm{TO}
-based: Setting 2
TErel
bm{TE_{rel}}
-based: Setting 1
TErel
bm{TE_{rel}}
-based: Setting 2

(γ,δ)(
gamma,
delta)

(0,0)(0, 0)

(0.025,0.1)(0.025, 0.1)

(0.05,0.15)(0.05, 0.15)

-

-

(γ,ϕ)(
gamma,
phi)

-

-

-

(0.025,0.1)(0.025, 0.1)

(0.05,0.15)(0.05, 0.15)

Ex-post TErel(x,x~)TE_{rel}(
bm{x},
tilde{
bm{x}})
in %

0.00

9.66

14.00

5.95

8.50

Average TO(x,x~)TO(
bm{x},
tilde{
bm{x}})
in %

0.00

5.94

9.59

7.03

10.87

Annualised turnover

1.96

0.93

0.75

1.25

1.08

Annualised trade count

1422.25

40.33

23.67

66.00

39.42

Table 1: Relative Strength Momentum Strategy with Trade Cost Optimisation

It is also worth mentioning that the tuning parameters of both trade cost optimisation approaches allow investors and managers to specify the optimisation according to their individual utility functions. This means that these trade cost optimisations can, for example, be adjusted to reflect individual cost structures and / or preferences with regards to the distance to the target portfolio of investors and portfolio managers.

4. A Tracking-Error-Based Trade Cost Optimisation

As in the first article about trade cost optimisations, we now discuss the technical details and mathematical derivations. Readers not interested in those technical details are encouraged to directly jump to the concluding remarks.

Section 4 is organised as follows. We will first translate the tracking-error-based trade cost optimisation into a standard mixed integer quadratic program (MIQP) with linear (in-)equality constraints in Section 4.1. In Section 4.2 we present the cutting plane algorithm, which allows us to solve quadratic programs by iteratively solving linear programs. A main step of the cutting plane algorithm is a Taylor series approximation of a quadratic constraint. This step is explained in detail in Section 4.3.

4.1. The Tracking-Error-Based Trade Cost Optimisation as Mixed Integer Quadratic Program (MIQP)

If we measure the distance to the target portfolio with relative tracking error, we intend to solve the optimisation problem

minxTErel(x,x~)s.t.C(x0,x)θ,
min
limits_{
bm{x}} TE_{rel}(
bm{x},
tilde{
bm{x}})

qquad
text{s.t.}
qquad
C(
bm{x}_0,
bm{x})
leq
theta,

with TErel(x,x~)=((xx~)Σ(xx~)x~Σx~)12TE_{rel}(
bm{x},
tilde{
bm{x}}) =
left(
frac{(
bm{x} -
tilde{
bm{x}})'
bm{
Sigma} (
bm{x} -
tilde{
bm{x}})}{
tilde{
bm{x}}'
bm{
Sigma}
tilde{
bm{x}}}
right)^{
frac{1}{2}}
.

We can apply the same augmentation technique, as presented in our first blog article about trade cost optimisation, to linearise all constraints. Our optimisation problem is then formulated as a function of the ((5n1)×1)((5
cdot n - 1)
times 1)
vector y:=(x+,x,x~+,x~,z)
bm{y} {:=} ({
bm{x}^+}', {
bm{x}^-}', {
tilde{
bm{x}}^+}', {
tilde{
bm{x}}^-}',
bm{z}')'
and the relations

x=x0+x+xandx=x~+x~+x~
bm{x} =
bm{x}_0 +
bm{x}^+ -
bm{x}^-

qquad
text{and}
qquad

bm{x} =
tilde{
bm{x}} +
tilde{
bm{x}}^+ -
tilde{
bm{x}}^-

are enforced via linear equality constraints. We set αTE=1x~Σx~
alpha_{TE} =
frac{1}{
tilde{
bm{x}}'
bm{
Sigma}
tilde{
bm{x}}}
and note that this constant does not depend on x
bm{x}
but only on x~
tilde{
bm{x}}
, which is a fixed portfolio and not adapted during the optimisation. Further note, that the relative tracking-error is non-negative, so we can apply the strictly monotonic transformation f:R0+R0+,xx2f:
mathbb{R}_{0}^{+}
rightarrow
mathbb{R}_{0}^{+}, x
mapsto x^2
to our objective function and still obtain the same optimal results. The objective function becomes

TErel(x,x~)2=αTE(xx~)Σ(xx~)=αTE(x~+x~)Σ(x~+x~),
begin{aligned}
TE_{rel}(
bm{x},
tilde{
bm{x}})^2
&=
alpha_{TE} (
bm{x} -
tilde{
bm{x}})'
bm{
Sigma} (
bm{x} -
tilde{
bm{x}})


&=
alpha_{TE} (
tilde{
bm{x}}^+ -
tilde{
bm{x}}^-)'
bm{
Sigma} (
tilde{
bm{x}}^+ -
tilde{
bm{x}}^-),

end{aligned}

i.e., after augmentation the objective function is a quadratic form in y
bm{y}
and the optimisation problem becomes a mixed integer quadratic program (MIQP). Solvers for such mixed integer quadratic programs (MIQPs) are not necessarily part of standard software packages for numerical optimisation. Therefore, we now discuss the cutting plane algorithm that can be utilised to solve mixed integer quadratic programs (MIQPs) sequentially with solvers for mixed integer linear programs (MILPs).

4.2. The Cutting Plane Algorithm

The basic idea of the cutting plane algorithm, going back to Kelley (1960), is to solve a convex optimisation problem by sequentially solving linear problems and iteratively adding linear constraints which ensure that we finally solve the convex problem1. In our case, this means that we solve a MIQP by sequentially solving several MILPs and iteratively adding linear constraints which ensure that at the end we solve the MIQP.

For simplicity we skip the integer constraints for a moment and illustrate the functioning of the cutting plane algorithm with a standard quadratic program. Quite generally, we want to solve the quadratic program

minxxQx+fxs.t.Axb,
min
limits_{
bm{x}}
bm{x}'
bm{Q}
bm{x} +
bm{f}'
bm{x}
qquad

text{s.t.}
qquad
bm{A}
bm{x}
leq
bm{b},

with linear inequality constraint. In a first step, the cutting plane algorithm transforms the problem, using a slack variable sR+s
in
mathbb{R}^+
, into

minx,sfx+ss.t.Axb,xQxs,s0,
min
limits_{
bm{x}, s}
bm{f}'
bm{x} + s
qquad

text{s.t.}
qquad

bm{A}
bm{x}
leq
bm{b},

quad
bm{x}'
bm{Q}
bm{x}
leq s,

quad s
geq 0,

which is a linear program with quadratic constraint. Solvers for linear programs usually come without an implementation of quadratic constraints. The idea of the cutting-plane algorithm now consists of locally approximating the convex constraint (in our case the quadratic constraint xQxs
quad
bm{x}'
bm{Q}
bm{x}
leq s
) using a first-order Taylor series expansion. In the following Section 4.3, we provide more details and explain how the Taylor series approximation of the quadratic constraint works. The Taylor series approximation basically results in adding a linear constraint in every iteration. This procedure, i.e., adding another linear constraint and solving the linear program

minx,sfx+ss.t.A~xb~,s0,
min
limits_{
bm{x}, s}
bm{f}'
bm{x} + s
qquad

text{s.t.}
qquad

tilde{
bm{A}}
bm{x}
leq
tilde{
bm{b}},

quad s
geq 0,

with an ever growing set of linear constraints (A~
tilde{
bm{A}}
and b~
tilde{
bm{b}}
are growing in every iteration) is repeated until the slack variable ss is close enough (e.g., measured by an absolute and relative tolerance) to the true quadratic value xQx
bm{x}'
bm{Q}
bm{x}
.

To better understand the functioning of the cutting plane algorithm, we want to provide a graphical illustration of the cutting plane algorithm for the trivial one-dimensional quadratic problem

minx[0,1]ax2+bx.
min
limits_{x
in [0,1]} a x^2 + b x.

Plots for the cases a=0.5a=0.5, b=0.6b=-0.6 and a=0.5a=0.5, b=0.3b=-0.3 are shown in Figure 2 on the left and right, respectively.

TCO II cutting plane light merged
Figure 2: Cutting Plane Algorithm

In the three-dimensional plots in Figure 2, the values of the variables xx and the slack variable ss are shown on the horizontal axes and the vertical axis represents function values depending on (x,s)(x, s). Note that the plots are flipped upside down. This makes it easier to visualise the iterations of the cutting plane algorithm that is approaching from below (in the flipped plot from above) towards the optimal value at the intersection of the surfaces. Due to the flipped vertical axis the highest values are at the bottom and the lowest values at the top.

Two different surfaces are shown in the plots: The lighter surface is the quadratic objective function of the original optimisation problem

f(x,s)=ax2+bxf(x,s) = a x^2 + b x

and the darker meshed plane surface represents the linear objective function of the cutting plane optimisation problem

g(x,s)=as+bx.g(x,s) = a s + b x.

At the intersection of both surfaces, the slack variable ss is equal to the true quadratic value, i.e., s=x2s=x^2. The cutting plane algorithm now operates on the meshed linear plane. The solution of the optimisation problem is the lowest point on the plane within the linear constraints (represented by grey tangential lines), which force the solver towards the intersection of the two surfaces. This can be nicely seen when looking at the red dots indicating the iterations of the cutting plane algorithm. At the intersection, the slack variable is equal to the true quadratic value and therefore the solution on the linear plane surface is also the solution of the quadratic problem, i.e., the lowest point on the parabolic surface. While the graphical illustration helps to understand the general functioning of the cutting plane algorithm, it is obvious that already in the two-dimensional case, and even more in the general nn-dimensional case, it is almost impossible to visualise the functioning of the cutting plane algorithm. Nevertheless, we hope that the three-dimensional visualisation of an exemplary one-dimensional problem allows our readers to roughly imagine the functioning in the nn-dimensional case.

4.3. The Taylor Series Approximation of the Quadratic Constraint

The quadratic constraint xQxs
bm{x}'
bm{Q}
bm{x}
leq s
is in every iteration linearised by applying a first-order Taylor series expansion. Let x=x0+δ
bm{x} =
bm{x}_0 +
bm{
delta}
, then the first-order Taylor series expansion at x0
bm{x}_0
is given by

xQxs=x0Qx0+2x0Qδs+O(δ2).
bm{x}'
bm{Q}
bm{x} - s
=
bm{x}_0'
bm{Q}
bm{x}_0 + 2
bm{x}_0'
bm{Q}
bm{
delta} - s
+
mathcal{O}(|
bm{
delta}|^2).

Choose δ=xx0
bm{
delta} =
bm{x} -
bm{x}_0
to obtain

xQxs=x0Qx0+2x0Qxs+O(xx02).
bm{x}'
bm{Q}
bm{x} - s
= -
bm{x}_0'
bm{Q}
bm{x}_0 + 2
bm{x}_0'
bm{Q}
bm{x} - s
+
mathcal{O}(|
bm{x} -
bm{x}_0|^2).

Therefore, in each iteration we add the linear inequality constraint

x0Qx0+2x0Qxs0,-
bm{x}_0'
bm{Q}
bm{x}_0 + 2
bm{x}_0'
bm{Q}
bm{x} - s
leq 0,

where x0Qx0-
bm{x}_0'
bm{Q}
bm{x}_0
is just a constant, so we get

(2x0Q1)(xs)x0Qx0.
left(
begin{matrix}
2
bm{x}_0'
bm{Q} & -1

end{matrix}
right)

left(
begin{matrix}

bm{x}


s

end{matrix}
right)

leq
bm{x}_0'
bm{Q}
bm{x}_0.

For x0
bm{x}_0
we always use the solution of the optimisation in the previous iteration.

5. Concluding Remarks

In this blog article, we discussed different measures for the distance of two portfolios. In particular, we provided a comparison of turnover and relative tracking error. We showed why relative tracking error might be deemed superior when measuring the distance to an ideal target portfolio.

Moreover, we developed a tracking-error-based trade cost optimisation and derived an augmented formulation in terms of a classical mixed integer quadratic program (MIQP). To allow a straightforward implementation, we explained how the cutting plane algorithm can be utilised to solve a quadratic program by iteratively solving several linear programs. The benefits of the tracking-error-based trade cost optimisation were shown with backtest results for a momentum portfolio strategy.

References


Drori, Y. and Teboulle, M. (2016), An optimal variant of Kelley’s cutting-plane method, Mathematical Programming, 160 (1-2), pp. 321-351.


Faber, M. (2010), Relative Strength Strategies for Investing, Available at SSRN: http://dx.doi.org/10.2139/ssrn.1585517.


Kelley, Jr. J. E. (1960), The cutting-plane method for solving convex programs, Journal of the Society for Industrial & Applied Mathematics, 8(4), pp. 703-712.


1: Note that there are several extensions and improved versions of Kelley’s (1960) cutting-plane algorithm (see for example Drori and Teboulle (2016)).

Disclaimer – The views and opinions expressed in this blog are those of the author and do not necessarily reflect the views of Scalable Capital GmbH, its subsidiaries or its employees ("Scalable Capital", "we"). The content is provided to you solely for informational purposes and does not constitute, and should not be construed as, an offer or a solicitation of an offer, advice or recommendation to purchase any securities or other financial instruments. Any representation is for illustrative purposes only and is not representative of any Scalable Capital product or investment strategy. The academic concepts set forth herein are derived from sources believed by the author and Scalable Capital to be reliable and have no connection with the financial services offered by Scalable Capital. Past performance and forward-looking statements are not reliable indicators of future performance. The return may rise or fall as a result of currency fluctuations. Please refer to our risk information.

Risk Warning – With investment comes risk. The value of your investment can go down as well as up and you may get back less than you invest. Past performance or future projections are not indicative of future performance. We do not provide any investment, legal and/or tax advice. If this website contains information regarding capital markets, financial instruments and/or other topics relevant for investments of assets, the exclusive purpose of this information is to give general guidance on investment management services provided by members of our group. Please note our Risk Warning and the Website Terms.

team-malte-kurz-de
Dr. Malte Kurz
QUANTITATIVE STRATEGIST
Malte works as Quantitative Researcher at Scalable Capital and is a Research Fellow of the Center for Quantitative Risk Analysis at the Ludwig-Maximilians-Universität (LMU) Munich. He studied Mathematical Finance at the University of Konstanz and Statistics at the LMU. He previously worked as a research and teaching assistant at the Chair of Financial Econometrics (LMU). In his PhD thesis he developed and analyzed methods for high-dimensional dependence modelling with applications in financial econometrics. Malte has published peer-reviewed research articles and regularly serves as a referee for academic journals.