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

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:

\[\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.