compute weights to minimize sum of squares with constraint

I believe that the answer that you are looking for is this:

if any xi is zero then wi = 1 for that i is minimum otherwise:

Let G(i) = (1/xi)^2

Let SUM = sum over i of G(i)

optimal w(i) is G(i)/SUM

Derivation follows

My vector math is a bit rusty so do check this work.

First I do vectors in 2D, (vectors generalize up to n dimensions) and get a result. Then derive identical result directly in different manner to show that result was correct. Then I generalize to get final result.

I will do some renaming.

xi = the vector A, since we are in 2D I will also call this vector (a,b)

wi = vector w

M is a diagonal matrix with A running down diagonal. note that wM is vector (x1w1,x2w2). Also note that M is essentially a coordinate scale matrix

sum w = 1. In vector form this means that w lies on the plane that crosses each axis at 1.

the matrix M scales this plane to one that crosses each axis at xi or in this case (a,0) and (0,b)

F is the function that we minimize namely sum(xi*wi)^2. In vector form F is wM dot wM, minimizing F is essentially finding the point on the plane wM that is closest to the origin (because that point will have minimum norm)

So the equation for the plane (line) that goes through (a,0) and (0,b) is

bx + ay - ab = 0 // test this by pluging in either of the above points.

the normal vector to this plane is (b,a)

the unit normal vector is (b/R, a/R) where R = sqrt(a*a + b*b)

thus the normalized plane equation is

bx/R + ay/R - ab/R = 0

the distance from the origin to this plane is just the constant term ab/R

scale the normal vector by the distance to the plane you get

(bab/R^2, aab/R^2)

Now this vector is a point in the plane that is minimum distance to the origin (you can verify that it is in the plane by stuffing it into either of the plane equations)

So the minimum value of wM is the point (bab/RR, aab/RR) = P. Since wM = P we solve for P by inverting M. Convenient that it is diagonal so the inverse is 1/a, 1/b down the diagonal and thus P * Minverse is

min w is (bb/RR, aa/RR) since R was sqrt(aa + bb) we get

w = (bb/(aa + bb),aa/(aa + bb))

End of vector derivation

In 2D we can directly minimize F by calculus. Since w1 + w2 = 1 we have w2 = 1-w1 so I can replace all references to w2. and I no longer need the subscript 1 on the w1 so now w = w1

F = (x1w1)^2 + (x2w2)^2 = aa(w^2) + bb(1-w)^2

minimum F is when dF/dW = 0

0 = 2aa(w) - 2bb(1 - w)

aaw = bb(1-w)

aaw = bb - bbw

(aa + bb)w = bb

w = bb/(aa + bb)

since w2 = 1=w

w2 = 1 - bb/(aa + bb) = (aa + bb - bb)/(aa + bb) = aa/(aa + bb)

So direct solution shows that the wi that minimizes F is same as vector result (bb/(aa + bb), aa/(aa + bb))

Now generalizing vectors to N dimensions

let xi be a,b,c,d,... (again just to remove the need to write subscripts)

wM is the plane that goes through points (a,0,0,0...) (0,b,0,0...)(0,0,c,0...)...

equation is:

bcd...*x + acd...*y + abd...*z ... - abcd... = 0

so each coefficient C(i) = product (j != i) xi

To produce Normal plane equation, divide by R where R is now sqrt(sum C(i)*C(i) )

distance to plane is abcd.../R i.e. (product xi)/R call this P/R

Normal vector scaled by distance is (C1*P/RR, C2*P/RR, C3*P/RR, ...) is solution point wM

hit by inverse of M to get

w = (C1*P/RRx1, C2*P/RRx2, ...)

but P/xi is just C(i) (because C(i) was just the product missing a single term xi)

and since R is root of sum of C(i) squared, the RR in the denom just becomes sum( C(i)^2 )

so optimal w(i) = C(i)*C(i)/ (sum (C(i)*C(i)))

Now if you replace definition of C(i) with P/xi and do some factoring it gets into the form I listed up front.

I strongly encourage not only checking the math, but also writing some code that evaluates F for a bunch of different randomly choosen w (perticularly small perturbations about the supposedly optimal one) and verifying that the point which the math claims is optimal really is.

Enjoy!

marlin314a at 2007-7-14 23:11:38 >