MATH60005 Optimisation - Coursework 1: Unconstrained Optimisation
MATH60005/70005: Optimisation (Autumn 23-24)
Instructions: read this first!
-
This coursework has a total of 20 marks and accounts for 10% of the module.
-
Students who want to take the final exam (90%) must submit this coursework.
-
Submission deadline: November 17th, 13:00 UK time, via Blackboard drop box.
-
Submit a single file, ideally a pdf typed in LaTeX or similar.
-
Marking criteria: Full marks will be awarded for work that 1) is mathematically correct, 2) shows an understanding of material presented in lectures, 3) gives details of all calculations and reasoning, and 4) is presented in a logical and clear manner.
-
Do not discuss your answers publicly via our forum. If you have any queries regarding your interpretation of the questions, please contact the lecturer at dkaliseb@imperial.ac.uk
-
Beware of plagiarism regulations. This is a group-based assessment with groups from 1 to 3 students. Make a single submission for the coursework indicating in the front page the CID of every group member. Do not include your name.
Questions
Part I: Unconstrained Optimisation (6 marks)
Letf(x,y)=x2 −2xy2 +12y4.
-
i) [3 marks] Is the function f coercive? Explain your answer.
-
ii) [3 marks] Find the stationary points of f and classify them according to whether they are saddle points, strict/nonstrict local/global minimum/maximum points.
Part II: Linear Least Squares - Denoising (8 marks)
You are given the noisy signal s ∈ R1000 shown in Figure 1 (corresponding to the file signal.mat), and the goal is to use linear least squares to denoise it.
i) [3 marks] Write a regularised least squares formulation for the denoising problem of the form
min ∥Ax−b∥2 +λ∥Lx∥2, λ>0, x∈R1000
1
-
Figure 1: A noisy signal composed of piecewise constant components.
where ∥Lx∥2 = P999 (xi − xi+1)2. Give precise definitions for A, b, and L. Cast an i=1
equivalent ordinary least squares problem of the form
min ∥Aˆx−bˆ∥2, x∈R1000
giving precise definitions for Aˆ and bˆ. Plot the solution of the regularised least squares problems for values of λ = 0.1,1,10,100,1000. Describe what you observe in terms of denoising level.
ii) We will now develop an alternative solution to the denoising problem. We consider instead the problem
min ∥Aˆx−bˆ∥1, x∈R1000
with the same Aˆ and bˆ as before, and where ∥x∥1 = P|xi|. Note that this problem is nonsmooth and we cannot directly apply least squares or gradient-based techniques.
iia) [3 marks] We will construct an algorithm to approximate the solution of the problem above. For this, we consider the weighted least squares problem
x∈R1000
1999
min Xw|aˆ⊤x−ˆb|2,
iii i=1
where aˆ ⊤ denotes the i−th row of the matrix Aˆ and w ∈ R1999 is a given weight vec- i
tor with positive entries. Proceeding similarly as in the linear least squares problem, derive an expression for the solution of this problem in terms of Aˆ , bˆ and W, which is a diagonal matrix with w in the diagonal. We call this solution x∗ = x∗(Aˆ , bˆ, W).
2
iib) [2 marks] We now construct the following algorithm:
Step0: Setavectorw0 =1∈R1999,avectorfullof1’s. Setk=0,andatoleranceδ.
Step 1: Solve xk = x∗(Aˆ , bˆ, Wk).
Step 2: Update the weights according to
wk+1 = 1 . i max{δ,|aˆ⊤xk −ˆb|}
Step3: Setk=k+1andgobacktoStep1.
Plot the final solution x∗ of this algorithm for δ = 10−5, 100 iterations, and values of λ = 0.1, 1, 10, 100, 1000. This iterative procedure approximates the solution of the problem
min ∥Aˆx−bˆ∥1. x∈R1000
Discuss the differences you observe in your results with respect to the regularized least squares from part i).
Part III: Gradient Descent (6 marks) Consider the problem (mq)
min f(x)≡X a⊤ix−bi2+η2 ,
x∈Rn
where ai ∈ Rn,bi ∈ R,i = 1,2,...,m, and η > 0. If We define A ∈ Rm×n and the vector
a⊤m andthefunctiong:Rm →Rasg(y)=Pm
bm
∇f(x)=A⊤∇g(Ax−b), and ∇2f(x)=A⊤∇2g(Ax−b)A.
i) [2 marks] Show that ∇2f(x) ⪰ 0 for all x ∈ Rn. Choose only one of the following two questions:
iiA) [4 marks] Show that if A has full column rank, then there exists a unique global minimiser.
Hint: for existence of a minimiser, you can use that for any z ∈ Rm, it holds that ∥z∥1 ≥ ∥z∥2. For uniqueness, use the following result: if a function f is such that ∇2f(x) ≻ 0 for all x ∈ Rn, then a stationary point of f is necessarily a strict global minimum.
iiB) [4marks]Showthatf∈C1,1 withL= η . L ∥A∥2
Hint: you can use that for two matrices A and B of compatible dimensions, it holds that ∥AB∥ ≤ ∥A∥∥B∥.
