3dgeometryoptimizationsolid-geometry
An ant is sitting in a vertex of a right parallelepiped with edges $2, 3, 12$. What is the length of the shortest path it can take to the opposite vertex?
Now, I tried to imagine that and we have a $3D$ box. Just open up the box by unfolding it into a $2D$ figure. now the path from vertex $A$ to vertex $B$ would be a straight line.
for $AB$ to be minimum, we need the base to be $(2+2)$ and the width to be $3$.
Answer is $5$. Sounds too easy for me.
By (5) you have formulas for the displacement in $x$ and in $y$ direction. These are simply numbers. The squared length is the sum of the squares of these displacements, by Pythagoras. That squared length is then written as a function of a two-element parameter vector $\alpha_i$. It is quadratic in $\alpha$, so it can be split into a matrix which gets multiplied by $\alpha_i$ from both sides, a vector which gets multiplied by $\alpha_i$ in what is essentially a dot product, and a constant part which does not depend on $\alpha_i$ at all. This separation is what (6) does.
Let's have a closer look. Remember that the form of your $x$ displacement was this:
$$ \Delta P_{x,i} = \begin{pmatrix}\Delta x_{i+1}\\-\Delta x_i\end{pmatrix}^{\mathrm T}\alpha_i + \Delta x_{i,0} = \alpha_i^{\mathrm T}\begin{pmatrix}\Delta x_{i+1}\\-\Delta x_i\end{pmatrix} + \Delta x_{i,0} $$
Lets introduce some abbreviations for the reoccurring vectors here:
$$ \beta_i := \begin{pmatrix}\Delta x_{i+1}\\-\Delta x_i\end{pmatrix} \\ \gamma_i := \begin{pmatrix}\Delta y_{i+1}\\-\Delta y_i\end{pmatrix} $$
Now you can write
$$ \Delta P_{x,i} = \beta_i^{\mathrm T}\alpha_i + \Delta x_{i,0} \\ \Delta P_{y,i} = \gamma_i^{\mathrm T}\alpha_i + \Delta y_{i,0} $$
and with these you can compute the squared length as the sum of the squared displacements in the two coordinate directions like this:
\begin{align*} \Delta P_{x,i}^2 + \Delta P_{y,i}^2 &= \left(\beta_i^{\mathrm T}\alpha_i + \Delta x_{i,0}\right)^2 + \left(\gamma_i^{\mathrm T}\alpha_i + \Delta y_{i,0}\right)^2 \\&= \left(\beta_i^{\mathrm T}\alpha_i\right)^2 + 2\left(\beta_i^{\mathrm T}\alpha_i\right)\Delta x_{i,0} + \Delta x_{i,0}^2 + \left(\gamma_i^{\mathrm T}\alpha_i\right)^2 + 2\left(\gamma_i^{\mathrm T}\alpha_i\right)\Delta y_{i,0} + \Delta y_{i,0}^2 \\&= \alpha_i^{\mathrm T}\beta_i\beta_i^{\mathrm T}\alpha_i + 2\Delta x_{i,0}\beta_i^{\mathrm T}\alpha_i + \Delta x_{i,0}^2 + \alpha_i^{\mathrm T}\gamma_i\gamma_i^{\mathrm T}\alpha_i + 2\Delta y_{i,0}\gamma_i^{\mathrm T}\alpha_i + \Delta y_{i,0}^2 \\&= \alpha_i^{\mathrm T}\left( \beta_i\beta_i^{\mathrm T} + \gamma_i\gamma_i^{\mathrm T} \right)\alpha_i + \left( 2\Delta x_{i,0}\beta_i^{\mathrm T} + 2\Delta y_{i,0}\gamma_i^{\mathrm T} \right)\alpha_i + \left( \Delta x_{i,0}^2 + \Delta y_{i,0}^2 \right) \end{align*}
So here you see that $H_{S,i}$ is the matrix
$$ H_{S,i}:=\beta_i\beta_i^{\mathrm T} + \gamma_i\gamma_i^{\mathrm T} $$
and $B_{S,i}$ is the row vector
$$ B_{S,i}:= 2\Delta x_{i,0}\beta_i^{\mathrm T} + 2\Delta y_{i,0}\gamma_i^{\mathrm T} $$
while the constant term is the last parenthesis and irrelevant for the subsequent optimization.
Based on this, (7) expresses $\alpha_i$ as the matrix-times-vector product
$$\alpha_i = E_i\alpha = \begin{pmatrix}\alpha_{i+1}\\\alpha_i\end{pmatrix}$$
The matrix $E_i$ here simply has two rows and $n$ columns. The first row has a $1$ in column $i+1$ and the second a $1$ in column $i$. This matrix $E_i$ can be combined with the matrices of the previous step in order to obtain an expression in $\alpha$, without the need to select elements based on $i$. With this formulation, the sum of products with matrices can be turned into a product with sums of matrices, using
\begin{align*} H_S &:= \sum_{i=1}^n E_i^{\mathrm T}H_{S,i}E_i \\ B_S &:= \sum_{i=1}^n B_{S,i}E_i \end{align*}
Explaining pretty much every equation in the MCP case is beyond the scope of this post. The above should give you an idea about the kind of transformations required. If you need more help, please ask more specific questions separately.
It is the famous problem invented by R. Bellman in 1956 [1]. It is known as 'Lost in a Forest Problem':
What is the best path to follow in order to escape a forest of known shape and dimensions?
The subproblem for the half-plane forest with known distance from the boundary was solved by J. R. Isbell in 1957 [2]. He described the path with the length
$$\left(\sqrt{3}+\frac{7\pi}{6}+1\right)d$$
where $d$ is the distance from the boundary of the forest. He gave the proof in outline that his path had minimal length. The complete and detailed proof was given by H. Joris in 1980 [3]. The consideration about this problem can also be found in the book [4].
The overview of the results on the general problem up to 2004 can be found in [5].
The form of the shortest path:
As @Will Nelson wrote the shortest path consists of the 3 line segments with lengths $\frac{2}{\sqrt{3}}d$, $\frac{1}{\sqrt{3}}d$ and $d$ and the arc of the circle with radius $d$ which subtends the angle $\frac{7\pi}{6}$. The total length of the path is
$$L_{\min}(d)=\frac{2}{\sqrt{3}}d+\frac{1}{\sqrt{3}}d+\frac{7\pi}{6}d+d=\left(\sqrt{3}+\frac{7\pi}{6}+1\right)d\approx 6.397d$$
In our case $d=40$ so $L_{\min}\approx 255.890<280$. The ant can survive!
R. Bellman, Minimization Problem, Bull. Amer. Math. Soc. 62 (1956) p. 270. [Available online at the AMS BAMS archive, free of charge.]
J. R. Isbell, An optimal search pattern, Naval Res. Logist. Quart. 4 (1957) pp. 357-359. [Available online at Wiley Online Library, 35$ cost.]
H. Joris, Le chasseur perdu dans la foret, Elem. Math. 35 (1980) pp. 1-14. [Available online at the site of École polytechnique fédérale de Lausanne, free of charge.]
Z. A. Melzak, Companion to Concrete Mathematics: Mathematical Techniques and Various Applications, Wiley, New York, 1973, pp. 150-153. [I couldn't find this book online. According to @Barry Cipra Google Books let some users see a big chunk of this book with relevant pages.]
S. R. Finch and J. E. Wetzel, Lost in a Forest, American Mathematical Monthly 111 (2004) pp. 645-654. [Available online at the site of Mathematical Association of America, free of charge.]
Update: Some references were added.
Best Answer
Here's a pictorial depiction of @Michael Rosenberg's answer. As @Toby Mak commented, you've to find the distance of path from $A$ to $C'$ in the diagram.
There are three potential ways to do so, out of which two are identical. Also, sorry for the missing labels, hope you understand.
Note that here the height we considered was $3$. If it was $2$, then there would have been one more possible way $$\sqrt{3^2+(12+2)^2}$$ which is obviously not the answer but one of the ways to reach the opposite vertex.