Say that we have $3$ groups of $10$ numbers: $$ g_{1}= \left\{x_1,x_2,...,x_{10} \right\}, g_{2}= \left\{y_1,y_2,...,y_{10} \right\}, g_{3}= \left\{z_1,z_2,...,z_{10} \right\}. $$ The sum of each group is given, such that: $$ \sum_{i=1}^{10}X_i = S_X $$ where $X = x,y,z$. Knowing that $\sqrt{x_i^2+y_i^2+z_i^2} < a$ where $a$ is a known constant, I want to find a way to find the groups $g$ that minimizes the following function: $$ \sum_{i=1}^{10} \sqrt{x_i^2+y_i^2+z_i^2} $$ I am seeking a way to find the solution numerically. What I have done is:
- Find an initial solution that satisfies all the conditions.
- Pertubate a single term and modify the rest of the terms in the same group so that the sum of the whole group remains the same.
- Check that it satifies $\sqrt{x_i^2+y_i^2+z_i^2} < a$. If not, undo the pertubation and go to the next term.
- Check if the pertubation have decreased the function $\sum_{i=1}^{10} \sqrt{x_i^2+y_i^2+z_i^2}$. If not, undo the pertubation and go to the next term.
- Repeat the process for every term.
- Repeat the cycle until no change was accepted in an entire cycle.
Cetainly , I can get to an resonable solution. However, there are also the following problems:
- It is very inefficient. I have to do several checks for every term.
- Depending on the initial solution I choose, I will very likely be trapped in a local minima.
- Depending on the sequence of my loop (for example, if I go $g_1$-$g_2$-$g_3$ and $g_3$-$g_2$-$g_1$ in every loop) I get to different solutions due to the conditions that include terms from different groups.
How can I improve my method?
If you replace the $<a$ constraint with $\le a$, you can reformulate as a second order cone programming (SOCP) problem, which is convex and thus has a unique globally optimal solution.
With sample values for $S_X$, $S_Y$, $S_Z$, and $a$, I get optimal solution $x_i=S_X/n$, $y_i=S_Y/n$, $z_i=S_Z/n$.