Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

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

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

From: keshav singh

Date: 3 Feb, 2012 09:32:17

Message: 1 of 3

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

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

From: Matt J

Date: 3 Feb, 2012 14:59:10

Message: 2 of 3

"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?

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

From: Steve Grikschat

Date: 3 Feb, 2012 15:09:21

Message: 3 of 3

"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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us