Mixing
Curve minimising distance between two points in $ mathbbR^2 $ with a circular obstacle
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Minimisation functional problem
$$ min_y int _ (-beta,0)^Asqrt(doty(x))^2+1 dx mbox such that x^2+y(x)^2geq R^2$$
Scaling everything, take $R=1, beta >1$
Starting at $(-beta,0)$ find the path with minimum distance taking you to $A=(x_0,y_0), y_0 geq 0 mbox wlog $ without going through the interior of the unit circle.
Let $ alpha $ be the angle between the x axis and the line segment joining $ (-beta,0)$ with $ A $. If $ sin alpha geq 1/ beta $, then the curve is that line segment.
You can try the problem with a square, a rhombus any compact set you like. In fact:
Generalisation: find a curve that minimises the distance between two points $A(x_A,y_A)$ and $ B(x_B,y_B) $ that doesn't go through some obstacles.
The obstacles are open bounded sets $B_i$, with the curve lying in $ mathbbR ^2 setminus cup_i=1^infty B_i$.
My difficulty: I am not familiar with inequality constraints. Any advice on how to tackle these problems either analytically or computationally would be appreciated.
calculus-of-variations
asked Jul 22 at 13:47
George Aliatimis
2110
add a comment |Â
up vote
1
down vote
favorite
Minimisation functional problem
$$ min_y int _ (-beta,0)^Asqrt(doty(x))^2+1 dx mbox such that x^2+y(x)^2geq R^2$$
Scaling everything, take $R=1, beta >1$
Starting at $(-beta,0)$ find the path with minimum distance taking you to $A=(x_0,y_0), y_0 geq 0 mbox wlog $ without going through the interior of the unit circle.
Let $ alpha $ be the angle between the x axis and the line segment joining $ (-beta,0)$ with $ A $. If $ sin alpha geq 1/ beta $, then the curve is that line segment.
You can try the problem with a square, a rhombus any compact set you like. In fact:
Generalisation: find a curve that minimises the distance between two points $A(x_A,y_A)$ and $ B(x_B,y_B) $ that doesn't go through some obstacles.
The obstacles are open bounded sets $B_i$, with the curve lying in $ mathbbR ^2 setminus cup_i=1^infty B_i$.
My difficulty: I am not familiar with inequality constraints. Any advice on how to tackle these problems either analytically or computationally would be appreciated.
calculus-of-variations
asked Jul 22 at 13:47
George Aliatimis
2110
4
Draw a line through the two points. If it avoids the circle, you're done. Else, the shortest path lies on the side of the circle on which the line passes the centre; it consists of the tangents from the points to the circle, up to the point of tangency, and the arc on the circle between the points of tangency.
– joriki
Jul 22 at 16:45
You need a $ge$ in the inequality constraint or you won't attain the minimum described in the above comment
– Calvin Khor
Jul 22 at 16:54
Thanks for your answer @joriki !
– George Aliatimis
Jul 22 at 17:14
I edited my question @Calvin Khor
– George Aliatimis
Jul 22 at 17:15
Tightening a string seems to be a good way of dealing with those problems. Can it be made more rigorous?
– George Aliatimis
Jul 22 at 17:17
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Minimisation functional problem
$$ min_y int _ (-beta,0)^Asqrt(doty(x))^2+1 dx mbox such that x^2+y(x)^2geq R^2$$
Scaling everything, take $R=1, beta >1$
Starting at $(-beta,0)$ find the path with minimum distance taking you to $A=(x_0,y_0), y_0 geq 0 mbox wlog $ without going through the interior of the unit circle.
Let $ alpha $ be the angle between the x axis and the line segment joining $ (-beta,0)$ with $ A $. If $ sin alpha geq 1/ beta $, then the curve is that line segment.
You can try the problem with a square, a rhombus any compact set you like. In fact:
Generalisation: find a curve that minimises the distance between two points $A(x_A,y_A)$ and $ B(x_B,y_B) $ that doesn't go through some obstacles.
The obstacles are open bounded sets $B_i$, with the curve lying in $ mathbbR ^2 setminus cup_i=1^infty B_i$.
My difficulty: I am not familiar with inequality constraints. Any advice on how to tackle these problems either analytically or computationally would be appreciated.
calculus-of-variations
asked Jul 22 at 13:47
George Aliatimis
2110
Minimisation functional problem
$$ min_y int _ (-beta,0)^Asqrt(doty(x))^2+1 dx mbox such that x^2+y(x)^2geq R^2$$
Scaling everything, take $R=1, beta >1$
Starting at $(-beta,0)$ find the path with minimum distance taking you to $A=(x_0,y_0), y_0 geq 0 mbox wlog $ without going through the interior of the unit circle.
Let $ alpha $ be the angle between the x axis and the line segment joining $ (-beta,0)$ with $ A $. If $ sin alpha geq 1/ beta $, then the curve is that line segment.
You can try the problem with a square, a rhombus any compact set you like. In fact:
Generalisation: find a curve that minimises the distance between two points $A(x_A,y_A)$ and $ B(x_B,y_B) $ that doesn't go through some obstacles.
The obstacles are open bounded sets $B_i$, with the curve lying in $ mathbbR ^2 setminus cup_i=1^infty B_i$.
My difficulty: I am not familiar with inequality constraints. Any advice on how to tackle these problems either analytically or computationally would be appreciated.
calculus-of-variations
asked Jul 22 at 13:47
George Aliatimis
2110
edited Jul 22 at 17:35
asked Jul 22 at 13:47
George Aliatimis
2110
asked Jul 22 at 13:47
George Aliatimis
2110
asked Jul 22 at 13:47
George Aliatimis
2110
2110
4
Draw a line through the two points. If it avoids the circle, you're done. Else, the shortest path lies on the side of the circle on which the line passes the centre; it consists of the tangents from the points to the circle, up to the point of tangency, and the arc on the circle between the points of tangency.
– joriki
Jul 22 at 16:45
You need a $ge$ in the inequality constraint or you won't attain the minimum described in the above comment
– Calvin Khor
Jul 22 at 16:54
Thanks for your answer @joriki !
– George Aliatimis
Jul 22 at 17:14
I edited my question @Calvin Khor
– George Aliatimis
Jul 22 at 17:15
Tightening a string seems to be a good way of dealing with those problems. Can it be made more rigorous?
– George Aliatimis
Jul 22 at 17:17
add a comment |Â
4
Draw a line through the two points. If it avoids the circle, you're done. Else, the shortest path lies on the side of the circle on which the line passes the centre; it consists of the tangents from the points to the circle, up to the point of tangency, and the arc on the circle between the points of tangency.
– joriki
Jul 22 at 16:45
You need a $ge$ in the inequality constraint or you won't attain the minimum described in the above comment
– Calvin Khor
Jul 22 at 16:54
Thanks for your answer @joriki !
– George Aliatimis
Jul 22 at 17:14
I edited my question @Calvin Khor
– George Aliatimis
Jul 22 at 17:15
Tightening a string seems to be a good way of dealing with those problems. Can it be made more rigorous?
– George Aliatimis
Jul 22 at 17:17
4
4
Draw a line through the two points. If it avoids the circle, you're done. Else, the shortest path lies on the side of the circle on which the line passes the centre; it consists of the tangents from the points to the circle, up to the point of tangency, and the arc on the circle between the points of tangency.
– joriki
Jul 22 at 16:45
Draw a line through the two points. If it avoids the circle, you're done. Else, the shortest path lies on the side of the circle on which the line passes the centre; it consists of the tangents from the points to the circle, up to the point of tangency, and the arc on the circle between the points of tangency.
– joriki
Jul 22 at 16:45
You need a $ge$ in the inequality constraint or you won't attain the minimum described in the above comment
– Calvin Khor
Jul 22 at 16:54
You need a $ge$ in the inequality constraint or you won't attain the minimum described in the above comment
– Calvin Khor
Jul 22 at 16:54
Thanks for your answer @joriki !
– George Aliatimis
Jul 22 at 17:14
Thanks for your answer @joriki !
– George Aliatimis
Jul 22 at 17:14
I edited my question @Calvin Khor
– George Aliatimis
Jul 22 at 17:15
I edited my question @Calvin Khor
– George Aliatimis
Jul 22 at 17:15
Tightening a string seems to be a good way of dealing with those problems. Can it be made more rigorous?
– George Aliatimis
Jul 22 at 17:17
Tightening a string seems to be a good way of dealing with those problems. Can it be made more rigorous?
– George Aliatimis
Jul 22 at 17:17
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
0
down vote
Considering the problem
$$
min_y int _ (-beta,0)^Aleft(sqrt(doty(x))^2+1right) dx mbox such that x^2+y^2ge R^2
$$
we will try to give an informal introduction to the handling of this problem with the help of slack variables $epsilon(x)$ and lagrange multipliers $lambda_1(x),lambda_2(x),lambda_3(x)$
First, the inequality is converted into an equivalent equality with the contribution of the slack variable
$$
x^2+y^2 ge R^2 equiv x^2+y^2-R^2-epsilon^2(x) = 0
$$
and then the main functional reads
$$
F(x,z,y,y',epsilon,epsilon')=sqrtz^2+1+lambda_1(x^2+y^2-R^2-epsilon^2)+lambda_2(2x+2y -2epsilon epsilon'z)+lambda_3(z-y')
$$
Note the inclusion as restriction also the derivative of $x^2+y^2-R^2-epsilon^2=0$
Now applying the Euler-Lagrange conditions for stationarity we have
$$
F_y-left(F_y'right)'=2lambda_1y+2lambda_2 z+lambda_3'=0\
F_z-left(F_z'right)'=2lambda_2y+fraczsqrtz^2+1+lambda_3 = 0\
F_epsilon-left(F_epsilon'right)'=2epsilon(lambda'_2-lambda_1)=0
$$
Assuming $epsilon(x) ne 0$ we have $lambda_1=lambda'_2$ and the equations reduce to
$$
(2lambda_2 y)'+lambda'_3=0Rightarrow 2lambda_2 y +lambda_3 = C_1
$$
and then
$$
2lambda_2 y +lambda_3 = C_1\
2lambda_2y+fracy'sqrt(y')^2+1+lambda_3 = 0
$$
or
$$
C_1 = fracy'sqrt(y')^2+1
$$
with solution
$$
y = pm fracC_1 xsqrt1-C_1^2+C_2
$$
Concluding, for $epsilon(x)ne 0;$ the solutions are $y = y^0_i+m_i(x-x_0^i);$ for $iin 1,2$
The solution for $epsilon(x) = 0;$ involves the angular circle segment.
answered Jul 22 at 18:34
Cesareo
5,7252412
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Considering the problem
$$
min_y int _ (-beta,0)^Aleft(sqrt(doty(x))^2+1right) dx mbox such that x^2+y^2ge R^2
$$
we will try to give an informal introduction to the handling of this problem with the help of slack variables $epsilon(x)$ and lagrange multipliers $lambda_1(x),lambda_2(x),lambda_3(x)$
First, the inequality is converted into an equivalent equality with the contribution of the slack variable
$$
x^2+y^2 ge R^2 equiv x^2+y^2-R^2-epsilon^2(x) = 0
$$
and then the main functional reads
$$
F(x,z,y,y',epsilon,epsilon')=sqrtz^2+1+lambda_1(x^2+y^2-R^2-epsilon^2)+lambda_2(2x+2y -2epsilon epsilon'z)+lambda_3(z-y')
$$
Note the inclusion as restriction also the derivative of $x^2+y^2-R^2-epsilon^2=0$
Now applying the Euler-Lagrange conditions for stationarity we have
$$
F_y-left(F_y'right)'=2lambda_1y+2lambda_2 z+lambda_3'=0\
F_z-left(F_z'right)'=2lambda_2y+fraczsqrtz^2+1+lambda_3 = 0\
F_epsilon-left(F_epsilon'right)'=2epsilon(lambda'_2-lambda_1)=0
$$
Assuming $epsilon(x) ne 0$ we have $lambda_1=lambda'_2$ and the equations reduce to
$$
(2lambda_2 y)'+lambda'_3=0Rightarrow 2lambda_2 y +lambda_3 = C_1
$$
and then
$$
2lambda_2 y +lambda_3 = C_1\
2lambda_2y+fracy'sqrt(y')^2+1+lambda_3 = 0
$$
or
$$
C_1 = fracy'sqrt(y')^2+1
$$
with solution
$$
y = pm fracC_1 xsqrt1-C_1^2+C_2
$$
Concluding, for $epsilon(x)ne 0;$ the solutions are $y = y^0_i+m_i(x-x_0^i);$ for $iin 1,2$
The solution for $epsilon(x) = 0;$ involves the angular circle segment.
answered Jul 22 at 18:34
Cesareo
5,7252412
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
add a comment |Â
up vote
0
down vote
Considering the problem
$$
min_y int _ (-beta,0)^Aleft(sqrt(doty(x))^2+1right) dx mbox such that x^2+y^2ge R^2
$$
we will try to give an informal introduction to the handling of this problem with the help of slack variables $epsilon(x)$ and lagrange multipliers $lambda_1(x),lambda_2(x),lambda_3(x)$
First, the inequality is converted into an equivalent equality with the contribution of the slack variable
$$
x^2+y^2 ge R^2 equiv x^2+y^2-R^2-epsilon^2(x) = 0
$$
and then the main functional reads
$$
F(x,z,y,y',epsilon,epsilon')=sqrtz^2+1+lambda_1(x^2+y^2-R^2-epsilon^2)+lambda_2(2x+2y -2epsilon epsilon'z)+lambda_3(z-y')
$$
Note the inclusion as restriction also the derivative of $x^2+y^2-R^2-epsilon^2=0$
Now applying the Euler-Lagrange conditions for stationarity we have
$$
F_y-left(F_y'right)'=2lambda_1y+2lambda_2 z+lambda_3'=0\
F_z-left(F_z'right)'=2lambda_2y+fraczsqrtz^2+1+lambda_3 = 0\
F_epsilon-left(F_epsilon'right)'=2epsilon(lambda'_2-lambda_1)=0
$$
Assuming $epsilon(x) ne 0$ we have $lambda_1=lambda'_2$ and the equations reduce to
$$
(2lambda_2 y)'+lambda'_3=0Rightarrow 2lambda_2 y +lambda_3 = C_1
$$
and then
$$
2lambda_2 y +lambda_3 = C_1\
2lambda_2y+fracy'sqrt(y')^2+1+lambda_3 = 0
$$
or
$$
C_1 = fracy'sqrt(y')^2+1
$$
with solution
$$
y = pm fracC_1 xsqrt1-C_1^2+C_2
$$
Concluding, for $epsilon(x)ne 0;$ the solutions are $y = y^0_i+m_i(x-x_0^i);$ for $iin 1,2$
The solution for $epsilon(x) = 0;$ involves the angular circle segment.
answered Jul 22 at 18:34
Cesareo
5,7252412
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Considering the problem
$$
min_y int _ (-beta,0)^Aleft(sqrt(doty(x))^2+1right) dx mbox such that x^2+y^2ge R^2
$$
we will try to give an informal introduction to the handling of this problem with the help of slack variables $epsilon(x)$ and lagrange multipliers $lambda_1(x),lambda_2(x),lambda_3(x)$
First, the inequality is converted into an equivalent equality with the contribution of the slack variable
$$
x^2+y^2 ge R^2 equiv x^2+y^2-R^2-epsilon^2(x) = 0
$$
and then the main functional reads
$$
F(x,z,y,y',epsilon,epsilon')=sqrtz^2+1+lambda_1(x^2+y^2-R^2-epsilon^2)+lambda_2(2x+2y -2epsilon epsilon'z)+lambda_3(z-y')
$$
Note the inclusion as restriction also the derivative of $x^2+y^2-R^2-epsilon^2=0$
Now applying the Euler-Lagrange conditions for stationarity we have
$$
F_y-left(F_y'right)'=2lambda_1y+2lambda_2 z+lambda_3'=0\
F_z-left(F_z'right)'=2lambda_2y+fraczsqrtz^2+1+lambda_3 = 0\
F_epsilon-left(F_epsilon'right)'=2epsilon(lambda'_2-lambda_1)=0
$$
Assuming $epsilon(x) ne 0$ we have $lambda_1=lambda'_2$ and the equations reduce to
$$
(2lambda_2 y)'+lambda'_3=0Rightarrow 2lambda_2 y +lambda_3 = C_1
$$
and then
$$
2lambda_2 y +lambda_3 = C_1\
2lambda_2y+fracy'sqrt(y')^2+1+lambda_3 = 0
$$
or
$$
C_1 = fracy'sqrt(y')^2+1
$$
with solution
$$
y = pm fracC_1 xsqrt1-C_1^2+C_2
$$
Concluding, for $epsilon(x)ne 0;$ the solutions are $y = y^0_i+m_i(x-x_0^i);$ for $iin 1,2$
The solution for $epsilon(x) = 0;$ involves the angular circle segment.
answered Jul 22 at 18:34
Cesareo
5,7252412
Considering the problem
$$
min_y int _ (-beta,0)^Aleft(sqrt(doty(x))^2+1right) dx mbox such that x^2+y^2ge R^2
$$
we will try to give an informal introduction to the handling of this problem with the help of slack variables $epsilon(x)$ and lagrange multipliers $lambda_1(x),lambda_2(x),lambda_3(x)$
First, the inequality is converted into an equivalent equality with the contribution of the slack variable
$$
x^2+y^2 ge R^2 equiv x^2+y^2-R^2-epsilon^2(x) = 0
$$
and then the main functional reads
$$
F(x,z,y,y',epsilon,epsilon')=sqrtz^2+1+lambda_1(x^2+y^2-R^2-epsilon^2)+lambda_2(2x+2y -2epsilon epsilon'z)+lambda_3(z-y')
$$
Note the inclusion as restriction also the derivative of $x^2+y^2-R^2-epsilon^2=0$
Now applying the Euler-Lagrange conditions for stationarity we have
$$
F_y-left(F_y'right)'=2lambda_1y+2lambda_2 z+lambda_3'=0\
F_z-left(F_z'right)'=2lambda_2y+fraczsqrtz^2+1+lambda_3 = 0\
F_epsilon-left(F_epsilon'right)'=2epsilon(lambda'_2-lambda_1)=0
$$
Assuming $epsilon(x) ne 0$ we have $lambda_1=lambda'_2$ and the equations reduce to
$$
(2lambda_2 y)'+lambda'_3=0Rightarrow 2lambda_2 y +lambda_3 = C_1
$$
and then
$$
2lambda_2 y +lambda_3 = C_1\
2lambda_2y+fracy'sqrt(y')^2+1+lambda_3 = 0
$$
or
$$
C_1 = fracy'sqrt(y')^2+1
$$
with solution
$$
y = pm fracC_1 xsqrt1-C_1^2+C_2
$$
Concluding, for $epsilon(x)ne 0;$ the solutions are $y = y^0_i+m_i(x-x_0^i);$ for $iin 1,2$
The solution for $epsilon(x) = 0;$ involves the angular circle segment.
answered Jul 22 at 18:34
Cesareo
5,7252412
edited Jul 26 at 10:13
answered Jul 22 at 18:34
Cesareo
5,7252412
answered Jul 22 at 18:34
Cesareo
5,7252412
answered Jul 22 at 18:34
Cesareo
5,7252412
5,7252412
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
add a comment |Â
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I am applying the variations to a family of functions $y_*$. The first integral can be presented as two boundary conditions which satisfy the line functions. This is only a non rigorous presentation, handling the functional tools and the calculus of variations. It is not my purpose to develop a full theory about the theme. Regards.
– Cesareo
Jul 22 at 19:40
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
@GeorgeAliatimis I hope now it looks better. I am intending to introduce some ideas about how to handle state inequality restrictions.
– Cesareo
Jul 26 at 10:20
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859420%2fcurve-minimising-distance-between-two-points-in-mathbbr2-with-a-circular%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
4
Draw a line through the two points. If it avoids the circle, you're done. Else, the shortest path lies on the side of the circle on which the line passes the centre; it consists of the tangents from the points to the circle, up to the point of tangency, and the arc on the circle between the points of tangency.
– joriki
Jul 22 at 16:45
You need a $ge$ in the inequality constraint or you won't attain the minimum described in the above comment
– Calvin Khor
Jul 22 at 16:54
Thanks for your answer @joriki !
– George Aliatimis
Jul 22 at 17:14
I edited my question @Calvin Khor
– George Aliatimis
Jul 22 at 17:15
Tightening a string seems to be a good way of dealing with those problems. Can it be made more rigorous?
– George Aliatimis
Jul 22 at 17:17