NUMERICAL OPTIMISATION
ASSIGNMENT 3
MARTA BETCKE
KIKO RUL·LAN
EXERCISE 1
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 combination
of basis vectors p = V a. You can use any basis, here orthonormal basis is useful;
(ii) use the result in Theorem 4.1 to obtain optimal p. Observe that complementarity condition (The-
orem 4.1 equation (4.8a)) results in two cases;
(iii) use Theorem 4.1 equation (4.8a) to obtain an explicit expression for each coefficient ai and plug
them into the remaining condition; Hint: After using the eigenvalue decomposition of BV = V
TBV ,
this can be reduced to finding the roots of a 4th order polynomial.
Submit solution via TurnitIn. [40pt]
EXERCISE 2
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.
Submit your implementation via Cody Coursework. [20pt]
EXERCISE 3
Implement a trust region function based on Algorithm 4.1 in Nocedal Wright. Let this function take a
handle to a solver for the constraint quadratic model problem as an argument. This will allow us to plug
in different solvers to obtain different trust region methods.
Submit your implementation via Cody Coursework. [20pt]
EXERCISE 4
Apply the trust region method to Rosenbrock function with a nearby starting point (1.2, 1.2) and a
farther away point (−1.2, 1). Pay attention to the choice of trust region radius in each case. Hint: In
case you are not confident with your implementation of the 2D subspace method, you can implement the
dogleg method, which is provided in Nocedal Wright.
Submit solution via TurnitIn. [20pt]
Remark. The submission to TurnitIn should not be longer than 4 pages. Avoid submitting more
code than needed (if any) and focus on explaining your results.
1