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.

  • 2
    $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Jul 5 '17 at 6:48
  • 1
    $\begingroup$ $f(X)$ is convex $\endgroup$ – A.Γ. Jul 5 '17 at 6:55
  • $\begingroup$ 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. $\endgroup$ – A.Γ. Jul 5 '17 at 7:54
  • $\begingroup$ @A.Γ. Is it convex????? really?? $\endgroup$ – Danny_Kim Jul 5 '17 at 8:37
  • 3
    $\begingroup$ @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. $\endgroup$ – A.Γ. Jul 5 '17 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.