Convergence to a Saddle | Block Relaxation Algorithms in Statistics -- Part I

I.3.8.1: Convergence to a Saddle

Convergence, even it occurs, does not need to be towards a minimum. Consider $f(x,y)=\frac16 y^3-\frac12y^2x+\frac12yx^2-x^2+2x.$ Perspective and contour plots of this function are in figures 1 and 2. Code for the plots is in saddle.R

plot of chunk saddle_contour

Figure 1: Contour Plot Bivariate Cubic

plot of chunk saddle_persp

Figure 2: Perspective Plot Bivariate Cubic

The derivatives are $\begin{align*} \mathcal{D}_1f(x,y)&=(y-2)(x-\frac12(y+2)),\\ \mathcal{D}_2f(x,y)&=\frac12(x-y)^2, \end{align*}$ and $\mathcal{D}^2f(x,y)=\begin{bmatrix} y-2&x-y\\ x-y&y-x \end{bmatrix}.$ Start with $y^{(0)}>2$ . Minimizing over $x$ for given $y^{(k)}$ gives $x^{(k)}=\frac12(y^{(k)}+2),$ and minimizing over $y$ for given $x^{(k)}$ gives $y^{(k+1)}=x^{(k)}.$ It follows that $\begin{align*} x^{(k+1)}-2&=\frac12(x^{(k)}-2),\\ y^{(k+1)}-2&=\frac12(y^{(k)}-2). \end{align*}$ Thus both $x^{(k)}$ and $y^{(k)}$ decrease to two with linear convergence rate $\frac12$ . The function $f$ has a saddle point at $(2,2)$ , and $\mathcal{D}^2f(2,2)= \begin{bmatrix}0&0\\0&0\end{bmatrix}.$