Linear Optimization problem............

[mads...@gmail.com]

Hi,

I have a set of N points in 3d space, a set of M variables and a set of
target positions for the N points. I need to find optimal values for
the M variables which will put the input points as close to their
target positions as possible.

A point is affected by each of the M variables through a simple linear
interpolation relationship: P` = P0 + t(P1 - P0). Where P0 and P1 are
determined by setting the variable to zero and one respectively while
holding all other variables to zero.

For instance, if I had three variables the position for a single point
would be computed as:

P` = (P00+t0(P10-P00)) + (P01+t1(P10-P01)) + (P02+t2(P12-P02))

where P0x and P1x are the postions of the point when tx = 0 and 1
respectively.

Obviously, I wish to contrain the solution to have values for the
variables between [0,1].

I'd greatly appreciate any help in determining how to set up a solution
to this problem. I really don't have much knowledge or experience with
linear optimization problems. I just know it is one. At first I thought
it might be a linear least-squares problem, but I couldn't figure out
how to couch it in those terms. It seems as though it should be fairly
straight-forward problem to solve, though.

Thanks in advance!

[Ray Koopman]

For each point i, let yi be the 3-vector specifying that point's
target position, let zi be the 3-vector given by sum_j^M Pi0j,
let Xi be a 3 by M matrix in which column j is Pi1j-Pi0j, and
let t be an M-vector that is the same for all N points. Then the
approximation to the target position is zi+Xi*t, where * denotes
matrix multiplication. The squared distance between the target and
the approximation is di^2 = (yi-zi)'*(yi-zi) - 2(yi-zi)'*Xi*t +
t'*Xi'*Xi*t, where ' denotes matrix transposition.

Stack the yi vertically to get a 3N vector y,
stack the zi vertically to get a 3N vector z,
and stack the Xi vertically to get a 3N by M matrix X.
Then sum_i^N di^2 = (y-z)'*(y-z) + (y-z)'*X*t + t'*X'*X*t,
which can be minimized with respect to t in the usual way.

If the unconstrained solution does not give all tj in [0,1]
then you need a bounded least squares minimizer. See
http://lib.stat.cmu.edu/general/bvls for one such routine.

[Ray Koopman]

Ray Koopman wrote:
> [...]

> Then sum_i^N di^2 = (y-z)'*(y-z) + (y-z)'*X*t + t'*X'*X*t,

That should be (y-z)'*(y-z) - 2(y-z)'*X*t + t'*X'*X*t

[mads...@gmail.com]

Thanks for the help. Your explanation was extremely helpful. The whole
thing makes much more sense to me now. I have one further question
related to the actual minimization process:

>Then sum_i^N di^2 = (y-z)'*(y-z) + (y-z)'*X*t + t'*X'*X*t,

>which can be minimized with respect to t in the usual way.

I'm assuming this means that I need to minimize the gradient of the
distance function?

grad(di^2) = -2X'*X*t - 2X*(y-z)

Minimization occurs when the gradient is zero hence:

X'*X*t + X'*(y-z) = 0

Is this correct?

Thanks again!

[Ray Koopman]

mads...@gmail.com wrote:
> Thanks for the help. Your explanation was extremely helpful.
> The whole thing makes much more sense to me now. I have one
> further question related to the actual minimization process:
>> Then sum_i^N di^2 = (y-z)'*(y-z) + (y-z)'*X*t + t'*X'*X*t,
>> which can be minimized with respect to t in the usual way.
>
> I'm assuming this means that I need to minimize the gradient
> of the distance function?

It's probably better to say that you need to minimize the norm
of the gradient than it is to say that you need to minimize the
gradient itself. Or, better yet, just say that you need to set
the gradient to zero.

>
> grad(di^2) = -2X'*X*t - 2X*(y-z)
>
> Minimization occurs when the gradient is zero hence:
>
> X'*X*t + X'*(y-z) = 0
>
> Is this correct?

Yes, except you've used the formula from my initial post,
which was wrong. The correct expression for sum(di^2) is
(y-z)'*(y-z) - 2(y-z)'*X*t + t'*X'*X*t,
its gradient is -2X'*(y-z) + 2X'*X*t,
and the equation to be solved is X'*X*t = X'*y.

[Ray Koopman]

Ray Koopman wrote:
> [...] and the equation to be solved is X'*X*t = X'*y.

Another careless error! That should be X'*X*t = X'*(y-z).

[mads...@gmail.com]

Excellent! Hopefully I will not need resort to a bounded minimizer.

Thanks so very much for your assistance. Are there any good books you
might recommend on this topic?

[Ray Koopman]

I'm not sure what you're looking for, but try

C.L. Lawson & R.J. Hanson
Solving Least Squares Problems
Prentice-Hall, 1974; republished by SIAM, 1995.