ILOG CPLEX 11.0 User's Manual > Continuous Optimization > Solving Problems with a Quadratic Objective (QP) > Entering QPs > Reformulating QPs to Save Memory |
Reformulating QPs to Save Memory |
INDEX PREVIOUS NEXT |
When the Q matrix is very dense or extremely large in dimension, excessive memory may be needed to solve the problem as conventionally formulated. However, you may be able to use an alternative formulation to avoid such bottlenecks. Specifically, if you can express Q as FF', (where F is another matrix, not necessarily square, having fewer nonzeros than Q, and F' is its transpose) then you can reformulate the QP like this:
min c'x + y'y Ax ~b y - Fx = 0 l <= x <= u y free |
In the reformulation, y is a vector of free variables, one variable for each column of F.
Portfolio optimization models in particular can benefit from this reformulation. In the most common portfolio models, Q is a covariance matrix of asset returns, while F is the matrix of the deviations of the asset returns from their mean used to compute the covariances. In that reformulation, the number of columns of F corresponds to the number of time periods for which returns are measured.
In general, while the number of rows in F must match the dimension of the square matrix Q, the number of columns of F can be fewer. So, even if Q is dense and F is also dense, you still may reduce the memory requirements to solve the model if F has more rows than columns.
Furthermore, if F is a sparser matrix than Q, this alternative formulation may improve performance even if F has more columns than Q.
Copyright © 1987-2007 ILOG S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |