Hand in on DTU Learn before 8 December 11pm.  The overall page limit exclude Appendix is 6.

1    Exercise for one-page report (40%)

In this exercise, we apply several methods that we learned in the course to solve the following minimization problem

min  f (z) = 1 x1(4) _ 2x1(2)x2 + x1(2) + 2x2(2) _ 4x1 + 5.

zeR2                              2

Please first complete the following questions, then write your one-page report.

1.  (by hand) Compute the gradient Vf (z) and the Hessian V2f (z).

2.  (by hand) Show that z* = [2, 2]T  is the only local minimizer of this function.

3.  (in Matlab) Make a contour plot of f (z) in the interval _5 s x1  s 5 and _2 s x2  s 8.

4.  (in Matlab) Write a Matlab function to return the function value f (z), its gradient Vf (z) and the Hessian V2f (z) with a given z.

5.  (in Matlab) Apply the steepest descent method (with line search), Newton’s method  (with fixed step length  1),  BFGS method  (with  H0   =  I  and line search), coordinate search method (with γ = 1) and nonlinear conjugate gra- dient method (with line search) to solve this minimization problem.

● Set the starting point as z0 = [3, 3]T .

● Set the stopping criteria as  ⅡVf Ⅱo  s 10-6  or k > 400, where k is the iteration index.

● For line search, we use the backtracking line search with ρ = 0.5 and c = 0.1.

● Save and output the first 8 iterates, i.e., z1 , . . . , z8  and plot them on the contour plot for each method.

● Use semilogy to plot ek  = Ⅱzk  _ z* Ⅱ2 , f (zk) and ⅡVf (zk)Ⅱ2  (if appli- cable) for each method.

● For nonlinear conjugate gradient method, you can implement it easily by modifying your code for the steepest descent method with backtracking line search.   You only need change the part for calculating the search direction pk . In nonlinear conjugate gradient method, we have

p0 = _Vf (z0 ),        pk+1 = _Vf (zk+1) + βk+1pk ,

where we use Polak-Ribi`ere method to obtain βk+1, i.e,

Vf (zk+1)T (Vf (zk+1) _ Vf (zk))

ⅡVf (zk)Ⅱ2(2)                          .

6.  (Report) In your report, you should include the following results, comments and explanations.

(a)  (10%) Include the recorded values of z1 , . . . , z8  from all methods in a

table.

(b)  (20%) According to the contour plots, the plots of ek and f (zk), which do

not need be included in the report, comment on and explain the progress of all 5 methods, e.g.  how the iterates move, how fast the convergences are, how the computational costs are, etc.

(c)  (10%) Test Newton’s method with different starting points: z0  = [2, 3]T and [3, 5]T , respectively. What happen? Why?

2    Convergence of CG method (in Matlab, 20%)

In this exercise, we consider a 500 x 500 symmetric matrix A constructed as follows. The elements in the main diagonal of A equal 1, and the off-diagonal elements are random numbers from the uniform distribution on  [_1, 1].   Then, we replace all elements in the off-diagonals with IaijI > τ by zero, where τ is a parameter.  For τ close to zero, A is close to the identity matrix, which is well-conditioned with the condition number 1.

1.  (5%) Download the Matlab function genA .m from the same place as the final assignment in DTU Learn, which generates the matrix A.  (Note that {aij} generated from the uniform distribution are fixed,  i.e.,  in genA .m different inputs τ modify the same matrix A.) Set the parameter τ as 0.01, 0.05, 0.09, and 0.3, and compute the condition number and the smallest eigenvalue of

A.  List them in a table and include the table in the pdf file with all your answers.   (Hint:  the smallest eigenvalue of A can be calculated by calling eigs(A,1,’sm’)).

2.  (5%) According to the table that you created from the previous question, comment on how the condition number changes and how the definiteness of A changes.

3.  (5%) Apply the CG method to solve the linear system Az  =  b with b  =   [1, 1, . . . , 1]T  and the starting point z0  = [0, 0, . . . , 0]T .  Plot the four curves   log10 (ⅡAzk _bⅡ2 ) corresponding to the CG iteration with τ = 0.01, 0.05, 0.09, 0.3, respectively, in the same figure. Include the figure in the pdf file with all your   answers.

4.  (5%) Comment on the convergence of CG with respect to the condition number of A. In addition, at τ = 0.3 you should observe that CG does not converge. Why?

3    Necessary condition (by hand, 20%)

In this exercise, we use the KKT conditions to solve a constrained optimization problem. Consider the following constrained problem

min (x1 _ 4)2 + x2(2)                                                                   (1)

z

s.t. x1 + x2  s 2,

1.  (5%) Verify the constrained problem (1) is convex.  (Hint: You need show the feasible set is a convex set and the objective function on the feasible set is a convex function.)

2.  (5%) Write done the KKT conditions for (1).

3.  (10%) Solve the constrained minimization problem (1) according to the KKT conditions. State the minimizer that you obtained and include your derivation in your answers.

4    Review: A regularized least-squares problem (20%)

We consider a regularized least squares problem with smoothing:

k                                       n-1

ze(m)Rn(in)       (αi(T)z _ bi)2 + δ      (xi+1 _ xi)2 ,                                (2)

i=1                                           i=1

where δ > 0 is a pre-given parameter, bi  e R and αi  e Rn  for all i = 1, . . . , k .

1.  (by hand, 5%) Verify that the objective function in matrix-vector form is ⅡAz _ bⅡ2(2) + δⅡLzⅡ2(2) .

What are the matrices A, L and the vector b? What are their dimensions?

2.  (by hand, 5%) According to the definition of 2-norm for vectors, the objective function can be further written as

 ┌ ^δL(A)┐ z _ ┌  ┐0(b) 2(2) .

So you can see that this minimization problem is a least-squares problem. According to the optimality condition, express its normal equation.

3.  (in Matlab) Download the data file Exe4 2022 .mat from the same place as the assignment. By loading Exe4 2022 .mat, you will obtain the vector b, the matrices A and L. The vector b in fact represents a blur noisy image covered by some texts.