Re: Linear Optimization problem............

madsvlad@xxxxxxxxx wrote:
> 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.

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.

.