Prev: read_grib on 64-bit R2009b
Next: Help me in SVM classify
From: Darren Rowland on 6 Aug 2010 03:39
Hi guys,

I have a simple example of constrained least squares that I am solving. The problem is

min x'*x s.t. Ax<=b

where A is a square matrix with tridiagonal structure.
I have formulated the problem for use with quadprog but this feels to me like swatting a fly with a sledgehammer. I would appreciate any suggestions for
obtaining the solution more directly.

Cheers,
Darren
From: Bruno Luong on 6 Aug 2010 04:18
"Darren Rowland" <darrenjremovethisrowland(a)hotmail.com> wrote in message <i3ge6o$a73$1(a)fred.mathworks.com>...
> Hi guys,
>
> I have a simple example of constrained least squares that I am solving. The problem is
>
> min x'*x s.t. Ax<=b
>
> where A is a square matrix with tridiagonal structure.
> I have formulated the problem for use with quadprog but this feels to me like swatting a fly with a sledgehammer. I would appreciate any suggestions for
> obtaining the solution more directly.

I doubt there is more "direct" method, what you have formulated is more or less equivalent to quadratic programming problem (projection on a convex polytopes), except for some rank-degenerated cases. So QUADPROG should be the right tool.

Bruno
From: John D'Errico on 6 Aug 2010 07:01
"Darren Rowland" <darrenjremovethisrowland(a)hotmail.com> wrote in message <i3ge6o$a73$1(a)fred.mathworks.com>...
> Hi guys,
>
> I have a simple example of constrained least squares that I am solving. The problem is
>
> min x'*x s.t. Ax<=b
>
> where A is a square matrix with tridiagonal structure.
> I have formulated the problem for use with quadprog but this feels to me like swatting a fly with a sledgehammer. I would appreciate any suggestions for
> obtaining the solution more directly.

lsqlin works as well.

n = size(A,2);
x = lsqlin(eye(n,n),zeros(n,1),A,b);

You essentially wish to minimize norm(x), finding
the closest point to the origin that also satisfies the
given set of linear inequalities. This is solved nicely
by algorithm LDP, as found in Lawson & Hanson,
"Solving Least Squares Problems". This ends up as
a simple transformation of your problem into a call
to lsqnonneg.

HTH,
John
From: Matt J on 6 Aug 2010 08:32
"Darren Rowland" <darrenjremovethisrowland(a)hotmail.com> wrote in message <i3ge6o$a73$1(a)fred.mathworks.com>...
> Hi guys,
>
> I have a simple example of constrained least squares that I am solving. The problem is
>
> min x'*x s.t. Ax<=b
>
> where A is a square matrix with tridiagonal structure.
========================


The Lagrange dual of this problem is

min 0.5*z'*H*z +b.'*z s.t. z>=0

where x=-A.'*z and H=A*A.'

Because H is diagonally concentrated, it should be quite rapidly minimized using the following simple algorithm

C=sum(abs(H),2);
z=....; %initial positiive value

for ii=1:numIterations

z=z - (H*z+b)./C; z(z<0)=0;

end
From: Matt J on 6 Aug 2010 09:02
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <i3gvc4$fuq$1(a)fred.mathworks.com>...

> Because H is diagonally concentrated, it should be quite rapidly minimized using the following simple algorithm
================

This can actually be optimized a bit more by pre-computing some quantities

C=sum(abs(H),2);
z=....; %initial positiive value

d=-b./C;
M=speye(length(H)) - bsxfun(@rdivide,H,C);


for ii=1:numIterations

z=M*z+d; z(z<0)=0;

end

x=-A.'*z; %Don't forget to transform solution back to original domain
 | 
Pages: 1
Prev: read_grib on 64-bit R2009b
Next: Help me in SVM classify