I.4.3.2: A Family of Quadratics

This example shows some of the properties of coordinate relaxation. We want to minimize $$\psi_{\lambda}(x,y)=\frac{1}{2}x^2+\frac{1}{2}y^2-\lambda xy.$$ For each $\lambda$ this is a quadratic in $x$ and $y$. If we fix $y$ and $\lambda$, the resulting function is a convex quadratic in $x$. And if we fix $x$ and $\lambda$, the resulting function is a convex quadratic in $y$. Thus coordinate relaxation can always be carried out, with a unique minimum in each substep.

The partials are given by $$\begin{align*} \frac{\partial\psi_{\lambda}}{\partial x}&=x-\lambda y,\\ \frac{\partial\psi_{\lambda}}{\partial y}&=y-\lambda x, \end{align*}$$ and the Hessian is the matrix $$\begin{bmatrix} 1 & -\lambda\\ -\lambda & 1 \end{bmatrix}.$$ Thus the eigenvalues of the Hessian are $1+\lambda$ and $1-\lambda$.

If $-1<\lambda<+1$ then the function has a unique isolated minimum equal to zero at $(0,0)$. If $\lambda=+1$ it has a minimum equal to zero on the line $x-y=0$ and if $\lambda=-1$ it has a minimum equal to zero on the line $x+y=0$. If $\lambda^{2}>1$ the unique stationary point at $(0,0)$ is a saddle point, and there are no minima or maxima.

Coordinate relaxation gives the algorithm $$\begin{align*} y^{(k+1)}&=\lambda x^{(k)}=\lambda^2 y^{(k)},\\ x^{(k+1)}&=\lambda y^{(k+1)}=\lambda^2 x^{(k)}, \end{align*}$$ or $$\begin{align*} x^{(k)}&=\lambda^{2k}x^{(0)},\\ y^{(k)}&=\lambda^{2k-1}x^{(0)}. \end{align*}$$ Thus we have convergence to $(0,0)$ if and only if $\lambda^2<1.$ In that case convergence is linear, with rate $\lambda^2,$ Convergence is immediate, to $(x^{(0)},x^{(0)})$ or $(x^{(0)},-x^{(0)})$, if $\lambda^2=1.$

For the function values we have $$\psi^{(k)}=\frac{1}{2}(1-\lambda^{2})\lambda^{4k-2}[x^{(0)}]^{2},$$ If $\lambda^2>1$ then the function values $\psi^{(k)}$ decrease, and diverge to $-\infty$. Also, $(x^{(k)},y^{(k)})$ diverges to infinity. By defining $\tilde\psi=\exp\psi,$ we easily change the problem into an equivalent one with the same iterates, for which function values converge to zero, but since $(x^{(k)},y^{(k)})$ is the same sequence as before it still diverges to infinity.

Note that $$\frac{\psi^{(k+1)}}{\psi^{(k)}}=\lambda^4,$$ while $$\frac{x^{(k+1)}}{x^{(k)}}=\frac{y^{(k+1)}}{y^{(k)}}= \lambda^2.$$ Thus function values converge twice as fast as the coordinates of the solution vector.