EXERCISE 1
NUMERICAL OPTIMISATION TUTORIAL 22/02/19 ASSIGNMENT 3 (submit by 11 p.m. 04/03)
MARTA BETCKE KIKO RUL·LAN
(a) Implement the BFGS method by modifying the descentLineSearch function. More help is pro- vided inside MATLAB Grader.
Submit your solution via MATLAB Grader. [10pt]
(b) Make your implementation efficient as explained in the lecture i.e. avoid explicitly forming the inverse Hessian matrix Hk. Copy the code lines implementing the update of Hk into your report and briefly explain what makes the implementation efficient.
Submit your solution via TurnitIn. [10pt]
EXERCISE 2 [DEMO]
Implement the SR-1 method by modifying the trustRegion function. More help is provided inside MATLAB Grader. Note: Here you are not expected to provide an efficient implementation as it would require some changes to solverCM2dSubspaceExt which are out of scope at this point. [0pt]
EXERCISE 3
(a) Minimise the function
f(x,y)=(x−3y)2 +x4
using BFGS (Ex 1a) and SR1 (Ex 2) methods starting from x0 = (10, 10)T . Compare the perfor- mance of the methods. To this end provide any parameters and plots that you consider relevant.
Submit your solution via TurnitIn.
(b) Both implementations return a sequence of matrices as a field of the info structure:
(i) {HBFGS}k≥0 when using BFGS, k
(ii) {BSR1}k≥0 when using SR1. k
[10pt]
Plot the error of these sequences obtained in Ex 3a with respect to the matrices they approximate. In particular, plot
(i) {||I − HBFGS∇2f(xk)||2}k≥0, k
(ii) {||I − (BSR1)−1∇2f(xk)||2}k≥0, k
and explain your results.
Submit your solution via TurnitIn.
EXERCISE 4
[20pt]
Implement the Gauss-Newton method for solution of nonlinear least square problems. As Gauss-Newton is a line search method, it can be easiest implemented inside the function descentLineSearch.m. More help is provided in Cody Coursework.
Submit your implementation via MATLAB Grader. [10pt]
EXERCISE 5 [DEMO]
You are given an implementation of the Levenberg-Marquardt method. This implementation plugs in the Levenberg-Marquardt solver solverCMlevenberg.m into the trust region function trustRegion.m. Briefly answer the following questions about the solver in solverCMlevenberg.m
(i) What is the effect of the for loop in line 36 and what is the reason for sequential execution? (ii) Explain the formula for calculating the L-M direction p.
(iii) Explain what is q and how it is calculated.
(iv) Explain what is λ and the formula used for its update.
EXERCISE 6
Consider a model
φ(x1, x2, x3; t) = (x1 + x2t2) exp(−x3t)
with parameters (x1, x2, x3).
Simulate the measurements sampling this model for a fixed choice of parameters (x1,x2,x3) =
(3,150,2) at 200 equi-spaced points in ti ∈ (0,4] and adding Gaussian noise n(ti) ∼ N(0,σ2) drawn from a normal distribution with 0 mean and standard deviation 5% of the maximal amplitude of the sampled model signal σ = 0.05 maxti |φ(ti)|,
φ ̃ ( x 1 , x 2 , x 3 ; t j ) = φ ( x 1 , x 2 , x 3 ; t j ) + n ( t j ) .
(a) Formulate the least-squares problem for fitting the model φ and derive its Jacobian.
Submit your solution via TurnitIn.
(b) Estimate the parameters (x1, x2, x3) from your simulated measurements using
(i) Gauss-Newton (implemented in Ex 1) (ii) Levenberg-Marquardt (provided)
[15pt]
Specify all the relevant parameters and explain the results. Visualise the fit by plotting the esti- mated signal versus the measurements.
Submit your solution via TurnitIn. [25pt]
Remark. The submission to TurnitIn should not exceed 8 pages. This is not a hard limit and there is no penalty for longer submissions. Avoid submitting code unless explicitly asked for and focus on explaining your results.
[0pt]
2