Saturday, August 14, 2010

QP Models with GAMS/Knitro

> My large QP portfolio model does not solve with GAMS/KNITRO.

Yes, for large problems you will get:

Memory estimate for Hessian is too small.
Increase the <modelname>.workfactor option from the current value of 1

For 2000 stocks with WORKFACTOR=10 I got the same error.

Even if the model is formulated as a QCP model, the GAMS link is not smart enough in setting up the hessian efficiently. Instead it looks like the QP is handled as a general NLP.

There are two easy workarounds. First of all you can solve this with IPOPT. The GAMS link for IPOPT is smarter in dealing with second derivatives than the link for KNITRO (as of GAMS 23.5). Note that it is better to solve as a QCP model than as an NLP model: GAMS is not smart enough to recognize this as a QP and exploit that:

model type GAMS generation time IPOPT time function evaluation time Total solver time
NLP 38 21.8 39.1 61.0
QCP 38 21.6 9.8 31.4

A second possibility is to reformulate model (1):

image

into model (2):

image

This formulation can be solved with KNITRO without the problems with the hessian storage.


As an aside we can improve formulation 1 by replacing the variance-covariance matrix Q by

imageWe exploit here symmetry in the quadratic form x’Qx. This exercise substantially reduces the GAMS generation time, and also further shaves off some time from the solver:

model type GAMS generation time IPOPT time function evaluation time Total solver time
QCP –triangular Q 18.8 21.3 4.6 26

We can also apply the triangular storage scheme to model (2). With a solver like SNOPT this leads to a very fast total solution time (i.e. generation time + solver time).

model type GAMS generation time SNOPT time
NLP –triangular Q in linear constraints 1 5

If needed we can even speed this up by not using the covariances but rather the mean adjusted returns directly:

image

I used T=300 time periods. This formulation yields:

model type GAMS generation time SNOPT time
NLP – Mean Adj Returns 0.5 2.3

Even for the simple QP portfolio model, careful modeling can help to improve the performance in a significant way.

6 comments:

  1. In many cases you can do these models quite efficiently using conic optimization which is supported in GAMS. Note all issues with Hessian complete vanishes because there no Hessian in conic optimization.

    The note

    http://www.mosek.com/fileadmin/reports/tech/portfolio.pdf


    tells how to reformulate your problem as conic problem.

    On a small GAMS example Michael B. and tried with MOSEK the conic formulation led faster solution times.

    ReplyDelete
  2. Mosek can solve this very fast as conic problem, but its solution is a little bit sloppy. With this data set it will be rejected as infeasible when fed into Mosek as QP. I have noticed that behavior also with other (large) data sets. Somehow all the formulations I showed, demonstrated better numerical behavior.

    ReplyDelete
  3. I am a bit confused. MOSEK can also solve it as QP and that is something different from a conic formulation. So if you input it as QP then you are not using the conic optimizer.

    The QP optimizer may sometimes say infeasible when it should not but that usually indicate a bad problem scaling (large numbers somewhere). Also there is there is parameter that can be set so it is more conservative about scaling infeasible. If I can see the log file I might be able to come up with a solution.

    Finally, regarding formulation then quite frequently you can reformulate the problem to have diagonal Q at the cost of increasing the number linear constraints and variables (as discussed in our note). This is in many cases advantageous for the interior-point optimizers.
    But I am sure you aware of that trick.

    ReplyDelete
  4. The sanity check for the conic solution was:

    1. Solve conic model
    2. Fix: x.fx(i) = x.l(i);
    3. Solve QP => INFEASIBLE.

    I.e. the conic solver does not deliver a solution that is within feasibility tolerances.

    ReplyDelete
  5. Maybe there is bug somewhere. Without running the problem it is hard to say though. If you submit the problem to GAMS support or MOSEK support (support@mosek.com) we shall look at it.

    ReplyDelete
  6. The model data is too big to email.

    Problem source is here: http://amsterdamoptimization.com/models/cone/portfcone.gms. Data is here: http://amsterdamoptimization.com/models/cone/portf.gdx. Here I just do:

    1. Solve conic problem
    2. Fix:x.fx(i) = x.l(i);
    3. Solve conic problem

    The second model will be declared infeasible. (The budget equation is actually violated by more than 1e-6).

    ReplyDelete