哈达玛流形上的近端梯度法收敛性分析

Analysis of Convergence of Proximal Gradient Method on Hadamard Manifold

摘要: 本文在哈达玛流形上提出了近端梯度算法，并给出了收敛性分析。具体地说，我们将非凸非光滑问题的近端梯度法从欧氏空间推广到哈达玛流形上。在黎曼流形上存在着非线性的困难，我们根据哈达玛流形的特殊结构，给出了理论证明。

Abstract: In this paper, a proximal gradient algorithm for Hadamard manifolds is presented and its conver-gence is analyzed. Specifically, we extend the proximal gradient method for Nonconvex nonsmooth problems from Euclidan space to Hadamard manifolds. The difficulty of nonlinearity on Bernhard Riemann manifolds is proved theoretically according to the special structure of Hadamard mani-folds. In this paper, a proximal gradient algorithm for Hadamard manifolds is presented and its convergence is analyzed. Specifically, we extend the proximal gradient method for nonconvex nonsmooth problems from Euclidean space to Hadamard manifolds. The difficulty of nonlinearity on Bernhard Riemann manifolds is proved theoretically according to the special structure of Hadamard manifolds.

1. 引言

流形是一般几何对象的总称，是欧式空间中的曲线，曲面等概念的推广。流形上的优化不仅是近年来信息科学领域发展起来的一门新兴学科，同时也是优化理论与方法的重要组成部分。在优化领域中，通过利用流形的几何结构，一些欧式空间的非凸问题可以转化为流形上的凸优化问题，一些约束优化问题可以视为流形上的无约束优化问题。因此，近年来这个领域的研究受到越来越多的关注。

哈达玛流形是一个完备的具有非正曲率 [1] [2] 的简单连通有限维黎曼流形，包括大量重要的矩阵流形和模型。在机器学习 [3]，图像处理 [4] 中都有着广泛的应用。由于其优良的几何结构，哈达玛流形上任意两点间测地线的唯一性假设，避免了算法设计的奇异性。近年来，国内外研究了各种非正曲率流形，如对称正定流形和n阶旋转群，已经出现在机器学习和计算机视觉中 [5] [6] [7]。考虑流形的几何结构，设计内在的迭代结构保持算法 [8] [9]，为一些任务的研究提供了更准确，更有效的途径。

作为非正曲率流形，哈达玛流形具有无共轭点的优良性质，因此其上任意两点之间存在唯一的测地线。它使算法的迭代在整个流形上有了很好的定义，并在这样的流形上发展了许多保持结构的算法。例如，Colao等人考虑了非线性哈达玛流形上的平衡问题，证明了一类双函数平衡点的存在性 [1] 和定义在哈达玛流形上的集值映射的不动点定理，并讨论了平衡点的近似问题。近几年，Ruizgarzon等人提出了哈达玛流形的约束向量优化问题弱有效Pareto点的经典充要条件 [10]，Ferreia和Louzeiro将梯度方法推广到截面曲率有界的流形上，并证明了一阶收敛速度 [11]。另一方面，Ferreira和Oliveira提出了一种求解哈达玛形上光滑凸函数的邻近点方法 [12]，并说明了Riemann流形中的凸分析，可以用来解决欧式空间中的非凸约束问题，并估计了𝑃 (1/l)的收敛速度 [9] [13]。Wang等人将求解多值向量场奇异点的非精确近点方法推广到哈达玛流形上 [14]。Bento等人还将一种近似点法推广到一般Riemann流形，并进行了收敛性分析 [15] 以及进一步的矢量优化 [16]。Ansari等人提出了一种正则化的非精确邻近点算法，用于寻找哈达玛流形上最大单调集值向量场的奇点 [17]。Baygorrea等人建立了哈达玛流形上拟凸极小化的非精确邻近点方法 [18] 并估计其收敛速度 [19]。Tang和Huang还估计了向量函数在哈达玛流形上的邻近点算法的收敛速度 [20]。近几年，Chen等人提出了Stiefel流形上的黎曼近似梯度(RPG)方法 [21]，而Torres Almeida等人则修改了邻近点算法来优化哈达玛流形上的DC函数 [22]。结果表明，基于梯度的方法和哈达玛流形上的邻近点算法极大地丰富了流形优化的研究。

在本文中，我们将以另一种方式加速求解哈达玛流形上一类非凸非光滑问题的内蕴近端梯度算法。也就是说，我们考虑下面的最小化问题：

$\underset{x\in M}{\min }F\left(x\right)=f\left(x\right)+g\left(x\right)$ (1)

其中 $M$ 是有限维哈达玛流形(具有非正截面曲率的流形)， $f$ 是测地光滑函数， $g$ 是下半连续函数，可以不连续。

2. 预备知识

我们在本节提出了一些关于哈达玛流形的概念。更详细的内容，请参阅 [2] [13] [18]。

哈达玛流形是一个具有非正截面曲率的完全单连通黎曼流形。在哈达玛流形上任意两点之间存在唯一的测地线。设 $M$ 是哈达玛流形，给定 $x\in M$， ${\text{T}}_{x}M$ 表示 $M$ 上在 $x$ 点的切空间。对任意 $y\in M$，指数映射定义为： ${\exp }_{x_k}:{\text{T}}_{x}M\to M$，指数映射定义为 ${\exp }_{x_k}^{-1}:M\to T_{x}M$ 满足 $\Vert {\exp }_x^{-1}y\Vert =\Vert {\exp }_y^{-1}x\Vert =d\left(x,y\right)$，其中， $\Vert ·\Vert$ 为切向量在对应黎曼度量 $\langle ,\rangle$ 下的范数。 $d\left(x,y\right)$ 是 $x$ 和 $y$ 两点间的测地距离。在哈达玛流形上，对于任意两点 $x,y\in M$，我们有 $\text{grad}\frac{1}{2}{\text{d}}^2\left(x,y\right)=-{\exp }_x^{-1}y$。设 $\gamma :\left[a,b\right]\to M$ 为一条曲线， $\nabla$ 表示 $M$ 上的Levi-Civita联络。一个沿着曲线 $\gamma$ 的向量场 $V$ 是平行向量场，当且仅当 ${\nabla }_{{\gamma }^{\prime }}V=0$，当 ${\nabla }_{{\gamma }^{\prime }}{\gamma }^{\prime }=0$ 时， $\gamma$ 是一条测地线。测地线 $\gamma (·)={\gamma }_v\left(·,x\right)$ 表示 $\gamma \left(0\right)=x$， ${\gamma }^{\prime }\left(0\right)=v$ 以及 $\gamma \left(1\right)={\exp }_{x}v$。 ${\text{P}}_{\left(x,y\right)}:{\text{T}}_{x}M\to {\text{T}}_{x}M$ 将向量 $v\in {\text{T}}_{x}M$ 映射到 ${\text{P}}_{\left(x,y\right)}v\in {\text{T}}_{x}M$ 并保持向量内积不变，称 ${\text{P}}_{\left(x,y\right)}$ 为M上的平行移动，即 ${\langle v,w\rangle }_x\text{=}{\langle {\text{P}}_{\left(x,y\right)}v,{\text{P}}_{\left(x,y\right)}w\rangle }_y$，特别地， ${\Vert v\Vert }_x\text{=}{\Vert {\text{P}}_{\left(x,y\right)}v\Vert }_y$。流形上的一个测地三角 $\Delta \left(xyz\right)$ 是由 $x,y,z$ 及连接这些点的三条最小测地线组成的集合。余弦定理是哈达玛流形上一个重要的性质，任意给定 $M$ 上的测地三角 $\Delta \left(xyz\right)$，有 $d^2\left(x,z\right)+d^2\left(z,y\right)\le d^2\left(x,y\right)+2\langle {\exp }_z^{-1}x,{\exp }_z^{-1}y\rangle$。

定义2.1 $M$ 上的可微函数 $f$ 的梯度是L-Lipschitz连续的，那么称 $f$ 是测地L-光滑(G-L光滑)函数。即 $\Vert {\text{P}}_{\left(x,y\right)}\text{grad}f\left(x\right)-\text{grad}f\left(y\right)\Vert \le Ld\left(x,y\right)$。

注：定义2.1等价于

$\Vert f\left(y\right)-f\left(x\right)-\langle \text{grad}f\left(x\right),{\exp }_x^{-1}y\rangle \Vert \le \frac{L}{2}{\Vert {\exp }_x^{-1}y\Vert }^2$ (2)

定义2.2 如果函数 $F:M\to R$ 在 $x\in M$ 满足

$\underset{d\left(x,y\right)\to \infty }{\lim }\frac{F\left(y\right)}{d\left(x,y\right)}=+\infty$

则称 $F$ 在 $x$ 点上是1-强制的。

定义2.3 令 $g:M\to R\cup \left\{+\infty \right\}$ 是一个下半连续的恰当函数， $g$ 在 $x\in M$ 上的Fréchet次微分定义为

${\partial }_{F}g\left(x\right):=\left\{v\in T_{x}M|\exists \left(x_m,v_m\right)\to \left(x,v\right),s.t.g\left(x_m\right)\to g\left(x\right),v_m\in {\partial }_{F}g\left(x_m\right)\right\}$

3. 哈达玛流形上的近端梯度法

在欧式空间中近端算法可以看作是解决一些非光滑、有约束、大规模问题的常规方法。本节中，我们将介绍哈达玛流形上的近端梯度法。

定义3.1 黎曼流形上的近端算子定义为：

$\begin{array}{c}{x}_{k+1}:=pro{x}_{{\lambda }_{k}g}\left({x^{\prime }}_k\right)\\ =\underset{x\in M}{\arg \min }\left(g\left(x\right)+\frac{1}{2{\lambda }_k}{d}^2\left(x,{x^{\prime }}_k\right)\right),\end{array}$

其中， ${x^{\prime }}_k={\exp }_{x_k}\left(-{\lambda }_k\text{grad}f\left(x_k\right)\right)$。

我们接下来给出下列假设：

假设3.1 $f$ 是一个恰当的，并且在M上是G-L光滑函数， $g$ 是一个恰当的，在M上是下半连续函数。

假设3.2 函数 $F=f+g$ 是1-强制的，并且在M上有下界。

引理3.1 设 $\Omega$ 在 $M$ 上是一个紧集，则存在一个常数 $C\left(0<C<+\infty \right)$ 使得任意 $x,y$ 和 $z\in M$，都有

$\Vert {\exp }_x^{-1}z-P_{\left(x,y\right)}{\exp }_y^{-1}z\Vert \le Cd\left(x,y\right)$ (3)

证明：由于 $M$ 是一个有限维哈达玛流形，我们可以把 ${\exp }_x^{-1}z$ 看作 $x$ 点处的光滑函数，此时，结论得证。

注 实际上，由引理3.1我们可以得出 $C\ge 1$。梯度向量场在 $M$ 上，当 $\lambda =1$ 时，梯度向量场 $\text{grad}\frac{1}{2}{d}^2\left(\cdot ,z\right)$ 是严格单调的。因此，对任意 $x,y$ 和 $z\in M$，我们有

$\langle {\text{P}}_{\left(x,y\right)}\text{grad}\frac{1}{2}{d}^2\left(\cdot ,z\right)-\text{grad}\frac{1}{2}{d}^2\left(\cdot ,z\right),{\exp }_x^{-1}y\rangle \ge d^2\left(x,y\right)$

即，

$\langle {\text{P}}_{\left(x,y\right)}\left(-{\exp }_y^{-1}z\right)-{\exp }_x^{-1}z,{\exp }_x^{-1}y\rangle \ge d^2\left(x,y\right)$

因此，

$\Vert {\exp }_x^{-1}z-P_{\left(x,y\right)}{\exp }_y^{-1}z\Vert \ge d\left(x,y\right)$

此时，在引理3.2中 $C\ge 1$。

接下来，我们给出哈达玛流形上满足上述假设的定步长近端梯度算法(如下算法1)。

Algorithm 1. Upper proximal gradient method

算法1. M上近端梯度法

收敛性分析

定理3.1 当假设3.1，3.2成立时，算法1生成的迭代序列 $\left\{x_k\right\}$ 在一个有界区域中，设 $x^{*}$ 是 $\left\{x_k\right\}$ 的任意聚点，则 $0\in \partial F\left(x^{*}\right)$。

证明：

$\begin{array}{c}{x}_{k+1}={\text{prox}}_{\alpha g}\left({\exp }_{x_k}\left(-\alpha \text{grad}f\left(x_k\right)\right)\right)\\ =\underset{x\in M}{\arg \min }\frac{1}{2\alpha }{\text{d}}^2\left(x,{\exp }_{x_k}\left(-\alpha \text{grad}f\left(x_k\right)\right)\right)+g\left(x\right)\end{array}$ (5)

令 ${\omega }_k={\exp }_{x_k}\left(-\alpha \text{grad}f\left(x_k\right)\right)$，则

$g\left(x_{k+1}\right)+\frac{1}{2\alpha }{\text{d}}^2\left(x_{k+1},{\omega }_k\right)\le g\left(x_k\right)+\frac{1}{2\alpha }{\text{d}}^2\left(x_k,{\omega }_k\right)$

由 $f$ 的G-L光滑性质，我们有，

$\begin{array}{c}F\left(x_{k+1}\right)=f\left(x_{k+1}\right)+g\left(x_{k+1}\right)\\ \le f\left(x_k\right)+\langle \text{grad}f\left(x_k\right),{\exp }_{x_k}^{-1}{x}_{k+1}\rangle +\frac{L}{2}{\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2\\ +g\left(x_k\right)+\frac{1}{2\alpha }\left({\text{d}}^2\left(x_k,{\omega }_k\right)-{\text{d}}^2\left(x_{k+1},{\omega }_k\right)\right)\end{array}$ (8)

由余弦定理，我们有，

$\begin{array}{l}{\text{d}}^2\left(x_k,{\omega }_k\right)-{\text{d}}^2\left(x_{k+1},{\omega }_k\right)\\ \le -{\text{d}}^2\left(x_{k+1},x_k\right)+2\langle \text{grad}f\left(x_k\right),{\exp }_{x_k}^{-1}{x}_{k+1}\rangle \\ =-{\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2-2\alpha \langle \text{grad}f\left(x_k\right),{\exp }_{x_k}^{-1}{x}_{k+1}\rangle \end{array}$ (9)

由(8)，(9)我们可得，

$\begin{array}{c}F\left(x_{k+1}\right)\le F\left(x_k\right)+\frac{1}{2\alpha }\left(-{\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2-2\alpha \langle \text{grad}f\left(x_k\right),{\exp }_{x_k}^{-1}{x}_{k+1}\rangle \right)\\ +\langle \text{grad}f\left(x_k\right),{\exp }_{x_k}^{-1}{x}_{k+1}\rangle +\frac{L}{2}{\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2\\ =F\left(x_k\right)-\left(\frac{1}{2\alpha }-\frac{L}{2}\right){\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2.\end{array}$ (10)

因为 $\alpha \le \frac{1}{L}$，所以， $F\left(x_{k+1}\right)\le F\left(x_k\right)$。从而可得 $F\left(x_k\right)$ 是非增的，因此，我们有

$F\left(x_k\right)\le F\left(x_1\right),\forall k>0.$

由于 $f$ 是1-强制的，我们可以得到 $\left\{x_k\right\}$ 是有界的，因此， $\left\{x_k\right\}$ 有聚点。因为 $F\left(x_k\right)$ 是非增的且有界，因此， $F$ 在 $\left\{x_k\right\}$ 所有的聚点上都有相同的值，记为 $F^{*}$。

接下来，我们将证明 $\left\{x_k\right\}$ 在一个有界域中。由(10)，我们可得

$\left(\frac{1}{2\alpha }-\frac{L}{2}\right){\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2\le F\left(x_k\right)-F\left(x_{k+1}\right)$

因此，

$\left(\frac{1}{2\alpha }-\frac{L}{2}\right){\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2}\le F\left(x_1\right)-F^{*}<\infty .$

进而，

${\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert }^2\to 0k\to \infty$

由(5)的最优性可得，

$\begin{array}{c}\text{0}\in \partial \text{g}\left(x_{k+1}\right)\text{+}\frac{1}{2\alpha }{\text{gradd}}^2\left(·,{\omega }_k\right)\\ =\text{grad}f\left(x_{k+1}\right)+\partial \text{g}\left(x_{k+1}\right)-\text{grad}f\left(x_{k+1}\right)+\frac{1}{2\alpha }{\text{gradd}}^2\left(·,{\omega }_k\right),\end{array}$

之后，我们有，

$\text{grad}f\left(x_{k+1}\right)-\frac{1}{2\alpha }{\text{gradd}}^2\left(·,{\omega }_k\right)\in \partial F\left(x_{k+1}\right)$

因此，

$\begin{array}{l}\Vert \text{grad}f\left(x_{k+1}\right)-\frac{1}{2\alpha }{\text{gradd}}^2\left(·,{\omega }_k\right)\Vert \\ =\Vert \text{grad}f\left(x_{k+1}\right)-\frac{1}{\alpha }\left(-{\exp }_{x_{k+1}}^{-1}{\omega }_k\right)\Vert \\ =\Vert \text{grad}f\left(x_{k+1}\right)-{\text{P}}_{\left(x_k,x_{k+1}\right)}\text{grad}f\left(x_k\right)+{\text{P}}_{\left(x_k,x_{k+1}\right)}\text{grad}f\left(x_k\right)+\frac{1}{\alpha }{\exp }_{x_{k+1}}^{-1}{\omega }_k\Vert \\ \le L\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert +\frac{1}{\alpha }\Vert {\text{P}}_{\left(x_k,x_{k+1}\right)}\alpha \text{grad}f\left(x_k\right)+{\exp }_{x_{k+1}}^{-1}{\omega }_k\Vert .\end{array}$

因为 $f$ 是G-L光滑的，且 $\left\{x_k\right\}$ 在一个有界域上，存在一个紧集 ${\Omega }_1\supset \left\{x_k\right\}$ 使得 $\text{grad}f\left(x\right)$ 的范数对于任意 $x\in {\Omega }_1$ 是有限的，那么， $\left\{{\omega }_k\right\}$ 自然在一个有界区域 ${\Omega }_2$ 中。除此之外，我们还可得到 $\left\{x_k\right\}$， $\left\{{\omega }_k\right\}$ 都在一个紧集 $\Omega$ 中。因此，由引理可得，存在一个常数 $C$，使得，

$\begin{array}{l}\Vert {\text{P}}_{\left(x_k,x_{k+1}\right)}\alpha \text{grad}f\left(x_k\right)+{\exp }_{x_{k+1}}^{-1}{\omega }_k\Vert \\ =\Vert {\text{P}}_{\left(x_k,x_{k+1}\right)}\left({\exp }_{x_k}^{-1}{\omega }_k\right)+{\exp }_{x_{k+1}}^{-1}{\omega }_k\Vert \\ \le C\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert .\end{array}$ (16)

由(14)，(15)，(16)我们可以得出

$\begin{array}{l}\Vert \text{grad}f\left(x_{k+1}\right)-\frac{1}{2\alpha }{\text{gradd}}^2\left(·,{\omega }_k\right)\Vert \\ \le \left(L+\frac{C}{\alpha }\right)\Vert {\exp }_{x_k}^{-1}{x}_{k+1}\Vert \to 0,\begin{array}{cc}& k\to \infty \end{array}.\end{array}$ (17)

设 $x^{*}$ 是 $\left\{x_k\right\}$ 的任意聚点，当 $j\to \infty$ 时， $\left\{x_k\right\}$ 的子列 $x_{k_j}\to x^{*}$。我们现在证明 $0\in \partial F\left(x^{*}\right)$。由(5)我们知道

$g\left(x_{k_j+1}\right)+\frac{1}{2\alpha }{\text{gradd}}^2\left(x_{k_j+1},{\omega }_{k_j}\right)\le g\left(x^{*}\right)+\frac{1}{2\alpha }{\text{gradd}}^2\left(x^{*},{\omega }_{k_j}\right),$

那么，

$g\left(x_{k_j+1}\right)\le g\left(x^{*}\right)+\frac{1}{2\alpha }\left({\text{gradd}}^2\left(x^{*},{\omega }_{k_j}\right)-{\text{gradd}}^2\left(x_{k_j+1},{\omega }_{k_j}\right)\right).$

有余弦定理，我们可以得到

$g\left(x_{k_j+1}\right)\le g\left(x^{*}\right)-\frac{1}{2\alpha }{\text{gradd}}^2\left(x_{k_j+1},x^{*}\right)+\frac{1}{\alpha }\langle {\exp }_{x^{*}}^{-1}{x}_{k_j+1},{\exp }_{x^{*}}^{-1}{\omega }_{k_j}\rangle .$

由于 $\left\{{\omega }_k\right\}$ 在一个有界区域中，对于任意 $j>0$， ${\exp }_{x^{*}}^{-1}{x}_{k_j+1}$ 自然也是有界的。因此，我们有

$\underset{j\to \infty }{\lim \sup }g\left(x_{k_j+1}\right)\le g\left(x^{*}\right).$

此外，由 $g\left(x\right)$ 下半连续，我们有

$\underset{j\to \infty }{\lim \inf }g\left(x_{k_j+1}\right)\ge g\left(x^{*}\right).$

所以，我们可以得到

$\underset{j\to \infty }{\lim }g\left(x_{k_j+1}\right)=g\left(x^{*}\right).$ (18)

由 $f\left(x\right)$ 的连续性和(18)，可知当 $j\to \infty$，

$F\left(x_{k_j+1}\right)\to F\left(x^{*}\right).$

由(14)，(17)—(19)，以及次微分的定义可得

$0\in \partial F\left(x^{*}\right)$.

4. 结论

本文针对于极小化非凸非光滑函数问题，主要研究了哈达玛流形上的近端梯度算法，我们首先将欧式空间的近端梯度算法推广到哈达玛流形上，再根据该流形的优良结构，给出流形上近端梯度法的收敛性证明。理论上，我们可以得出我们提出的哈达玛流形上的近端梯度算法是收敛的。由于流形上非线性性质，收敛速度的理论研究存在一定的困难，还需要进一步研究。