Help solving a bounded linear-least squares problem.
svlad
I have a set of m points controlled linearly by n variables. The
variables move the points along line segments.
For a single point I have:
p` = p0 + sum_(i=1 to n) {( pi1 - p0) * t }
where pi1 is the position of the point when the ith variable has a
value of 1. p0 is the rest position of the point when the ith variable
is 0. In this case p0i is the same so I am using the notation p0. The
simple diagram below illustrates how a single point might be affected
by three different variables.
x p21
p31 x |
\ |
\ |
\ |
\o---------------------x p11
My goal is to find values for the variables t that minimizes the
distance between the point and its target position. By defining di as
the delta of (pi1 - p0) the problem can be stated in matrix-vector
form:
| d11 d12 . . . d1n | z = [p10 p20 . . . pm0]'
| d21 d22 . . . d2n |
X = | . . . | y = [tp1 tp2 . . . tpm]'
| . . . |
| dm1 dm2 . . . dmn |
X is a mxn matrix containing the n delta values for the m points.
z is a m-vector containing the original position of each point
y is a m-vector containing the target positions for each point.
t is a n-vector containing the variables to be optimized.
The problem can now be stated in matrix-vector terms as:
y = z + (X * t)
Since I need to minimize the distance I have:
d2 = (y - z + X * t)^2
= (y - z)'*(y - z) + (y - z)' * X*t + t'*X'*X*t
The gradient of the distance function is:
d2/dt = -2X'*(y-z) + 2X'*X*t
Setting to zero gives:
X'*X*t - X'*(y-z) = 0
For the unbounded case this can be solved directly as ||Ax -b||2 with A
= X' * X and b = X' * (y-z).
In my problem, each variable in t can have lower and upper bounds. I
thought BVLS would be the ticket for solving such a problem, but it
turns out that BVLS does not produce the optimal solution in regards to
the distance-squared between the original points and their target
positions. It does, however, minimize the norm of the gradient.
Unfortunately, the minimization of the gradient norm does not appear to
correlate to the minimization of the distances between the points once
the bound constraints are in effect (as an aside, I would appreciate if
someone could explain to me why this occurs).....unless I've done
something foolish which is entirely possible.
For more background on my BVLS woes you can follow this thread:
http://groups.google.com/group/sci.math.num-analysis/browse_thread/thread/f44a2ed1285ef34f
So how do I set up and solve this problem so that I can minimize the
distance between the points (in a least-squares sense) when the
variables are bounded? In addition, I would also like to implement a
sort of mutual exclusivity between certain variables e.g. if t1 > 0
then t5 = 0.
Any help would be greatly appreciated!
Peter Spellucci
In article <1164682507.4...@l39g2000cwd.googlegroups.com>,
"svlad" <mads...@gmail.com> writes:
>I need some help solving a bounded linear-least squares problem:
>
>I have a set of m points controlled linearly by n variables. The
>variables move the points along line segments.
>
>For a single point I have:
>
> p` = p0 + sum_(i=1 to n) {( pi1 - p0) * t }
below you have t dependent on the coordinate!
and p0 : you mean p0i ?
>where pi1 is the position of the point when the ith variable has a
>value of 1. p0 is the rest position of the point when the ith variable
this makes the confusion even larger: the rest position now refers
to single coordinates?
>is 0. In this case p0i is the same so I am using the notation p0. The
>simple diagram below illustrates how a single point might be affected
>by three different variables.
>
> x p21
> p31 x |
> \ |
> \ |
> \ |
> \o---------------------x p11
>
this looks as if you had a set of
different directions : the same directions
for al the points? and the stepsize: different
for the different directions?
but below you apply different t's for the
different coordinates?????
>My goal is to find values for the variables t that minimizes the
>distance between the point and its target position. By defining di as
>the delta of (pi1 - p0) the problem can be stated in matrix-vector
>form:
>
> | d11 d12 . . . d1n | z = [p10 p20 . . . pm0]'
> | d21 d22 . . . d2n |
> X = | . . . | y = [tp1 tp2 . . . tpm]'
> | . . . |
> | dm1 dm2 . . . dmn |
>
>X is a mxn matrix containing the n delta values for the m points.
in the rows!
>z is a m-vector containing the original position of each point
should this be a matrix?? or what do you mean by
position???
>y is a m-vector containing the target positions for each point.
>t is a n-vector containing the variables to be optimized.
>
>The problem can now be stated in matrix-vector terms as:
>
>y = z + (X * t)
>
>Since I need to minimize the distance I have:
>
>d2 = (y - z + X * t)^2
> = (y - z)'*(y - z) + (y - z)' * X*t + t'*X'*X*t
one again the "2" is missing here
>
>The gradient of the distance function is:
>
>d2/dt = -2X'*(y-z) + 2X'*X*t
>
>Setting to zero gives:
>
>X'*X*t - X'*(y-z) = 0
>
>For the unbounded case this can be solved directly as ||Ax -b||2 with A
>= X' * X and b = X' * (y-z).
>
>In my problem, each variable in t can have lower and upper bounds. I
>thought BVLS would be the ticket for solving such a problem, but it
>turns out that BVLS does not produce the optimal solution in regards to
>the distance-squared between the original points and their target
>positions. It does, however, minimize the norm of the gradient.
>Unfortunately, the minimization of the gradient norm does not appear to
>correlate to the minimization of the distances between the points once
>the bound constraints are in effect (as an aside, I would appreciate if
>someone could explain to me why this occurs).....unless I've done
>something foolish which is entirely possible.
>
>For more background on my BVLS woes you can follow this thread:
>
>http://groups.google.com/group/sci.math.num-analysis/browse_thread/thread/f44a2ed1285ef34f
>
>So how do I set up and solve this problem so that I can minimize the
>distance between the points (in a least-squares sense) when the
>variables are bounded? In addition, I would also like to implement a
>sort of mutual exclusivity between certain variables e.g. if t1 > 0
>then t5 = 0.
this makes the problem much harder: will end up in a mixed continuous discrete
problem or nonlinearity
>
>Any help would be greatly appreciated!
>
there is a confusion:
let us assume that your problem formulation is correct (I don't believe this)
so we have
f(t)=(y-z+X*t)^2 = min subject to t(i) in [0,1] , i=1,...,n
and y,z are in m-dimensional space , X is m times n
then the Kuhn Tucker conditions are
2*X'*(y-z-X*t) - lambda1+lambda2 =0
lambda1(i)*t(i)=0
lambda2(i)*(1-t(i))=0
lambda1(i), lambda2(i) >=0, 0<=t(i)<=1
you can solve this using e.g. SOR with projection on the box.
since the multipliers lambda1 and lambda2 cannot be nonzero simultaneously,
you can read off from the sign of the gradient what to do: move the t(i)
or fix it at the bound
hth
peter
svlad
appreciated...........
> >
> > x p21
> > p31 x |
> > \ |
> > \ |
> > \ |
> > \o---------------------x p11
> >
> this looks as if you had a set of
> different directions : the same directions
> for al the points? and the stepsize: different
> for the different directions?
> but below you apply different t's for the
> different coordinates?????
What the ASCII diagram above is supposed to (sorry for the confusion)
depict is how a single point (m=1) might be affected by three variables
(n=3). Each variable corresponds to an equation for linear
interpolation along a line. The lines associated with each variable
have the same starting point, but obviously different endpoints.
Now....each of the m points has its own set of n line equations for the
n variables i.e. the same n variables move each point differently. The
goal here is find a set of values for the n variables which minimizes
the distance between each point and its corresponding target position.
Each of the n columns of the X matrix corresponds to the vector of the
line defined by one of the n variables. There are actually (m*3) rows
in the matrix to account for the fact that I have points in R^3. This
is why I believe that
y = z + X * t
is the correct formulation of this problem.
> >My goal is to find values for the variables t that minimizes the
> >distance between the point and its target position. By defining di as
> >the delta of (pi1 - p0) the problem can be stated in matrix-vector
> >form:
> >
> > | d11 d12 . . . d1n | z = [p10 p20 . . . pm0]'
> > | d21 d22 . . . d2n |
> > X = | . . . | y = [tp1 tp2 . . . tpm]'
> > | . . . |
> > | dm1 dm2 . . . dmn |
> >
> >X is a mxn matrix containing the n delta values for the m points.
>
> in the rows!
>
> >z is a m-vector containing the original position of each point
> should this be a matrix?? or what do you mean by
> position???
Sorry....I was taking a notational short-cut. My points are in R^3 each
point has three line equations (x, y , z):
X is a (m*3) x n matrix containing the n delta values for the m points
(dx, dy, dz).
z is a (m*3) vector containing the original position of the each point
in R^3.
y is a (m*3) vector containing the target positions for each point in
R^3.
t is still a n-vector containing the variable to be optimized.
> >y is a m-vector containing the target positions for each point.
> >t is a n-vector containing the variables to be optimized.
> >
> >The problem can now be stated in matrix-vector terms as:
> >
> >y = z + (X * t)
> >
> >Since I need to minimize the distance I have:
> >
> >d2 = (y - z + X * t)^2
> > = (y - z)'*(y - z) + (y - z)' * X*t + t'*X'*X*t
> one again the "2" is missing here
A typo I make almost everytime :(
> there is a confusion:
> let us assume that your problem formulation is correct (I don't believe this)
> so we have
>
> f(t)=(y-z+X*t)^2 = min subject to t(i) in [0,1] , i=1,...,n
> and y,z are in m-dimensional space , X is m times n
> then the Kuhn Tucker conditions are
>
> 2*X'*(y-z-X*t) - lambda1+lambda2 =0
> lambda1(i)*t(i)=0
> lambda2(i)*(1-t(i))=0
> lambda1(i), lambda2(i) >=0, 0<=t(i)<=1
>
> you can solve this using e.g. SOR with projection on the box.
> since the multipliers lambda1 and lambda2 cannot be nonzero simultaneously,
> you can read off from the sign of the gradient what to do: move the t(i)
> or fix it at the bound
Is it also valid to use the magnitude of the gradient in the manner of
the BVLS active set strategy to determine which variable most wants to
become active? If that is true and I solve the variables in the order
of greatest gradient magnitude to smallest gradient magnitude, could I
then implement the mutex constraints by clamping a variable to its
lower bound (0) if one of its mutex variables is not at its lower
bound? That would be cheap and easy.
Thanks again!
Peter Spellucci
In article <1164762109.1...@j44g2000cwa.googlegroups.com>,
Now I got it. o.k. but the input to BVLS must be
matrix X
right hand side y-z
variable t in the [0,1] box,
not the gradient !
hth
peter
svlad
In a "DOH!" moment, that just occurred to me last night........a very
silly mistake on my part :( I should've looked a closer at what BVLS
was really doing.
Thank you for your assistance!