# Is there any good algorithm or mathematical way of minimizing sum of difference of variables?

I want to find an optimal solution $X=[x_1, x_2, x_3, x_4, x_5]$, for $x_i\in\mathbb{R}^n$, that minimizes $$f(X) = \lVert y_1-x_1 \rVert^3 + \lVert y_2-x_2 \rVert^3 + \lVert y_3-x_3 \rVert^3 + \lVert x_1-x_5 \rVert^3 + \lVert x_2-x_4 \rVert^3 + \lVert x_3-x_5 \rVert^3 + \lVert x_4-x_5 \rVert^3,$$ where $y_1$, $y_2$, and $y_3$ are given vectors.

I failed to prove that the objective function $f(X)$ is convex, and I am roughly guessing $f(X)$ is a non-convex function.

Please recommend me some material, subjects, algorithms, or whatever related to this problem form. Thank you for reading my question.

• We have $y_1\to x_1\to x_5$, $y_2\to x_2\to x_4\to x_5$ and $y_3\to x_3\to x_5$. You only need to position $x_5$ optimally and arrange the other points inbetween – Hagen von Eitzen Jul 5 '17 at 6:48
• $f(X)$ is convex – A.Γ. Jul 5 '17 at 6:55
• It is not clear if you are interested in analytical solution that works for all $y_i$ and $n$ or a numerical solution works for you too. For a numerical solution: I would find the analytical solution for the power $2$ and took it as an initial point for the power $3$ in Newton's method. – A.Γ. Jul 5 '17 at 7:54
• @A.Γ. Is it convex????? really?? – Danny_Kim Jul 5 '17 at 8:37
• @Danny_Kim $(u,v)\mapsto\|u-v\|=t\ge 0$ is convex and $t\mapsto t^3$ is convex and increasing for $t\ge 0$, hence, $\|u-v\|^3$ convex. Sum of convex is convex. – A.Γ. Jul 5 '17 at 11:25