• Introduction

• Sparse Index Tracking

  • Problem formulation
  • Interlude: Majorization-Minimization (MM) algorithm
  • Resolution via MM

• Holding Constraints and Extensions

  • Problem formulation
  • Holding constraints via MM
  • Extensions

• Numerical Experiments

• Conclusions

Fund managers follow two basic investment strategies:

• Index tracking or benchmark replication is a strategy investment aimed at mimicking the risk/return profile of a financial instrument.

• For practical reasons, the strategy focuses on a reduced basket of representative assets.

• The problem is also regarded as portfolio compression and it is intimately related to compressed sensing and \(\ell_{1}\)-norm minimization techniques (Benidis et al. 2018a), (Benidis et al. 2018b).

• One example is the replication of an index, e.g., Hang Seng Index, based on a reduced basket of assets.

• Price and return of an asset or an index: \(p_{t}\) and \(r_{t}=\frac{p_{t}-p_{t-1}}{p_{t-1}}\)
• Returns of an index in \(T\) days: \(\boldsymbol{\mathbf{r}}^{b}=[r_{1}^{b},\dots,r_{T}^{b}]^{\top}\in\mathbb{R}^{T}\)
• Returns of \(N\) assets in \(T\) days: \(\mathbf{X}=[\mathbf{r}_{1},\dots,\mathbf{r}_{T}]^{\top}\in\mathbb{R}^{T\times N}\) with \(\mathbf{r}_{t}\in\mathbb{R}^{N}\)
• Assume that an index is composed by a weighted collection of \(N\) assets with normalized index weights \(\mathbf{b}\) satisfying
  • \(\mathbf{b}>\mathbf{0}\)
  • \(\mathbf{b}^{\top}\mathbf{1}=1\)
  • \(\mathbf{X}\mathbf{b}=\mathbf{r}^{b}\)
• We want to design a (sparse) tracking portfolio \(\mathbf{w}\) satisfying
  • \(\mathbf{w}\geq\mathbf{0}\)
  • \(\mathbf{w}^{\top}\mathbf{1}=1\)
  • \(\mathbf{X}\mathbf{w}\approx\mathbf{r}^{b}\)

• How should we select \(\mathbf{w}\)?

• Straightforward solution: full replication \(\mathbf{w}=\mathbf{b}\)
  • Buy appropriate quantities of all the assets
  • Perfect tracking

• But it has drawbacks:
  • We may be trying to hedge some given portfolio with just a few names (to simplify the operations)
  • We may want to deal properly with illiquid assets in the universe
  • We may want to control the transaction costs for small portfolios (AUM)

• How can we overcome these drawbacks?

  👉 Sparse index tracking.

• Use a small number of assets: \(\mathsf{card}(\mathbf{w})<N\)
  • can allow hedging with just a few names
  • can avoid illiquid assets
  • can reduce transaction costs for small portfolios

• Challenges:
  • Which assets should we select?
  • What should their relative weight be?

Sparse regression: \[\begin{array}{ll} \underset{\mathbf{w}}{\mathsf{minimize}} & \left\Vert \mathbf{r}-\mathbf{X}\mathbf{w}\right\Vert _{2}+\lambda\left\Vert \mathbf{w}\right\Vert _{0} \end{array}\] tries to fit the observations by minimizing the error with a sparse solution:

• Recall that \(\mathbf{b}\in\mathbb{R}^{N}\) represents the actual benchmark weight vector and \(\mathbf{w}\in\mathbb{R}^{N}\) denotes the replicating portfolio.

• Investment managers seek to minimize the following tracking error (TE) performance measure: \[\textsf{TE}\left(\mathbf{w}\right) =\left(\mathbf{w}-\mathbf{b}\right)^{T}\boldsymbol{\Sigma}\left(\mathbf{w}-\mathbf{b}\right)\] where \(\boldsymbol{\Sigma}\) is the covariance matrix of the index returns.

• In practice, however, the benchmark weight vector \(\mathbf{b}\) may be unknown and the error measure is defined in terms of market observations.

• A common tracking measure is the empirical tracking error (ETE): \[\textsf{ETE}(\mathbf{w})=\frac{1}{T}\big\|\mathbf{X}\mathbf{w}-\mathbf{r}^{b}\big\|^2_{2}\]

• Problem formulation for sparse index tracking (Maringer and Oyewumi 2007): \[ \begin{array}{ll} \underset{\mathbf{w}}{\textsf{minimize}} & \frac{1}{T}\big\|\mathbf{X}\mathbf{w}-\mathbf{r}^{b}\big\|_{2}^{2}+\lambda\|\mathbf{w}\|_{0}\\ \textsf{subject to} & \mathbf{w}\in\mathcal{W} \end{array} \]
  • \(\|\mathbf{w}\|_{0}\) is the \(\ell_{0}\)-“norm” and denotes \(\mathsf{card}(\mathbf{w})\)
  • \(\mathcal{W}\) is a set of convex constraints (e.g., \(\mathcal{W}=\{\mathbf{w}|\mathbf{w}\geq\mathbf{0},\mathbf{w}^{\top}\mathbf{1}=1\}\))
  • we will treat any nonconvex constraint separately

• This problem is too difficult to deal with directly:

  👉 Discontinuous, non-differentiable, non-convex objective function.

• Two-step approach:
  1. stock selection:
     • largest market capital
     • most correlated to the index
     • a combination cointegrated well with the index
  2. capital allocation:
     • naive allocation: proportional to the original weights
     • optimized allocation: usually a convex problem
• Mixed Integer Programming (MIP)
  • practical only for small dimensions, e.g. \(\binom{100}{20}>10^{20}\).
• Genetic algorithms
  • solve the MIP problems in reasonable time
  • worse performance, cannot prove optimality.

• Consider the following presumably difficult optimization problem: \[\begin{array}{ll} \underset{{\mathbf x}}{\textsf{minimize}} & f\left({\bf x}\right)\\ \textsf{subject to} & {\bf x}\in\mathcal{X}, \end{array}\] with \(\mathcal{X}\) being the feasible set and \(f\left({\bf x}\right)\) being continuous.

• Idea: successively minimize a more managable surrogate function \(u\left({\bf x},{\bf x}^{(k)}\right)\): \[{\bf x}^{(k+1)}=\arg\min_{{\bf x}\in\mathcal{X}}u\left({\bf x},{\bf x}^{(k)}\right),\] hoping the sequence of minimizers \(\left\{ {\bf x}^{(k)}\right\}\) will converge to optimal \({\bf x}^{\star}\).

• Question: how to construct \(u\left({\bf x},{\bf x}^{(k)}\right)\)?

• Answer: that’s more like an art (Sun et al. 2017).

Algorithm MM

Set \(k=0\) and initialize with a feasible point \({\bf x}^0\in \mathcal X\).
repeat

• \({\bf x}^{(k+1)}=\arg\min_{{\bf x}\in {\mathcal X}} u\left({\bf x},{\bf x}^{(k)}\right)\)

• \(k \gets k+1\)

until convergence
return \(\mathbf{x}^{(k)}\)

• Under some technical assumptions, every limit point of the sequence \(\left\{ {\bf x}^{k}\right\}\) is a stationary point of the original problem.

• If further assume that the level set \(\mathcal{X}^{0}=\left\{ {\bf x}|f\left({\bf x}\right)\leq f\left({\bf x}^{0}\right)\right\}\) is compact, then \[\lim_{k\to\infty}d\left({\bf x}^{(k)},\mathcal{X}^{\star}\right)=0,\] where \(\mathcal{X}^{\star}\) is the set of stationary points.

• Good approximation in the interval \([-\gamma,\gamma]\).
  
• Concave for \(w\ge0\).
• So-called folded-concave for \(w\in\mathbb{R}\).
• For our problem we set \(\gamma=u\), where \(u\leq1\) is an upperbound of the weights (we can always choose \(u=1\)).

• Continuous and differentiable approximate formulation: \[ \begin{array}{ll} \underset{\mathbf{w}}{\textsf{minimize}} & \frac{1}{T}\big\|\mathbf{X}\mathbf{w}-\mathbf{r}^{b}\big\|_{2}^{2}+\lambda\mathbf{1}^{\top}\mathbf{\boldsymbol{\rho}}{}_{p,u}(\mathbf{w})\\ \textsf{subject to} & \mathbf{w}\in\mathcal{W} \end{array} \] where \(\boldsymbol{\rho}_{p,u}(\mathbf{w})=[\rho_{p,u}(w_{1}),\dots,\rho_{p,u}(w_{N})]^{\top}\).

• This problem is still non-convex: \(\boldsymbol{\rho}_{p,u}(\mathbf{w})\) is concave for \(\mathbf{w}\geq\mathbf{0}\).

• We will use MM to deal with the non-convex part.

Lemma 1

The function \(\rho_{p,\gamma}(w)\), with \(w\geq0\), is upperbounded at \(w^{(k)}\) by the surrogate function \[h_{p,\gamma}(w,w^{(k)})=d_{p,\gamma}(w^{(k)})w+c_{p,\gamma}(w^{(k)}),\] where \[\begin{aligned} d_{p,\gamma}(w^{(k)}) &= \frac{1}{\log(1+\gamma/p)(p+w^{(k)})},\\ c_{p,\gamma}(w^{(k)}) &= \frac{\log\left(1+w^{(k)}/p\right)}{\log(1+\gamma/p)}-\frac{w^{(k)}}{\log(1+\gamma/p)(p+w^{(k)})} \end{aligned}\] are constants.

• The function \(\rho_{p,\gamma}(w)\) is concave for \(w\geq0\).
• An upper bound is its first-order Taylor approximation at any point \(w_{0}\in\mathbb{R}_{+}\). \[\begin{aligned} \rho_{p,\gamma}(w) &= \frac{\log(1+w/p)}{\log(1+\gamma/p)}\\ & \leq \frac{1}{\log(1+\gamma/p)}\left[\log\left(1+w_{0}/p\right)+\frac{1}{p+w_{0}}(w-w_{0})\right] \\ & = \color{red}{\underbrace{\color{black}{\frac{1}{\log(1+\gamma/p)(p+w_{0})}}}_{d_{p,\gamma}}}\color{black}{w} \\ & \qquad + \color{red}{\underbrace{\color{black}{\frac{\log\left(1+w_{0}/p\right)}{\log(1+\gamma/p)}-\frac{w_0}{\log(1+\gamma/p)(p+w_{0})}}}_{b_{p,\gamma}}} \end{aligned}\]

• Now in every iteration we need to solve the following problem: \[ \begin{array}{ll} \underset{\mathbf{w}}{\textsf{minimize}} & \frac{1}{T}\big\|\mathbf{X}\mathbf{w}-\mathbf{r}^{b}\big\|_{2}^{2}+\lambda{\mathbf{d}_{p,u}^{(k)}}^{\top}\mathbf{w}\\ \textsf{subject to} & \mathbf{w}\in\mathcal{W} \end{array} \] where \(\mathbf{d}_{p,u}^{(k)}=\left[d_{p,u}(w_{1}^{(k)}),\dots,d_{p,u}(w_{N}^{(k)})\right]^{\top}\).

• This problem is convex (actually a QP).

• Requires a solver in each iteration.

Algorithm 1: Linear Approximation for the Index Tracking problem (LAIT)

Set \(k=0\) and choose \(\mathbf{w}^{(0)}\in\mathcal{W}\).

repeat

• Compute \(\mathbf{d}_{p,u}^{(k)}\)

• \({\bf w}^{(k+1)}=\arg\min_{{\bf w}\in\mathcal{W}} \frac{1}{T}\big\|\mathbf{X}\mathbf{w}-\mathbf{r}^{b}\big\|_{2}^{2}+\lambda{\mathbf{d}_{p,u}^{(k)}}^{\top}\mathbf{w}\)

• \(k \gets k+1\)

until convergence
return \(\mathbf{w}^{(k)}\)

• Advantages:

  ✅ The problem is convex.
  ✅ Can be solved efficiently by an off-the-shelf solver.

• Disadvantages:

  ❌ Needs to be solved many times (one for each iteration).
  ❌ Calling a solver many times increases significantly the running time.

• Can we do something better?

  ✅ For specific constraint sets we can derive closed-form update algorithms!

• Expand the objective: \(\frac{1}{T}\big\|\mathbf{X}\mathbf{w}-\mathbf{r}^{b}\big\|_{2}^{2}+\lambda{\mathbf{d}_{p,u}^{(k)}}^{\top}\mathbf{w}=\frac{1}{T}\mathbf{w}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{w}+\left(\lambda\mathbf{d}_{p,u}^{(k)}-\frac{2}{T}\mathbf{X}^{\top}\mathbf{r}^{b}\right)^{\!\!\top}\!\!\mathbf{w}+\mathsf{\mathit{const.}}\)

• Further upper-bound it:

Lemma 2

Let \(\mathbf{L}\) and \(\mathbf{M}\) be real symmetric matrices such that \(\mathbf{M}\succeq\mathbf{L}\). Then, for any point \(\mathbf{w}^{(k)}\in\mathbb{R}^{N}\) the following inequality holds: \[\mathbf{w}^{\top}\mathbf{L}\mathbf{w}\leq\mathbf{w}^{\top}\mathbf{M}\mathbf{w}+2{\mathbf{w}^{(k)}}^{\!\top}\!\!\left(\mathbf{L}-\mathbf{M}\right)\mathbf{w}-{\mathbf{w}^{(k)}}^{\top}\!\!\left(\mathbf{L}-\mathbf{M}\right)\mathbf{w}^{(k)}.\] Equality is achieved when \(\mathbf{w}=\mathbf{w}^{(k)}\).

• Based on Lemma 2:
  • Majorize the quadratic term \(\frac{1}{T}\mathbf{w}^{\top}\mathbf{X}^{\top}\mathbf{X}\mathbf{w}\).
  • In our case \(\mathbf{L}_{1}=\frac{1}{T}\mathbf{X}^{\top}\mathbf{X}\).
  • We set \(\mathbf{M}_{1}=\lambda_{\text{max}}^{(\mathbf{L}_{1})}\mathbf{I}\) so that \(\mathbf{M}_{1}\succeq\mathbf{L}_{1}\) holds.
• The objective becomes: \[ \begin{aligned} & \mathbf{w}^{\top}\mathbf{L}_{1}\mathbf{w}+\left(\lambda{\mathbf{d}_{p,u}^{(k)}}-\frac{2}{T}\mathbf{X}^{\top}\mathbf{r}^{b}\right)^{\top}\!\mathbf{w} \\ & \leq \mathbf{w}^{\top}\mathbf{M}_{1}\mathbf{w}+2{\mathbf{w}^{(k)}}^{\!\top}\!\left(\mathbf{L}_{1}-\mathbf{M}_{1}\right)\mathbf{w}-{{\mathbf{w}^{(k)}}^{\!\top}\!\!\left(\mathbf{L}_{1}-\mathbf{M}_{1}\right)\mathbf{w}^{(k)}} \\ & \qquad +\left(\lambda{\mathbf{d}_{p,u}^{(k)}}-\frac{2}{T}\mathbf{X}^{\top}\mathbf{r}^{b}\right)^{\!\top}\!\mathbf{w} \\ & = \lambda_{\text{max}}^{(\mathbf{L}_{1})}\mathbf{w}^{\top}\mathbf{w}+\!\left(\!2\left(\mathbf{L}_{1}-\lambda_{\text{max}}^{(\mathbf{L}_{1})}\mathbf{I}\right)\mathbf{w}^{(k)}+\lambda{\mathbf{d}_{p,u}^{(k)}}-\frac{2}{T}\mathbf{X}^{\top}\mathbf{r}^{b}\!\right)^{\!\!\top}\mathbf{\!\!w}+const. \end{aligned} \]

The new optimization problem at the \((k+1)\)-th iteration becomes \[ \begin{array}{ll} \underset{\mathbf{w}}{\textsf{minimize}} & \mathbf{w}^{\top}\mathbf{w}+{\mathbf{q}_{1}^{(k)}}^{\top}\mathbf{w}\\ \textsf{subject to} & \begin{array}{l} \mathbf{w}^{\top}\mathbf{1}=1,\\ \mathbf{0}\leq\mathbf{w}\leq\mathbf{1}, \end{array} \biggl\}\mathcal{W} \end{array} \] where \[\mathbf{q}_{1}^{(k)}=\frac{1}{\lambda_{\text{max}}^{(\mathbf{L}_{1})}}\left(2\left(\mathbf{L}_{1}-\lambda_{\text{max}}^{(\mathbf{L}_{1})}\mathbf{I}\right)\mathbf{w}^{(k)}+\lambda{\mathbf{d}_{p,u}^{(k)}}-\frac{2}{T}\mathbf{X}^{\top}\mathbf{r}^{b}\right).\]

• This problem can be solved with a closed-form update algorithm.

Proposition 1

The optimal solution to the previous problem with \(u=1\) is: \[w_{i}^{\star}=\begin{cases} -\frac{\mu+q_{i}}{2},\quad & i\in\mathcal{A},\\ 0,\quad & i\notin\mathcal{A}, \end{cases}\] with \[\mu=-\frac{\sum_{i\in A}q_{i}+2}{\mathit{card}(\mathcal{A})},\] and \[\mathcal{A}=\big\{ i\big|\mu+q_{i}<0\big\},\] where \(\mathcal{A}\) can be determined in \(O(\log(N))\) steps.

Algorithm 2: Specialized Linear Approximation for the Index Tracking problem (SLAIT)

Set \(k=0\) and choose \(\mathbf{w}^{(0)}\in\mathcal{W}\).

repeat

• Compute \(\mathbf{q}_{1}^{(k)}\)

• \({\bf w}^{(k+1)}=\arg\min_{{\bf w}\in\mathcal{W}} \mathbf{w}^{\top}\mathbf{w}+{\mathbf{q}_{1}^{(k)}}^{\top}\mathbf{w}\)

• \(k \gets k+1\)

until convergence
return \(\mathbf{w}^{(k)}\)