# step-fixed algorithm first iterates

let us have the fixed-step gradient algorithm, with $$p = 2$$ and we assume that for $$X = (x, y)$$,

$$∇ f(X) = \begin{pmatrix} x -1\\ y -2 \end{pmatrix}$$

Let me assume we intialize with $$X_0 = (0,0)$$ what will be the first three iterates $$X_1, X_2, X_3$$? I am assuming it they would be $$X_1 = (2,4), X_2 = (0,0), X_3 = (2,4)$$, is this correct?

• What is $\Delta f(x,y)$? And how did you conclude those would be the iterates? Commented Jul 18 at 17:32
• haha, sorry I meant gradient! I followed some lecture notes I found online, just by mentally trying to follow with some computations, but I have no idea if that s correct, I am still learning about this fixed step gradient version. Commented Jul 18 at 17:42
• As in other questions, what is $p$ in your description, and what is $s$ in your previous comment? We cannot look into your head, you will have to become better at explaining what it is you are asking. Commented Jul 18 at 18:16
• But you do: "but I have no idea if that s correct". I have no idea what "that s" is supposed to refer to. Commented Jul 18 at 21:31
• The resulting confusion simply reinforces my suggestion that you ought to put more work into how you write questions. Commented Jul 19 at 4:06

Gradient descent has the following iteration

$$$$X_{k+1} = X_k - \alpha_k \nabla f(X_k).$$$$

Assuming that $$X_0 = 0$$, and $$\nabla f(X) = \begin{bmatrix} x-1 \\ y - 2\end{bmatrix}$$ the iterates are:

\begin{align} X_1 &= \begin{bmatrix} 0 \\ 0 \end{bmatrix} - \alpha_0\begin{bmatrix} -1 \\ -2 \end{bmatrix} = \begin{bmatrix} \alpha_0 \\ 2\alpha_0 \end{bmatrix}, \\ X_2 &= \begin{bmatrix} \alpha_0 \\ 2\alpha_0 \end{bmatrix} - \alpha_1\begin{bmatrix} \alpha_0-1 \\ 2\alpha_0-2\end{bmatrix} = \begin{bmatrix} \alpha_0-\alpha_1(\alpha_0-1) \\ 2(\alpha_0-\alpha_1(\alpha_0-1))\end{bmatrix}, \\ X_3 &= \begin{bmatrix} \alpha_0-\alpha_1(\alpha_0-1) \\ 2(\alpha_0-\alpha_1(\alpha_0-1)) \end{bmatrix} -\alpha_2\begin{bmatrix}1-\alpha_0 + \alpha_1(\alpha_0-1) \\ 2(1-\alpha_0 + \alpha_1(\alpha_0-1))\end{bmatrix}. \end{align}

I don't think this provides any insights though, I am not sure what the purpose is of looking at these iterates. Typically a computer computes those.

By the way, if the gradient is $$\begin{bmatrix} x-1\\ y-2\end{bmatrix}$$ then the function was \begin{align} f(x,y) &= \frac{1}{2}x^2 - x + \frac{1}{2}y^2 - y + c \\ &= \frac{1}{2}\begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} - \begin{bmatrix} x & y \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} + c \\ &= \frac{1}{2}X^TAX - X^T B + c. \end{align} Taking the gradient and setting it to zero in order to find the stationary points we get

$$$$\frac{1}{2}(A+A^T)X = B.$$$$

If $$A+A^T$$ is non-singular then this has a unique solution $$X = 2(A+A^T)^{-1}B$$. Since $$\frac{1}{2}(A+A^T) = I_2$$ in your case you get $$X = B = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$. In general $$A+A^T$$ may be singular, then if $$B$$ is not in the span of $$A+A^T$$ there is no solution. If $$A+A^T$$ is singular and $$B$$ is in the span of $$A+A^T$$ then there are infinitely many solutions each a shifted variant of the others along the kernel of $$A+A^T$$. The gradient decent algorithm is meant to minimize the objective $$f$$, the latter has a minimum when $$X^TAX\geq 0$$ and $$B$$ is in the span of $$A+A^T$$. If $$X^TAX\geq 0$$ then $$A+A^T$$ is positive semi-definite, and a sufficient condition for the gradient descent algorithm to converge is $$0<\alpha_k<\frac{2}{\frac{1}{2}\lambda_{\max}(A+A^T)}$$. For a fixed step size the optimal choice is $$\alpha = \frac{2}{\lambda_{\min} + \lambda_{\max}}$$, where $$\lambda_{\min}$$ and $$\lambda_{\max}$$ are the respectively the minimum and maximum eigenvalues of $$\frac{1}{2}(A+A^T)$$, see the Wikipedia article on the convergence of the Richardson iteration.

• Thanks, wait what is $α_1$? Commented Jul 18 at 18:46
• @V_head I just allowed for different step sizes $\alpha_0, \alpha_1,\alpha_2$, you can make all of those equal if you wish, then it's fixed step size gradient descent. But the latter is not very efficient. Commented Jul 18 at 18:58
• Yeah exactly, because mine is $α = 2$ Commented Jul 18 at 19:02
• So then: $X_1 = [2, 2], X_2 = [0, 0] ...$, interesting, thanks Commented Jul 18 at 19:06
• @V_head Then you can check by plugging this in that the iteration will oscillate between $\begin{bmatrix} 0 \\ 0 \end{bmatrix}$ and $\begin{bmatrix} 2 \\ 2 \end{bmatrix}$. The step is simply too large, so it overjumps the solution $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$. Note that the sufficient condition for convergence was $0<\alpha_k<\frac{2}{\frac{1}{2}\lambda_{\max}(A+A^T)}$ which is your case reads $0<\alpha_k<2$, but you picked $\alpha_k = 2$, which is outside of this range. If you pick $1.999$ it should converge but slowly. $\alpha = \frac{\lambda_1+\lambda_2}{2}=1$ is much better here. Commented Jul 18 at 19:07