MOSEK is not solving my quadratic optimization problem fast enough. What should I do?

Assume that you are solving the quadratic optimization problem

$\begin{array}{lccc} \displaystyle{} \mbox{minimize}&\displaystyle{} 0.5x^{T}Qx + c^{T}x &\displaystyle{} &\displaystyle{}\\ \displaystyle{} \mbox{subject to}&\displaystyle{} A x &\displaystyle{} = &\displaystyle{} b, \\ \displaystyle{} &\displaystyle{} x \geq{} 0. &\displaystyle{} &\displaystyle{}\\ \end{array}$

The solution speed is of course dependent on the number constraints variables but an even more important factor is the sparsity structure in

$Q$

and to some extent in

$A$

. Therefore, if you are not satsified with the solution speed then the first step is to investigate

$Q$

. If

$Q$

is a block diagonal matrix with small blocks, it is as good as it gets.

However, if

$Q$

is a dense matrix then a reformulation might be worthwhile. Now assume a matrix

$F$

is known such that

$Q=FF^{T}$

then the above problem can be rewritten as follows

$\begin{array}{lccl} \displaystyle{} \mbox{minimize}&\displaystyle{} 0.5y^{T} y + c^{T}x &\displaystyle{} &\displaystyle{}\\ \displaystyle{} \mbox{subject to}&\displaystyle{} A x &\displaystyle{} = &\displaystyle{} b, \\ \displaystyle{} &\displaystyle{} F^{T} x - y &\displaystyle{} = &\displaystyle{} 0, \\ \displaystyle{} &\displaystyle{} x \geq{} 0. &\displaystyle{} &\displaystyle{}\\ \end{array}$

The last problem has more constraints and variables than original one but if

$Q$

is of low rank then

$F$

has few columns and hence

$y$

is short. This implies that the second problem require much less storage to store and will solve much faster than the original problem.

One obvious question is how to obtain the

$F$

matrix. From the convexity assumption we know that

$Q$

is positive semi-definite, and for a positive semi-definite matrix

$Q$

there exist an

$F$

such that

$Q=FF^{T}$

. One one way to compute

$F$

is to use Cholesky factorization or an eigenvalue decomposition. However, in practice the origin of

$Q$

is often an

$FF^{T}$

expression, i.e. the original factors used for computing

$Q$

can be used in the formulation. Note that this is in particular the case if

$Q$

is covariance matrix estimated from historical data.

Many variants of this idea are described in the modelling sections of the MOSEK manuals.