SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
ppauper
Posts: 70239
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: 8621
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: 60753
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
User avatar
Cuchulainn
Topic Author
Posts: 60753
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
User avatar
ppauper
Posts: 70239
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: 60753
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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".
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
User avatar
katastrofa
Posts: 8621
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
triangle.png (17.22 KiB) Viewed 1880 times
(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: 70239
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: 70239
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: 60753
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
User avatar
katastrofa
Posts: 8621
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: 8621
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Extremes

June 22nd, 2018, 1:09 am

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

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
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
 
User avatar
ppauper
Posts: 70239
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: 60753
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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.
http://www.datasimfinancial.com
http://www.datasim.nl

Approach your problem from the right end and begin with the answers. Then one day, perhaps you will find the final question..
R. van Gulik
ABOUT WILMOTT

PW by JB

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


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

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


GZIP: On