Homework 6

Due: Nov. 30, 22:00:00

Fixed step size gradient descent

1. Let $\begin{array}{c}Q=\left(\begin{array}{cc}3& a\\ 0& 3\end{array}\right)\end{array}$$Q = \begin{pmatrix} 3 & a\\ 0 &3 \end{pmatrix}$ be a $2\times 2$$2\times 2$ real matrix, where $a$$a$ is a real number. Suppose $f:{\mathbb{R}}^2\to \mathbb{R}$$f: \mathbb{R}^2\to \mathbb{R}$ is a quadratic function where $f(x)=x^{\mathsf{T}}Qx$$f(x) = x^{\mathsf{T}}Qx$.

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

   • Assume $a=4$$a = 4$. We would like to use the gradient descent method with fixed step size to minimize $f$$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$$1000$, find an initial point $x_0$$x_0$ such that the algorithm does not converge when starting from $x_0$$x_0$.

2. Let $Q\succ \mathbf{0}$$Q \succ \mathbf{0}$ be a positive definite $n\times n$$n\times n$ matrix and $f(x)=x^{\mathsf{T}}Qx+w^{\mathsf{T}}x$$f(x) = x^{\mathsf{T}}Q x + w^\mathsf{T} x$. We implement the gradient descent method with some fixed step size.

   Suppose that we can only compute the gradient of $f$$f$ with some error $\delta$$\delta$. That is, $x_{k+1}=x_k-t(\mathrm{\nabla }f(x_k)+{\delta }_k)$$x_{k+1} = x_k - t(\nabla f(x_k)+ \delta_k)$, where ${\delta }_k\in {\mathbb{R}}^n$$\delta_k \in \mathbb{R}^n$ and $\Vert {\delta }_k{\Vert }_2\le D$$\lVert \delta_k \rVert_2 \leq D$.

   Assume that we select a sufficiently small $t$$t$ such that the algorithm converges if ${\delta }_k=0$$\delta_k = 0$.

   Let $\lambda ={\lambda }_{min}(Q)$$\lambda = \lambda_{\min}(Q)$ be the smallest eigenvalue of $Q$$Q$.

   • Show that $x_{k+1}-x^{\ast }=(I-2tQ)(x_k-x^{\ast })-t{\delta }_k$$x_{k+1} - x^* = (I - 2tQ)(x_k-x^*) - t\delta_k$.
   • Show that $\Vert x_{k+1}-x^{\ast }{\Vert }_2\le |1-2t\lambda |\cdot \Vert x_k-x^{\ast }{\Vert }_2+t\cdot D$$\lVert x_{k+1}-x^* \rVert_2 \leq \abs{1- 2t\lambda} \cdot \lVert x_k-x^* \rVert_2 + t\cdot D$.
   • Show that $\Vert x_k-x^{\ast }{\Vert }_2\le {|1-2t\lambda |}^k\cdot \Vert x_0-x^{\ast }{\Vert }_2+\frac{1-{|1-2t\lambda |}^k}{\lambda }\cdot D$$\lVert x_k-x^* \rVert_2 \leq \abs{1- 2t\lambda}^k \cdot \lVert x_0-x^* \rVert_2 + \frac{1-\abs{1-2t\lambda}^k}{\lambda} \cdot D$.
   • Show that for any $\epsilon >0$$\varepsilon > 0$, there exists $k_0$$k_0$ such that for all $k>k_0$$k > k_0$, $\Vert x_k-x^{\ast }{\Vert }_2<D/\lambda +\epsilon$$\lVert x_k - x^* \rVert_2 < D/\lambda + \varepsilon$.

Condition number

3. Consider the function $f(x_1,x_2)=x_1^2+2\alpha x_1{x}_2+x_2^2$$f(x_1, x_2) = x_1^2 + 2\alpha x_1x_2 + x_2^2$, where $\alpha \in (0,1)$$\alpha \in (0, 1)$.

   • Compute the eigenvalues and the condition number of ${\mathrm{\nabla }}^{2}f$$\nabla^2 f$.
   • If $\alpha$$\alpha$ goes to $1$$1$, what happens to the condition number of ${\mathrm{\nabla }}^{2}f$$\nabla^2 f$ and the convergence rate of the fixed step gradient descent method?
   • If $\alpha =1$$\alpha = 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$.

Exact line search and backtracking line search

4. We now verify the first two examples of Chapter 9.3.2 of our textbook.

   • Let $f(x)=\frac{1}{2}{x}^{\mathsf{T}}Qx$$f(x) = \frac{1}{2} x^\mathsf{T} Q x$ where $Q=\text{diag}\{1,\gamma \}$$Q = \text{diag}\{1,\gamma\}$ for some $\gamma >0$$\gamma > 0$. We start from $x_0=(\gamma ,1{)}^{\mathsf{T}}$$x_0 = (\gamma, 1)^\mathsf{T}$ and apply the exact line search. Verify that $x_k=(\gamma (\frac{\gamma -1}{\gamma +1}{)}^k,(-\frac{\gamma -1}{\gamma +1}{)}^k{)}^{\mathsf{T}}$$x_k = (\gamma (\frac{\gamma-1}{\gamma+1})^k, (-\frac{\gamma-1}{\gamma+1})^k)^\mathsf{T}$.

   • Let $f(x_1,x_2)=e^{x_1+3x_2-0.1}+e^{x_1-3x_2-0.1}+e^{-x_1-0.1}$$f(x_1, x_2) = e^{x_1+3x_2-0.1}+e^{x_1-3x_2-0.1}+e^{-x_1-0.1}$. We start from $y_0=(-2,1{)}^{\mathsf{T}}$$y_0 = (-2, 1)^\mathsf{T}$ and apply the backtracking line search with $\alpha =0.1,\beta =0.7$$\alpha = 0.1, \beta =0.7$. Give the result after 15 iterations, i.e., $y_{15}$$y_{15}$ and $\mathrm{\nabla }f(y_{15})$$\nabla f(y_{15})$.

     (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., $(y_0,\mathrm{\nabla }f(y_0),t_0),(y_1,\mathrm{\nabla }f(y_1),t_1),\dots ,(y_{14},\mathrm{\nabla }f(y_{14}),t_{14})$$(y_0, \nabla f(y_0), t_0), (y_1, \nabla f(y_1), t_1), \ldots, (y_{14}, \nabla f(y_{14}), t_{14})$.)

Newton's method

5. Consider the second example of Problem 5. Let $f(x_1,x_2)=e^{x_1+3x_2-0.1}+e^{x_1-3x_2-0.1}+e^{-x_1-0.1}$$f(x_1, x_2) = e^{x_1+3x_2-0.1}+e^{x_1-3x_2-0.1}+e^{-x_1-0.1}$. We start from $y_0=(-2,1{)}^{\mathsf{T}}$$y_0 = (-2, 1)^\mathsf{T}$ and apply the Newton's method $y_{k+1}=y_k-({\mathrm{\nabla }}^{2}f(y_k){)}^{-1}\mathrm{\nabla }f(y_k)$$y_{k+1} = y_k - (\nabla^2 f(y_k))^{-1} \nabla f(y_k)$.

   • Compute ${\mathrm{\nabla }}^{2}f(x_1,x_2)$$\nabla^2 f(x_1, x_2)$.

   • Give the result after 10 iterations ($y_{10}$$y_{10}$ and $\mathrm{\nabla }f(y_{10})$$\nabla f(y_{10})$).

     Hint: you may need the formula ${\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)}^{-1}={\displaystyle \frac{1}{ad-bc}}\left(\begin{array}{cc}d& -b\\ -c& a\end{array}\right)$$\begin{pmatrix} a & b\\c & d\end{pmatrix}^{-1} = \dfrac{1}{ad-bc} \begin{pmatrix} d & -b\\-c & a\end{pmatrix}$.

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

Questionnaire

• How long does it take you to do this homework?
• If $1$$1$ represents "very easy" and $10$$10$ represents "too hard", how difficult do you feel this homework is? (You can give different points for different problems.)