Find the largest range of values of the step size α for which the algorithm is globally convergent

Question

Consider a fixed-step-size gradient algorithm applied to the following function f.

$$ f(x)=1+2x_1+3(x_1^2+x_2^2 )+4x_1 x_2$$

Find the range of values of the step size α for which the fixed step algorithm converges globally .

Answer 1

Your algorithm is $$x_{k+1}=x_{k}-\alpha\frac{\partial f}{\partial x}\bigg\vert_{x=x_k}$$ and you are searching for $x^*$ such that $$\frac{\partial f}{\partial x}(x^*)=0$$ If you carry out the calculations $x^*=\frac{1}{5}\left[\matrix{-3\\2}\right]$.

Consider now the square distance from this point $$V_k=\|x_k-x^*\|^2$$ You have to find $\alpha$ for which $$V_{k+1}-V_k<0 \qquad \forall x\neq x^*$$ Note that your function is quadratic so you have global convergence (you can start from any point in $\mathbb{R}^2$). $$V_{k+1}-V_{k}=-\alpha\left[2\frac{\partial f}{\partial x}\bigg\vert_{x=x_k}^T(x_k-x^*)-\alpha\bigg\|\frac{\partial f}{\partial x}\bigg\vert_{x=x_k}\bigg\|^2\right]$$ So you want to find $\alpha>0$ such that $$2\frac{\partial f}{\partial x}\bigg\vert_{x=x_k}^T(x_k-x^*)-\alpha\bigg\|\frac{\partial f}{\partial x}\bigg\vert_{x=x_k}\bigg\|^2> 0 \qquad \forall x\neq x^*$$ Also $$\frac{\partial f}{\partial x}\bigg\vert_{x=x_k}=Q(x_k-x^*)$$ with $$Q=\left[\matrix{6 & 4\\ 4 & 6}\right]$$ So the above inequality can be written as $$(x_k-x^*)^TQ[2Q^{-1}-\alpha\mathbb{I}]Q(x_k-x^*)>0 \qquad \forall x\neq x^*$$ Thus if $$\alpha<2\lambda_{\min}(Q^{-1})=\frac{2}{\lambda_{\max}(Q)}=\frac{3+\sqrt{5}}{2}$$ then the algorithm is globally convergent.