## Saturday, February 27, 2016

### Cardinality Constrained Portfolio Optimization: MIQP without MIQP Solver

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

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:

##### Modeling trick

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

 \begin{align} &\sum_i \delta_i \ge \text{minAssets}\\ &\sum_i \delta_i \le \text{maxAssets} \end{align}
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.
##### Cutting Plane Algorithm

In the cutting plane method we replace the quadratic objective

 $\min\> \lambda \sum_{i,j} x_i Q_{i,j} x_j - \sum_i \mu_i x_i$
by
 \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}
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.

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
1. Mathworks, Mixed-Integer Quadratic Programming Portfolio Optimization.
2. 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.