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

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

so that

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

and hence

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

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

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

with break points at

The variables are

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

Hence the convexity requirement leads to the constraints

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

must hold. Therefore, the problem to be solved is

Maximizing

or

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

where

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

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

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

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

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

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)\),

is a solution to (6).

Next consider a factorization

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

and

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,

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

### 8.4.2 Slippage costs¶

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

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

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

as

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

#### 8.4.2.2 Transaction costs¶

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

or as a fixed-charge plus linear function

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,

which we can express as

We thus get a *conic integer problem*

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

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

We next introduce a variable transformation,

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

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

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