# How to minimize that expression in four variables?

I mean $$\sqrt{w^2+(21-x)^2}+\sqrt{(20-w)^2+z^2}+\sqrt{x^2+(20-y)^2}+\sqrt{y^2+(21-z)^2}.$$

The command

Minimize[Sqrt[x^2 + (20 - y)^2] + Sqrt[y^2 + (21 - z)^2] +
Sqrt[z^2 + (20 - w)^2] + Sqrt[w^2 + (21 - x)^2], {x, y, z, w}]


is running without any response on my comp for hours. The numerical optimizations

NMinimize[ Sqrt[x^2 + (20 - y)^2] + Sqrt[y^2 + (21 - z)^2] +
Sqrt[z^2 + (20 - w)^2] + Sqrt[w^2 + (21 - x)^2], {x, y, z, w},
Method -> "DifferentialEvolution"]


{58., {x -> 11.579, y -> 8.97237, z -> 11.579, w -> 8.97237}

and the same with Method->"RandomSearch"

{58., {x -> 10.5551, y -> 9.94753, z -> 10.5551, w -> 9.94753}}

and the same with Method->"NelderMead"

{58., {x -> 18.3218, y -> 2.55062, z -> 18.3218, w -> 2.55062}}

suggest the optimal value under consideration is taken in many points.

• Maple 2021 answers $\{x=-\frac{21 w}{20}+21,y=w,z=-\frac{21 w}{20}+21,w=w,\,\,\,\,\\,\,\,\,\sqrt{x^{2}+(20-y)^{2}}+\sqrt{y^{2}+(21-z)^{2}}+\sqrt{z^{2}+(20-w)^{2}}+\sqrt{w^{2}+(21-x)^{2}}=58\}$. – user64494 Apr 13 at 13:00
• The minimum is achieved on a 1 dimensional subspace of R4. Therefore, numerical routines can get different answers, depending on the methods and working precision. – Daniel Huber Apr 13 at 13:42
• The Maple result indicates that the min value of 58 is obtained for any w in the interval {0, 20}; the other variables will vary accordingly. – Bob Hanlon Apr 13 at 14:04
• @BobHanlon: Thank you for your valuable comment. – user64494 Apr 13 at 14:11
• Reduce[Sqrt[x^2 + (20 - y)^2] + Sqrt[y^2 + (21 - z)^2] + Sqrt[z^2 + (20 - w)^2] + Sqrt[w^2 + (21 - x)^2] == 58 /. {x -> -21 w/20 + 21, y -> w, z -> -21 w/20 + 21}, w, Reals] evaluates to 0<=w<=20 – Bob Hanlon Apr 13 at 14:15

In the recently released Mathematica 12.3 this works faster (using newly added convex optimization methods).

In[1]:= Minimize[Sqrt[x^2 + (20 - y)^2] + Sqrt[y^2 + (21 - z)^2] + Sqrt[z^2 + (20 - w)^2] + Sqrt[w^2 + (21 - x)^2], {x, y, z, w}] // AbsoluteTiming // InputForm

Out[1]//InputForm= {2.204591, {58, {x -> 21/2, y -> 10, z -> 21/2, w -> 10}}}

• It would be nice if Minimize could indicate the non-uniqueness of an optimal solution. – user64494 May 22 at 3:30

Here is its proof known to me. The expression Sqrt[x^2 + (20 - y)^2] + Sqrt[y^2 + (21 - z)^2] + Sqrt[z^2 + (20 - w)^2] + Sqrt[w^2 + (21 - x)^2] is nothing but the length of the broken line between the points {0,0},{x,20-y},{x+21-z,20},{x+21,40-w},{42,40}. It's clear its length is greater than or equal to the distance between the points {0,0} and {42,40} which equals 58. Unfortunately, the command

Resolve[ForAll[{x,y,z,w},Sqrt[x^2 + (20 - y)^2] + Sqrt[y^2 + (21 - z)^2] +
Sqrt[z^2 + (20 - w)^2] + Sqrt[w^2 + (21 - x)^2] >=58],Reals]


is running without any response on my comp for hours as well as the command with EucledeanDistance instead of Sqrt.