Serving the Quantitative Finance Community

 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 17th, 2018, 6:34 pm

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
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 17th, 2018, 7:10 pm

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 :-)
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 17th, 2018, 8:08 pm

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.
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 18th, 2018, 7:54 am

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.
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 18th, 2018, 9:45 am

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
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 18th, 2018, 11:26 am

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".
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 18th, 2018, 12:56 pm

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.)
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 18th, 2018, 1:23 pm

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
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 18th, 2018, 2:00 pm

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[$]
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 18th, 2018, 7:27 pm

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?

Image
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 19th, 2018, 12:14 pm

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.
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 22nd, 2018, 1:09 am

 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 22nd, 2018, 10:46 am

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?

Image
 
User avatar
ppauper
Posts: 11729
Joined: November 15th, 2001, 1:29 pm

Re: Extremes

June 22nd, 2018, 3:14 pm

cuch, your pic shows up as a sign that says "no hotlinking"
 
User avatar
Cuchulainn
Topic Author
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Extremes

June 23rd, 2018, 2:06 pm

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.