Riemannian optimization on stiefel and grassmann manifolds — Examples

For $q=\pm 1\in \mathrm{O}(1)$, $(xq{)}^{\mathsf{T}}A(xq)=x^{\mathsf{T}}Ax$, so the objective is well-defined on lines by [F1]. Since $A$ is positive semidefinite, $f([x])\ge 0$ for every unit $x$. If $x\in \mathrm{span}(e_1,e_2)$, then $Ax=0$ and $f([x])=0$, so every such line is a global minimizer.

The vectors $x=(\cos \theta )e_1+(\sin \theta )e_2$ for $0\le \theta <\pi$ are unit and give distinct lines: two such vectors span the same line only when their angles differ by a multiple of $\pi$, which cannot occur for distinct parameters in this half-open interval. Thus they parametrize continuum many distinct lines. At each such $x$, $Ax=0$, so the ambient gradient $2Ax$ and its horizontal projection vanish. The family is a continuum of Grassmann critical minimizers.

The ambient gradient is $\mathrm{\nabla }f(x)=2Ax$, so $\mathrm{\nabla }f(e_2)=2e_2$. Its Stiefel projection is $2e_2-e_2(e_2^{\mathsf{T}}2e_2)=0$ by [F1]; hence $e_2$ is critical.

Both $e_1$ and $e_3$ are tangent at $e_2$ by [F2]. The curves $x_{-}(t)=\cos (t)e_2+\sin (t)e_1$ and $x_{+}(t)=\cos (t)e_2+\sin (t)e_3$ stay on the unit sphere and have initial velocities $e_1,e_3$. Their objective values are $f(x_{-}(t))={\cos }^{2}t<1$ and $f(x_{+}(t))={\cos }^{2}t+2{\sin }^{2}t=1+{\sin }^{2}t>1$ for all sufficiently small nonzero $t$. Thus arbitrarily nearby feasible points have smaller and larger values, proving strict saddle behavior.

The ambient gradient of $f$ is $-2Ax$. At $x=e_2$, the Stiefel projection in [F1] is zero, so the eigendirection is stationary; at the global minimizer $e_1$, $f(e_1)=-5$. For the displayed start, $p(A)b=(1,1\mathrm{/}4,-1\mathrm{/}4{)}^{\mathsf{T}}\mathrm{/}\sqrt{3}$ is nonzero and belongs to $K_2(A,b)=\mathrm{span}\{b,Ab\}$.

The squared norm of this vector is $(1+1\mathrm{/}16+1\mathrm{/}16)\mathrm{/}3=3\mathrm{/}8$, and its $A$-quadratic form is $(5+2\mathrm{/}16)\mathrm{/}3=41\mathrm{/}24$. Dividing gives Rayleigh quotient $41\mathrm{/}9$, hence objective $-41\mathrm{/}9$ and gap $5-41\mathrm{/}9=4\mathrm{/}9$.

Here ${\lambda }_1=5$, ${\lambda }_2=2$, ${\lambda }_3=0$, the top multiplicity is one, and $\tau =\mathrm{\parallel }(I-P)b\mathrm{\parallel }\mathrm{/}\mathrm{\parallel }Pb\mathrm{\parallel }=\sqrt{2}$. Since step 1.1 places the candidate in $K_2$, its quotient shows ${\theta }_2\ge 41\mathrm{/}9$. For Krylov dimension $m=2$, the theorem [F2] gives ${\lambda }_1-{\theta }_2\le \frac{(5-0)(\sqrt{2}{)}^2}{T_1(1+2(5-2)\mathrm{/}(2-0){)}^2}=\frac{10}{4^2}=\frac{5}{8}\mathrm{.}$ Since ${\theta }_2\ge 41\mathrm{/}9$, its Ritz gap obeys $0\le {\lambda }_1-{\theta }_2\le 4\mathrm{/}9\le 5\mathrm{/}8$, so the candidate comparison and source bound agree. Also $b$ and $Ab$ are independent because the third coordinate of $Ab$ is zero while that of $b$ is nonzero, so the two-dimensional Krylov space is attained without breakdown.