Optomisation

Question 1

Golden Section Search: Description

Answer 1

Assume f is unimodal. Comparing f(x1) and f(x2) allows us to discard a subinterval (x2, b] or [a, x1) each iteration. The minimum of the function will be in the remaining interval.

Question 2

Golden Section Search: Method

Answer 2

Algorithm involving
T = (sqrt(5)-1)/1
x1=a+(1-T)(b-a)
x2=a+T(b-a)

Question 3

Golden Section Search: Robustness

Answer 3

Safe, slowly convergent linearly with constant C ~ 0.618.

Always reuse one of two test points, so is beneficial is computationally expensive to computer function value.

Question 4

Steepest Descent: Description

Answer 4

Calculate local minimum by taking descending steps from a given point of a function.
Step size too small - slow descent.
Step size too large - may overshoot or diverge from minimum, or ping pong effect.

Question 5

Steepest Descen: Method

Answer 5

xi+1 = xi-Alpha * Nablaf’(x)

Calculate Alpha. Sub into eqn.

Question 6

Newton’s Method:

Answer 6

This is the one where you take away Nabla/Hessian from xi. Calculate by subbing in si.
xi+1 = xi - (Nablaf’(x) / Hessian(f’x))
si = xi+1 - xi

Question 7

Derive Newtons Method from Taylor

Answer 7

Write out f(x+h) expansion
Differentiate f(x+h) with respect to h.
Maximum when df(x+h)/dh = 0
Remember xi+1 = xi + h

Question 8

Newtons Method Multidimensional

Answer 8

Replace f’ & f’’ with Nabla and Hessian.
f’(x) = Nablaf(x).
f’‘(x) = Hf(x)
si = xi+1 - xi

Question 9

Newton’s Method: Convergence and Robustness

Answer 9

Much faster than steepest descent as 2nd order (Newton’s) vs 1st order. However, computing Hessian is expensive!
Quadratic Convergence.
Not robust as must start relatively close to solution