用于变分不等式的双重自适应次梯度外梯度方法

《Communications in Nonlinear Science and Numerical Simulation》：Double self-adaptive subgradient extragradient methods for variational inequalities

　　摘要
本文介绍了两种具有双重自适应规则的迭代算法，用于解决实希尔伯特空间中的变分不等式问题。在亚梯度外梯度方法的基础上，我们提出了两种不同的自适应规则来替代标准的单一自适应规则。这种策略调整了两次投影计算中涉及的步长，从而便于参数选择。在适当的条件下，我们通过结合粘性迭代和Mann型迭代，证明了这两种提出算法的强收敛性。最后，我们将我们的算法与有限维和无限维希尔伯特空间中的现有方法进行了比较，包括一个应用于信号处理的例子，证明了它们的有效性和改进的实际性能。

引言
变分不等式是优化理论中非线性问题的一个重要研究课题。它与偏微分方程、博弈论和动力系统等数学问题紧密相关，并在各个领域找到了广泛的应用。例如，Be?dziński等人[1]研究了接触力学中的半变分-变分不等式，Chen和Wang[2]将微分变分不等式应用于动态博弈，Donato等人[3]和Nagurney[4]分别探讨了经济均衡和网络经济学，Fargetta和Scrimali[5]考虑了紧急管理中的医疗供应问题，Yang和Tang[6]通过偏微分变分不等式研究了随机微分博弈。本文主要研究希尔伯特空间中的变分不等式问题，即寻找满足???3??*,?????*?≥0,???∈??的p*∈C，其中C是实希尔伯特空间?中的一个非空闭凸子集，??:?→?是一个非线性算子。为了简便起见，我们将问题(1.1)称为VIP，其解集称为Ω。

多年来，已经有多种方法用于解决VIP问题，其中投影方法（PM）[7]引起了众多研究者的关注。该方法迭代过程如下：????+1=?????(???????????????)，其中PC表示从?到C的度量投影，算子??是L-Lipschitz连续的且η-强单调的，步长??∈(0,2????2)。需要注意的是，PM要求算子是强单调的（且Lipschitz连续的）才能保证收敛性。然而，VIP问题通常涉及更一般的仅单调算子。对于这样的算子，PM通常不能保证收敛。为了解决单调变分不等式问题，Korpelevi?[8]在1976年提出了以下算法：{????=?????(???????????????), ????+1=?????(???????????????)，其中PC表示从?到C的度量投影，算子??是L-Lipschitz连续且单调的，步长??∈(0,1??)。这种算法被称为外梯度方法（EGM），也称为双投影方法。通过两步投影迭代，避免了强单调性假设的前提。自Korpelevi?[8]提出以来，EGM得到了广泛的开发和扩展。后续工作提出了各种改进：Anh等人[9]和Thong等人[10]引入了惯性技术来加速收敛，Mijajlovi?和Ja?imovi?[11]将该方法扩展到拟变分不等式，Millán等人[12]结合了非精确投影，Tan等人[13]将方法推广到Hadamard流形，Thang和Le[14]为拟均衡问题开发了自适应变体，Hu等人[15]结合了Bregman投影和Korpelevi?及Tseng的外梯度技术。

然而，EGM在每次迭代中都需要对闭凸子集C进行两次投影计算，这可能会根据C的结构影响算法的收敛速度。因此，Censor等人[16]考虑用半空间{Tn}上的投影来替代EGM中的第二次投影。具体步骤如下：?{ {?{ {?????=?????(???????????????), ????:={??∈?:?????????????????????,????????≤0}, ????+1=???????(???????????????)。上述方法称为亚梯度外梯度方法（SEGM），其中涉及的参数和算子与EGM中的保持一致。数值实验表明，与EGM相比，SEGM加快了收敛过程。在Censor等人[16]的开创性工作之后，SEGM被广泛采用并进一步改进。值得注意的发展包括：针对拟单调问题的全自适应策略[17]、用于更快收敛的双惯性技术[18]、松弛惯性变体[19]、黄金比率技术[20],[21]、针对双层拟单调问题的修改[22]以及新的投影框架[23]。

另一方面，当前的SEGM仍有一些局限性。注意，SEGM中涉及的算子是L-Lipschitz连续算子，这需要在数值实验中预先知道Lipschitz常数L。为了避免这种计算，可以使用自适应规则来选择步长。此外，为了获得迭代算法生成的序列的强收敛结果，通常需要执行一些相应的迭代，例如Halpern型迭代、粘性迭代和Mann型迭代（参见[24],[25],[26],[27],[28]及其引用文献）。例如，Thong等人[24]提出了以下算法：?{ { { { { {?????=????+?????(??????????1), ????=?????(?????????????????), ????:={??∈?:???????????????????????,????????≤0}, ????=???????(?????????????????), ????+1=????????(????)+(1?????)?????），其中????+1=?{ {?{ {?min?{??∥?????????∥∥???????????????∥,????}, 如果???????????????≠0, 否则????。在施加适当的参数条件下，Thong等人[24]证明了由上述算法生成的序列{tn}在涉及拟单调和Lipschitz连续算子的情况下强收敛到Ω的某个元素。通过上述自适应规则，步长{τn}的选择与Lipschitz常数无关。

受到上述结果的启发，我们旨在通过更灵活的步长选择策略进一步提高迭代算法的计算效率和收敛性能。在以前的方法中，包括标准的EGM和SEGM，每次迭代都涉及两次投影，通常共享一个共同的步长。为了克服这一限制，我们提出了一种双重自适应规则，使用两个独立的非递增序列分别确定步长{τn}和{λn}。我们框架的一个显著特点是，当两种规则的初始值和系数相同时，它自然回归到单步长情况。这允许在我们的数值实验中公平比较双重和单一自适应策略，从而展示了所提出修改的实际优势。此外，我们将双重自适应规则结合到粘性和Mann型迭代中，得到了两个新的算法，这些算法属于亚梯度外梯度框架。在温和的假设下，为这两种算法建立了强收敛性。最后，我们在有限维和无限维希尔伯特空间中测试了所提出的算法，并将其性能与现有方法进行了比较。数值结果证实，新算法在实践中表现出改进的收敛行为。

部分片段
初步介绍
在本节中，我们回顾了一些基本概念和事实。设?是一个实希尔伯特空间，对于任何??,??∈?和??∈?，众所周知∥??+??∥2≤∥??∥2+2???,??+???以及∥????+(1???)??∥2=??∥??∥2+(1???)∥??∥2???(1???)∥?????∥2。如果对于所有??,??∈?，都有∥?????????∥≤??∥?????∥，则映射??:?→?被称为L-Lipschitz连续的，其中L>0。如果存在ρ∈[0, 1)使得对于所有??,??∈?，都有∥?????????∥≤??∥?????∥，则映射??:?→?被称为收缩映射。如果对于所有??,??∈?，都有??????????,??????≥0，则映射??:?→?被称为单调映射。如果对于所有??,??∈?，都有?????,??????≥0??????,??????≥0，则映射??:?→?被称为拟单调映射。

主要结果
在本节中，我们提出了两种新的自适应亚梯度外梯度方法，用于解决希尔伯特空间中的变分不等式问题。首先，我们给出以下条件：
(C1) 可行集C是实希尔伯特空间?中的一个非空闭凸子集，解集Ω是非空的。
(C2) 算子??:?→?是拟单调的且L-Lipschitz连续的。
(C3) 对于任何序列{????}??且tn→q，算子??:?→?满足：∥????∥≤lim inf??→∞∥??????∥。
(C4) 设??:?→?是一个收缩映射。

数值实验
在本节中，我们展示了几个计算实验，并将我们在第3节中提出的方法与文献中的一些现有方法进行了比较。所有代码都是用MATLAB R2023b编写的，并在配备Intel(R) Core(TM) i5-12500 CPU @ 3.00 GHz、RAM 8.00 GB的PC上运行。在所有这些例子中，我们将算法3.1（New 1）和3.2（New 2）与[24]中的算法3.2（Com 1）以及[9]中的算法3.4（Com 2）进行了比较。值得注意的是，当????=????，即??=??时……

结论
本文在Censor等人[16]提出的经典亚梯度外梯度方法的基础上，结合了粘性和Mann型迭代，创建了两种用于解决实希尔伯特空间中变分不等式问题的双重自适应迭代算法。摆脱了单一自适应规则的传统设置，我们通过两个独立的自适应规则提供了更灵活的步长选择策略，从而在数值行为上获得了更好的效果。

利益冲突
作者声明没有利益冲突。

CRedI
作者贡献声明
谢忠兵：撰写——审阅与编辑，撰写——原始草案，方法论。
李明：撰写——审阅与编辑，软件，资金获取，数据管理。

利益冲突声明
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。

谢忠兵 | 李明
重庆工业大学数学科学学院，重庆，400054，中国