Skip to main content
Post Closed as "Not suitable for this site" by Alex M., user44191, Ben McKay, Hollis Williams, Bugs Bunny
added 8 characters in body
Source Link
Sven
  • 11
  • 2

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$$D(A1,M_{x,y})= \sqrt{(M_x-A1_x)^2+(M_{y}-A1_y)^2}$$ $$D(M_{x,y}, A2)= \sqrt{(A2_x-M_x)^2+(A2_y-M_y)^2}$$

$$D(B1,M_{x,y})= \sqrt{(M_x-B1_x)^2+(M_y-B1_y)^2}$$ $$D(M_{x,y}, B2)= \sqrt{(B2_x-M_x)^2+(B2_y-M_y)^2}$$

and the following waiting time $$W(M_{x,y},A1,B1) = \max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$$

Then the the objective function would be $$Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$$M_\text{Middle}= \left(\frac{A1_x+B1_x}2, \frac{A1_y+B1_y}2\right)$$

Slope $m$ of equation $M(y)$

$$m=-\frac{B1_x-A1_x}{B1_y-A1_y}$$

Using $M_\text{Middle}$ and $m$ in $M(y)$ I get for $b$

$$b = \frac{A1_y+B1_y}2+\frac{B1_x-A1_x}{B1_y-A1_y}\frac{A1_x+B1_x}2 = \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

The final equation should be:

$$M(y) = -\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

Not I can insert this equation into $Z$ and would get

\begin{align} Z = {} & \sqrt{(M_x-A1_x)^2+ \left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-A1_y\right)^2} \\[6pt] & {} + \sqrt{(A2_x-M_x)^2+\left(A2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \\[6pt] & {} + \sqrt{(M_x-B1_x)^2+\left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-B1_y\right)^2} \\[6pt] & {} + \sqrt{(B2_x-M_x)^2+\left(B2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \end{align}\begin{align} Z = {} & \sqrt{(M_x-A1_x)^2+ \left(-\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-A1_y\right)^2} \\[6pt] & {} + \sqrt{(A2_x-M_x)^2+\left(A2_y--\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \\[6pt] & {} + \sqrt{(M_x-B1_x)^2+\left(-\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-B1_y\right)^2} \\[6pt] & {} + \sqrt{(B2_x-M_x)^2+\left(B2_y--\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \end{align}

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$$D(A1,M_{x,y})= \sqrt{(M_x-A1_x)^2+(M_{y}-A1_y)^2}$$ $$D(M_{x,y}, A2)= \sqrt{(A2_x-M_x)^2+(A2_y-M_y)^2}$$

$$D(B1,M_{x,y})= \sqrt{(M_x-B1_x)^2+(M_y-B1_y)^2}$$ $$D(M_{x,y}, B2)= \sqrt{(B2_x-M_x)^2+(B2_y-M_y)^2}$$

and the following waiting time $$W(M_{x,y},A1,B1) = \max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$$

Then the the objective function would be $$Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$$M_\text{Middle}= \left(\frac{A1_x+B1_x}2, \frac{A1_y+B1_y}2\right)$$

Slope $m$ of equation $M(y)$

$$m=-\frac{B1_x-A1_x}{B1_y-A1_y}$$

Using $M_\text{Middle}$ and $m$ in $M(y)$ I get for $b$

$$b = \frac{A1_y+B1_y}2+\frac{B1_x-A1_x}{B1_y-A1_y}\frac{A1_x+B1_x}2 = \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

The final equation should be:

$$M(y) = -\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

Not I can insert this equation into $Z$ and would get

\begin{align} Z = {} & \sqrt{(M_x-A1_x)^2+ \left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-A1_y\right)^2} \\[6pt] & {} + \sqrt{(A2_x-M_x)^2+\left(A2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \\[6pt] & {} + \sqrt{(M_x-B1_x)^2+\left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-B1_y\right)^2} \\[6pt] & {} + \sqrt{(B2_x-M_x)^2+\left(B2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \end{align}

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$$D(A1,M_{x,y})= \sqrt{(M_x-A1_x)^2+(M_{y}-A1_y)^2}$$ $$D(M_{x,y}, A2)= \sqrt{(A2_x-M_x)^2+(A2_y-M_y)^2}$$

$$D(B1,M_{x,y})= \sqrt{(M_x-B1_x)^2+(M_y-B1_y)^2}$$ $$D(M_{x,y}, B2)= \sqrt{(B2_x-M_x)^2+(B2_y-M_y)^2}$$

and the following waiting time $$W(M_{x,y},A1,B1) = \max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$$

Then the the objective function would be $$Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$$M_\text{Middle}= \left(\frac{A1_x+B1_x}2, \frac{A1_y+B1_y}2\right)$$

Slope $m$ of equation $M(y)$

$$m=-\frac{B1_x-A1_x}{B1_y-A1_y}$$

Using $M_\text{Middle}$ and $m$ in $M(y)$ I get for $b$

$$b = \frac{A1_y+B1_y}2+\frac{B1_x-A1_x}{B1_y-A1_y}\frac{A1_x+B1_x}2 = \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

The final equation should be:

$$M(y) = -\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

Not I can insert this equation into $Z$ and would get

\begin{align} Z = {} & \sqrt{(M_x-A1_x)^2+ \left(-\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-A1_y\right)^2} \\[6pt] & {} + \sqrt{(A2_x-M_x)^2+\left(A2_y--\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \\[6pt] & {} + \sqrt{(M_x-B1_x)^2+\left(-\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-B1_y\right)^2} \\[6pt] & {} + \sqrt{(B2_x-M_x)^2+\left(B2_y--\frac{B1_x-A1_x}{B1_y-A1_y}M_x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \end{align}

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

deleted 80 characters in body; edited title
Source Link
Michael Hardy
  • 1
  • 12
  • 85
  • 126

Proofing Proving convexity of total distance between two parties with one meeting point

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$D(A1,M_{x,y})= \sqrt{(M_{x}-A1_{x})^{2}+(M_{y}-A1_{y})^{2}}$$$D(A1,M_{x,y})= \sqrt{(M_x-A1_x)^2+(M_{y}-A1_y)^2}$$ $D(M_{x,y}, A2)= \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}-M_{y})^{2}}$$$D(M_{x,y}, A2)= \sqrt{(A2_x-M_x)^2+(A2_y-M_y)^2}$$

$D(B1,M_{x,y})= \sqrt{(M_{x}-B1_{x})^{2}+(M_{y}-B1_{y})^{2}}$$$D(B1,M_{x,y})= \sqrt{(M_x-B1_x)^2+(M_y-B1_y)^2}$$ $D(M_{x,y}, B2)= \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}-M_{y})^{2}}$$$D(M_{x,y}, B2)= \sqrt{(B2_x-M_x)^2+(B2_y-M_y)^2}$$

and the following waiting time $W(M_{x,y},A1,B1) = max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$$$W(M_{x,y},A1,B1) = \max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$$

Then the the objective function would be $Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$$$Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$M_{Middle}= (\frac{A1_{x}+B1_{x}}{2}, \frac{A1_{y}+B1_{y}}{2})$$$M_\text{Middle}= \left(\frac{A1_x+B1_x}2, \frac{A1_y+B1_y}2\right)$$

Slope m$m$ of equation $M(y)$

$m=-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}$$$m=-\frac{B1_x-A1_x}{B1_y-A1_y}$$

Using $M_{Middle}$$M_\text{Middle}$ and $m$ in $M(y)$ I get for b$b$

$b = \frac{A1_{y}+B1_{y}}{2}+\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}\frac{A1_{x}+B1_{x}}{2} = \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$$$b = \frac{A1_y+B1_y}2+\frac{B1_x-A1_x}{B1_y-A1_y}\frac{A1_x+B1_x}2 = \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

The final equation should be:

$M(y) = -\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$$$M(y) = -\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

Not I can insert this equation into $Z$ and would get

$Z= \sqrt{(M_{x}-A1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-A1_{y})^{2}}+ \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}+ \sqrt{(M_{x}-B1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-B1_{y})^{2}}+ \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}$\begin{align} Z = {} & \sqrt{(M_x-A1_x)^2+ \left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-A1_y\right)^2} \\[6pt] & {} + \sqrt{(A2_x-M_x)^2+\left(A2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \\[6pt] & {} + \sqrt{(M_x-B1_x)^2+\left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-B1_y\right)^2} \\[6pt] & {} + \sqrt{(B2_x-M_x)^2+\left(B2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \end{align}

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Proofing convexity of total distance between two parties with one meeting point

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$D(A1,M_{x,y})= \sqrt{(M_{x}-A1_{x})^{2}+(M_{y}-A1_{y})^{2}}$ $D(M_{x,y}, A2)= \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}-M_{y})^{2}}$

$D(B1,M_{x,y})= \sqrt{(M_{x}-B1_{x})^{2}+(M_{y}-B1_{y})^{2}}$ $D(M_{x,y}, B2)= \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}-M_{y})^{2}}$

and the following waiting time $W(M_{x,y},A1,B1) = max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$

Then the the objective function would be $Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$M_{Middle}= (\frac{A1_{x}+B1_{x}}{2}, \frac{A1_{y}+B1_{y}}{2})$

Slope m of equation $M(y)$

$m=-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}$

Using $M_{Middle}$ and $m$ in $M(y)$ I get for b

$b = \frac{A1_{y}+B1_{y}}{2}+\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}\frac{A1_{x}+B1_{x}}{2} = \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$

The final equation should be:

$M(y) = -\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$

Not I can insert this equation into $Z$ and would get

$Z= \sqrt{(M_{x}-A1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-A1_{y})^{2}}+ \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}+ \sqrt{(M_{x}-B1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-B1_{y})^{2}}+ \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}$

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Proving convexity of total distance between two parties with one meeting point

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$$D(A1,M_{x,y})= \sqrt{(M_x-A1_x)^2+(M_{y}-A1_y)^2}$$ $$D(M_{x,y}, A2)= \sqrt{(A2_x-M_x)^2+(A2_y-M_y)^2}$$

$$D(B1,M_{x,y})= \sqrt{(M_x-B1_x)^2+(M_y-B1_y)^2}$$ $$D(M_{x,y}, B2)= \sqrt{(B2_x-M_x)^2+(B2_y-M_y)^2}$$

and the following waiting time $$W(M_{x,y},A1,B1) = \max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$$

Then the the objective function would be $$Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$$M_\text{Middle}= \left(\frac{A1_x+B1_x}2, \frac{A1_y+B1_y}2\right)$$

Slope $m$ of equation $M(y)$

$$m=-\frac{B1_x-A1_x}{B1_y-A1_y}$$

Using $M_\text{Middle}$ and $m$ in $M(y)$ I get for $b$

$$b = \frac{A1_y+B1_y}2+\frac{B1_x-A1_x}{B1_y-A1_y}\frac{A1_x+B1_x}2 = \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

The final equation should be:

$$M(y) = -\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}$$

Not I can insert this equation into $Z$ and would get

\begin{align} Z = {} & \sqrt{(M_x-A1_x)^2+ \left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-A1_y\right)^2} \\[6pt] & {} + \sqrt{(A2_x-M_x)^2+\left(A2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \\[6pt] & {} + \sqrt{(M_x-B1_x)^2+\left(-\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}-B1_y\right)^2} \\[6pt] & {} + \sqrt{(B2_x-M_x)^2+\left(B2_y--\frac{B1_x-A1_x}{B1_y-A1_y}x+ \frac{B1_y^2-A1_y^2+B1_x^2-A1_x^2}{2(B1_y-A1_y)}\right)^2} \end{align}

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

added 1472 characters in body
Source Link
Sven
  • 11
  • 2

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates (A1$A1$, A2$A2$, B1$B1$, B2$B2$, M$M_{x,y}$) whereas M$M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from A1$A1$ to A2 Person$A2$

Person B wants to go from B1$B1$ to B2 But$B2$

But Person A needs to meet Person B at a variable meeting point M(x,y)$M_{x,y}$

Let D(C1,C2)$D(C1,C2)$ be the Euclidean distance between two coordinates C1$C1$ and C2$C2$. Let W(M,A1,B1)

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point M$M$, depending on the location of A1$A1$ and B1$B1$

Then we have the following distances

$D(A1,M_{x,y})= \sqrt{(M_{x}-A1_{x})^{2}+(M_{y}-A1_{y})^{2}}$ $D(M_{x,y}, A2)= \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}-M_{y})^{2}}$

$D(B1,M_{x,y})= \sqrt{(M_{x}-B1_{x})^{2}+(M_{y}-B1_{y})^{2}}$ $D(M_{x,y}, B2)= \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}-M_{y})^{2}}$

and the following waiting time $W(M_{x,y},A1,B1) = max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$

Then the the objective function would be Z = D(A1,M(x,y))+ D(M(x,y),A2) + D(B1,M(x,y)) + D(M(x,y),B2) + W(M(x,y),A1,B1)$Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$

I have plotted this asfor varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function W(M,A1,B1)$W(M_{x,y}$ is a max() function, depending on D(A1,M(x,y)) and D(B1,M(x,y)). This max functions which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation M(y) = mx + b$M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$M_{Middle}= (\frac{A1_{x}+B1_{x}}{2}, \frac{A1_{y}+B1_{y}}{2})$

Slope m of equation $M(y)$

$m=-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}$

Using $M_{Middle}$ and $m$ in $M(y)$ I get for b

$b = \frac{A1_{y}+B1_{y}}{2}+\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}\frac{A1_{x}+B1_{x}}{2} = \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$

The final equation should be:

$M(y) = -\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$

Not I can insert this equation into $Z$ and would get

Z = D(A1,M(y))+ D(M(y),A2) + D(B1,M(y)) + D(M,B2)$Z= \sqrt{(M_{x}-A1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-A1_{y})^{2}}+ \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}+ \sqrt{(M_{x}-B1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-B1_{y})^{2}}+ \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}$

Now I "only" need to build the first and second derivative. The problem I am struggling with is that each term D() is a root-term based on (coming from the Pythagoras Formula). Within that Formula I additionally have the Equation for meeting point M$M_{x}$. I cancould use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates (A1, A2, B1, B2, M) whereas M is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from A1 to A2 Person B wants to go from B1 to B2 But Person A needs to meet Person B at a variable meeting point M(x,y)

Let D(C1,C2) be the Euclidean distance between two coordinates C1 and C2. Let W(M,A1,B1) be the waiting time of A for B, or B for A (whoever arrives first/has the shorter distance) at meeting point M, depending on the location of A1 and B1

Then the the objective function would be Z = D(A1,M(x,y))+ D(M(x,y),A2) + D(B1,M(x,y)) + D(M(x,y),B2) + W(M(x,y),A1,B1)

I have plotted this as see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function W(M,A1,B1) is a max() function, depending on D(A1,M(x,y)) and D(B1,M(x,y)). This max functions is somewhat problematic (at least to me). My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation M(y) = mx + b. Not I can insert this equation into

Z = D(A1,M(y))+ D(M(y),A2) + D(B1,M(y)) + D(M,B2)

Now I "only" need to build the first and second derivative. The problem I am struggling with is that each term D() is a root-term (coming from the Pythagoras Formula). Within that Formula I additionally have the Equation for meeting point M. I can use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates ($A1$, $A2$, $B1$, $B2$, $M_{x,y}$) whereas $M_{x,y}$ is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from $A1$ to $A2$

Person B wants to go from $B1$ to $B2$

But Person A needs to meet Person B at a variable meeting point $M_{x,y}$

Let $D(C1,C2)$ be the Euclidean distance between two coordinates $C1$ and $C2$.

Let $W(M_{x,y},A1,B1)$ be the waiting time of Person A for Person B, or Person B for Person A (whoever arrives first/has the shorter distance) at meeting point $M$, depending on the location of $A1$ and $B1$

Then we have the following distances

$D(A1,M_{x,y})= \sqrt{(M_{x}-A1_{x})^{2}+(M_{y}-A1_{y})^{2}}$ $D(M_{x,y}, A2)= \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}-M_{y})^{2}}$

$D(B1,M_{x,y})= \sqrt{(M_{x}-B1_{x})^{2}+(M_{y}-B1_{y})^{2}}$ $D(M_{x,y}, B2)= \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}-M_{y})^{2}}$

and the following waiting time $W(M_{x,y},A1,B1) = max(D(A1,M_{x,y})-D(B1,M_{x,y}),D(B1,M_{x,y})-D(A1,M_{x,y}))$

Then the the objective function would be $Z = D(A1,M_{x,y}) + D(M_{x,y},A2) + D(B1,M_{x,y}) + D(M_{x,y},B2) + W(M,A1,B1)$

I have plotted this for varying coordinates for $M_{x,y}$ and see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function $W(M_{x,y}$ is a max() function, which is somewhat problematic (at least to me) for derivations. My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation $M(y) = mx + b$. I derive the equation in the following way:

Middle point between $A1$ and $B1$

$M_{Middle}= (\frac{A1_{x}+B1_{x}}{2}, \frac{A1_{y}+B1_{y}}{2})$

Slope m of equation $M(y)$

$m=-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}$

Using $M_{Middle}$ and $m$ in $M(y)$ I get for b

$b = \frac{A1_{y}+B1_{y}}{2}+\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}\frac{A1_{x}+B1_{x}}{2} = \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$

The final equation should be:

$M(y) = -\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}$

Not I can insert this equation into $Z$ and would get

$Z= \sqrt{(M_{x}-A1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-A1_{y})^{2}}+ \sqrt{(A2_{x}-M_{x})^{2}+(A2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}+ \sqrt{(M_{x}-B1_{x})^{2}+(-\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})}-B1_{y})^{2}}+ \sqrt{(B2_{x}-M_{x})^{2}+(B2_{y}--\frac{B1_{x}-A1_{x}}{B1_{y}-A1_{y}}x+ \frac{B1_{y}^2-A1_{y}^2+B1_{x}^2-A1_{x}^2}{2(B1_{y}-A1_{y})})^{2}}$

Now I "only" need to build the first and second derivative based on $M_{x}$. I could use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Source Link
Sven
  • 11
  • 2
Loading