NUMERICAL OPTIMISATION TUTORIAL 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
NUMERICAL OPTIMISATION
TUTORIAL 1
EXERCISE 1. The purpose of this exercise is to provide a few useful hacks how to easily imple- ment 2D optimisation computations in Matlab.
Rosenbrock function
f (x, y) = 100(y - x2 )2 + (1 - x)2
is a popular function for testing optimisation methods.
(a) Calculate the gradient Vf and the Hessian V2f .
(b) Find the minimiser x* of the function f . Show that x* is unique and that V2f (x* ) is posi- tive definite.
(d) Calculate the contours of f analytically. Contours are sets xc : f (x) = c where c is a real constant.
(d) Write a Matlab function that implements the Rosenbrock function. Implement a function that can be evaluated at many points simultaneously. Hint: Matlab’s “.*” operation.
(e) Create a two dimensional grid using Matlab’s command meshgrid. Plot f on the grid using your implemented Matlab function. Check out the following functions: surf (use option ’EdgeColor’ = ’none’ when using many grid points), surfc, contour, contourf. Can you see the minimiser? Can you use some transformation to highlight the minimiser?
(f) Compute the gradient Vf and the Hessian V2f numerically using finite differences. Check out the functions gradient, diff, and implement finite differences as a matrix multiplica- tion.
(g) You can also compute the eigenvalues of the Hessian V2f numerically using eig function in Matlab. Plot the smallest eigenvalue as a function of the (x, y). What information does it give you?
EXERCISE 2. Basic linear algebra review, in particular eigenvalues, positive definiteness and quadratic function calculus.
(a) Show that A = BT B is symmetric positive semidefinite for all B e Rn Xn . Hint: you can use the Rayleigh quotient representation of the eigenvalue Ax = λx .
(b) Let f(x) = xT Ax with A symmetric positive semidefinite matrix A e Rn Xn . Show that f(x) is convex on the domain Rn . Hint: you may want to show the equivalent inequality instead
f(y + α(x - y)) - αf(x) - (1 - α)f(y) < 0.
EXERCISE 3. Compute 2nd degree Taylor expansion (the reminder term is of 2nd order) of the following functions at a generic point in their domain
(a) f(x) = cos(1/x) for x e R+ ,
(b) g(x) = exp(||x||2 ) for x = (x1 , x2 ) e R2 . Hint: expand along a fixed direction p e R2 .
EXERCISE 4. Investigate convergence, a.k.a. Q-convergence, exponential convergence or alge- braic convergence, of the following series xk as k → o
(a) xk = 1/k ,
(b) xk = 1/k!,
(c) xk = 2 + (0.5)2k .
2022-02-16