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}.$