Thread Subject:

optimization problem solution: [500x12000].X = [500x1] ???

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

"keshav singh" wrote in message <jgg9j1$9m6$1@newscl01ah.mathworks.com>...
> 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.
==================

If you consider this a large matrix, you might want to look into a new computer. A 500x12000 matrix is about 50MB...peanuts for any computer less than 7 years old. If you convert the matrix to single floats, that will drop from 50MB to 25 MB.

Also, you might want to look into a more recent version of MATLAB. I can think of no other reason why LSQLIN wouldn't be accepting a sparse matrix for input... there's certainly nothing about such a restriction in the current documentation.



> 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.
===================

Then you need more constraints to improve the problem conditioning. And why would LSQLIN handle the singularity any better?

"keshav singh" wrote in message <jgg9j1$9m6$1@newscl01ah.mathworks.com>...
> 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

Hi Keshav,

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

+Steve