The optimization toolbox of Matlab does not contain an MIQP (Mixed Integer Quadratic Programming) solver. So when they discuss a cardinality constrained portfolio problem (this means only a certain number of assets can be in the portfolio), an interesting cutting plane technique is used instead. This method will solve a series of linear MIP models instead of attacking the MIQP model directly.

Let’s first formulate the problem as proper MIQP model. First here is how the data is prepared:

##### Data

##### Quadratic Data Trick

The main deviation from the original model is that we don’t store the variance-covariance matrix \(Q\) as a full dense matrix but as an upper-triangular matrix (it includes the diagonal). We multiply the off-diagonal elements by two, so that the expression \(\sum_{i,j} x_i Q_{i,j} x_j \) will yield exactly the same result for any \(x\). Basically we replace expressions like \(x_1 Q_{1,2} x_2 +x_2 Q_{2,1} x_1\) by \( 2 x_1 Q_{1,2} x_2\). The sole purpose of this trick is to have fewer non-zero elements in the quadratic form \(x^TQx\). This really can help for larger problems (this looks mainly a GAMS problem: GAMS is slower in generating the model when the nonzero count of the Q matrix increases; it does not make much difference for the QP solver).

The model itself looks like:

##### MIQP Model

##### Modeling trick

In the original model the variable \(K\) was not present and the min- and max-fraction constraints were formulated as:

This duplicates a summation. Our formulation adds a single variable (with a lower- and upper-bound) but we get rid of an equation that includes a summation. As a result we reduce the number of non-zero elements in the constraint matrix.

\[\begin{align} &\sum_i \delta_i \ge \text{minAssets}\\ &\sum_i \delta_i \le \text{maxAssets} \end{align}\]

##### Cutting Plane Algorithm

In the cutting plane method we replace the quadratic objective

by

\[\min\> \lambda \sum_{i,j} x_i Q_{i,j} x_j - \sum_i \mu_i x_i \]

where \(K\) is the current iteration or cycle, and \(x^*_k\) is the optimal MIP solution from the k-th iteration. This is essentially a Taylor approximation.

\[\begin{align} \min\>& \lambda y - \sum_i \mu_i x_i\\ & y \ge - {x^*_k}^T Q x^*_k + 2{x^*_k}^T Q x \> \text{for \(k=1,...,K-1\)} \end{align}\]

Here is our version of the algorithm:

In this second model we replaced the original objective by the new linear objective and the cuts. The equation **cut** is indexed by a dynamic set **cuts** that grows during the iteration loop. We start the iteration scheme with an empty set **cuts**. Note that in the calculation of \(\beta\) we changed the expression from \(2{x^*_k}^T Q\) to \({x^*_k}^T (Q+Q^T)\). This is to compensate for the upper-triangularization trick we used before.

The results are:

miqp 0.036039

iter1 -0.002430

iter2 0.013922

iter3 0.025362

iter4 0.034862

iter5 0.035138

iter6 0.035646

iter7 0.035731

iter8 0.035776

iter9 0.035790

iter10 0.035828

We see the objectives converge towards the optimal MIQP objective.

##### References

- Mathworks, Mixed-Integer Quadratic Programming Portfolio Optimization.
- J. E. Kelley, Jr. "
*The Cutting-Plane Method for Solving Convex Programs*." J. Soc. Indust. Appl. Math. Vol. 8, No. 4, pp. 703-712, December, 1960.

## No comments:

## Post a Comment