Homework 6

Due: Nov. 30, 22:00:00

Fixed step size gradient descent

  1. Let Q=(3a03) be a 2×2 real matrix, where a is a real number. Suppose f:R2R is a quadratic function where f(x)=xTQx.

    • Determine the range of a such that f has a global minimum.

    • Assume a=4. We would like to use the gradient descent method with fixed step size to minimize f.

      • Determine the range of step size so that the algorithm will converge no matter which initial point we choose.
      • If we set the step size to be 1000, find an initial point x0 such that the algorithm does not converge when starting from x0.
  2. Let Q0 be a positive definite n×n matrix and f(x)=xTQx+wTx. We implement the gradient descent method with some fixed step size.

    Suppose that we can only compute the gradient of f with some error δ. That is, xk+1=xkt(f(xk)+δk), where δkRn and δk2D.

    Assume that we select a sufficiently small t such that the algorithm converges if δk=0.

    Let λ=λmin(Q) be the smallest eigenvalue of Q.

    • Show that xk+1x=(I2tQ)(xkx)tδk.
    • Show that xk+1x2|12tλ|xkx2+tD.
    • Show that xkx2|12tλ|kx0x2+1|12tλ|kλD.
    • Show that for any ε>0, there exists k0 such that for all k>k0, xkx2<D/λ+ε.

Condition number

  1. Consider the function f(x1,x2)=x12+2αx1x2+x22, where α(0,1).

    • Compute the eigenvalues and the condition number of 2f.
    • If α goes to 1, what happens to the condition number of 2f and the convergence rate of the fixed step gradient descent method?
    • If α=1, does the gradient descent method converge with some fixed step size? If so, find a step size and explain why the rate of convergence is less than 1.
  1. We now verify the first two examples of Chapter 9.3.2 of our textbook.

    • Let f(x)=12xTQx where Q=diag{1,γ} for some γ>0. We start from x0=(γ,1)T and apply the exact line search. Verify that xk=(γ(γ1γ+1)k,(γ1γ+1)k)T.

    • Let f(x1,x2)=ex1+3x20.1+ex13x20.1+ex10.1. We start from y0=(2,1)T and apply the backtracking line search with α=0.1,β=0.7. Give the result after 15 iterations, i.e., y15 and f(y15).

      (Remark: You are encouraged to compute with some program (Please use your own code!). You can use any language you like. If so, please submit your code at the same time. Of course, you can also use paper and pencil if you like. If so, you should write down all intermediate results, i.e., (y0,f(y0),t0),(y1,f(y1),t1),,(y14,f(y14),t14).)

Newton's method

  1. Consider the second example of Problem 5. Let f(x1,x2)=ex1+3x20.1+ex13x20.1+ex10.1. We start from y0=(2,1)T and apply the Newton's method yk+1=yk(2f(yk))1f(yk).

    • Compute 2f(x1,x2).

    • Give the result after 10 iterations (y10 and f(y10)).

      Hint: you may need the formula (abcd)1=1adbc(dbca).

      (Remark: Again, you should submit your code or all intermediate results.)