MATLAB: Optimization problem solution: [500×12000].X = [500×1] ?

Question

Hello,

I've run into the problem that I need to solve an optimization problem for very large matrices. The equality constraint matrix is around 500 (rows) by 12000 (column), There are two other constraints sum-to-unity and non-negativity. The only way I can make such a large matrix is using sparse, but lsqlin/ quadprog constraints (matlab fn) do not cooperate with sparse matrices. Is there some other way I can formulate the problem so I can specify this problem and solve?

I have tried with 'quadprog', as we can always rewrite a least squares problem as a quadratic optimization , and I think quadprog accepts sparse equality constraints. But there might be trouble if the matrix H of quadprog equivalent to A'*A of the lsqlin formulation is singular.

Any and all replies are really appreciated!

~Keshav

Answer 1

Here's a suggestion I posted over at the newsgroup:

The default algorithms for both lsqlin and quadprog accept sparse matrices. However, they only solve problems with equality constraints OR bounds on the variables, but not both. Therefore, since your problem has both, they switch to a dense matrix algorithm.

A possibility is to try the interior-point convex algorithm in quadprog (released in R2011a). It accepts sparse matrices and all combinations of constraints for quadprog. Here's an example:

http://www.mathworks.com/help/toolbox/optim/ug/brn4nlc.html#bssex3v