8 Case studies

8.1 Introduction

This chapter discusses a number of case studies and examples with details that are beyond the general character of the previous chapters.

8.2 A resource constrained production and inventory problem

The resource constrained production and inventory problem [Zie82] can be formulated as follows:

(1)\[\begin{split}\begin{array}{lll} \mbox{minimize} & \sum_{j=1}^n (d_j x_j + e_j/x_j) & \\ \mbox{subject to} & \sum_{j=1}^n r_j x_j \leq b, &\\ & x_j \geq 0, & j=1,\dots,n, \end{array}\end{split}\]

where \(n\) denotes the number of items to be produced, \(b\) denotes the amount of common resource, and \(r_j\) is the consumption of the limited resource to produce one unit of item \(j\). The objective function represents production and inventory costs. Let \(c_j^p\) denote the cost per unit of product \(j\) and \(c_j^i\) denote the rate of of holding costs, respectively. Further, let

\[d_j = \frac{c_j^p c_j^r}{2}\]

so that

\[d_j x_j\]

is the average holding costs for product \(j\). If \(D_j\) denotes the total demand or product \(j\) and \(c_j^o\) the ordering cost per order of product j then let

\[e_j = c_j^o D_j\]

and hence

\[\frac{e_j}{x_j} = \frac{c_j^o D_j}{x_j}\]

is the average ordering costs for product \(j\). It is not always possible to produce a fractional number of items. In such cases a constraint saying \(x_j\) has to be integer valued should be added. In summary, the problem finds the optimal batch size such that the inventory and ordering cost are minimized while satisfying the constraints on the common resource. Given \(d_j, e_j \geq 0\) problem (1) is equivalent to the conic quadratic problem

\[\begin{split}\begin{array}{lll} \mbox{minimize} & \sum_{j=1}^n (d_j x_j + e_j t_j) \\ \mbox{subject to} & \sum_{j=1}^n r_j x_j \leq b,\\ & (t_j, x_j, \sqrt{2}) \in \mathcal{Q}_r^3, & j=1,\dots,n,\\ & x_j \geq 0, & j=1,\dots,n. \\ \end{array}\end{split}\]

8.3 Maximum likelihood estimator of a convex density function

In [TV98] the problem of estimating a density function that is know in advance to be convex is considered. Here we will show that problem can be posed as a conic quadratic optimization problem.

Formally the problem is to estimate an unknown convex density function

\[g : \R_+ \rightarrow \R_+.\]

Let \(Y\) be the real-valued random variable with density function \(g\) and let \({y_1, . . . , y_n}\) be an ordered sample of n outcomes of \(Y\) where it is assumed \(y_1 < y_2 < \ldots < y_n\). The estimator of \(\tilde g \geq 0\) is a piecewise linear function

\[\tilde g : [y_1, y_n] \rightarrow \R_+\]

with break points at

\[(y_i, \tilde g(yi)),\, i = 1, \ldots , n.\]

The variables are

\[x_i > 0, i = 1, \ldots , n,\]

which \(x_i\) is an estimator of \(g(y_i)\). The slope for \(i\)‘h segment of the density function is given by

\[\frac{x_{i+1}-x_i}{y_{i+1}-y_i}.\]

Hence the convexity requirement leads to the constraints

\[\frac{x_{i+1}-x_i}{y_{i+1}-y_i} \leq \frac{x_{i+2}-x_{i+1}}{y_{i+2}-y_{i+1}}, \, i=1,\ldots,n-2.\]

Recall the area under the density function must be 1. Hence,

\[\sum_{i=1}^{n-1} (y_{i+1}-y_i)\left ( \frac{x_{i+1}+x_i}{2} \right ) = 1\]

must hold. Therefore, the problem to be solved is

\[\begin{split}\begin{array}{lccll} \maximize & \prod_{i=1}^n x_i & \\ \st & \frac{x_{i+1}-x_i}{y_{i+1}-y_i} - \frac{x_{i+2}-x_{i+1}}{y_{i+2}-y_{i+1}} & \leq & 0 & i=1,\ldots,n-2, \\ & \sum_{i=1}^{n-1} (y_{i+1}-y_i)\left ( \frac{x_{i+1}+x_i}{2} \right ) & = & 1, \\ & x\geq 0. & \\ \end{array}\end{split}\]

Maximizing

\[\prod_{i=1}^n x_i\]

or

\[(\prod_{i=1}^n x_i)^\frac{1}{n}\]

will produce identical optimums. Using that observation we reach the problem

(2)\[\begin{split} \begin{array}{lccll} \maximize & t & \\ \st & \left (\prod_{i=1}^n x_i \right )^\frac{1}{n}-t & \geq & 0, \\ & - \Delta y_{i+1} x_i & \\ & + (\Delta y_i+\Delta y_{i+1}) x_{i+1} & \\ & - \Delta y_i x_{i+2} & \leq & 0 & i=1,\ldots,n-2, \\ & \sum_{i=1}^{n-1} \Delta y_i\left ( \frac{x_{i+1}+x_i}{2} \right ) & = & 1, \\ & x,t\geq 0 & \\ \end{array}\end{split}\]

where

\[\Delta y_i = y_{i+1} - y_i.\]

The first constraint in problem (2) is the geometric mean cone. Furthermore, in Sec. 3.2.7 (Geometric mean) we showed how to model the geometric mean cone using conic quadratic constraints, so the problem (2) is conic quadratic representable.

8.4 Markowitz portfolio optimization

8.4.1 Basic notions

Recall from Sec. 3.3.3 (Markowitz portfolio optimization) that the standard Markowitz portfolio optimization problem is

(3)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x\\ \mbox{subject to} & x^T \Sigma x \leq \gamma\\ & e^T x = 1\\ & x \geq 0, \end{array}\end{split}\]

where \(\mu\in \R^n\) is a vector of expected returns for \(n\) different assets and \(\Sigma \in \mathcal{S}_+^n\) denotes the corresponding covariance matrix.

Problem (3) maximizes the expected return of investment given a budget constraint and an upper bound \(\gamma\) on the allowed risk. Alternatively, we can minimize the risk given a lower bound \(\delta\) on the expected return of investment, i.e., we can solve a problem

(4)\[\begin{split}\begin{array}{ll} \mbox{minimize} & x^T \Sigma x\\ \mbox{subject to} & \mu^T x \geq \delta\\ & e^T x = 1\\ & x \geq 0. \end{array}\end{split}\]

Both problems (3) and (4) are equivalent in the sense that they describe the same Pareto-optimal trade-off curve by varying \(\delta\) and \(\gamma\). In fact, given a solution to either problem, we can easily find the parameters for the other problem, which results in the same solution. The optimality conditions for (4) are

(5)\[2\Sigma x = \nu \mu + \lambda e + z, \quad \nu(\mu^T x - \delta) = 0, \quad e^Tx = 1, \quad x,z,\nu\geq 0, \quad x^T z = 0,\]

where \(\nu\in \R_+\), \(\lambda\in\R\), \(z\in \R^n_+\) are dual variables, and the optimality conditions for (3) are

(6)\[2\alpha \Sigma x = \mu + \zeta e + v, \quad \alpha(x^T \Sigma x - \gamma) = 0, \quad e^Tx = 1, \quad \alpha, v\geq 0, \quad x^T v = 0,\]

where \(\alpha\in\R_+\), \(\zeta\in\R\), \(v\in \R^n_+\) are dual variables. Furthermore, from (5) we see that

\[x^T \Sigma x = (1/2)(\nu \mu^T x + \lambda e^T x) = (1/2)(\nu \delta + \lambda).\]

Thus, given a solution \((x^\star, \nu^\star, \lambda^\star, z^\star)\) to (5), we see that for \(\gamma = (x^\star)^T \Sigma x^\star=(1/2)(\nu^\star \delta + \lambda^\star)\),

\[x=x^\star, \quad \alpha=1, \quad \zeta=\lambda^\star, \quad v=z^\star\]

is a solution to (6).

Next consider a factorization

(7)\[ \Sigma = V^T V\]

for some \(V\in\R^{k\times n}\). We can then rewrite both problems (3) and (4) in conic quadratic form as

(8)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x\\ \mbox{subject to} & (1/2, \gamma, Vx) \in \mathcal{Q}_r^{k+2}\\ & e^Tx = 1\\ & x \geq 0, \end{array}\end{split}\]

and

(9)\[\begin{split}\begin{array}{ll} \mbox{minimize} & t\\ \mbox{subject to} & (1/2, t, Vx) \in \mathcal{Q}_r^{k+2}\\ & \mu^T x \geq \delta\\ & e^Tx = 1\\ & x \geq 0, \end{array}\end{split}\]

respectively. In practice, a suitable factorization (7) is either readily available, or it easily obtained. We mention typical choices below.

• Data-matrix. \(\Sigma\) might be specified directly in the form (7), where \(V\) is a normalized data-matrix with \(k\) observations of market data (for example daily returns) of the \(n\) assets. When the observation horizon \(k\) is shorter than \(n\), which is typically the case, the conic representation is both more parsimonious and has better numerical properties.

• Cholesky. Given \(\Sigma\succ 0\), we may factor it as (7) where \(V\) is an upper-triangular Cholesky factor. In this case \(k=n\), i.e., \(V\in\R^{n\times n}\), so there is little difference in complexity between the conic and quadratic formulations.

• Factor model. For a factor model we have

  \[\Sigma = D + U^T U\]

  where \(D\succ 0\) is a diagonal matrix, and \(U \in \R^{k\times n}\) is a low-rank matrix (\(k\ll n\)). The factor model directly gives us a factor

  (10)\[\begin{split}V = \left [ \begin{array}{c}D^{1/2} \\ U\end{array}\right ]\end{split}\]

  of dimensions \((n+k)\times n\). The dimensions of \(V\) in (10) are larger than the dimensions of the Cholesky factors of \(\Sigma\), but \(V\) in (10) is very sparse, which usually results in a significant reduction of solution time.

We can also combine the formulations (3) and (4) into an alternative problem that more explicitly computes a trade-off between risk and return,

(11)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x - \lambda x^T \Sigma x\\ \mbox{subject to} & e^T x = 1\\ & x \geq 0, \end{array}\end{split}\]

with a trade-off parameter \(\lambda\geq 0\). One advantage of (11) is that the problem is always feasible. This formulation also produces the same optimal trade-off curve, i.e., for a particular (feasible) choice of \(\delta\) (or \(\gamma\)), there exists a value of \(\lambda\) for which the different problems have the same solution \(x\). The conic formulation of (11) is

(12)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x - \lambda t\\ \mbox{subject to} & (1/2, t, Vx) \in \mathcal{Q}_r^{k+2}\\ & e^T x = 1\\ & x \geq 0. \end{array}\end{split}\]

8.4.2 Slippage costs

In a more realistic model we correct the expected return of investment by slippage terms \(T_j(x_j)\),

(13)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x - \sum_j T_j(x_j)\\ \mbox{subject to} & x^T \Sigma x \leq \gamma\\ & e^T x = 1\\ & x \geq 0, \end{array}\end{split}\]

which accounts for several different factors.

8.4.2.1 Market impact

The phenomenon that the price of an asset changes when large volumes are traded is called market impact, and for large-volume trading it is the most important slippage contribution. Empirically it has been demonstrated that market impact, i.e., the additional cost of buying or selling an asset is well-approximated by the conic representable function

\[T_j(x_j) = \alpha_j x_j^{3/2}\]

with coefficients \(\alpha_j\geq 0\) estimated from historical data. Using the result of Sec. 3.2.6 (Simple sets involving power functions) we can write the epigraph

\[x_j ^{3/2} \leq t_j\]

as

\[(s_j, t_j, x_j), (1/8, x_j, s_j) \in \mathcal{Q}_r^3,\]

i.e, we get a conic formulation of (13)

(14)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x - \alpha^T t\\ \mbox{subject to} & (1/2, \gamma, Vx) \in \mathcal{Q}_r^{k+2}\\ & (s_j, t_j, x_j) \in \mathcal{Q}_r^3\\ & (1/8, x_j, s_j) \in \mathcal{Q}_r^3\\ & e^T x = 1\\ & x \geq 0. \end{array}\end{split}\]

8.4.2.2 Transaction costs

For smaller volume trading the main slippage contribution is transaction costs, which can modeled as a linear function

\[T_j(x_j) = \alpha_k x_j\]

or as a fixed-charge plus linear function

\[\begin{split}T_j(x_j) = \left \{ \begin{array}{ll} 0, & x = 0,\\ \alpha_j x_j + \beta_k , & 0 < x_j \leq \rho_j, \end{array} \right .\end{split}\]

which can be modeled as using indicator variables (see Sec. 6.2.1 (Implication of positivity)). To that end, let \(z_j\) be an indicator variable,

\[(z_j=0) \rightarrow (x_j=0)\]

which we can express as

(15)\[x_j \leq \rho_j z_j, \quad z_j \in \{0,1\}.\]

We thus get a conic integer problem

(16)\[\begin{split}\begin{array}{ll} \mbox{maximize} & \mu^T x - e^T t\\ \mbox{subject to} & (1/2, \gamma, Vx) \in \mathcal{Q}_r^{k+2}\\ & \alpha_j x_j + \beta_j z_j \leq t_j\\ & x_j \leq \rho_j z_j\\ & e^T x = 1\\ & x \geq 0\\ & z \in \{0,1\}^n. \end{array}\end{split}\]

Since the objective function minimizes \(t_j\) we exclude the possibility that \(x_j=0\) and \(z_j=1\).

8.4.3 Maximizing the Sharpe ratio

The Sharpe ratio defines an efficiency metric of a portfolio as the expected return per unit risk, i.e.,

\[S(x) = \frac {\mu^T x - r_f}{ (x^T \Sigma x)^{1/2}},\]

where \(r_f\) denotes the return of a risk-free asset. By assumption, we have that \(\mu^T x>r_f\) (i.e., there exists a risk-associated portfolio with a greater yield than the risk-free asset), so maximizing the Sharpe ratio is equivalent to minimizing \(1/S(x)\). In other words, we have the following problem

\[\begin{split}\begin{array}{lccc} \text{minimize} & \frac{\| V^T x \|}{\mu^T x - r_f}\\ \text{subject to} & e^Tx & = & 1\\ & x &\geq & 0. \end{array}\end{split}\]

We next introduce a variable transformation,

\[y = \gamma \mu^T x, \qquad \gamma \geq 0.\]

Since a positive \(\gamma\) can be chosen arbitrarily and \((\mu - r_fe)^T x>0\), we have without loss of generality that

\[(\mu -r_fe)^T y = 1.\]

Thus, we obtain the following conic problem for maximizing the Sharpe ratio,

\[\begin{split}\begin{array}{lccc} \text{minimize} & t\\ \text{subject to} & (t, Vy) & \in &\mathcal{Q}^{k+1}\\ & e^Ty & = & \gamma \\ & (\mu -r_fe)^T y& = & 1\\ & \gamma & \geq & 0\\ & y &\geq &0, \end{array}\end{split}\]

and we recover \(x : = y/\gamma\).