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.