Optimizing Vector Magnitude through 180-Degree Rotations

[Jeff.Nevington]

Wasn't sure whether to post this in the computing section or not but here goes anyway,

I have n number of 2d vectors (all have the same magnitude),
for each vector I can choose whether or not to multiply it by -1 (spinning it through 180 degrees),
all of the vectors are then added together,
The objective is to maximize the magnitude of the final vector, the only variable being whether or not to multiply the vector by -1.

Here is an example,
I have 2 vectors, both magnitude 1, one at 30° and one at -80° from the horizontal axis. Adding both of these together I will have a new vector at -37.6° with magnitude 1.31. However if I flip the -80° vector (spin it through 180), it becomes 100°. The new resultant vector is 64.7° with a magnitude of 1.64.

It is easy to check all combinations for a small number of vectors but it soon becomes unfeasible.

The main observation that I keep coming back to is that the objective should be to minimize the sum of the differences between the angles (i.e. the maximum magnitude will be achieved when the vectors change direction the least amount - trying to make them as similar to a straight line as possible). I am having trouble figuring out how to write the problem down mathematically so it makes sense.

Does anyone have any ideas on this? I feel like it should be really quite simple to solve and just requires some good math common sense but I have been fiddling with it for days now and I am going around in circles (literally).

I should point out that I do have a solution that seems to work but is very messy. I pick a single point far away from the origin (further than if all the vectors made a straight line) and then find the arrangement of vectors that gives the minimum distance to that point (this is a convex linear programming problem). I then move the point through several degrees relative to the origin and repeat the process. I keep going until the point has made a full circle. I then find which solution gave the largest magnitude (there are always at least 2 because for every solution there is a symmetrical one). Although I am pretty certain this approach finds the maximum magnitude it seems very messy to me and I cannot prove that it works mathematically.

Any help greatly appreciated,
Jeff

 

[kontejnjer]

Someone correct me if I'm wrong, but the way I see it, in order to maximize your sum, you have to maximize the inner (scalar) product of the vectors, \vec{a} \vec{b}=|\vec{a}|*|\vec{b}|*Cos(\alpha-\beta). Each time you add a new vector, just add a condition checking whether Cos(\alpha-\beta) is positive (since magnitudes can't be negative), and if not, flip its direction, this guarantees that the scalar product will be positive since Cos(x+\pi)=-Cos(x) for any x.

 

[Jeff.Nevington]

Thankyou for your response!

Your proposed method would work perfectly if the list of vectors had a fixed, pre-determined order in which they were fed into your algorithm. If I understand correctly you suggest to take the first two vectors, \vec{a} and \vec{b}, find the maximum dot product by checking both directions for \vec{b} and then finding the resultant vector. This new vector will then be checked against the next vector in the sequence and so on until all the vectors had been checked.

The problem is that the chosen direction for \vec{b} (the one that makes Cos(\alpha-\beta) positive) is dependent on all of the vectors that came before it.

In the example I gave in the original post with two vectors, this method would work fine, giving a resultant vector of magnitude 1.64 and angle 64.7°. However, if I had a third vector of magnitude 1 and angle -37.6° and maximized the dot product again I would have a final resultant vector of magnitude 1.74 at 30°. This is not the highest possible magnitude for these three vectors. If checked the third vector (-37.6°) against the second vector (-80°) initially, then checked the first vector (30°) last, the trend would change and I would end up with a resultant vector of magnitude 2.31 at -37.6°.

Maybe what I need is for \alpha to remain constant in your algorithm. Say there was an \alpha that represents the overall trend of the vectors, I could check all of the vectors against this and the order in which I checked them would have no effect.

Thanks again for the reply,

Jeff