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

29 May 2019  | 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:

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

and turnover

$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 
bm{x}_0 = (
frac{1}{3},
frac{1}{3},
frac{1}{3})'
and consider three different target portfolios


tilde{
bm{x}}_1 =
left(
begin{matrix}0

0.5

0.5
end{matrix}
right),

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

0

0.5
end{matrix}
right),

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

0.5

0
end{matrix}
right).

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

$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 
bm{x}
by $r_{$
bm{x}}
, we obtain the following sample volatilities (standard deviations) for daily percentage return differences:


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.,


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 
text{Cov}(
bm{r}) =
bm{
Sigma}
and 
bm{r}
denoting the vector of asset returns. Therefore, a definition of tracking error $TE($
cdot,
cdot)
as distance between two portfolios in terms of weight vectors is given by

$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 
tilde{
bm{x}}_4 = (0.59, 0, 0.41)
for which $TO($
bm{x}_0,
tilde{
bm{x}}_4) = 0.3333
and 
hat{
sigma}(r_{
bm{x}_{0}} - r_{
tilde{
bm{x}}_{4}}) = 0.5413
. So it has equal turnover distance compared to the one between 
bm{x}_0
and 
tilde{
bm{x}}_3
and almost equal tracking error distance. However, the target portfolios have empirical volatilities of 
hat{
sigma}(r_{
tilde{
bm{x}}_{3}}) = 0.7001
and 
hat{
sigma}(r_{
tilde{
bm{x}}_{4}}) = 0.7840
. Therefore, while the absolute dispersion in terms of tracking error from the current portfolio, 
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 $TE_{rel}($
cdot,
cdot)

$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


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 
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 
bm{x}_0
to 
tilde{
bm{x}}_3
and 
bm{x}_0
to 
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 
bm{x}_0
to 
tilde{
bm{x}}_1
and 
bm{x}_0
to 
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 $TE_{rel}($
bm{x},
tilde{
bm{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


min
limits_{
bm{x}} C(
bm{x}_0,
bm{x})

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

where $C($
bm{x}_0,
bm{x})
are the costs to trade from 
bm{x}_0
to 
bm{x}
and $TO($
bm{x},
tilde{
bm{x}})
is the turnover distance of the post-trade weights, 
bm{x}
, to the ideal weights, 
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 
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 
bm{x}_0 = (0.4, 0.3, 0.3)'
and as target portfolio weight 
tilde{
bm{x}} = (0.5, 0.25, 0.25)'
. For 
gamma = 0.025
optimal solutions of the optimisation problem are


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

0.2500

0.2750
end{matrix}
right),

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

0.2750

0.2500
end{matrix}
right),

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

0.2625

0.2625
end{matrix}
right),

with


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 $c_{var} = 0$ and reconsider the example above, it holds

$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($
tilde{
bm{x}},
tilde{
bm{x}}) = 0
with the same fit value, i.e. costs, as the other three stated solutions with $TO($
bm{x}_{i},
tilde{
bm{x}}) = 0.025
, $i = 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

$TE_{rel}($
bm{x}_0,
tilde{
bm{x}}) >
phi.

Then we apply our standard trade cost optimisation to find


hat{
bm{x}} =
arg
min
limits_{
bm{x}} C(
bm{x}_0,
bm{x})

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

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


min
limits_{
bm{x}} TE_{rel}(
bm{x},
tilde{
bm{x}})

text{s.t.}
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. ###### 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 $TO$-based trade cost optimisation settings, we observe average turnover distances of 5.94% and 9.59% for the two considered parameter settings 
gamma = 0.025
, 
delta=0.1
and 
gamma = 0.05
, 
delta=0.15
, respectively. The observed ex-post relative tracking error distances are 9.66% and 14.00%.

In contrast to the $TO$-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: 
gamma = 0.025
, 
phi=0.1
and 
gamma = 0.05
, 
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 $TO$-based trade cost optimisation and the second plot to the $TE_{rel}$-based one. We clearly see that the $TE_{rel}$-based trade cost optimisation is capable of producing a performance which is even closer to the ideal strategy performance than for the $TO$-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 
gamma = 0.025
, 
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 $TO$-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


bm{TO}
-based: Setting 1


bm{TO}
-based: Setting 2


bm{TE_{rel}}
-based: Setting 1


bm{TE_{rel}}
-based: Setting 2

$($
gamma,
delta)

$(0, 0)$

$(0.025, 0.1)$

$(0.05, 0.15)$

$($
gamma,
phi)

$(0.025, 0.1)$

$(0.05, 0.15)$

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

0.00

9.66

14.00

5.95

8.50

Average $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

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


min
limits_{
bm{x}} TE_{rel}(
bm{x},
tilde{
bm{x}})

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

with $TE_{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 $((5$
cdot n - 1)
times 1)
vector 
bm{y} {:=} ({
bm{x}^+}', {
bm{x}^-}', {
tilde{
bm{x}}^+}', {
tilde{
bm{x}}^-}',
bm{z}')'
and the relations


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

text{and}

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

are enforced via linear equality constraints. We set 
alpha_{TE} =
frac{1}{
tilde{
bm{x}}'
bm{
Sigma}
tilde{
bm{x}}}
and note that this constant does not depend on 
bm{x}
but only on 
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:$
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


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 
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


min
limits_{
bm{x}}
bm{x}'
bm{Q}
bm{x} +
bm{f}'
bm{x}

text{s.t.}
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 $s$
in
mathbb{R}^+
, into


min
limits_{
bm{x}, s}
bm{f}'
bm{x} + s

text{s.t.}

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

bm{x}'
bm{Q}
bm{x}
leq 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 
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


min
limits_{
bm{x}, s}
bm{f}'
bm{x} + s

text{s.t.}

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

geq 0,

with an ever growing set of linear constraints (
tilde{
bm{A}}
and 
tilde{
bm{b}}
are growing in every iteration) is repeated until the slack variable $s$ is close enough (e.g., measured by an absolute and relative tolerance) to the true quadratic value 
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


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

Plots for the cases $a=0.5$, $b=-0.6$ and $a=0.5$, $b=-0.3$ are shown in Figure 2 on the left and right, respectively. ###### Figure 2: Cutting Plane Algorithm

In the three-dimensional plots in Figure 2, the values of the variables $x$ and the slack variable $s$ are shown on the horizontal axes and the vertical axis represents function values depending on $(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) = 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) = a s + b x.$

At the intersection of both surfaces, the slack variable $s$ is equal to the true quadratic value, i.e., $s=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 $n$-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 $n$-dimensional case.

### 4.3. The Taylor Series Approximation of the Quadratic Constraint

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


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 
bm{
delta} =
bm{x} -
bm{x}_0
to obtain


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

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

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


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 
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.

Risikohinweis – Die Kapitalanlage ist mit Risiken verbunden und kann zum Verlust des eingesetzten Vermögens führen. Weder vergangene Wertentwicklungen noch Prognosen haben eine verlässliche Aussagekraft über zukünftige Wertentwicklungen. Wir erbringen keine Anlage-, Rechts- und/oder Steuerberatung. Sollte diese Website Informationen über den Kapitalmarkt, Finanzinstrumente und/oder sonstige für die Kapitalanlage relevante Themen enthalten, so dienen diese Informationen ausschließlich der allgemeinen Erläuterung der von Unternehmen unserer Unternehmensgruppe erbrachten Wertpapierdienstleistungen. Bitte lesen Sie auch unsere Risikohinweise und Nutzungsbedingungen. 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.