SERVING THE QUANTITATIVE FINANCE COMMUNITY

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

For an equilateral triangle with vertices at (0,0), (1,0) and (1/2,1/2*sqrt(3)) then (X,Y)=(1/2,1/(2*sqrt(3))) is the point that minimizes the sum of the distances

if you look at (d/dx) and (d/dy) at that point, and the second derivatives, it's a minimum

For this case I get (1/2, 0.288674) using derivative-free Differential Evolution and the constraint is the triangle's bounding box.
so the same value

katastrofa
Posts: 8975
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: Extremes

The general solution is in the attached photo (S at the top). If you cannot read it, I can rewrite it here in Latex. Us the physical analogy and the problem becomes trivial

Cuchulainn
Topic Author
Posts: 61589
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

For an equilateral triangle with vertices at (0,0), (1,0) and (1/2,1/2*sqrt(3)) then (X,Y)=(1/2,1/(2*sqrt(3))) is the point that minimizes the sum of the distances

if you look at (d/dx) and (d/dy) at that point, and the second derivatives, it's a minimum

For this case I get (1/2, 0.288674) using derivative-free Differential Evolution and the constraint is the triangle's bounding box.
so the same value
Yes. DE is a randomized search algorithm. Probably a sledgehammer for a humble triangle. It's the mathematical equivalent of cruelty to animals.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Cuchulainn
Topic Author
Posts: 61589
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

The general solution is in the attached photo (S at the top). If you cannot read it, I can rewrite it here in Latex. Us the physical analogy and the problem becomes trivial
Latex would be nice.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

out of curiosity, what does your code give for the triangle with vertices (0,0), (4,0), (5,1)
I seem to be getting the point to be at the vertex (4,0) where there's an issue with computing the derivatives

Cuchulainn
Topic Author
Posts: 61589
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

out of curiosity, what does your code give for the triangle with vertices (0,0), (4,0), (5,1)
I seem to be getting the point to be at the vertex (4,0) where there's an issue with computing the derivatives
I get (4,0) as well but no directional derivatives are used, so no over/underflow.
One workaround might be to perturb/regularize one vertex to $(4, \varepsilon)$ and try your gradients again.

From the Wiki link (Case I) the "the Fermat point lies at the obtuse angled vertex".
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

katastrofa
Posts: 8975
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: Extremes

Is this how you solve the problem?
$S = d_1 + d_2 + d_3 = \sqrt{x^2+y^2} + \sqrt{(x-a)^2+y^2} + \sqrt{(x-d)^2+(y-h)^2}$
$\frac{\partial S}{\partial x} = 0$
$\frac{\partial S}{\partial y} = 0$
triangle.png (17.22 KiB) Viewed 2664 times
(On the drawing from the previous posts I tried to explain the physical analogy which explains the geometric solution from wikipedia.)

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

Is this how you solve the problem?
$S = d_1 + d_2 + d_3 = \sqrt{x^2+y^2} + \sqrt{(x-a)^2+y^2} + \sqrt{(x-d)^2+(y-h)^2}$
$\frac{\partial S}{\partial x} = 0$
$\frac{\partial S}{\partial y} = 0$

triangle.png

(On the drawing from the previous posts I tried to explain the physical analogy which explains the geometric solution from wikipedia.)
yes

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

The $2\pi/3$ thing may be correct at least for the interior points
Triangle with vertices at $(x_{i},y_{i})$ for $i=1,2,3$ and center at $(x,y)$
Write $x_{i}=y+d_{i}\cos\theta_{i}$ and $y_{i}=y+d_{i}\sin\theta_{i}$
$d_{i}=\left(\left(x-x_{i}\right)^{2}+\left(y-y_{i}\right)^{2}\right)^{1/2}$
$\tan\theta_{i}=\frac{y-y_{i}}{x-x_{i}}$
Minimize $\sum_{i=1}^{3}d_{i}$:
$\frac{d\;}{dx}\sum_{i=1}^{3}d_{i} =\sum_{i=1}^{3}\frac{x-x_{i}}{d_{i}}=\sum_{i=1}^{3}\cos\theta_{i}$
$\frac{d\;}{dy}\sum_{i=1}^{3}d_{i} =\sum_{i=1}^{3}\frac{y-y_{i}}{d_{i}}=\sum_{i=1}^{3}\sin\theta_{i}$
So $\sum_{i=1}^{3}\cos\theta_{i}=\sum_{i=1}^{3}\sin\theta_{i}=0$,
and the $\theta_{i}$ differ by $\pm2\pi/3$

Cuchulainn
Topic Author
Posts: 61589
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

Is this how you solve the problem?
$S = d_1 + d_2 + d_3 = \sqrt{x^2+y^2} + \sqrt{(x-a)^2+y^2} + \sqrt{(x-d)^2+(y-h)^2}$
$\frac{\partial S}{\partial x} = 0$
$\frac{\partial S}{\partial y} = 0$

triangle.png

(On the drawing from the previous posts I tried to explain the physical analogy which explains the geometric solution from wikipedia.)
What happens when $d < 0$ and $d > a$ cases? i.e. the Fermat points should be (0,0) and and (a,0), respectively, yes? Does your formula need modification?

http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

katastrofa
Posts: 8975
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: Extremes

Oh, yes (I've signalled it in the drawing - in case lovenatalya asked). The derivatives of S won't zero anymore, so you'd need to solve a constraint optimisation problem by adding the Lagrange multipliers. It's probably faster to reparametrise the problem, though: go along the triangle sides (d_i and d_j lie on the side and add up to its length) and find the minimum d_k.

katastrofa
Posts: 8975
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

### Re: Extremes

Cuchulainn
Topic Author
Posts: 61589
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

Oh, yes (I've signalled it in the drawing - in case lovenatalya asked). The derivatives of S won't zero anymore, so you'd need to solve a constraint optimisation problem by adding the Lagrange multipliers. It's probably faster to reparametrise the problem, though: go along the triangle sides (d_i and d_j lie on the side and add up to its length) and find the minimum d_k.
Strictly speaking, we need to us the sides of the triangle as constraints, i.e. each side can be written as
$ax + by + c <= 0$ (3 of these)
Indeed, 3 Lagrange multipliers map constrained optimisation problem to an unconstrained one.
Plan B is is to use penalty method which is easier to apply (just choose a big penalty term).

In my godzilla solver I use the triangle's bounding box as the constraint, maybe a risk of the left-over space?

http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

ppauper
Posts: 70239
Joined: November 15th, 2001, 1:29 pm

### Re: Extremes

cuch, your pic shows up as a sign that says "no hotlinking"

Cuchulainn
Topic Author
Posts: 61589
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Re: Extremes

cuch, your pic shows up as a sign that says "no hotlinking"
I used the triangle's bounding box as a rough guide to constraints. Hopefully the minimum doesn't end up in the gap.
Last edited by Cuchulainn on June 26th, 2018, 1:40 pm, edited 1 time in total.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...

GZIP: On