CS3331: Numerical Methods
Quiz 5
June. 13, 1997

1.

(4%) We want to use steepest descent (or gradient descent) to minimize an objective function $E({\bf x})$, where ${\bf x}=[x_1, \ldots , x_n]$.

(a)

List the simple formula of steepest descent for minimizing $E({\bf x})$.

(b)

List the normalized version of steepest descent for minimizing $E({\bf x})$.

2.

(7%) Let E(x)=x²-2x.

(a)

(2%) Write down the simple steepest descent formula for x_n+1 (in terms of x_n and $\eta$).

(b)

(3%) Find the general solution of x_n+1 (in terms of x₀ and $\eta$).

(c)

(2%) What's the range for $\eta$ for the convergence of the simple steepest descent formula?

3.

(5%) Let E(x) = x³-x².

(a)

(2%) Write down the simple steepest descent formula for x_n+1 (in terms of x_n and $\eta$).

(b)

(3%) What's the range for $\eta$ for the convergence of the simple steepest descent formula? (Suppose that we want to find the minimum between x=0 and x=1.)

4.

(12%) Let E(x,y) = x²-2xy+y².

(a)

(2%) Write down the simple steepest descent formula for $\left[ \begin{array} {c} x_{n+1}\\ y_{n+1}\\ \end{array} \right]$ (in terms of x_n, y_n, and $\eta$).

(b)

(2%) To find the gradient path, we can assume that a given point $\left[ \begin{array} {c} x(t)\\ y(t)\\ \end{array} \right]$ on the gradient path has a velocity vector equal to the negative gradient vector of E(x,y). In other words, we can have the formula

$$\left[ \begin{array} {c} \dot{x}\\ \dot{y}\\ \end{array}... ...= A \left[ \begin{array} {c} x\\ y\\ \end{array} \right]$$

Find the matrix A.

(c)

(4%) Solve the above equation by assuming that $\left[ \begin{array} {c} x(t)\\ y(t)\\ \end{array} \right] = c_1 e^{\lambda_1 t} {\bf u}_1 + c_2 e^{\lambda_2 t} {\bf u}_2$. What is $\lambda_1$, $\lambda_2$, ${\bf u}_1$, and ${\bf u}_2$?

(d)

(2%) What is c₁ and c₂ if x(0)=1 and y(0)=0?

(e)

(2%) So what's the function of the gradient path when expressed as a y=f(x)?

5.

(2%) Plot the paths of gradient descent on the following contour plot of the "peaks" function. The points labeled with "*" is the starting locations.

  

Figure: The function of "peaks" and its contour. Please plot the ideal gradient paths on top of the contour plot.