Consider the following optimization problem: computing geodesics, i.e. the shortest route between two points, on a two-dimensional surface on which it is easier to move quickly on some parts of the surface than on others. You can think of the reason for this as some kind of friction. Mathematically, the problem is to minimize

(3) |

over smooth functions and defining the path on the two-dimensional surface as a function of time, with the boundary conditions and (any two given points in ). Here is the friction function describing how difficult it is to move at the given point on the surface. The question is: what is the shortest route?

We can approximate the infinite-dimensional problem by discretizing the functional by replacing the functions and with the corresponding vectors and with , where . Approximating the derivative function by finite differences, we wish to minimize

(4) |

where .

Consider the friction and a path consisting of points starting at and ending at . Compare the convergence properties of the following optimization methods: gradient descent, Newton's method, line search based on gradient descent and line search based on conjugate gradient descent (Fletcher-Reeve and Polack-Ribiero algorithm). Repeat the optimization for .

Explain the reasons for the good or bad performance of each of the optimization methods. Present your results clearly, structured and legible.