CSC466H1/CSC2305H Homework 1

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC466H1/CSC2305H

Homework 1

January 19, 2023

1.  (Exercise 2.6) An point is an isolated local minimizer if there exists a neighborhood of that point on which it is the only local minimizer.  Prove that all isolated local minimizers are strict local minimizers. Hint: Consider an isolated local minimizer x* and a neighborhood N on which it is the only local minimizer. Show that, if x  x*  is in N, then it must be the case that f (x) > f (x* ).

2.  (Exercise 2.8) Suppose that f is a convex function.   Show that the set of global minimizers of f is a convex set.

3.  Prove Theorem 3.6(i). You can assume that c1  < 1/2.

4.  (Exercise 3.13) Show that the quadratic function that interpolates φ(0), φ\ (0), and φ(α0 ), is given by formula (3.57) in the textbook. Then, show that, if the sufficient decrease condition is not satisfied at α0 , this quadratic function is convex and the minimizer α 1  satisfies

α0        

2(1 - c1 ) .

Since usually c1  < 1/2 (or even smaller), this means that α 1  < α0 .

5.  Consider the function f : Rn → R given by the formula

f (x) = - exp(-xT AT Ax) + exp(-  |x - (2, 2)T |2 ),                                       (2)

where

A =  、.                                                                                                (3)

The contour plot of this function on the region [0, 6] × [-6, 2] is shown in Figure 1. The local minimum x* ≈ (2.93, -3.08)T  is shown on the plot.

2

0 

-2

-4

-6

4

Figure 1: A contour plot of the function f (x). A local minimum is mark with an asterisk.

(a) Write down an explicit formula for Vf (x).

(b) Implement the steepest descent method, using exact line search, starting from the point x0  = (2, 0)T .  To perform exact line search, use the MATLAB func- tion fminsearch or the SciPy function scipy .optimize .fmin to minimize the function φ(α) = f (xk + αpk) at each iteration, setting the tolerance to around machine precision.  What is the size of Vfk  after 100 iterations?  What is the value of xk? Why do you see this behavior? Hint: What are the eigenvalues of AT A?

(c) Implement Newton’s method, starting from x0 = (3, -2.9)T , using the step length αk  = 1 and the Newton step pk  = -B_k1 Vfk, where Bk  is a finite-difference approximation to the Hessian V2fk ,

∂i f (xk + hej) - ∂i f (xk)

,

where e1 = (1, 0)T , e2 = (0, 1)T , and h = 10_8 , for i, j = 1, 2. What are the sizes of Vfk, for k = 1, 2, 3, 4, 5? What is the value of x5 ? Use Newton’s method again, this time starting from x0 = (3, -2.8). What do you see, and why? What about if you start from x0 = (3, -2.7)?

(d) Implement the steepest descent method with exact line search, starting from x0 = (2, 0)T , except now, make the search directions conjugate, in the sense that pk(T)V2fkpk _1 ≈ 0. This can be done by setting rk = -Vfk, and letting

rk(T)Bkpk _1                                                                                                                          (5)

pk(T)_ 1 Bkpk _ 1 ,

where Bk is the finite-difference approximation to the Hessian that you constructed in part (c).  What are the sizes of Vfk, for k = 1, 2, 3, 4, 5?  What is the value of x5 ?  What happens if, instead of setting rk  equal to the gradient, you set r2k _1 = e1  and r2k = e2 , for k > 1?


2023-01-29