NUMERICAL OPTIMISATION
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
NUMERICAL OPTIMISATION
COURSE WORK (50%)
Submit your solutions to Turnitin. Your report must be typeset and should not exceed 15 pages. Most questions can be answered with a few sentences in addition to equations and plots. Please only include code into your report when explicitly asked for (please follow the particular guidelines, most of the time we only want to see small snippets).
UCL rules and regulations on late submission and plagiarism apply.
EXERCISE 1 [30pt]
We are given a function f : Ω = R+× R → R
f(x,y) = (y + lnx)2 + (y − x)2 , x > 0.
(a) Note that ln(x) on real numbers x is not formally defined for x ≤ 0. How can you define the objective function f so that the optimisation methods still work correctly? [2 pt]
(b) Calculate the gradient ∇f and the Hessian ∇2 f. [2 pt]
(c) Plot the function and its contours. What can you say about the function: is it convex or not, are there and how many stationary points and local / global minima? Justify your answers qualitatively. [3 pt]
(d) Find the minimiser x* ∈ Ω of the function f and describe how you obtained it. Hint: You may compute it numerically but verify analytically that it satisfies the sufficient conditions. Show that x* is unique. [8 pt]
(e) Show that the gradient, ∇f, is locally Lipschitz continuous. Hint : Recall integral form of Taylor’s theorem and that Frobenious norm is an upper bound on the L2 matrix norm. [5 pt]
(f*) Show that the Hessian, ∇2 f, is locally Lipschitz continuous on Ω = (β,∞) × R with β > 0. Make sure to show working highlighting the main steps in your proof. Hint : Young’s inequality is a useful way of bounding products. [10 pt]
EXERCISE 2 [18pt]
(a) Apply steepest descent with an appropriate line search to the function f in Ex.1 starting from x0 = (3, −2)T and x0 = (0.05, 4)T . Plot the iterates over the function contours. State your choice of a line search and any important parameters. What do you observe? [2pt]
(b) Investigate convergence of the steepest descent (a) iterates a posteriori and include one rel- evant error plot per starting point. What are the empirical convergence rates and how did you obtain them? Do they agree with the theoretical predictions? Paraphrase the relevant theoretical results. [4pt]
(c) Apply Newton with an appropriate line search to the function f in Ex.1 starting from x0 = (3, −2)T and x0 = (0.05, 4)T . Plot the iterates over the function contours. State your choice of a line search and any important parameters. What do you observe? [2pt]
(d) Investigate convergence of the Newton (c) iterates a posteriori and include one relevant error plot per starting point. What are the empirical convergence rates and how did you obtain them? Do they agree with the theoretical predictions? Paraphrase the relevant theoretical results. [4pt]
(e) Can global convergence of both methods be guaranteed or not and why? Paraphrase the relevant theoretical results. [6pt]
EXERCISE 3 [20pt]
(a) Implement the dogleg trust region method for strictly convex functions (with s.p.d. Hessian). Your implementation should return the Cauchy point whenever the gradient and Newton steps are collinear.
Include your implementation in the report. Highlight the part where you solve for the in- tersection point between the trust region and the dogleg path and provide a short narrative explanation. [6pt]
(b) Apply the dogleg trust region method to minimise the function f : R2 → R f(x,y) = 100(y2 + x2 − 1)2 + (1 − x)2
with three different starting points x0 = (−1.5, 1.5)T , x0 = (1.5, 0)T and x0 = (0, 0)T . Plot the trajectories traced by the iterates over the function contours. State your choice of the stopping condition and any relevant parameters. What do you observe? [3pt]
(c) Investigate convergence of the dogleg iterates in (b) a posteriori and include one relevant error plot per starting point. What are the empirical convergence rates and how did you obtain them? Do they agree with the theoretical predictions? Paraphrase the relevant theoretical results. [4pt]
(d) Perturb the 2nd and 3rd starting points to x0 = (1.5, 0.1)T and x0 = (0, 0.1)T , respectively, and run the method again. Plot the trajectories and convergence for the perturbed points. What do you observe and can you explain the difference in behaviour of the method between the original and perturbed points? [4pt]
(e) Can global convergence be expected or not, and why? Paraphrase the relevant theoretical results. Hint : If you need to bound local Lipschitz constants, it is sufficient to give a high level answer for the type of functions. [3pt]
EXERCISE 4 [20pt]
(a) Implement Polak-Ribie`re nonlinear conjugate gradient method. Copy the relevant lines in your report. Hint: Modify the descentLineSearch.m template from tutorial 2. [2pt]
(b) Apply the Fletcher-Reeves and Polak-Ribie`re nonlinear conjugate gradient methods to min-imise the function f : R+ × R → R
f(x, y) = x ln(x) + y 2 + c e −σ2/(x−a)2+(y−b)2
for parameter values a = 2, b = 0, σ = 0.5 and c = 4.
Try two initial points x0 = (2, 0.5)T and x0 = (2.5, 0.1)T and set the tolerance tol = 1e-4. State your choice of any relevant parameters. Plot the iterates over the function contours. [4pt]
(c) Explain what you observe in the plots you made in (b). Include plots of relevant quantities which corroborate your hypothesis. [5pt]
(d) Propose a strategy to remedy the problem and explain the theoretical guarantees you have for your approach. Hint: Can the global convergence and what type be guaranteed? Implement your strategy, rerun your solver and compare its behaviour with the results in (b). [5pt]
(e) Investigate convergence of the all three methods in (b-d) a posteriori and include one relevant error plot per method. What are the empirical convergence rates and how did you obtain them? Do they agree with the theoretical predictions? Paraphrase the relevant theoretical results. [4pt]
EXERCISE 5 [12pt]
(a) Implement the BFGS method by modifying the descentLineSearch.m function from tutorial 2. Make your implementation efficient 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 your implementation efficient. [6pt]
(b) Minimise the function f : R2 → R
f(x,y) = (x − 4y)2 + x4
using BFGS implemented in (a) starting from x0 = (−8, −8)T . Visualise the path traced by the iterates over the function contour. Which line search did you choose and why? State your choices of any relevant parameters. [1pt]
(c) Investigate convergence of the BFGS iterates in (b) a posteriori and include one relevant error plot. What is the empirical convergence rate and how did you obtain it? Does it agree with the theoretical prediction? Paraphrase the relevant theoretical result. [3pt]
(d) Can global convergence of BFGS and of what type be expected or not, and why? Paraphrase the relevant theoretical result. [2pt]
2024-03-04