I have tried many times to solve this problem and would be grateful for any advice:

Let the quadratic function $F: \mathbb{R}^{n} \longrightarrow \mathbb{R}$ defined by:

$$ F(\mathbf{x})=\frac{1}{2} \langle A \mathbf{x}, \mathbf{x} \rangle - \langle \mathbf{c}, \mathbf{x} \rangle, \quad \forall \mathbf{x} \in \mathbb{R}^{n} $$

where $A$ is a real symmetric positive definite (square) matrix, $\mathbf{c} \in \mathbb{R}^{n}$

Let $0<\lambda_{1} \leq \lambda_{2} \leq \cdots \leq \lambda_{n}$ be the eigenvalues of the matrix $A$ and let $\mathbf{w}_{1}, \mathbf{w}_{2}, \ldots, \mathbf{w}_{n}$ be the corresponding eigenvectors in $\mathbb{R}^{n}$ (reminder: For all $1 \leq i \leq n, A \mathbf{w}_{i}=\lambda_{i} \mathbf{w}_{i}$ and $\left\{\mathbf{w}_{i}\right\}_{1 \leq i \leq n}$ is an orthonormal basis of $\mathbb{R}^{n}$. Applying the steepest descent method to determine

$$\mathbf{u}^{\star}:=\min _{\mathbf{u} \in \mathbb{R}^{n}} F(\mathbf{u})$$

that is, we construct a sequence $\left\{\mathbf{u}^{(k)}\right\}_{k \in N}$,

$$u^{(k+1)}=u^{(k)}-\rho_{k} \nabla F\left(u^{(k)}\right)$$

for a given $\mathbf{u}^{(0)}$.

I managed to show (was asked to): $\mathbf{u}^{(k+1)}-\mathbf{u}^{\star}=\mathbf{u}^{(k)}-\mathbf{u}^{\star}-\rho_{k} A\left(\mathbf{u}^{(k)}-\mathbf{u}^{\star}\right), \quad \forall k \in \mathbb{N}$

Now I want to prove that:

  1. Assume now that $\mathbf{u}^{(0)}=\mathbf{u}^{\star}+\alpha \mathbf{w}_{m}$, with $\alpha \in \mathbb{R}^{*}(\alpha \neq 0)$ and $m \in\{1,2, \ldots, n\}$. Show that the gradient method converges in exactly one iteration. Does it help that $\mathbf{u}^{(0)}$ and $\mathbf{u}^{\star}$ lie on the same straight line? I don't know how to find $\rho_{k}$ for the first iteration

  2. Assume $\lambda_{1}<\lambda_{n}$, and that $<\mathbf{u}^{(0)}-\mathbf{u}^{\star}, \mathbf{w}_{1}>\neq 0$ and $<\mathbf{u}^{(0)}-\mathbf{u}^{\star}, \mathbf{w}_{n}>\neq$ 0 . Prove that the gradient method does not converge in a finite number of iterations, namely $\mathbf{u}^{(k)} \neq \mathbf{u}^{\star}, \forall k \in \mathbb{N}$ (clue: write $\mathbf{u}^{(k)}-\mathbf{u}^{\star}=\sum_{i=1}^{i=n} \alpha_{i}^{(k)} \mathbf{w}_{i}$, for $\alpha_{i}^{(k)} \in \mathbb{R}$ and prove by induction, that $\alpha_{1}^{(k)} \neq 0, \alpha_{n}^{(k)} \neq 0$ $) .$ Why the "distance" of the kth iteration from the minimum is connected to the eigenvectors?


It holds $\mathbf{A} \mathbf{u}^* = \mathbf{c}$, so the gradient expresses as $$ \nabla F(\mathbf{x}) = \mathbf{Ax-c} = \mathbf{A}(\mathbf{x}-\mathbf{u}^*) $$

The gradient update yields $$ \mathbf{u}_1 = \mathbf{u}_0 - \rho_0 \mathbf{A}(\mathbf{u}_0-\mathbf{u}^*) $$ For the given choice $\mathbf{u}_0 = \mathbf{u}^*+\alpha \mathbf{w}_m$, this simplifies into $$ \mathbf{u}_1 = \mathbf{u}^*+\alpha \mathbf{w}_m - \alpha \rho_0 \lambda_m \mathbf{w}_m $$ By choosing the step size $\rho_0=1/\lambda_m$, the gradient descent method reaches the solution in one step!