next up previous
Next: Digit Classification [3 P] Up: NNA_Exercises_2009 Previous: Quasi-Newton's Method [3 P]

Function Minimization [3 P]

Compare different algorithms for function minimization. You are required to use MATLAB for this assignment. The MATLAB file is available for download on the course homepage3. Complete the lines marked with $ ..............$ in the file conjgrad.m (search for the tag HOMEWORK) as required for the following points.

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

$\displaystyle F = \int_0^1 \rho(x(t),y(t)) \left( \left( \frac{dx(t)}{dt}\right)^2 + \left( \frac{dy(t)}{dt}\right)^2 \right)dt$ (3)

over smooth functions $ x(t)$ and $ y(t)$ defining the path on the two-dimensional surface as a function of time, with the boundary conditions $ (x(0), y(0)) =
(a, b)$ and $ (x(1), y(1)) = (c, d)$ (any two given points in $ \mathbb{R}^2$ ). Here $ \rho(x, y)$ 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 $ F$ by replacing the functions $ x(t)$ and $ y(t)$ with the corresponding vectors $ {\bf x}$ and $ {\bf y}$ with $ (x_n, y_n)$ , where $ n = 1,...,N$ . Approximating the derivative function by finite differences, we wish to minimize

$\displaystyle F({\bf x},{\bf y})= \sum_{i=1}^{N-1} \rho(x_i,y_i) \left( \left( ...
...t}\right)^2 + \left( \frac{y_{i+1} - y_{i}}{\Delta t}\right)^2 \right)\Delta t,$ (4)

where $ \Delta t = 1/(N-1)$ .

Consider the friction $ \rho(x,y)=1+\alpha\exp(-x^2-y^2)$ and a path consisting of $ N = 10$ points starting at $ (-1,-1)$ and ending at $ (2,1)$ . 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 $ \alpha = 0, 0.5, 1.6, 5$ .

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


next up previous
Next: Digit Classification [3 P] Up: NNA_Exercises_2009 Previous: Quasi-Newton's Method [3 P]
Haeusler Stefan 2010-01-19