Hadamard流形上变分不等式的Armijo型切半空间投影外梯度法

An Armijo-Type Extragradient Algorithm with Half-Space Projection for Variational Inequalities on Hadamard Manifolds

摘要: 本文针对Hadamard流形上的变分不等式问题，提出了一种改进的切半空间投影外梯度算法(R-SSEG)。该算法旨在解决传统外梯度法在流形环境下因执行两次度量投影而导致的计算成本过高问题。不同于以往研究中将投影步骤抽象为算子的操作，本文充分利用流形的切空间线性结构，基于KKT条件推导出了切半空间投影的显式闭式解，从而显著降低了单步迭代的计算复杂度。同时，算法采用Armijo型线搜索准则，保证了迭代序列的能量单调下降性质。在理论上，我们证明了算法在单调条件下的全局收敛性，并在强伪单调条件下建立了序列的Q-线性收敛速率。最后，进行高维环境的大规模数值仿真实验，验证了该算法相比于经典及前沿同类算法在计算效率上的优势。

Abstract: This paper investigates the variational inequality problem on Hadamard manifolds. To mitigate the high computational burden incurred by executing two metric projections in traditional extragradient methods within manifold environments, we propose a modified Tangent Half-space Projection Extragradient Algorithm (R-SSEG). Distinct from existing studies that conceptualize the projection step merely as an abstract operator, this work fully exploits the linear structure of the tangent space. Based on the Karush-Kuhn-Tucker (KKT) conditions, we derive an explicit closed-form solution for the tangent half-space projection, thereby significantly reducing the computational complexity of single-step iterations. Furthermore, the algorithm incorporates an Armijo-type line search criterion, which theoretically guarantees the monotonic descent property of the energy of the iterative sequence. In terms of theoretical analysis, we establish the global convergence of the algorithm under monotone conditions and prove the Q-linear convergence rate of the sequence under strongly pseudomonotone conditions. Finally, large-scale numerical simulations in high-dimensional settings are conducted, verifying the superior computational efficiency of the proposed algorithm compared to both classical and state-of-the-art counterparts.

1. 引言

变分不等式(Variational Inequalities, VI)作为非线性分析与最优化中的核心模型，在机器学习[1]、网络均衡、图像与信号重建、稀疏表示等诸多领域均有广泛应用；在欧式有限与无限维线性空间中，VI的理论与算法已形成较为完备的体系，参见例如[2] [3]及其中的参考文献。近年来，随着数据与约束结构的几何化趋势增强，越来越多的实际问题天然地以流形约束形式出现，变量所在空间不再是线性空间，而是带有内在几何的黎曼流形，典型例子包括正定矩阵空间、Grassmann、Stiefel流形、超球与双曲空间等。此时，约束常表现为非线性甚至非凸，线性空间方法难以直接迁移，促使人们将VI的理论与算法从欧氏空间推广到黎曼流形框架，参见例如[4]-[6]。这一推广不仅能忠实刻画问题的几何本质，还可在不引入局部坐标的情况下利用全局几何结构获得更为稳定与可解释的算法性质；相应地许多欧式空间中的优化、均衡方法在流形情形下也展现出重要优势，参见例如[6]。

具体而言，本文聚焦于Németh [4]在Hadamrd流形上提出的变分不等式问题。设$M$ 为一维数有限的Hadamrd流形，$C\subset M$ 为非空闭测地凸集，$F:C\to TM$ 为一单值向量场。该问题旨在寻找一点$x^{\text{*}}$ ，使得对任意$y\in C$ ，满足如下不等式：

$\langle F\left(x^{\text{*}}\right),{\text{exp}}_{x^{\text{*}}}^{-1}y\rangle \ge 0$ (1.1)

其中$\langle \cdot ,\cdot \rangle$ 表示黎曼度量，${\text{exp}}^{-1}$ 表示黎曼指数映射的逆映射。该模型是经典欧氏空间变分不等式在黎曼几何框架下的自然推广，也是后续算法设计与收敛性分析的数学基础。

鉴于流形上度量投影的高昂计算成本，如何设计高效的投影算法成为近年来的研究热点。Censor等人[7]在欧氏空间提出了次梯度外梯度法，通过向包含解集的半空间投影来替代向原约束集的第二次投影。随后，这一思想被推广至黎曼流形环境[8] [9]。

在步长策略的选择上，近期的研究呈现出多样化的趋势。一方面，为了避免线搜索带来的额外计算，Tan等人[10]最近提出了一种基于自适应步长的流形次梯度外梯度算法，通过局部信息动态调整步长参数。类似的自适应方法也见于Sahu等人[11]的研究，此外，Shehu等人[12]引入了惯性加速技术，Alakoya等人[13]则搜索了金分割步长策略。另一方面，经典的Armijo型线搜索凭借其严格的能量耗散性质和理论分析上的几何直观性，在保证算法全局稳健收敛方面依然具有不可替代的重要价值。特别是在处理高维复杂约束问题时，如何结合切空间几何结构，设计出兼具理论深度与计算便捷性的算法框架，仍值得深入探究。

受上述工作启发，本文提出了一种Hadamard流形上的Armijo型切半空间投影外梯度算法(R-SSEG)。与现有工作相比，本文的主要贡献在于：构造了基于KKT条件的显式投影公式，不同于部分文献将半空间投影仅描述为抽象算子，我们利用黎曼指数映射的逆映射将问题转化至切空间，并基于KKT条件推导出了半空间投影的显式解析解。这一处理将复杂的流形子问题简化为切空间中的向量代数运算，极大地提升了算法的可执行性。在Armijo准则下，严格证明了算法生成的序列满足单调下降性质。在算子满足单调性和Lipschitz连续性时证明了全局收敛性；在强伪单调条件下，进一步证明了算法具有Q-线性收敛速率。通过高维的变分不等式算例，验证了该算法在大规模问题中相比于传统算法及同类前沿算法在计算时间与收敛精度上的综合优势。

本文的结构如下。第二节介绍黎曼流形上的基础知识和性质。主要内容在第三节，包括算法的收敛性质以及收敛速率。第四节是数值模拟。第五节是总结。

2. 预备知识

本节介绍本文所用的符号和Hadamard流形上的基本概念和性质，可参阅文献[14]。

设$M$ 为一有限维可微流形，对任意$x\in M$ ，记其切空间为$T_{x}M$ 。Hadamard流形上切空间$T_{x}M$ 是与${ℝ}^n$ 等距同构的Hilbert空间，所有切空间的并$TM\text{:}={\displaystyle \underset{x\in M}{\cup }{T}_{x}M}$ 称为切丛。若在每个$T_{x}M$ 上配备一个内积${\langle \cdot ,\cdot \rangle }_x$ ，则$\left(M,\langle \cdot ,\cdot \rangle \right)$ 称为黎曼流形，相应的范数记为${\Vert V\Vert }_x=\sqrt{{\langle V,V\rangle }_x}$ 。后续不引起混淆时下标$x$ 省略。

记$\nabla$ 为与黎曼度量相容且无挠的Levi-Civita连接。设$\gamma :\left[a,b\right]\to M$ 为分段$C^1$ 曲线，其长度$\ell \left(\gamma \right)\text{:}={\displaystyle {\int }_a^b\Vert \dot{\gamma }\left(t\right)\Vert \text{d}t}$。若${\nabla }_{\dot{\gamma }}\dot{\gamma }=0$ ，则称$\gamma$ 为测地线；当$\Vert \dot{\gamma }\left(t\right)\Vert \equiv 1$ 时称其为单位测地线。对任意$x,y\in M$ ，定义两点之间的黎曼距离$d\left(x,y\right)\text{:}=\text{inf}\left\{\ell \left(\gamma \right):\gamma :x⇝y\right\}$ 。若某条曲线的长度达到该下确界，则称其为连接$x$ ，$y$ 的最短测地线。

设$\gamma :\left[a,b\right]\to M$ 为光滑曲线。向量场$F$ 若满足${\nabla }_{\dot{\gamma }}F=0$ ，则称向量场$F$ 沿$\gamma$ 平行。对任意$v\in T_{\gamma \left(a\right)}M$ ，会存在唯一平行的向量场$V$ 使得$V\left(\gamma \left(a\right)\right)=v$ 。我们定义平行移动，。当$\gamma$ 是连接$x$ ，$y$ 的最短测地线时，记代替。平行移动是等距同构：。

对任意$x\in M$ 与$v\in T_{x}M$ ，记${\gamma }_v\left(\cdot ,x\right)$ 为以$x$ 为起点、初速度为$v$ 的测地线。指数映射${\exp }_x:T_{x}M\to M$ ，即${\exp }_x\left(v\right):={\gamma }_v\left(1,x\right)$ ，该映射是一个微分同胚。本文后续统一记其逆映射(即黎曼对数映射)为${\log }_x:={\exp }_x^{-1}$ ；当$y$ 与$x$ 由唯一最短测地线相连时，${\log }_{x}y\in T_{x}M$ 合法且满足$\Vert {\log }_{x}y\Vert =d\left(x,y\right)$ 。

引理1. [14] (Hopf-Rinow)若从任意点出发的测地线在所有$t\in ℝ$ 上都有定义，则称$M$ 完备。若$M$ 完备，则有

(i) 任意两点可由最短测地线连接；

(ii) 度量空间$\left(M,d\right)$ 完备且有界闭集紧；

(iii) 对每个$x$ ，${\exp }_x$ 在某领域内为微分同胚。

若$M$ 完备、单连通且所有截面曲率非正，则称$M$ 为Hadamard流形。

下文算法以及收敛性均在Hadamard流形上讨论，有以下全局性质：

(i) 对任意$x\in M$ ，$\exp :T_{x}M\to M$ 为微分同胚，因而${\log }_x$ 在全体$M$ 上是良定的；

(ii) 任意两点由唯一最短测地线连接；

(iii) 距离由对数映射给出：$d\left(x,y\right)=\Vert {\log }_{x}y\Vert$ ；

(iv) 沿唯一测地线的平行移动唯一且为等距同构。

引理2. 设$\Delta \left(p_1,p_2,p_3\right)$ 是Hadamard流形$M$ 中的一个测地三角形，则对每个$i=1,2,3\left(\text{mod}\text{3}\right)$ ，令${\gamma }_i:\left[0,l_i\right]\to M$ 为连接$p_i$ 到$p_{i+1}$ 的测地线，其长度为$l_i=L\left({\gamma }_i\right)$ ，并令${\alpha }_i:=\angle \left({{\gamma }^{\prime }}_i\left(0\right)\text{,}-{{\gamma }^{\prime }}_{i-1}\left(l_{i-1}\right)\right)$ 表示切向量${{\gamma }^{\prime }}_i\left(0\right)$ 与$-{{\gamma }^{\prime }}_{i-1}\left(l_{i-1}\right)$ 之间的夹角，那么成立：

(i) ${\alpha }_1+{\alpha }_2+{\alpha }_3\le \pi$ ；

(ii) $l_i^2+l_{i+1}^2-2l_i{l}_{i+1}\cos {\alpha }_{i+1}\le l_{i-1}^2$ ；

(iii) $l_{i+1}\cos {\alpha }_{i+2}+l_i\cos {\alpha }_i\ge l_{i+2}$ 。

利用距离函数与对数映射，命题中的(i)和(iii)可分别改写为：

$d^2\left(p_i,p_{i+1}\right)+d^2\left(p_{i+1},p_{i+2}\right)-2\langle {\log }_{p_{i+1}}{p}_i,{\log }_{p_{i+1}}{p}_{i+2}\rangle \le d^2\left(p_{i-1},p_i\right)$

与

$d\left(p_i,p_{i+1}\right)\le \langle {\log }_{p_i}{p}_{i+2},{\log }_{p_i}{p}_{i+1}\rangle +\langle {\log }_{p_{i+1}}{p}_{i+2},{\log }_{p_{i+1}}{p}_i\rangle ,$

这里用到了关系式$\langle {\log }_{p_{i+1}}{p}_i,{\log }_{p_{i+1}}{p}_{i+2}\rangle =d\left(p_i,p_{i+1}\right)d\left(p_{i+1},p_{i+2}\right)\cos {\alpha }_{i+1}$ 。更多细节可参阅[15]。

引理3. 设$\left\{x_n\right\}\subset M$ ，使得$x_n\to x_0\in M$ ，则有

(i) 对任意的$y\in M$ 有${\log }_{x_n}\left(y\right)\to {\log }_{x_0}\left(y\right)$ 以及${\log }_y\left(x_n\right)\to {\log }_y\left(x_0\right)$ 。

(ii) 如果$c_n\in T_{x_n}M$ 以及$c_n\to c_0$ ，那么$c_0\in T_{x_0}M$ 。

(iii) 给$u_n,v_n\in T_{x_n}M$ 以及$u_0,v_0\in T_{x_0}M$ ，如果$u_n\to u_0$ ，$v_n\to v_0$ ，则有$\langle u_n,v_n\rangle \to \langle u_0,v_0\rangle$ 。

定义1. 在Hadamard流形$M$ 上，给定非空闭测地凸集$C\subset M$ ，对任意的$x\in M$ ，$x$ 到$C$ 的投影为

$P_C\left(x\right):=\underset{y\in C}{\arg \min }d\left(x,y\right)$ .

定义2. 设$M$ 是Hadamard流形，算子$F$ 是一个向量场，如果对任意的$x\in M$ ，$F\left(x\right)\in T_{x}M$ ，则称该向量场$F$ 为单值的。

定义3. [16]设$M$ 为一个Hadamard流形。称向量场$F\in \mathfrak{X}\left(M\right)$ ：

(i) 是单调的，若对任意$x,y\in M$ ，满足$\langle F\left(x\right),{\log }_{x}y\rangle \le \langle F\left(y\right),-{\log }_{y}x\rangle$ ；

(ii) 是伪单调的，若对任意$x,y\in M$ ，满足$\langle F\left(x\right),{\log }_{x}y\rangle \ge 0$ ，有$\langle F\left(y\right),{\log }_{y}x\rangle \le 0$ ；

(iii) 是强伪单调的[17]，若对任意$x,y\in M$ ，满足$\langle F\left(x\right),{\log }_{x}y\rangle \ge 0$ ，则存在常数$\zeta >0$ ，使得

$\langle F\left(y\right)\text{,}{\log }_{y}x\rangle \le -\zeta d^2\left(x,y\right)$ .

定义4. 对任意$x,y\in M$ ，给定常数$L>0$ ，我们说向量场$F$ 是Lipschitz的，若

接着将本文研究的主要问题通过以下定义形式给出。

定义5. 设$M$ 是Hadamard流形，$C\subset M$ 是测地凸集，向量场$F:C\to TM$ ，黎曼变分不等式(RVI)即对任意的$y\in C$ ，找到$x\in C$ ，使得

$\langle F\left(x\right)\text{,}{\log }_{x}y\rangle \ge 0$

当$M={ℝ}^n$ 时，${\log }_{x}y=y-x$ ，即经典${ℝ}^n$ 中的变分不等式(VI)，$\langle F\left(x\right),y-x\rangle \ge 0$ 。

3. 主要结果

在本节中，将介绍我们的一种Armijo型切半空间投影外梯度算法，且在后续讨论中，我们需要假设满足以下条件：

(H1) $\text{RVI}\left(C,F\right)$ 解集非空，即$\text{Sol}\left(C,F\right)\ne \varnothing$ 。

(H2) $M$ 为Hadamard流形，因而对任意非空闭测地凸集$C\subset M$ ，度量投影$P_C$ 单值且非扩张。

(H3) 集合$C\subset M$ 非空、闭、且测地凸。向量场$F:C\to TM$ ，满足$F\left(x\right)\in T_{x}M$ ，$F$ 是强伪单调的，且在有界集上一致连续。

(H4) 取Armijo参数$u\in \left(0,1\right)$ 、步长衰减率$l\in \left(0,1\right)$ 、以及初始步长收缩因子$\gamma >0$ 。

下面的引理将在证明收敛时有用。

引理4. 令能量泛函$E_n:={\Vert v_n\Vert }^2$ ，对算法中的

$v_{n+1}=v_n-\max \left\{0,\frac{\langle s_n,v_n\rangle }{{\Vert s_n\Vert }^2}\right\}{s}_n$ ，$H_n^{\tan }=\left\{v:\langle s_n,v\rangle \le 0\right\}$ ，$s_n={\log }_{y_n}{u}_n$ ，且记${\rho }_n=\frac{{\langle s_n,v_n\rangle }_{+}}{\Vert s_n\Vert }$ ，有

$E_{n+1}\le E_n-\frac{{\left({\langle s_n,v_n\rangle }_{+}\right)}^2}{{\Vert s_n\Vert }^2}$

其中${\left(a\right)}_{+}=\max \left\{a,0\right\}$ 。

证明 记${\alpha }_n:=\max \left\{0,\frac{\langle s_n,v_n\rangle }{{\Vert s_n\Vert }^2}\right\}$ ，$v_n\in T_{y_n}M$ ，则有$v_{n+1}=v_n-\alpha s_n$ ，且

${\Vert v_{n+1}\Vert }^2={\Vert v_n\Vert }^2-2\alpha \langle s_n,v_n\rangle +{\alpha }^2{\Vert s_n\Vert }^2$

(i) 若$\langle s_n,v_n\rangle \le 0$ ，则${\alpha }_n=0$ ，${\Vert v_{n+1}\Vert }^2={\Vert v_n\Vert }^2$ ，等号成立；

(ii) 若$\langle s_n,v_n\rangle >0$ ，则${\alpha }_n=\frac{\langle s_n,v_n\rangle }{{\Vert s_n\Vert }^2}$ ，那么${\Vert v_{n+1}\Vert }^2={\Vert v_n\Vert }^2-\frac{{\left({\langle s_n,v_n\rangle }^2\right)}_{+}}{{\Vert s_n\Vert }^2}$

综上，不等式成立，且$\langle s_n,v_n\rangle >0$ 时能量泛函严格下降。

该引理说明通过修正外法分量后所得的向量沿着迭代方向的能量是严格下降的，在物理或某些其他领域叫做能量耗散，这将为我们后续算法构造Lyapunov型函数提供理论支撑。

引理5. 设$M$ 是Hadamard流形，在任意紧领域$U\subset M\times M\times TM$ 内，存在常数$C>0$ ，使得对所有$\left(x,y,\xi \right)\in U$ 有

(1.2)

其中余项满足$\Vert R\left(x,y,\xi \right)\Vert \le C\left(d^2\left(x,y\right)+d\left(x,y\right)\Vert \xi \Vert +{\Vert \xi \Vert }^2\right)$ ，特别地，当$d\left(x,y\right)\to 0$ 时，且$\Vert \xi \Vert$ 有界时，$\Vert R\left(x,y,\xi \right)\Vert \to 0$ 。

证明 固定$y\in M$ ，记$a:={\log }_{y}x\in T_{y}M$ ，，则$\Vert a\Vert =d\left(x,y\right)$ ，$\Vert \omega \Vert =\Vert \xi \Vert$ ；

设$\xi \in T_{x}M$ ，定义二元映射$\phi \left(a,\omega \right)={\log }_y\left({\exp }_x\xi \right)$ ，易知$\phi$ 在$\left(a,\omega \right)=\left(\text{0,0}\right)$ 附近是$C^2$ 的。且显然$\phi \left(\text{0,0}\right)={\log }_y\left({\exp }_{y}0\right)={\log }_{y}y=0$ ；

令$a=0$ ，对$\forall h\in T_{y}M$ ，令$\omega \left(t\right)=th$ ，

考虑复合曲线$\gamma \left(t\right)=\phi \left(\text{0,}\omega \left(t\right)\right)={\log }_y\left({\exp }_{y}th\right)$ ，即${\gamma }^{\prime }\left(0\right)=h$ ；另一方面，

${\gamma }^{\prime }\left(0\right)=D_{\omega }\phi \left(0,0\right)\left[h\right]=h$

即$D_{\omega }\phi \left(\text{0,0}\right)=Id$ 。

令$\omega =0$ ，对$\forall h\in T_{y}M$ ，令$a\left(t\right)=th$ ，记$x\left(t\right)={\exp }_y\left(a\left(t\right)\right)$ ，

考虑复合曲线$\eta \left(t\right)=\phi \left(a\left(t\right),0\right)={\log }_y\left({\exp }_{x\left(t\right)}0\right)={\log }_y\left(x\left(t\right)\right)={\log }_y\left({\exp }_y\left(th\right)\right)$ ，$D_a\phi \left(\text{0,0}\right)=Id$ 。

从而有

$D\phi \left(0,0\right)\left[\left(a,\omega \right)\right]=D_a\phi \left(0,0\right)\left[a\right]+D_{\omega }\phi \left(0,0\right)\left[\omega \right]=a+\omega ,$

由Taylor展开

$\phi \left(a,\omega \right)=\phi \left(0,0\right)+D\phi \left(0,0\right)\left[\left(a,\omega \right)\right]+R\left(a,\omega \right)$

故(1.1)得证。

对于$T_{y}M\times T_{y}M\subset {ℝ}^n$ ，$\phi \left(a,\omega \right)$ 可看作Banach空间值的$C^2$ 映射。

又$\forall \left(a,\omega \right)\in T_{y}M\times T_{y}M$

$\phi \left(a,\omega \right)=\phi \left(0,0\right)+D\phi \left(0,0\right)\left[\left(a,\omega \right)\right]+{\displaystyle {\int }_0^1\left(1-t\right)D^2\phi }\left(ta,t\omega \right)\left[\left(a,\omega \right),\left(a,\omega \right)\right]\text{d}t,$

令$R\left(a,\omega \right)={\displaystyle {\int }_0^1\left(1-t\right)D^2\phi }\left(ta,t\omega \right)\left[\left(a,\omega \right),\left(a,\omega \right)\right]\text{d}t$ ，由积空间紧，易知

$\underset{\Vert \left(u,v\right)\Vert \le \epsilon }{\sup }\Vert D^2\phi \left(u,v\right)\Vert \le C^{\prime },$

从而

$\Vert R\left(a,\omega \right)\Vert \le {\displaystyle {\int }_0^1\left(1-t\right)\Vert D^2\phi \left(ta,t\omega \right)\Vert {\Vert \left(a,\omega \right)\Vert }^2\text{d}t}\le \frac{1}{2}{C}^{\prime }{\Vert \left(a,\omega \right)\Vert }^2,$

常数吸收即得

$\Vert R\left(a,\omega \right)\Vert \le C\left({\Vert a\Vert }^2+\Vert a\Vert \Vert \omega \Vert +{\Vert \omega \Vert }^2\right)$

综上得证。

引理6. 设$\left(M,g\right)$ 是Hadamard流形，可行集$C\subset M$ 闭、测地凸。给定迭代

若存在$\left\{x_n\right\}$ 满足：

${\rho }_n=\frac{{\left(\langle s_n,v_n\rangle \right)}_{+}}{\Vert s_n\Vert }\to 0$ 、$d\left(x_n,y_n\right)\to 0$ 、，

且$x_n\to x^{*}\in C$ ，则极限点$x^{*}$ 满足RVI，即$\forall \omega \in C$

$\langle F\left(x^{*}\right)\text{,}{\log }_{x^{*}}\omega \rangle \ge 0$ .

证明 由引理3以及$d\left(x_n,y_n\right)\to 0$ ，且$x_n\to x^{*}$ 知$y_n\to x^{*}$ ，又由$y_n=P_C\left(u_n\right)$ 的度量投影最优性知，

$\begin{array}{cc}\forall \omega \in C,& \langle s_n,{\log }_{y_n}\omega \rangle \le 0\end{array}$ (1.3)

由引理4

(1.4)

其中

$\Vert R_n\Vert \le C\left(d^2\left(x_n,y_n\right)+{\beta }_{n}d\left(x_n,y_n\right)\Vert F\left(x_n\right)\Vert +{\beta }_n^2{\Vert F\left(x_n\right)\Vert }^2\right)$ ,

由Armijo回溯步长可得$\left\{{\beta }_n\right\}$ 的统一上界，${\beta }_n\le \frac{\mu }{L}$ ，$F$ 连续易得$\left\{{\beta }_n\Vert F\left(x_n\right)\Vert \right\}$ 有界，结合(1.4)有

记$d_n:=d\left(x_n,y_n\right)$ 、$T_n:={\beta }_n\Vert F\left(x_n\right)\Vert$ 、${\tilde{T}}_n:=\Vert v_n\Vert ={\beta }_n\Vert F\left(y_n\right)\Vert$ 、$e_n:={\log }_{y_n}{x}_n+R_n$ ，从而Armijo接受准则为

$F$ 的Lipschitz性知

${\tilde{T}}_n={\beta }_n\Vert F\left(y_n\right)\Vert \le {\beta }_n\left(\Vert F\left(x_n\right)\Vert +L{d}_n\right)=T_n+{\beta }_{n}L{d}_n\le T_n+\overline{\beta }L{d}_n$ ,

其中$\overline{\beta }=\frac{\mu }{L}$ ，则

,

且有$\Vert e_n\Vert \le d_n+\Vert R_n\Vert$ ，再由引理4得

$\Vert R_n\Vert \le C\left(d_n^2+d_n{T}_n+T_n^2\right)\le C{\left(d_n+T_n\right)}^2$ ,

从而

$\begin{array}{c}{\langle s_n,v_n\rangle }_{+}\le d_n{\tilde{T}}_n+T_n{\tilde{T}}_n+\Vert R_n\Vert {\tilde{T}}_n\\ \le \left(T_n+\overline{\beta }L{d}_n\right)\left(d_n+T_n+\Vert R_n\Vert \right)\\ \le T_n\left(T_n+d_n\right)+C_1{\left(d_n+T_n\right)}^2\end{array}$

又

从而

${\rho }_n=\frac{{\langle s_n,v_n\rangle }_{+}}{\Vert s_n\Vert }\le \frac{T_n\left(T_n+d_n\right)+C_1{\left(d_n+T_n\right)}^2}{T_n-d_n-C_2{\left(d_n+T_n\right)}^2}$ (1.5)

下证$T_n\to 0$ ，反证，假设$T_n\cancel{\to }0\left(n\to \infty \right)$ ，则定存在子列$\left\{n_k\right\}$ ，使得$T_{n_k}>0$ ，即

$\underset{n\to \infty }{\lim }\text{sup}{T}_n=\tau >0,且T_{n_k}\ge \frac{\tau }{2},\forall k>0,$ (1.6)

从而对(1.5)，取$\delta >0$ ，做常数吸收，$\exists c_0>0$ ，使得

${\rho }_n=\frac{{\langle s_n,v_n\rangle }_{+}}{\Vert s_n\Vert }\ge \frac{c_0{T}_n^2}{T_n}=c_0{T}_n$ ,

但由(1.6)，有${\rho }_n\ge c_0\frac{\tau }{2}>0$ ，矛盾，从而$T_n\to 0\left(n\to \infty \right)$ 。

此时，由Armijo准则给

有

$s_n=-{\beta }_{n}F\left(y_n\right)+o\left(n\right)$ (1.7)

其中$o\left(n\right)$ 由投影位移和场值差控制，结合(1.3) (1.7)有

$\langle -{\beta }_{n}F\left(y_n\right)+o\left(n\right)\text{,}{\log }_{y_n}\omega \rangle \le 0$

令$n\to \infty$ ，则$y_n\to x^{*}$ ，即有$\forall \omega \in C$

$\langle F\left(x^{*}\right)\text{,}{\log }_{x^{*}}\omega \rangle \ge 0$

综上得证。

该引理直接给出了我们算法(R-SSEG)迭代的停机准则，这是一个必要条件，说明只要当两类残差趋于0，则任何聚点都是RVI的解。

引理7. 设向量场$F$ 在$C$ 上满足L-Lipschitz连续。若采用算法1中的Armijo线搜索规则，则生成的步长序列$\left\{{\beta }_n\right\}$ 是有界的。即对任意$n\ge 0$ 均有：

$\min \left\{\gamma ,\frac{\mu l}{L}\right\}\le {\beta }_n\le \gamma$

其中$\gamma$ 为初始缩放因子，$l$ 为衰减率，$\mu$ 为Armijo参数。

证明 由算法1的步骤1，每次迭代开始前，令试探步长$\beta =\gamma$ 。若该步长满足Armijo条件，则${\beta }_n=\gamma$ ；若不满足，则由因子$l\in \left(\text{0,1}\right)$ 进行回溯缩减。最终接受的步长${\beta }_n\le \gamma$ 。

若初始步长$\beta =\gamma$ 满足条件，则${\beta }_n=\gamma$ ，下界显然成立。若需回溯，假设在第$m_n$ 次回溯时步长被接受。由Lipschitz连续性及Armijo准则，当试探步长$\beta \le \frac{\mu }{L}$ 时，不等式条件成立，即回溯过程不会无限进行，由于${\beta }_n$ 是接受步长，而其前一次试探步长${\beta }^{\prime }=\frac{{\beta }_n}{l}$ 必定不满足条件，故必有${\beta }^{\prime }>\frac{\mu }{L}$ ，综上得证。

引理8. 对$\forall \omega \in H_n^{\tan }$ ，有$\langle v_n-v_{n+1},\omega -v_{n+1}\rangle \le 0$ ，且若取$\omega =0$ 以及$\omega ={\log }_{y_n}p\left(p\in C\right)$ ，则分别有

$\langle v_n,v_{n+1}\rangle \ge {\Vert v_{n+1}\Vert }^2$

$\langle {\log }_{y_n}p,v_{n+1}\rangle \ge \langle {\log }_{y_n}p,v_n\rangle .$

证明 在$T_{y_n}M$ 中，给$s_n\ne 0$ ，$H_n^{\tan }=\left\{\omega \in T_{y_n}M:\langle s_n,\omega \rangle \le 0\right\}$ ，$H_n^{\tan }$ 闭且凸，$v_{n+1}$ 是$v_n$ 到$H_n^{\tan }$ 的正交投影，$\forall \omega \in H_n^{\tan }$ ，考虑线段$\omega \left(t\right)=\left(1-t\right)v_{n+1}+t\omega$ ，其中$t\in \left[\text{0},\text{1}\right]$ ，则$\forall t\in [\text{0},\text{1}]$ 都有$\omega \left(t\right)\in H_n^{\tan }$ ，令

$g\left(t\right)={\Vert v_n-\omega \left(t\right)\Vert }^2$ ,

由$v_{n+1}$ 是到$H_n^{\tan }$ 的最近点，则$t=0$ 也是使$g\left(t\right)$ 最小的点，即$\forall t\in \left[\text{0},\text{1}\right]$ ，$g\left(t\right)\ge g\left(0\right)$ ，而$g$ 是关于$t$ 的多项式，$t=0$ 是最小值点，从而右导数$g^{\prime }\left(0_{+}\right)\ge 0$ ，有

$v_n-\omega \left(t\right)=\left(v_n-v_{n+1}\right)-t\left(\omega -v_{n+1}\right)$ ,

$g\left(t\right)={\Vert \left(v_n-v_{n+1}\right)-t\left(\omega -v_{n+1}\right)\Vert }^2={\Vert v_n-v_{n+1}\Vert }^2-2t\langle v_n-v_{n+1},\omega -v_{n+1}\rangle +t^2{\Vert \omega -v_{n+1}\Vert }^2$ ,

则

$g^{\prime }\left(t\right)=-2\langle v_n-v_{n+1},\omega -v_{n+1}\rangle +2t{\Vert \omega -v_{n+1}\Vert }^2$ ,

$g^{\prime }\left(0_{+}\right)=-2\langle v_n-v_{n+1},\omega -v_{n+1}\rangle$ ,

$\langle v_n-v_{n+1},\omega -v_{n+1}\rangle \le 0$ .

若取$\omega =0$ ，则$\langle v_n,v_{n+1}\rangle \ge {\Vert v_{n+1}\Vert }^2$ ；

若取$\omega ={\log }_{y_n}p$ ，有

$\langle s_n,{\log }_{y_n}p\rangle \le 0$

即${\log }_{y_n}p\in H_n^{\tan }$

从而有

$\langle v_n-v_{n+1},{\log }_{y_n}p-v_{n+1}\rangle \le 0$

即

$\langle v_n-v_{n+1},{\log }_{y_n}p\rangle \le \langle v_n-v_{n+1},v_{n+1}\rangle$

展开会有

$\langle v_{n+1},{\log }_{y_n}p\rangle \ge \langle v_n,{\log }_{y_n}p\rangle$

综上得证。

下面这个引理给出的不等式是由RVI结合单调性结合得出的派生不等式。注意这与RVI定义并不产生歧义。

引理9. 若$p\in Sol$ ，则对$\forall y\in C$ ，有

$\langle F\left(y\right)\text{,}{\log }_{y}p\rangle \le 0$ .

证明 由(1.1)知，$\forall p\in Sol$ ，有

$\langle F\left(p\right)\text{,}{\log }_{p}y\rangle \le 0$

作平行移动到$T_{y}M$ ，得

由定义3易得

(1.8)

取$x=p$ ，结合(1.8)有

综上得证。

引理10. 由算法步骤3，设$x_{n+1}={\exp }_{y_n}\left(v_{n+1}\right)$ ，则对$\forall p\in C$ ，有

$d^2\left(x_{n+1},p\right)\le d^2\left(y_n,p\right)+{\Vert v_{n+1}\Vert }^2-2\langle v_{n+1},{\log }_{y_n}p\rangle .$

证明 将距离函数写成一个光滑凸函数，固定$\omega$ ，

$f_{\omega }\left(x\right)\text{:}=\frac{1}{2}{d}^2\left(x,\omega \right)$ (1.9)

在Hadamard流形上，$f_{\omega }\left(x\right)$ 测地凸，黎曼梯度$\nabla f_{\omega }\left(y\right)=-{\log }_y\omega$ ，且$Hess{f}_{\omega }\left(y\right)\le Id$ 。

对$\forall v\in T_{y}M$ ，有

$f_{\omega }\left({\exp }_{y}v\right)\le f_{\omega }\left(y\right)+\langle \nabla f_{\omega }\left(y\right)\text{,}v\rangle +\frac{1}{2}{\Vert v\Vert }^2$

将(1.9)代入上式得

$\frac{1}{2}{d}^2\left({\exp }_{y}v,\omega \right)\le \frac{1}{2}{d}^2\left(y,\omega \right)+\frac{1}{2}{\Vert v\Vert }^2-\langle {\log }_y\omega ,v\rangle ,$

取$\left(y,v,\omega \right)=\left(y_n,v_{n+1},p\right)$ ，引理得证。

通过上述一系列引理，接下来给出我们拟解决的问题(1.1)的算法(R-SSEG)。

Algorithm 1. Armijo-type Cut Half-space Projection Extragradient Algorithm (R-SSEG)

算法1. Armijo型切半空间投影外梯度算法(R-SSEG)

初始化 选初始点$x_0\in C$ 。设定初始步长缩放因子$\gamma >0$ ，Armijo参数$\mu \in \left(\text{0,1}\right)$ ，步长衰减率$l\in \left(\text{0,1}\right)$ ，容忍度$\epsilon >0$ 。置迭代计数器$n=0$ 。 步骤1 令试探步长$\beta =\gamma$ ，执行以下Armijo线搜索过程 计算试探点$u={\exp }_{x_n}\left(-\beta F\left(x_n\right)\right)$ ，$y=P_C\text{(}u\text{)}$ ， 检查Armijo条件 , 若不满足，则令$\beta \leftarrow \beta \cdot l$ ，重复上述计算； 若满足，则记当前步长为${\beta }_n=\beta$ 、中间点为$y_n=y$ 。 步骤2 若$d\left(x_n,y_n\right)<\epsilon$ ，则停止迭代，输出$x_n$ 为(1.1)的解。否则，在切空间$T_{x_n}M$ 中执行显式修正 $s_n={\text{log}}_{x_n}{y}_n$ , 计算$v_n$ 在半空间 $H_n^{\text{tan}}=\left\{v\in T_{x_n}M:\langle s_n,v\rangle \le 0\right\}$ 上的投影$v_{n+1}$ ，为 $v_{n+1}=v_n-\text{max}\left\{0,\frac{\langle s_n,v_n\rangle }{{\Vert s_n\Vert }^2}\right\}{s}_n$ . 步骤3 以修正后的方向生成下一个迭代点 $x_{n+1}={\exp }_{y_n}\left(v_{n+1}\right)$ . 步骤4 满足以下准则时停止 $d\left(x_n,y_n\right)\le \epsilon ,{\rho }_n:=\frac{{\left(s_n,v_n\right)}_{+}}{\Vert s_n\Vert }\le \epsilon .$ 否则令$n\leftarrow n+1$ ，返回步骤1。

接下来这个命题给出算法中修正外法向量的显式推导。

命题1 设$H_n^{\tan }=\left\{v\in T_{x_n}M:\langle s_n,v\rangle \le 0\right\}$ 为切空间中的闭半空间，其中$s_n\ne 0$ 。对任意$v_n\in T_{x_n}M$ ，其在$H_n^{\tan }$ 上的度量投影$v_{n+1}=P_{H_n^{\tan }}\left(v_n\right)$ 具有如下显式闭式解，

$v_{n+1}=v_n-\max \left\{0,\frac{\langle s_n,v_n\rangle }{{\Vert s_n\Vert }^2}\right\}{s}_n.$

证明 由度量投影的定义，求解投影$v_{n+1}$ 等价于在Hilbert空间$T_{x_n}M$ 中求解如下二次规划问题，

$\begin{array}{l}\underset{v\in T_{x_n}M}{\min }\frac{1}{2}{\Vert v-v_n\Vert }^2\\ \text{s}\text{.t}\text{.}\langle s_n,v\rangle \le 0\end{array}$

引入拉格朗日乘子$\lambda \ge 0$ ，构造拉格朗日函数

$L\left(v,\lambda \right)=\frac{1}{2}{\Vert v-v_n\Vert }^2+\lambda \langle s_n,v\rangle$

由凸优化的Karush-Kuhn-Tucker (KKT)条件，最优解$v^{*}$ 与乘子${\lambda }^{*}$ 需满足，

$\{\begin{array}{l}{v}^{\text{*}}-v_n+{\lambda }^{\text{*}}{s}_n=0\hfill \\ \langle s_n,v^{\text{*}}\rangle \le 0,{\lambda }^{\text{*}}\ge 0\hfill \\ {\lambda }^{\text{*}}\langle s_n,v^{\text{*}}\rangle =0\hfill \end{array}$

由平稳性条件得$v^{\text{*}}=v_n-{\lambda }^{\text{*}}{s}_n$ 。根据互补松弛条件，分两种情况讨论，

(i) 若$v_n\in H_n^{\tan }$ ，取${\lambda }^{*}=0$ ，此时$v^{*}=v_n$ ，满足所有条件。

(ii) 若$v_n\notin H_n^{\tan }$ ，则投影点必位于边界超平面上，即$\langle s_n,v^{*}\rangle =0$ 。代入$v^{*}$ 得

$\langle s_n,v_n-{\lambda }^{*}{s}_n\rangle =0$ ,

解得${\lambda }^{*}=\max \left\{0,\frac{s_n,v_n}{{\Vert s_n\Vert }^2}\right\}$ ，代回平稳性方程，命题得证。

值得一提的是，在算法1中，以及本节的引理和下文中我们都记该拉格朗日乘子为${\rho }_n$ 。

在确立了算法迭代步骤的显式表达及其计算可行性后，下文将重点讨论算法的收敛性质。我们将证明算法1生成的迭代序列满足引理6所述的收敛准则，从而建立算法的全局收敛性。

定理1 假设条件(H1)~(H4)成立。由算法生成的序列$\left\{x_n\right\}$ 满足引理6的所有条件，即$\left\{x_n\right\}$ 收敛至变分不等式(1.1)的解集RVI (C, F)中的点。

证明 令$\left(y,v,\omega \right)=\left(x_n,-{\beta }_{n}F\left(x_n\right),p\right)$ 结合引理10得

$d^2\left({\exp }_{x_n}\left(-{\beta }_{n}F\left(x_n\right),p\right)\right)\le d^2\left(x_n,p\right)+{\beta }_n^2{\Vert F\left(x_n\right)\Vert }^2+2{\beta }_n\langle F\left(x_n\right),{\log }_{x_n}p\rangle$

即

$d^2\left(u_n,p\right)\le d^2\left(x_n,p\right)+{\beta }_n^2{\Vert F\left(x_n\right)\Vert }^2+2{\beta }_n\langle F\left(x_n\right)\text{,}{\log }_{x_n}p\rangle$

由度量收缩不等式

$d^2\left(u,p\right)\ge d^2\left(u,y\right)+d^2\left(y,p\right)$

有

$d^2\left(y_n,p\right)\le d^2\left(x_n,p\right)+{\beta }_n^2{\Vert F\left(x_n\right)\Vert }^2+2{\beta }_n\langle F\left(x_n\right)\text{,}{\log }_{x_n}p\rangle$ (1.10)

记，则

(1.11)

又

由引理9，结合Armijo步长规则，有

再由三角不等式易得

$2\mu d\left(x_n,y_n\right)d\left(x_n,p\right)\le 2\mu d^2\left(x_n,y_n\right)+2\mu d\left(x_n,y_n\right)d\left(y_n,p\right)$ (1.12)

结合(1.10) (1.11) (1.12)，得

$d^2\left(y_n,p\right)\le d^2\left(x_n,p\right)+C_{\mu }{d}^2\left(x_n,y_n\right)+2{\beta }_n^2{\Vert F\left(y_n\right)\Vert }^2$

其中常数$C_{\mu }:=4+4\mu$ ，$\mu \in \left(\text{0,1}\right)$ ，即满足Fejér单调。

由引理4和引理10，$d^2\left(x_{n+1},p\right)\le d^2\left(y_n,p\right)+{\Vert v_{n+1}\Vert }^2$ ，能量不等式${\Vert E_{n+1}\Vert }^2\le {\Vert E_n\Vert }^2-{\rho }_n^2$ ，其中角项${\rho }_n=\frac{{\langle s_n,v_n\rangle }_{+}}{\Vert s_n\Vert }$ ，作Lyapunov能量泛函，令

${\Phi }_n:=d^2\left(x_n,p\right)+k{\Vert v_n\Vert }^2$ ,

则有

$\begin{array}{c}{\text{Φ}}_{n+1}=d^2\left(x_{n+1},p\right)+k{\Vert v_{n+1}\Vert }^2\\ \le d^2\left(y_n,p\right)+{\Vert v_{n+1}\Vert }^2+k{\Vert v_{n+1}\Vert }^2\\ \le d^2\left(x_n,p\right)+C_{\mu }{d}^2\left(x_n,y_n\right)+2{\beta }_n^2{\Vert F\left(y_n\right)\Vert }^2+\left(1+k\right){\Vert v_{n+1}\Vert }^2\\ ={\text{Φ}}_n+C_{\mu }{d}^2\left(x_n,y_n\right)+3{\beta }_n^2{\Vert F\left(y_n\right)\Vert }^2-\left(1+k\right){\rho }_n^2,\end{array}$

又因Fejér单调确保序列$\left\{x_n\right\}$ 和中间点序列$\left\{y_n\right\}$ 落在以$p$ 为中心的某个有界球内，可知$\Vert {\log }_{y_n}\omega \Vert$ 在该球上一致有界，结合Armijo步长序$\left\{{\beta }_n\right\}$ ，易知

从而

${\Phi }_{n+1}\le {\Phi }_n+C_{\mu }{d}^2\left(x_n,y_n\right)-\left(1+k\right){\rho }_n^2+C_k$

再由引理4，做望远求和得

$\begin{array}{c}{\displaystyle \sum _{n=0}^{\infty }{\rho }_n^2}\le {\displaystyle \sum _{n=0}^{\infty }\left({\Vert v_n\Vert }^2-{\Vert v_{n+1}\Vert }^2\right)}\\ ={\Vert v_0\Vert }^2-\underset{N\to \infty }{\lim }{\Vert v_N\Vert }^2\\ <\infty .\end{array}$

易得${\rho }_n\to 0$ 。

由Jacobi场的一阶误差，在含序列$\left\{x_n\right\}$ 、$\left\{y_n\right\}$ 的有界球内，存在常数$C>0$ ，使得

,

结合切空间的最优性表达，$\forall \omega \in C$ ，$\frac{1}{{\beta }_n}\langle {\log }_{y_n}{u}_n,{\log }_{y_n}\omega \rangle \le 0$ ，从而

$\begin{array}{l}0\le -\langle F\left(y_n\right),{\text{log}}_{y_n}\omega \rangle =\langle -F\left(y_n\right)-\frac{1}{{\beta }_n}{\text{log}}_{y_n}{u}_n,{\text{log}}_{y_n}\omega \rangle +\langle \frac{1}{{\beta }_n}{\text{log}}_{y_n}{u}_n,{\text{log}}_{y_n}\omega \rangle \\ \le \langle -F\left(y_n\right)-\frac{1}{{\beta }_n}{\text{log}}_{y_n}{u}_n,{\text{log}}_{y_n}\omega \rangle \\ \le \Vert F\left(y_n\right)+\frac{1}{{\beta }_n}{\text{log}}_{y_n}{u}_n\Vert \cdot \Vert {\text{log}}_{y_n}\omega \Vert \\ \le \left(C+L\right)d\left(x_n,y_n\right)\Vert {\text{log}}_{y_n}\omega \Vert \end{array}$

下证$d_n\left(x_n,y_n\right)\to 0$ ，反证，若$d_n\left(x_n,y_n\right)\cancel{\to }0$ ，则定存在${\epsilon }_k>0$ ，使得子列$\left\{n_k\right\}$ ，有

$d\left(x_{n_k},y_{n_k}\right)\ge {\epsilon }_k,\forall k$

取${\epsilon }_k>\frac{c_2}{c_1}$ ，使得$-\langle F\left(y_{n_k}\right)\text{,}{\log }_{y_{n_k}}p\rangle \ge {\epsilon }_k>0$ ，则

$0\le -\langle F\left(y_{n_k}\right)\text{,}{\log }_{y_{n_k}}p\rangle \le \left(C+L\right)d\left(x_{n_k},y_{n_k}\right)\Vert {\log }_{y_{n_k}}p\Vert$ ,

又因为$s_n={\log }_{y_n}{u}_n={\log }_{y_n}p+\left({\log }_{y_n}{u}_n-{\log }_{y_n}p\right)$ ，且

${\rho }_n=\frac{{\left(\langle s_n,v_n\rangle \right)}_{+}}{\Vert s_n\Vert }=\frac{{\left(-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n\rangle \right)}_{+}}{\Vert {\log }_{y_n}{u}_n\Vert }$ ,

所以

$-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n\rangle =-{\beta }_n\langle F\left(y_n\right),{\log }_{y_n}p\rangle -{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n-{\log }_{y_n}p\rangle$

易得

${\left(-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n\rangle \right)}_{+}\ge {\left(-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}p\rangle \right)}_{+}-{\beta }_n\left|\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n-{\log }_{y_n}p\rangle \right|$

而

${\left(-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}p\rangle \right)}_{+}={\beta }_n\left(-\langle F\left(y_n\right)\text{,}{\log }_{y_n}p\rangle \right)$

那么

${\left(-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n\rangle \right)}_{+}\ge {\beta }_n\left(-\langle F\left(y_n\right)\text{,}{\log }_{y_n}p\rangle \right)-{\beta }_n\left|\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n-{\log }_{y_n}p\rangle \right|$

此时令$M:=\underset{B\left(q\right)}{\sup }\Vert F\Vert <\infty$ ，，则有

$\left|\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n-{\log }_{y_n}p\rangle \right|\le M\left(\Vert {\log }_{y_n}{u}_n\Vert +\Vert {\log }_{y_n}p\Vert \right)\le M\left(\Vert s_n\Vert +R\right)$

从而

${\left(-{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{u}_n\rangle \right)}_{+}\}\Vert s_n\Vert \ge \frac{{\beta }_{\max }}{\Vert s_n\Vert }\left(-\langle F\left(y_n\right)\text{,}{\log }_{y_n}p\rangle \right)-{\beta }_{\max }M\left(1+\frac{R}{\Vert s_n\Vert }\right)$

吸收常数，可记作

${\rho }_n\ge c_1\left(-\langle F\left(y_n\right)\text{,}{\log }_{y_n}p\rangle \right)-c_2$

此时

${\rho }_n\ge c_1{\epsilon }_k-c_2>c_1\cdot \frac{c_2}{c_1}-c_2=0$

与${\rho }_n\to 0$ 矛盾，故

$d\left(x_n,y_n\right)\to 0$

那么由引理6知，任何聚点都是(1.1)的解。

事实上，取$\left\{x_{n_j}\right\}$ 是迭代序列的任意收敛子列，若$x_{n_j}\to x^{*}\in C$ ，则$y_{n_j}\to x^{*}$ ，易有

$\langle \frac{1}{{\beta }_n}{\log }_{y_n}{u}_n,{\log }_{y_n}\omega \rangle =-\langle F\left(y_n\right)\text{,}{\log }_{y_n}\omega \rangle +o\left(\text{1}\right)$ ，

则$\forall \omega \in C$ ，

$\langle -F\left(y_{n_j}\right)\text{,}{\log }_{y_{n_j}}\omega \rangle \le 0$ ，

令$n_j\to 0$ ，有

$\langle F\left(x^{*}\right)\text{,}{\log }_{x^{*}}\omega \rangle \ge 0$

综上得证。

这个定理给出了我们的算法(R-SSEG)生成的迭代序列满足引理6的收敛准则，从而得到了全局收敛性，下面这个定理将会给出强结构下的收敛速率。

定理2 设$\left(M,g\right)$ 是Hadamard流形，$C\subset M$ 为闭测地凸集，解集$Sol\ne \varnothing$ ，令$F:M\to TM$ 在有界球上满足L-Lipschitz条件，算法R-SSEG产生的序列$\left\{x_n\right\}$ 以及中间点$\left\{y_n\right\}$ 由Armijo规则生成，且步长有界，若$F$ 在上满足强伪单调性，即

$\langle F\left(y\right)\text{,}{\log }_y{x}^{*}\rangle \le -\zeta d^2\left(y,x^{*}\right)$ ,

则序列$\left\{x_n\right\}$ 以Q-线性速率收敛至$x^{*}\in Sol$ ，即存在$\rho \in \left(\text{0,1}\right)$ 和$N>0$ ，使得对所有$n\ge N$ 有

$d^2\left(x_{n+1},x^{*}\right)\le \rho d^2\left(x_n,x^{*}\right)$ .

证明 由Hadamard流形的非正截面曲率性质和测地三角形的几何关系，即引理2，对任意三点$x,y,z\in M$ ，有

$d^2\left(x,z\right)+d^2\left(y,z\right)-2\langle {\log }_{z}x,{\log }_{z}y\rangle \le d^2\left(x,y\right)$ ,

结合算法更新步骤，利用$y_n$ 作为度量投影点的性质，即$\langle {\log }_{y_n}{x}_n+{\beta }_{n}F\left(x_n\right),{\log }_{y_n}p\rangle \le 0$ ，我们有如下流形上的基本下降关系

,

此时，又由Armijo型线搜索条件易有

将该估计代入上述距离不等式中有

$\begin{array}{c}{d}^2\left(x_{n+1},p\right)\le d^2\left(x_n,p\right)-d^2\left(y_n,x_n\right)+{\mu }^2{d}^2\left(x_n,y_n\right)\\ =d^2\left(x_n,p\right)-\left(1-{\mu }^2\right)d^2\left(y_n,x_n\right)\end{array}$

从而得到如下黎曼距离不等式

$d^2\left(x_{n+1},p\right)\le d^2\left(x_n,p\right)-\left(1-{\mu }^2\right)d^2\left(y_n,x_n\right)$

结合引理9有

$d^2\left(x_{n+1},x^{*}\right)\le d^2\left(x_n,x^{*}\right)-\left(1-{\mu }^2\right)d^2\left(x_n,y_n\right)+2{\beta }_n\langle F\left(y_n\right)\text{,}{\log }_{y_n}{x}^{*}\rangle$ ,

由$F$ 的强伪单调性有

$d^2\left(x_{n+1},x^{*}\right)\le d^2\left(x_n,x^{*}\right)-\left(1-{\mu }^2\right)d^2\left(x_n,y_n\right)-2{\beta }_n\zeta d^2\left(y_n,x^{*}\right)$ ,

再根据Armijo步长下界得

$d^2\left(x_{n+1},x^{*}\right)\le d^2\left(x_n,x^{*}\right)-\left(1-{\mu }^2\right)d^2\left(x_n,y_n\right)-2{\beta }_{\min }\zeta d^2\left(y_n,x^{*}\right)$ (1.13)

设测地三角形$\Delta \left(x_n,y_n,x^{*}\right)\subseteq M$ ，由Young不等式结合三角不等式有

$d^2\left(x_n,x^{*}\right)\le \left(1+\epsilon \right)d^2\left(y_n,x^{*}\right)+\left(1+\frac{1}{\epsilon }\right)d^2\left(x_n,y_n\right)$ ,

简化系数后就有

$-d^2\left(y_n,x^{*}\right)\le -\frac{1}{1+\epsilon }{d}^2\left(x_n,x^{*}\right)+\frac{1}{\epsilon }{d}^2\left(x_n,y_n\right)$ (1.14)

(1.14)代入(1.13)有

$d^2\left(x_{n+1},x^{*}\right)\le d^2\left(x_n,x^{*}\right)-\left(1-{\mu }^2\right)d^2\left(x_n,y_n\right)+2{\beta }_{\min }\zeta \left[-\frac{1}{1+\epsilon }{d}^2\left(x_n,x^{*}\right)+\frac{1}{\epsilon }{d}^2\left(x_n,y_n\right)\right]$ ,

即

$d^2\left(x_{n+1},x^{*}\right)\le \left(1-\frac{2{\beta }_{\min }\zeta }{1+\epsilon }\right)d^2\left(x_n,x^{*}\right)+\left[-\left(1-{\mu }^2\right)+\frac{2{\beta }_{\min }\zeta }{\epsilon }\right]d^2\left(x_n,y_n\right)$ ,

记$C_1=1-\frac{2{\beta }_{\min }\zeta }{1+\epsilon }$ ，，只要令$\frac{2{\beta }_{\min }\zeta }{\epsilon }=1-{\mu }^2$ ，就有

$d^2\left(x_{n+1},x^{*}\right)\le \left(1-\frac{2{\beta }_{\min }\zeta }{1+\epsilon }\right)d^2\left(x_n,x^{*}\right)$ ,

再令$\rho =1-\frac{2{\beta }_{\min }\zeta }{1+\epsilon }<1$ ，即

$d^2\left(x_{n+1},x^{*}\right)\le \rho d^2\left(x_n,x^{*}\right)$

综上得证。

4. 数值算例

在本节中，我们在Hadamard流形背景下通过大规模数值实验验证了本文提出的Armijo型切半空间投影外梯度算法(R-SSEG)的有效性。为了全面评估算法性能，我们R-SSEG分别与经典的Tseng外梯度算法[18]以及同类最新的自适应步长算法[10]进行了多维度的对比测试。所有实验代码均由Python3.11编写，并在配备Inter Core i5 CPU@2.50GHz的计算机上运行。

4.1. 实验环境与流形几何结构

为了验证算法在大规模问题下的表现，我们同最新文献中的设定一致，选取$n$ 维正定向量空间$M={ℝ}_{++}^n=\left\{x\in {ℝ}^n|x_i>0,i=1,\cdots ,n\right\}$ 作为底流形。为了使其构成Hadamard流形，我们赋予其如下黎曼度量，对任意点$x\in M$ 及切向量$u,v\in T_{x}M\cong {ℝ}^n$ ，

定义内积为：

${\langle u,v\rangle }_x={\displaystyle \sum _{i=1}^n\frac{u_i{v}_i}{x_i^2}}$ .

在此度量下，流形$M$ 具有非正截面曲率。两点$x,y\in M$ 之间的黎曼距离定义为

$d\left(x,y\right)=\sqrt{{\displaystyle \sum _{i=1}^n{\left(\ln \left(x_i\right)-\ln \left(y_i\right)\right)}^2}}={\Vert \ln \left(x\right)-\ln \left(y\right)\Vert }_2$

其中$\ln (\cdot )$ 表示逐分量取自然对数，${\Vert \cdot \Vert }_2$ 为欧式范数。

相应的指数映射${\exp }_x:T_{x}M\to M$ 及其逆映射${\log }_x:M\to T_{x}M$ 具有显示表达，分别由下式逐分量计算：

${\left({\exp }_{x}v\right)}_i=x_i{\text{e}}^{\frac{v_i}{x_i}},{\left({\log }_{x}y\right)}_i=x_i\ln \left(\frac{y_i}{x_i}\right),i=1,\cdots ,n.$

4.2. 伪单调变分不等式问题设置

为了在统一且具有代表性的测试环境下评估算法性能，本文选取了Tan等人[10]中提出的高维伪单调变分不等式问题(Example 4.2)作为基准算例。

我们考虑流形上的变分不等式问题RVI (C, F)，其中约束集$C$ 设为流形上的闭凸盒约束：

$C=\left\{x\in {ℝ}^n|1\le x_i\le 5,i=1,\cdots ,n\right\}$

函数$F:M\to TM$ 定义为：

$F\left(x_i\right)=x_i\ln \left(x_i\right)$

该函数在定义域内满足强伪单调性，问题的理论唯一解为

$x^{*}={\left(\text{1,1,}\cdots ,1\right)}^{\text{T}}$ .

为了测试算法在大规模计算中的表现，我们将问题维度统一设定成$n=5000$ 。所对比算法的各自参数设置如下：

(1) 通用设置：所有算法均采用相同的停止准则，即当黎曼距离残差$d\left(x_n,y_n\right)<{10}^{-6}$ 时停止迭代。初始点$x_0$ 在${\left[2,5\right]}^n$ 区间内随机生成。

(2) R-SSEG与Tseng算法：采用相同的Armijo线搜索参数以确保公平对比：缩放因子$\gamma =0.5$ ，衰减率$l=0.5$ ，参数$\mu =0.4$ 。

(3) Adaptive-SEG算法：采用其原文建议的自适应参数设置：初始步长${\theta }_0=0.5$ ，参数，$\beta =0.9$ ，序列参数设为${\omega }_n=1+\frac{0.1}{{\left(n+1\right)}^2}$ ，${\mu }_n=\frac{0.1}{{\left(n+1\right)}^2}$ 。

4.3. 实验结果与分析

4.3.1. 与经典Tseng算法的对比

图1展示了R-SSEG算法与经典的Tseng算法在$n=5000$ 维问题上的收敛行为对比。从图1(左)可以看出，两种算法的残差均呈线性下降趋势，这与本文定理中证明的Q-线性收敛速率一致。值得注意的是，R-SSEG算法在达到10⁻⁶精度所需的迭代次数显著少于Tseng算法。这一优势同样体现在计算时间上(图1右)，尽管R-SSEG引入了半空间构造，但由于其避免了第二次昂贵的流形度量投影，总CPU耗时仍优于Tseng算法。这初步验证了利用切半空间投影策略替代第二次流形投影，能够有效降低单步计算成本并加速收敛。

Figure 1. Comparison of convergence performance between R-SSEG and Tseng algorithms ($n=5000$ )

图1. R-SSEG算法与Tseng算法的收敛性能对比($n=5000$ )

4.3.2. 与最新Adaptive-SEG算法的对比

为了进一步验证算法在高精度求解下的竞争力，我们将R-SSEG与Tan等人[10]最近发表的自适应步长算法(Adaptive-SEG)进行了对比，结果如图2所示。

Figure 2. Comparison of convergence performance between R-SSEG and Adaptive-SEG algorithms ($n=5000$ )

图2. R-SSEG算法与Adaptive-SEG的收敛性能对比($n=5000$ )

收敛速率分析(图2左)：尽管Adaptive-SEG算法通过自适应策略避免了线搜索，但在处理高维复杂流形问题时，其步长更新在后期趋于保守，导致收敛曲线出现了明显的拖尾现象，迭代次数超过100次仍未达到10⁻³精度。相比之下，R-SSEG算法凭借Armijo准则保障的能量单调下降性质以及基于KKT条件的显式修正步，获得了更高质量的下降方向，呈现出陡峭且稳定的线性收敛特征，仅需约64次迭代即可达到10⁻⁶精度。

综合效率分析(图2右)：在计算时间方面，虽然自适应算法因无内循环在迭代初期略快，但R-SSEG算法在追求高精度解时迅速反超。实验结果表明，R-SSEG算法在达到最终停止准则时的总耗时显著短于Adaptive-SEG算法。

4.3.3. 参数敏感性与计算开销分析

为了全面评估R-SSEG算法的鲁棒性，我们基于高维算例(Example 4.2)对Armijo线搜索中的关键参数$\left(\gamma ,l,\mu \right)$ 进行了敏感性分析。图3展示了在不同参数设置下算法的收敛残差曲线。

可以看出，初始步长缩放因子$\gamma$ 主要影响算法的初期下降速度。较大的$\gamma$ (如1.5)能提供更大的初始探测步长，从而加速早期收敛，而较小的$\gamma$ (如0.2)虽然收敛稍缓，但并未破坏算法的收敛性。图3(b)显示，算法在较宽的步长衰减率$l\in \left[\text{0}.\text{3},\text{0}.\text{9}\right]$ 范围内均能保持稳定的线性收敛特征。图3(c)则表明算法对Armijo参数$\mu$ 具有较强的钝感性，说明R-SSEG不依赖于苛刻的参数微调。

此外，我们还统计了算法R-SSEG在上述实验中的平均回溯次数(Average Number of Backtracking steps, ANB)。ANB定义为总回溯次数除以总迭代步数，即$\frac{1}{k}{\displaystyle \sum _{n=0}^k{m}_n}$ ，其中$m_n$ 是第$n$ 次迭代满足Armijo条件所需的内循环次数。统计结果如表1所示。

Table 1. Statistics of Average Number of Backtracking steps (ANB) under different parameter settings ($n=5000$ )

表1. 不同参数设置下的平均回溯次数(ANB)统计($n=5000$ )

$\gamma$ 变化($l=0.5,\mu =0.4$ )		$\gamma$ 变化($\gamma =0.5,\mu =0.4$ )		$\gamma$ 变化($\gamma =0.5,l=0.4$ )
参数值	ANB	参数值	ANB	参数值	ANB
0.2	0.3478	0.3	1.1900	0.1	4.4800
0.5	1.4756	0.5	1.4756	0.4	1.4756
1.0	2.4756	0.7	2.0588	0.7	0.4237
1.5	2.8056	0.9	5.9538	0.9	0.2807

数据表明，在绝大多数参数组合下，ANB数值均维持在极低水平(通常小于1)，这意味着算法生成的试探步长具有极高的接受率，极少触发多次昂贵的函数值评估。这从数值计算角度证明了R-SSEG算法的高效性。

Figure 3. Sensitivity analysis of R-SSEG algorithm under different parameter settings ($n=5000$ )

图3. R-SSEG算法在不同参数设置下的灵敏度分析($n=5000$ )

4.4. 总结

综合上述两组实验结果，R-SSEG算法不仅在效率上显著优于经典Tseng算法，而且在收敛精度和后期收敛速度上优于最新的自适应算法。这表明，Armijo线搜索方法在本文研究的变分不等式问题上仍具有重要研究价值，且更值得关注的是，Armijo规则结合KKT显示投影的组合策略在处理大规模、高精度流形变分不等式问题时，具有独特的优势和实用价值。此外，参数敏感性实验证实了算法对初始步长及衰减率等设置具有较强鲁棒性，不依赖于苛刻的参数调优。特别是极低的平均回溯次数(ANB < 1)表明，本文采用的Armijo准则能够在保证收敛的前提下，极大地减少函数估值的计算开销，进一步从数值层面解释了算法高效性的来源。

5. 结论

本文构建了一种基于Armijo线搜索的切半空间投影外梯度算法(R-SSEG)。该算法创新性地利用流形切空间的线性结构与KKT条件，推导出了修正步的显式闭式解，在大幅降低单步计算复杂度的同时，通过Armijo准则严格保证了迭代序列的能量耗散性质与强伪单调条件下的Q-线性收敛速率。大规模数值实验证实，R-SSEG在追求高精度解时，相比于经典算法及前沿自适应步长算法展现出显著的效率优势。这一成果不仅确立了显式几何投影结合稳健线搜索策略在处理高维复杂流形问题中的优越性，也为未来结合惯性加速技术或推广至Stiefel等一般黎曼流形的研究提供了坚实的算法框架与理论基础。

NOTES

^*通讯作者。