EXERCISE 1

Implement the trust region framework function based on the pseudocode in the lecture  [NW, Algorithm 4.1]. Use the provided template trustRegion.m to guide your implementation. One of the arguments of trustRegion.m function is a Matlab’s handle to a constraint quadratic model solver (an example is the 2d subspace solver derived and implemented in the following exercises). Such construction will allow us to plug in different solvers to obtain different trust region methods.

EXERCISE 2

Derive the 2D subspace trust region method for convex functions (with s.p.d. Hessian). Note that

(i) when p is constraint to a subspace V = span(g, B − 1g), it can be expressed as a linear combi- nation of basis vectors p = Va. You can use any basis, here orthonormal basis is useful;

(ii)  Mor´e Sorensen theorem [NW Theorem 4.1] provides a characterisation of optimal p.  First,

observe that complementarity condition  [NW Theorem 4.1 equation  (4.8b)] results in two cases;

(iii) use the first condition in Mor´e Sorensen theorem  [NW Theorem 4.1  (4.8a)] to obtain an explicit expression for each of the coefficients ai  and plug them into the remaining condition; Hint:  After using the eigenvalue decomposition of BV  = VT BV, this can be reduced to finding the roots of a 4th order polynomial.

EXERCISE 3

(a) Implement the 2D subspace trust region method for convex functions (with s.p.d. Hessian).

This implementation should return the Cauchy point whenever the gradient and Newton steps are collinear.

(b) Apply the 2D subspace trust region method to minimise function

f (x, y) = x2 + 5x4 + 10y2

with two different starting points. Plot the trajectories traced by the iterates over the function contours.