求解约束极小极大问题的隐式梯度加速方法

Accelerated Implicit Gradient-Based Methods for Solving Constrained Minimax Problems

摘要: 求解约束极小极大问题的隐式梯度(GBAL)算法基本思路是，采用增广拉格朗日方法处理内层优化问题，再利用隐式梯度信息对外部变量进行迭代更新。在此基础上，本文提出了一种求解约束极小极大问题的隐式梯度加速算法，通过引入Nesterov加速梯度算法的一个变体算法更新外部变量来提升算法性能。理论分析表明，在内层问题解映射满足Lipschitz连续性且目标函数对外层变量为凸的条件下，所提出的加速算法实现了R-线性收敛速率，通过数值实验验证，加速算法在计算效率和收敛性方面均展现出优越性能。

Abstract: The fundamental approach of the Implicit Gradient-Based (GBAL) algorithm for solving constrained minimax problems involves using the augmented Lagrangian method to address the inner optimization problem, followed by iterative updates of the external variables utilizing implicit gradient information. Building upon this, this paper introduces an accelerated implicit gradient algorithm for solving constrained minimax problems, which enhances the algorithm’s performance by incorporating a variant of the Nesterov accelerated gradient algorithm to update the external variables. Theoretical analysis demonstrates that under the conditions where the solution mapping of the inner problem satisfies Lipschitz continuity and the objective function is convex with respect to the outer variables, the proposed accelerated algorithm achieves an R-linear convergence rate. Numerical experiments confirm that the accelerated algorithm exhibits superior performance in terms of computational efficiency and convergence.

1. 引言

极小极大问题(minmax problem)起源于博弈论中的基础数学问题，是最优化领域中一类典型的优化问题。随着计算机技术的飞速发展，约束最优化方法作为一种有效的最优化方法，在工业工程设计，优化管理等多方面的应用，越来越受到研究者的重视[1]，以下是带约束的极小极大问题的常见形式：

$\underset{x\in X}{\text{min}}\underset{y\in Y}{\text{max}}f\left(x,y\right),$ (1)

其中$X=\left\{x\in {ℝ}^n:g_i\left(x\right)\le 0,i\in {ℐ}_1,h_j\left(x\right)=0,j\in {ℰ}_1\right\}$ ，$Y=\{y\in {ℝ}^m:g_i\left(x,y\right)\le 0,i\in {ℐ}_2,h_j\left(x,y\right)=0,j\in {ℰ}_2\}$ 。

尽管(1)和无约束的极小极大问题似乎密切相关，但前者实际上更具挑战性。例如，若$f\left(x,y\right)$ 关于$x$ 是凸的，关于$y$ 是凹的时，无约束的极小极大问题很容易解决，但问题(1)通常是NP-困难的，即使对于$f\left(x,y\right)$ 是强凸强凹情况也是一样。此外，经典的极小极大不等式[2]不适用于这类问题。综上，为求解无约束的极小极大问题开发的现有算法不能直接应用于求解(1)。但另一方面，与无约束的极小极大问题相比，(1)可用于对更广泛的应用进行建模，所以研究其解法也有着极其重要的意义。

在本文关注以下带约束的极小极大问题：

(P) $\underset{x\in X}{\text{min}}\underset{y\in Y\left(x\right)}{\text{max}}f\left(x,y\right)$ ，

其中$Y\left(x\right)=\left\{y\in {ℝ}^m:h\left(x,y\right)=0,g\left(x,y\right)\le 0\right\}$ ，函数$f:{ℝ}^{n\times m}\mapsto ℝ$ ，$h:{ℝ}^{n\times m}\mapsto {ℝ}^{m_1}$ ，$g:{ℝ}^{n\times m}\mapsto {ℝ}^{m_2}$ 是连续可微的，$X\subseteq {ℝ}^n$ 是一个闭凸集。

2. 预备知识

基于梯度方法是利用梯度信息来指导搜索方向，该方法已经在求解无约束双层优化问题中显示出成效[3]。求解约束极小极大问题的隐式梯度(GBAL)算法扩展了基于梯度方法用于处理约束极小极大问题。首先定义内层问题$\left({\text{P}}_x\right)$ ：

$\left({\text{P}}_x\right)\underset{y\in {ℝ}^m}{\text{max}}f\left(x,y\right)\text{s}\text{.t}\text{.}h\left(x,y\right)=0,g\left(x,y\right)\le 0.$

假设函数$f,h$ 和$g$ 在某个$\left(x^{\text{*}},y^{\text{*}}\right)$ 的邻域内是连续可微的，并且对变量$y$ 是二次连续可微的。用$S\left(x\right)$ 表示问题$\left({\text{P}}_x\right)$ 的可行集。问题$\left({\text{P}}_x\right)$ 的拉格朗日函数定义如下：

$L\left(x,y,\lambda ,\mu \right):=f\left(x,y\right)+{\lambda }^{\text{T}}h\left(x,y\right)-{\mu }^{\text{T}}g\left(x,y\right),$

其中$h={\left(h_1,\cdots ,h_{m_1}\right)}^{\text{T}},g={\left(g_1,\cdots ,g_{m_2}\right)}^{\text{T}}$ ，且$\left(\lambda ,\mu \right)\in {ℝ}^{m_1}\times {ℝ}^{m_2}$ 是拉格朗日乘子。

定义集合

$\begin{array}{l}\alpha :=\left\{j:g_j\left(x,y\left(x\right)\right)=0,{\mu }_j\left(x\right)>0\right\},\\ \beta :=\left\{j:g_j\left(x,y\left(x\right)\right)=0,{\mu }_j\left(x\right)=0\right\},\\ \gamma :=\left\{j:g_j\left(x,y\left(x\right)\right)<0,{\mu }_j\left(x\right)=0\right\}.\end{array}$

记$z\left(x\right):=\left(y\left(x\right),\lambda \left(x\right),{\mu }_{\alpha }\left(x\right)\right)$ 和

$M\left(x\right):=\left[\begin{array}{cc}R\left(x\right)& Q\left(x\right)\\ 0& S\left(x\right)\end{array}\right],N\left(x\right):=\left[\begin{array}{c}K\left(x\right)\\ 0\end{array}\right],$

其中$S\left(x\right):=-I_{\left|\gamma \right|}$ 且

$\begin{array}{l}R\left(x\right):=\left[\begin{array}{ccc}{\nabla }_{yy}^{2}L\left(x,y\left(x\right),\lambda \left(x\right),\mu \left(x\right)\right)& {\nabla }_{y}h{\left(x,y\left(x\right)\right)}^{\text{T}}& {\nabla }_y{g}_{\alpha }{\left(x,y\left(x\right)\right)}^{\text{T}}\\ {\nabla }_{y}h\left(x,y\left(x\right)\right)& 0& 0\\ {\nabla }_y{g}_{\alpha }\left(x,y\left(x\right)\right)& 0& 0\end{array}\right],\\ Q\left(x\right):=\left[\begin{array}{c}{\nabla }_y{g}_{\gamma }{\left(x,y\left(x\right)\right)}^{\text{T}}\\ 0\\ 0\end{array}\right],K\left(x\right):=\left[\begin{array}{c}{\nabla }_{yx}^{2}L\left(x,y\left(x\right),\lambda \left(x\right),\mu \left(x\right)\right)\\ {\nabla }_{x}h\left(x,y\left(x\right)\right)\\ {\nabla }_x{g}_{\alpha }\left(x,y\left(x\right)\right)\end{array}\right].\end{array}$

假设2.1. a) 假设$h,\nabla h$ 和${\nabla }^{2}h$ 是Lipschitz连续的，并且各自的常数为$L_{h_0}>0,L_{h_1}>0$ 和$L_{h_2}>0$ 。

b) 假设$g,\nabla g$ 和${\nabla }^{2}g$ 是Lipschitz连续的，并且各自的常数为$L_{g_0}>0,L_{g_1}>0$ 和$L_{g_2}>0$ 。

假设2.2. a) 假设$f,{\nabla }_{x}f,{\nabla }_{y}f,{\nabla }_{yx}^{2}f$ 和${\nabla }_{yy}^{2}f$ 在$y$ 上是Lipschitz连续的，各自的常数为 $L_{f_{0,2}}>0,L_{f_{1,2}}>0,L_{f_{2,2}}>0,L_{f_{21,2}}>0$ 和$L_{f_{22,2}}>0$ 。

b) 假设${\nabla }_{x}f,{\nabla }_{y}f,{\nabla }_{yx}^{2}f$ 和${\nabla }_{yy}^{2}f$ 在$x$ 上是Lipschitz连续的，各自的常数为$L_{f_{1,1}}>0,L_{f_{2,1}}>0,L_{f_{21,1}}>0$ 和$L_{f_{22,1}}>0$ 。

假设2.3. 假设内层问题的雅可比唯一性条件成立。

在假设2.3成立的条件下，拉格朗日乘子是有界的，有如下假设成立。

假设2.4. 假设存在常数$ℳ$ ，使得对于任何满足KKT条件的$\left(\lambda ,\mu \right)$ ，以下成立：

$\Vert \lambda ,\mu \Vert \le ℳ.$

在假设2.3成立的条件下，使用标准的隐函数定理，可以得到如下结论，说明内层问题解的存在性与局部与唯一性：

引理2.1. 设$\left(x^{\text{*}},y^{\text{*}}\right)\in X\times {ℝ}^m$ 是一个点，在此点附近函数$f,h$ 和$g$ 都是二次连续可微的。设存在 $\left({\lambda }^{\text{*}},{\mu }^{\text{*}}\right)\in {ℝ}^{m_1}\times {ℝ}^{m_2}$ 使得问题$\left({\text{P}}_{x^{\text{*}}}\right)$ 的雅可比唯一性条件在$\left(y^{\text{*}},{\lambda }^{\text{*}},{\mu }^{\text{*}}\right)$ 处满足，则存在${\delta }_0>0$ 和${\epsilon }_0>0$ ，以及一个二次连续可微的映射$\left(y,\lambda ,\mu \right):{\mathbb{B}}_{{\delta }_0}\left(x^{\text{*}}\right)\mapsto {\mathbb{B}}_{{\epsilon }_0}\left(y^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_0}\left({\lambda }^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_0}\left({\mu }^{\text{*}}\right)$ ，使得当$x\in {\mathbb{B}}_{{\delta }_0}\left(x^{\text{*}}\right)$ 时，问题$\left({\text{P}}_x\right)$ 的雅可比唯一性条件在$\left(y\left(x\right),\lambda \left(x\right),\mu \left(x\right)\right)$ 处满足。

在假设内层问题具有唯一局部解的情况下，极小极大问题(P)可以简化为以下单层问题：

$\underset{x\in X}{\text{min}}\varphi \left(x\right):=f\left(x,y\left(x\right)\right):y\left(x\right)=\text{arg}\underset{y\in Y\left(x\right)}{\text{max}}f\left(x,y\right)$ .

为了解决这个问题，GBAL算法的基本思路如下：首先在每次迭代中使用增广拉格朗日法得到$y\left(x\right)$ 的值。然后，基于通过链式法则计算的$\varphi$ 的梯度更新变量$x$ ，具体如下：

$\nabla \varphi \left(x\right)={\nabla }_{x}f\left(x,y\left(x\right)\right)+\nabla y{\left(x\right)}^{\text{T}}{\nabla }_{y}f\left(x,y\left(x\right)\right),$

其中$\nabla y\left(x\right)$ 在雅可比唯一性条件成立的前提下，可以使用隐函数定理获得。然而除非内层问题有闭式解，否则$\nabla y\left(x\right)$ 不能被直接使用，这就限制了这仅适用于非常特定的问题。为了突破这一限制，GBAL算法提出通过隐函数定理来估计$\nabla y\left(x\right)$ 的值，这需要用到以下引理。

引理2.2. 假设引理2.1中的条件成立。则对于任意$x\in {\mathbb{B}}_{{\delta }_0}\left(x^{\text{*}}\right)$ 和在引理2.1中定义的 $\left(y\left(x\right),\lambda \left(x\right),\mu \left(x\right)\right)$ ，以下结论成立。

a) 梯度函数$\nabla z\left(x\right)$ 可以表示为：

$\nabla z\left(x\right)=-R{\left(x\right)}^{-1}K\left(x\right).$ (2)

b) 存在常数$0<{\delta }_1<{\delta }_0$ 和$0<{\epsilon }_1<{\epsilon }_0$ ，使得对于$\left(x,y,\lambda ,\mu \right)\in {\mathbb{B}}_{{\delta }_1}\left(x^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left(y^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left({\lambda }^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left({\mu }^{\text{*}}\right)$ ，矩阵$R\left(x,y,\lambda ,\mu \right)$ 是非奇异的，其中$R\left(x,y,\lambda ,\mu \right)$ 是通过将$R\left(x\right)$ 中的$y\left(x\right),\lambda \left(x\right)$ 和$\mu \left(x\right)$ 替换为$y,\lambda$ 和$\mu$ 来定义的。此外，存在$\eta >0$ ，使得

$\Vert R{\left(x,y,\lambda ,\mu \right)}^{-1}\Vert \le \eta$ .

给出目标函数$f$ 的近似梯度如下：

$\overline{\nabla }f\left(\overline{x},\overline{y}\right):={\nabla }_{x}f\left(\overline{x},\overline{y}\right)+U_{\overline{\lambda },\overline{\mu }}\left(\overline{x},\overline{y}\right){\nabla }_{y}f\left(\overline{x},\overline{y}\right),$ (3)

其中$U_{\overline{\lambda },\overline{\mu }}\left(\overline{x},\overline{y}\right):={\left\{\left[\begin{array}{lll}E\hfill & 0\hfill & 0\hfill \end{array}\right]\nabla z\left(\overline{x},\overline{y},\overline{\lambda },\overline{\mu }\right)\right\}}^{\text{T}}$，$\nabla z\left(\overline{x},\overline{y},\overline{\lambda },\overline{\mu }\right)$ 是将(2)中的$\overline{y},\overline{\lambda }$和$\overline{\mu }$ 替换为$y\left(\overline{x}\right),\lambda \left(\overline{x}\right)$和$\mu \left(\overline{x}\right)$ 来定义的。

下面是近似梯度与原始梯度之间的一些连续属性和误差界限。

引理2.3. 在假设2.1，2.2，2.3和2.4成立的情况下，以下陈述成立：

a) 假设存在$\left(\overline{x},\overline{y},\overline{\lambda },\overline{\mu }\right)\in {\mathbb{B}}_{{\delta }_1}\left(x^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left(y^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left({\lambda }^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left({\mu }^{\text{*}}\right)$，且$\left(y\left(x\right),\lambda \left(x\right),\mu \left(x\right)\right)$ 如引理2.1所给出，则：

$\Vert \overline{\nabla }f\left(\overline{x},\overline{y}\right)-\nabla f\left(\overline{x},y\left(\overline{x}\right)\right)\Vert \le L_1\Vert \overline{y}-y\left(\overline{x}\right)\Vert +L_2\Vert \overline{\lambda }-\lambda \left(\overline{x}\right)\Vert +L_3\Vert \overline{\mu }-\mu \left(\overline{x}\right)\Vert ,$ (4)

其中$L_1:=L_{f_{1,2}}+\eta C_K{L}_{f_{2,2}}+L_{U_y}{L}_{f_{0,2}}$ ，$L_2:=\eta L_{h_1}{L}_{f_{0,2}}+{\eta }^2{C}_K{L}_{h_1}{L}_{f_{0,2}}$ ，$L_3:=\eta L_{g_1}{L}_{f_{0,2}}+{\eta }^2{C}_K{L}_{g_1}{L}_{f_{0,2}}$ 且 $C_K:=L_{f_{2,1}}+ℳL_{h_1}+ℳL_{g_1}+L_{h_0}+L_{g_0}$ ，$L_{U_y}:=\eta L_{K_y}+{\eta }^2{C}_K{L}_{R_y}$ ，$L_{K_y}:=L_{f_{21,2}}+ℳL_{h_2}+ℳL_{g_2}+L_{h_1}+L_{g_1}$ ， $L_{R_y}:=L_{f_{22,2}}+ℳL_{h_2}+ℳL_{g_2}+2L_{h_1}+2L_{g_1}$ 。

b) 对于$\overline{x}\in {\mathbb{B}}_{{\delta }_1}\left(x^{\text{*}}\right)$，$y\left(\overline{x}\right),\lambda \left(\overline{x}\right)$和$\mu \left(\overline{x}\right)$ 在$x$ 上是Lipschitz连续的，常数为$L_y=\eta C_K$ 。

c) 对于$\overline{x}\in {\mathbb{B}}_{{\delta }_1}\left(x^{\text{*}}\right)$，$\nabla f$ 在$x$ 上是Lipschitz连续的，常数为$L_f$ ，即对于任意给定的${\overline{x}}_1,{\overline{x}}_2\in {\mathbb{B}}_{{\delta }_1}\left(x^{\text{*}}\right)$，有：

$\Vert \nabla f\left({\overline{x}}_1,y\left({\overline{x}}_1\right)\right)-\nabla f\left({\overline{x}}_2,y\left({\overline{x}}_2\right)\right)\Vert \le L_f\Vert {\overline{x}}_1-{\overline{x}}_2\Vert ,$ (5)

其中$L_f:=\left(L_1+L_2+L_3\right)L_y+L_{f_{1,1}}+\eta C_K{L}_{f_{2,1}}+L_{U_x}{L}_{f_{0,2}}$ ，$L_{U_x}:=\eta L_{K_x}+{\eta }^2{C}_K{L}_{R_x}$ $L_{R_x}:=L_{f_{22,1}}+ℳL_{h_2}+ℳL_{g_2}+2L_{h_1}+2L_{g_1}$ ，$L_{K_x}:=L_{f_{21,1}}+ℳL_{h_2}+ℳL_{g_2}+L_{h_1}+L_{g_1}$ 。

以下是具体的GBAL算法：

算法1. 求解约束极小极大问题的隐式梯度(GBAL)算法

输入：$x_0\in X$ ，$y_0\in {ℝ}^m$ ，$\zeta >0$ 和非负序列${\left\{{\alpha }_k\right\}}_{k\ge 0}$ 。

1：初始化$k=0$ ，${\overline{y}}_0=y_0$ 。

for $k=0,1,2,\cdots$ do

2：利用算法2求解内层问题$\left({\text{P}}_{x_k}\right)$ ，得到${\overline{y}}_k,{\overline{\lambda }}_k$和${\overline{\mu }}_k$ ；

3：如果$\overline{\nabla }f\left(x_k,{\overline{y}}_k\right)<\zeta$ 则停止，其中$\overline{\nabla }f$ 的定义在(3)中给出；

4：更新

$x_{k+1}=\arg \underset{u\in X}{\text{min}}\left\{\langle \overline{\nabla }f\left(x_k,{\overline{y}}_k\right),u\rangle +\frac{1}{2{\alpha }_k}{\Vert u-x_k\Vert }^2\right\};$ (6)

end for

其中使用的非精确增广拉格朗日算法[4]如下：

算法2. 非精确增广拉格朗日算法

输入：$y_0\in {ℝ}^m,w_0\in {ℝ}^m$ 和固定常数$x_k$ ，乘子${\lambda }_0\in {ℝ}^{m_1},{\mu }_0\in {ℝ}_{+}^{m_2}$ ，非负序列${\left\{c_t\right\}}_{t\ge 0}$ ，参数$\sigma \in \left[0,1\right)$ 和整数$t_k$ 。

for $t=1,2,\cdots ,t_k$ do

1：定义

$v_t={\nabla }_y{L}_{c_t}\left(x_k,y_{t-1},{\lambda }_{t-1},{\mu }_{t-1}\right)$ ；

2：找到$y_t\in {ℝ}^m$ 使得

$\frac{2}{c_t}\left|\langle w_{t-1}-y_t,v_t\rangle \right|+{\Vert v_t\Vert }^2\le \sigma \left({\Vert h\left(x_k,y_t\right)\Vert }^2+{\Vert \text{min}\left\{\frac{1}{c_t}{\mu }_{t-1},-g\left(x_k,y_t\right)\right\}\Vert }^2\right)$ ；

3：更新

$\begin{array}{l}{\lambda }_t={\lambda }_{t-1}+c_{t}h\left(x_k,y_t\right),\\ {\mu }_t=\text{max}\left\{0,{\mu }_{t-1}+c_{t}g\left(x_k,y_t\right)\right\},\\ w_t=w_{t-1}-c_t{v}_t.\end{array}$

end for

其中$c>0$ ，$L_c$ 是问题$\left({\text{P}}_x\right)$ 的增广拉格朗日函数：

$\begin{array}{c}{L}_c\left(x,y,\lambda ,\mu \right):=f\left(x,y\right)+{\displaystyle \sum }_{i=1}^{m_1}\left({\lambda }_i{h}_i\left(x,y\right)+\frac{c}{2}{h}_i{\left(x,y\right)}^2\right)\\ +\frac{1}{2c}{\displaystyle \sum }_{i=1}^{m_2}\left[{\left(\text{max}\left\{0,{\mu }_i+c{g}_i\left(x,y\right)\right\}\right)}^2-{\mu }_i^2\right].\end{array}$

以下是关于算法2收敛速率的结论。

引理2.4. [5]令$S\left(x\right)$ 是问题$\left({\text{P}}_x\right)$ 的解集，$M\left(x\right)$ 是问题$\left({\text{P}}_x\right)$ 的对偶问题的解集。假设$S\left(x\right)$ 和$M\left(x\right)$ 都是非空的，则以下结论成立。

a) 整个序列$p_t:=\left({\lambda }_t,{\mu }_t\right)$ 收敛到问题$\left({\text{P}}_x\right)$ 对偶问题的解。

b) 对于$y\left(x_k\right)\in S\left(x_k\right)$ 和任意充分大的$t$ ，有：

$\Vert y_t-y\left(x_k\right)\Vert \le \frac{\kappa \left(1+\sqrt{\sigma }\right)}{c_t}\Vert p_{t-1}-p_t\Vert ,$ (7)

因此

$\underset{t\to \infty }{\lim }\Vert y_t-y\left(x_k\right)\Vert =0$ .

其中$\kappa$ 是引用[5]中的一个误差界比例系数。

c) 如果额外满足

$\underset{t\to \infty }{\lim \inf }{c}_t>2\kappa \left(\sigma +\sqrt{\sigma }\right),$

那么对于$p\left(x_k\right)\in M\left(x_k\right)$ 和任意充分大的$t$ ，有：

$\Vert p_t-p\left(x_k\right)\Vert \le {\rho }_t\Vert p_{t-1}-p\left(x_k\right)\Vert ,$ (8)

其中

${\rho }_t:=\frac{\kappa \sqrt{1+\sigma }}{\sqrt{c_t^2-2\kappa \left(\sigma +\sqrt{\sigma }\right)c_t+{\kappa }^2\left(1+\sigma \right)}},$

并且

$\underset{t\to \infty }{\lim \sup }\left\{{\rho }_t\right\}<1$ .

3. 求解约束极小极大问题的隐式梯度加速算法

3.1节介绍了Nesterov加速梯度算法变体。3.2节将提到的Nesterov加速梯度算法变体应用到GBAL算法中，提出了求解约束极小极大问题的隐式梯度加速(aGBAL)算法，并对其进行了收敛性分析。最后的3.3节进行了数值实验的测试，验证了所提出的加速算法的加速性能。

3.1. Nesterov加速梯度算法变体

Nesterov加速梯度算法(Nesterov Accelerated Gradient, NAG)由Nesterov于1983年提出[1] [6]，旨在解决传统梯度下降法在优化光滑凸函数时收敛速度不足的问题。为了更好地处理复杂目标函数，下面引入一个NAG变体[1] [7]，这个算法通过引入动量权重和正则化项来增强稳定性，以更好地适应不同的优化问题。

定义动量权重如下，其中为了对目标函数的强凸性进行动态调节，引入了广义参数${\lambda }_k\ge 0$ ：

${\eta }_k=\frac{{\theta }_k\left({\mu }_f+{\lambda }_k\right)-{\theta }_k^2{\mu }_f}{{\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f},$

则中间点

$x_k^{md}={\eta }_k{x}_k+\left(1-{\eta }_k\right)x_k^{ag}$

当${\lambda }_k=0$ 时，就退化为经典Nesterov形式，此时${\eta }_k={\theta }_k/\left(1+{\theta }_k\right)$ ，与NAG中${\gamma }_k=1/\left(k+2\right)$ 的参数设计相同。

迭代点的更新通过求解以下优化问题实现：

$x_{k+1}=\arg \underset{u\in X}{\min }\langle \nabla f\left(x_k^{md}\right),u\rangle +\frac{{\mu }_f}{4}{\Vert u-x_k^{md}\Vert }^2+\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4{\theta }_k}{\Vert u-x_k\Vert }^2,$

其目标函数可视为梯度项与复合二次正则项的组合。当${\lambda }_k=0$ 且${\theta }_k$ 满足递推关系：

${\theta }_{k+1}^2=\left(1-{\theta }_{k+1}\right){\theta }_k^2,$

该问题等价于Nesterov的校正步骤，其解析解可显式写为：

$x_{k+1}=x_k^{md}-\frac{2{\theta }_k}{{\mu }_f}\nabla f\left(x_k^{md}\right).$

3.2. 隐式梯度加速算法

结合上一节所提到的Nesterov加速梯度算法的变体，提出了下方求解约束极小极大问题的隐式梯度加速(aGBAL)算法。

算法3. 求解约束极小极大问题的隐式梯度加速(aGBAL)算法

输入：$x_0\in X,y_0\in {ℝ}^m,\zeta >0$ 以及非负序列${\left\{{\alpha }_k\right\}}_{k\ge 0},{\left\{{\lambda }_k\right\}}_{k\ge 0}$ 。

1：初始化$k=0,x_0^{ag}=x_0$ 和${\overline{y}}_0=y_0$ 。

for $k=0,1,2,\cdots$ do

2：定义

${\eta }_k=\frac{{\theta }_k\left({\mu }_f+{\lambda }_k\right)-{\theta }_k^2{\mu }_f}{{\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f}和x_k^{md}={\eta }_k{x}_k+\left(1-{\eta }_k\right)x_k^{ag}\text{.}$ (9)

3：利用算法2求解内层问题$\left({\text{P}}_{x_k^{md}}\right)$ ，得到${\overline{y}}_k, {\overline{\lambda }}_k$和${\overline{\mu }}_k$ ；

4：如果$\overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right)<\zeta$ ，则停止，其中$\overline{\nabla }f$ 的定义见(3)；

5：更新

$x_{k+1}=\text{arg}\underset{u\in X}{\text{min}}\left\{\langle \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right),u\rangle +\frac{{\mu }_f}{4}{\Vert u-x_k^{md}\Vert }^2+\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4{\theta }_k}{\Vert u-x_k\Vert }^2\right\},$

$x_{k+1}^{ag}=\arg \underset{u\in X}{\text{min}}\left\{\langle \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right),u\rangle +\frac{1}{2{\alpha }_k}{\Vert u-x_k^{md}\Vert }^2\right\}.$ $\left(10\right)$

end for

注意到，如果$\overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right)=\nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right)$ ，则(9)和(10)构成的就是上述Nesterov加速梯度变体。以下，分析此算法的主要收敛特性。

定理3.1. 假设序列${\left\{{\overline{y}}_k,x_k,x_k^{md},x_k^{ag}\right\}}_{k\ge 0}$ 是通过算法3生成的，并且满足假设2.1，2.2，2.3和2.4以及引理2.4的假设。取$k_0\ge 0$ ，使得对于任意$k\ge k_0$ ，都有$\left(x_k,{\overline{y}}_k,{\lambda }_k,{\mu }_k\right)\in {\mathbb{B}}_{{\delta }_1}\left(x^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left(y^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left({\lambda }^{\text{*}}\right)\times {\mathbb{B}}_{{\epsilon }_1}\left({\mu }^{\text{*}}\right)$，其中${\delta }_1$ 和${\epsilon }_1$ 在引理2.2中给出了定义。步长选择满足：

${\alpha }_k\le \frac{1}{L_f},\forall k\ge k_0$ (11)

且

${\theta }_k^2\le \frac{{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{4},\forall k\ge k_0$ (12)

a) 如果$f$ 是关于$x$ 是强凸函数，参数为${\mu }_f>0$ ，且满足

$\frac{{\lambda }_{k_0}}{{\text{Γ}}_{k_0+1}}=\frac{{\lambda }_{k_0+1}}{{\text{Γ}}_{k_0+2}}=\cdots ,$ (13)

选择${\gamma }_k={\theta }_k$ ，则对于任意$N\ge k_0+1$ ，有：

$f\left(x_N^{ag},y\left(x_N^{ag}\right)\right)-f^{\text{*}}\le {\text{Γ}}_N\left[f\left(x_{k_0},y\left(x_{k_0}\right)\right)-f^{\text{*}}+\frac{{\mu }_f+{\lambda }_{k_0}{\text{Γ}}_{k_0+1}^{-1}}{4}{\Vert x^{\text{*}}-x_{k_0}\Vert }^2+\frac{1}{2{\mu }_f}{\displaystyle \sum }_{k=k_0}^{N-1}\frac{\left(6{\theta }_k+{\alpha }_k{\mu }_f\right)T_k^2}{{\text{Γ}}_{k+1}}\right]$ (14)

其中

$T_k:=\frac{L_1\kappa \left(1+\sqrt{\sigma }\right)\left(1+{\rho }_k\right)}{c_k}{\displaystyle \prod }_{i=k_0+1}^{k-1}{\rho }_i\Vert p_{k_0}-p\left(x_k\right)\Vert +\left(L_2+L_3\right){\displaystyle \prod }_{i=k_0+1}^k{\rho }_i\Vert p_{k_0}-p\left(x_k\right)\Vert ,$

${\text{Γ}}_{k_0+1}:=\{\begin{array}{ll}1,\hfill & {\gamma }_{k_0}=1\hfill \\ 1-{\gamma }_{k_0},\hfill & {\gamma }_{k_0}<1\hfill \end{array},{\text{Γ}}_k:={\text{Γ}}_{k_0+1}{\displaystyle \prod }_{i=k_0+1}^{k-1}\left(1-{\gamma }_i\right),\forall k\ge k_0+2,$

$0<{\gamma }_k\le \frac{\sqrt{{\alpha }_k{\mu }_f}}{2},\forall k\ge k_0.$ (15)

其中$L_1,L_2,L_3$ 的定义见(4)，$\kappa ,{\rho }_k$ 和$c_k$ 的定义见(7)和(8)。

b) 如果$f$ 关于$x$ 是凸函数，$X$ 有界，且满足(13)，则对于任意$N\ge k_0+1$ ，有：

$\begin{array}{c}f\left(x_N^{ag},y\left(x_N^{ag}\right)\right)-f^{\text{*}}\le {\text{Γ}}_N[\frac{\left(1-{\gamma }_{k_0}\right)\left[f\left(x_{k_0},y\left(x_{k_0}\right)\right)-f^{\text{*}}\right]}{{\text{Γ}}_{k_0+1}}+\frac{{\lambda }_{k_0}}{{\text{Γ}}_{k_0+1}}{\Vert x^{\text{*}}-x_{k_0}\Vert }^2\\ +{\displaystyle {\sum }_{k=k_0}^{N-1}\frac{1}{{\text{Γ}}_{k+1}}}\left({\theta }_k{D}_x{T}_k+\frac{{\alpha }_k{T}_k^2}{2}\right),\end{array}$ (16)

其中在${\text{Γ}}_k$ 中取${\gamma }_k={\theta }_k$ 。

Proof. 首先证明a)。注意到子问题(10)的强凸性，对$\forall x\in X$ ，有：

$\begin{array}{c}\langle \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right),x_{k+1}-x\rangle \le \frac{{\mu }_f}{4}\left[{\Vert x-x_k^{md}\Vert }^2-{\Vert x-x_{k+1}\Vert }^2-{\Vert x_{k+1}-x_k^{md}\Vert }^2\right]\\ +\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4{\theta }_k}\left[{\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2-{\Vert x_{k+1}-x_k\Vert }^2\right],\end{array}$ (17)

并且对$\forall u\in X$ ，有：

$\langle \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right),x_{k+1}^{ag}-u\rangle \le \frac{1}{2{\alpha }_k}\left[{\Vert u-x_k^{md}\Vert }^2-{\Vert u-x_{k+1}^{ag}\Vert }^2-{\Vert x_{k+1}^{ag}-x_k^{md}\Vert }^2\right].$ (18)

令$u=\left(1-{\theta }_k\right)x_k^{ag}+{\theta }_k{x}_{k+1}$ ，借助${\Vert \cdot \Vert }^2$ 的凸性，得出：

$\begin{array}{c}{\Vert u-x_k^{md}\Vert }^2={\Vert \frac{{\eta }_k\left(1-{\theta }_k\right)}{1-{\eta }_k}\left(x_{k+1}-x_k\right)+\frac{{\theta }_k-{\eta }_k}{1-{\eta }_k}\left(x_{k+1}-x_k^{md}\right)\Vert }^2\\ \le \frac{{\eta }_k{\theta }_k\left(1-{\theta }_k\right)}{1-{\eta }_k}{\Vert x_{k+1}-x_k\Vert }^2+\frac{{\theta }_k\left({\theta }_k-{\eta }_k\right)}{1-{\eta }_k}{\Vert x_{k+1}-x_k^{md}\Vert }^2,\end{array}$

将(9)中${\eta }_k$ 的表达式代入上式，有：

${\Vert u-x_k^{md}\Vert }^2\le \frac{{\theta }_k^2\left[\left({\mu }_f+{\lambda }_k\right)-{\theta }_k{\mu }_f\right]\left(1-{\theta }_k\right)}{{\mu }_f+{\lambda }_k-{\theta }_k{\mu }_f-{\theta }_k{\lambda }_k}{\Vert x_{k+1}-x_k\Vert }^2$

$\begin{array}{c}+\frac{{\theta }_k\left({\theta }_k-\frac{{\theta }_k\left({\mu }_f+{\lambda }_k\right)-{\theta }_k^2{\mu }_f}{{\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f}\right)}{\frac{{\mu }_f+{\lambda }_k-{\theta }_k\left({\mu }_f+{\lambda }_k\right)}{{\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f}}{\Vert x_{k+1}-x_k^{md}\Vert }^2\\ =\frac{{\theta }_k^2\left({\mu }_f+{\lambda }_k-{\theta }_k{\mu }_f-{\theta }_k{\mu }_f-{\theta }_k{\lambda }_k+{\theta }_k^2{\mu }_f\right)}{{\mu }_f+{\lambda }_k-{\theta }_k{\mu }_f-{\theta }_k{\lambda }_k}{\Vert x_{k+1}-x_k\Vert }^2\\ +\frac{{\theta }_k^2-\frac{{\theta }_k^2({\mu }_f+{\lambda }_k-{\theta }_k^3{\mu }_f}{{\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f}}{\frac{{\mu }_f+{\lambda }_k-{\theta }_k\left({\mu }_f+{\lambda }_k\right)}{{\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f}}{\Vert x_{k+1}-x_k^{md}\Vert }^2\\ ={\theta }_k^2\left(1-\frac{{\theta }_k{\mu }_f-{\theta }_k^2{\mu }_f}{{\mu }_f+{\lambda }_k-{\theta }_k{\mu }_f-{\theta }_k{\lambda }_k}\right){\Vert x_{k+1}-x_k\Vert }^2\\ +\frac{\left({\mu }_f+{\lambda }_k-{\theta }_k^2{\mu }_f\right){\theta }_k^2-{\theta }_k^2\left({\mu }_f+{\lambda }_k\right)+{\theta }_k^3{\mu }_f}{{\mu }_f+{\lambda }_k-{\theta }_k\left({\mu }_f+{\lambda }_k\right)}{\Vert x_{k+1}-x_k^{md}\Vert }^2\\ ={\theta }_k^2\left(1-\frac{{\theta }_k{\mu }_f\left(1-{\theta }_k\right)}{\left(1-{\theta }_k\right){\mu }_f+\left(1-{\theta }_k\right){\lambda }_k}\right){\Vert x_{k+1}-x_k\Vert }^2\\ +\frac{{\theta }_k^2\left({\theta }_k{\mu }_f-{\theta }_k^2{\mu }_f\right)}{\left(1-{\theta }_k\right){\mu }_f+\left(1-{\theta }_k\right){\lambda }_k}{\Vert x_{k+1}-x_k^{md}\Vert }^2\\ ={\theta }_k^2\left(1-\frac{{\theta }_k{\mu }_f}{{\mu }_f+{\lambda }_k}\right){\Vert x_{k+1}-x_k\Vert }^2+\frac{{\theta }_k^2\left(1-{\theta }_k\right){\theta }_k{\mu }_f}{\left(1-{\theta }_k\right){\mu }_f+\left(1-{\theta }_k\right){\lambda }_k}{\Vert x_{k+1}-x_k^{md}\Vert }^2\\ ={\theta }_k^2\left[\left(1-\frac{{\theta }_k{\mu }_f}{{\mu }_f+{\lambda }_k}\right){\Vert x_{k+1}-x_k\Vert }^2+\frac{{\theta }_k{\mu }_f}{{\mu }_f+{\lambda }_k}{\Vert x_{k+1}-x_k^{md}\Vert }^2\right]\end{array}$ (19)

此外，由引理2.3 c)的光滑性，得到：

$f\left(x_{k+1}^{ag},y\left(x_{k+1}^{ag}\right)\right)\le f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x_{k+1}^{ag}-x_k^{md}\rangle +\frac{L_f}{2}{\Vert x_{k+1}^{ag}-x_k^{md}\Vert }^2.$ (20)

将(17)乘以${\theta }_k$ ，并将其与(18)相加，有：

$\begin{array}{l}\langle \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right),{\theta }_k\left(x_{k+1}-x\right)+x_{k+1}^{ag}-u\rangle \\ \le \frac{{\theta }_k{\mu }_f}{4}\left[{\Vert x-x_k^{md}\Vert }^2-{\Vert x-x_{k+1}\Vert }^2-{\Vert x_{k+1}-x_k^{md}\Vert }^2\right]\\ +\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}\left[{\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2-{\Vert x_{k+1}-x_k\Vert }^2\right]\\ +\frac{1}{2{\alpha }_k}\left[{\Vert u-x_k^{md}\Vert }^2-{\Vert u-x_{k+1}^{ag}\Vert }^2-{\Vert x_{k+1}^{ag}-x_k^{md}\Vert }^2\right].\end{array}$

将(19)代入上式，注意到对于项$\Vert x_{k+1}-x_k^{md}\Vert$ 与$\Vert x_{k+1}-x_k\Vert$ ，可以合并同类项，即：

$\left[\frac{1}{2{\alpha }_k}\left(\frac{{\theta }_k^3{\mu }_f}{{\mu }_f+{\lambda }_k}\right)-\frac{{\theta }_k{\mu }_f}{4}\right]{\Vert x_{k+1}-x_k^{md}\Vert }^2$

$\begin{array}{l}=\frac{2{\theta }_k^3{\mu }_f-{\alpha }_k{\theta }_k{\mu }_f\left({\mu }_f+{\lambda }_k\right)}{4{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{\Vert x_{k+1}-x_k^{md}\Vert }^2\\ =\frac{{\theta }_k{\mu }_f\left[2{\theta }_k^2-{\alpha }_k\left({\mu }_f+{\lambda }_k\right)\right]}{4{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{\Vert x_{k+1}-x_k^{md}\Vert }^2,\end{array}$

$\begin{array}{l}\left[\frac{{\theta }_k^2}{2{\alpha }_k}\left(1-\frac{{\theta }_k{\mu }_f}{{\mu }_f+{\lambda }_k}\right)-\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}\right]{\Vert x_{k+1}-x_k\Vert }^2\\ =\left[\frac{{\theta }_k^2\left({\mu }_f+{\lambda }_k-{\theta }_k{\mu }_f\right)}{2{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}-\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}\right]{\Vert x_{k+1}-x_k\Vert }^2\\ =\frac{2{\theta }_k^2\left({\mu }_f+{\lambda }_k-{\theta }_k{\mu }_f\right)-\left[\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k\right]{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{4{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{\Vert x_{k+1}-x_k\Vert }^2\\ =\frac{2{\theta }_k^2{\mu }_f\left(1-{\theta }_k\right)-{\alpha }_k\left(1-{\theta }_k\right){\mu }_f\left({\mu }_f+{\lambda }_k\right)+2{\theta }_k^2{\lambda }_k-{\alpha }_k{\lambda }_k\left({\mu }_f+{\lambda }_k\right)}{4{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{\Vert x_{k+1}-x_k\Vert }^2\\ =\frac{\left[2{\theta }_k^2-{\alpha }_k\left({\mu }_f+{\lambda }_k\right)\right]\left[\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k\right]}{4{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}{\Vert x_{k+1}-x_k\Vert }^2,\end{array}$

整理可以得到：

$\begin{array}{l}\langle \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right),{\theta }_k\left(x_{k+1}-x\right)+x_{k+1}^{ag}-u\rangle \\ \le -\frac{1}{4}\left(1-\frac{2{\theta }_k^2}{{\alpha }_k\left({\mu }_f+{\lambda }_k\right)}\right)\left\{{\theta }_k{\mu }_f{\Vert x_{k+1}-x_k^{md}\Vert }^2+\left[\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k\right]{\Vert x_{k+1}-x_k\Vert }^2\right\}\\ +\frac{{\theta }_k{\mu }_f}{4}\left({\Vert x-x_k^{md}\Vert }^2-{\Vert x-x_{k+1}\Vert }^2\right)+\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}\left({\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2\right)\\ -\frac{1}{2{\alpha }_k}\left({\Vert u-x_{k+1}^{ag}\Vert }^2+{\Vert x_{k+1}^{ag}-x_k^{md}\Vert }^2\right),\end{array}$

结合不等式(20)，并定义${\text{Δ}}_k^{md}:=\nabla f\left(x_k^{md},{\overline{y}}_k\right)-\nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right)$，可以获得：

$\begin{array}{l}f\left(x_{k+1}^{ag},y\left(x_{k+1}^{ag}\right)\right)\\ \le \left(1-{\theta }_k\right)\left[f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x_k^{ag}-x_k^{md}\rangle \right]\\ +{\theta }_k\left[f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x-x_k^{md}\rangle +\frac{{\mu }_f}{4}{\Vert x-x_k^{md}\Vert }^2\right]\\ -\frac{1}{2{\alpha }_k}\left\{\left(1-L_f{\alpha }_k\right){\Vert x_{k+1}^{ag}-x_k^{md}\Vert }^2+{\Vert u-x_{k+1}^{ag}\Vert }^2\right\}-\frac{{\theta }_k{\mu }_f}{4}{\Vert x-x_{k+1}\Vert }^2\\ +\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}\left[{\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2\right]+\langle {\text{Δ}}_k^{md},{\theta }_k\left(x_{k+1}-x\right)+x_{k+1}^{ag}-u\rangle .\end{array}$ (21)

可以将上式末尾的内积表达式分解为三部分：

$\langle {\text{Δ}}_k^{md},{\theta }_k\left(x_{k+1}-x_k^{md}\right)+{\theta }_k\left(x_k^{md}-x\right)+x_{k+1}^{ag}-u\rangle ,$

对每一部分内积$\langle {\text{Δ}}_k^{md},\cdot \rangle$ 应用Cauchy-Schwarz不等式$\langle a,b\rangle \le \frac{\alpha }{2}{\Vert a\Vert }^2+\frac{1}{2\alpha }{\Vert b\Vert }^2$ ，对于第一部分 ${\theta }_k\langle {\text{Δ}}_k^{md},x_{k+1}-x_k^{md}\rangle$ ，选择${\alpha }_1=\frac{4}{{\mu }_f}$ ，得到：

${\theta }_k\langle {\text{Δ}}_k^{md},x_{k+1}-x_k^{md}\rangle \le \frac{2{\theta }_k}{{\mu }_f}{\Vert {\text{Δ}}_k^{md}\Vert }^2+\frac{{\theta }_k{\mu }_f}{8}{\Vert x_{k+1}-x_k^{md}\Vert }^2.$

对于第二部分${\theta }_k\langle {\text{Δ}}_k^{md},x_k^{md}-x\rangle$ ，选择${\alpha }_2=\frac{2}{{\mu }_f}$ ，得到：

${\theta }_k\langle {\text{Δ}}_k^{md},x_k^{md}-x\rangle \le \frac{{\theta }_k}{{\mu }_f}{\Vert {\text{Δ}}_k^{md}\Vert }^2+\frac{{\theta }_k{\mu }_f}{4}{\Vert x-x_k^{md}\Vert }^2.$

对于第三部分$\langle {\text{Δ}}_k^{md},x_{k+1}^{ag}-u\rangle$ ，选择${\alpha }_k$ ，得到：

$\langle {\text{Δ}}_k^{md},x_{k+1}^{ag}-u\rangle \le \frac{{\alpha }_k}{2}{\Vert {\text{Δ}}_k^{md}\Vert }^2+\frac{1}{2{\alpha }_k}{\Vert u-x_{k+1}^{ag}\Vert }^2.$

将上述三个不等式相加，合并同类项，最终得到不等式：

$\begin{array}{l}\langle {\text{Δ}}_k^{md},{\theta }_k\left(x_{k+1}-x\right)+x_{k+1}^{ag}-u\rangle \\ \le \left(\frac{3{\theta }_k}{{\mu }_f}+\frac{{\alpha }_k}{2}\right){\Vert {\text{Δ}}_k^{md}\Vert }^2+\frac{{\theta }_k{\mu }_f}{4}[\frac{1}{2}{\Vert x_{k+1}-x_k^{md}\Vert }^2+{\Vert x-x_k^{md}\Vert }^2]+\frac{1}{2{\alpha }_k}{\Vert u-x_{k+1}^{ag}\Vert }^2.\end{array}$ (22)

由函数$f$ 关于$x$ 的强凸性，可以得到：

$\begin{array}{l}\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x_k^{ag}-x_k^{md}\rangle \le f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)-f\left(x_k^{md},y\left(x_k^{md}\right)\right)-\frac{{\mu }_f}{2}{\Vert x_k^{ag}-x_k^{md}\Vert }^2,\\ \langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x-x_k^{md}\rangle \le f\left(x,y\left(x\right)\right)-f\left(x_k^{md},y\left(x_k^{md}\right)\right)-\frac{{\mu }_f}{2}{\Vert x-x_k^{md}\Vert }^2,\end{array}$

将上式代入(21)并结合(22)，可以得出：

$\begin{array}{c}f\left(x_{k+1}^{ag},y\left(x_{k+1}^{ag}\right)\right)\le \left(1-{\theta }_k\right)f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)+{\theta }_{k}f\left(x,y\left(x\right)\right)+\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}{\Vert x-x_k\Vert }^2\\ -\frac{{\lambda }_k+{\mu }_f}{4}{\Vert x-x_{k+1}\Vert }^2+\frac{6{\theta }_k+{\mu }_f{\alpha }_k}{2{\mu }_f}{\Vert {\text{Δ}}_k^{md}\Vert }^2.\end{array}$

将$x=x^{\text{*}}$ 代入上述不等式，再将两边减去$f\left(x^{\text{*}},y\left(x^{\text{*}}\right)\right)$ ，可以得到：

$\begin{array}{l}f\left(x_{k+1}^{ag},y\left(x_{k+1}^{ag}\right)\right)-f\left(x^{\text{*}},y\left(x^{\text{*}}\right)\right)\\ \le \left(1-{\theta }_k\right)f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)+{\theta }_{k}f\left(x^{\text{*}},y\left(x^{\text{*}}\right)\right)+\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}{\Vert x-x_k\Vert }^2\\ -\frac{{\lambda }_k+{\mu }_f}{4}{\Vert x-x_{k+1}\Vert }^2+\frac{6{\theta }_k+{\mu }_f{\alpha }_k}{2{\mu }_f}{\text{Δ}}_k^{md}{}^2-f\left(x^{\text{*}},y\left(x^{\text{*}}\right)\right)\\ =\left(1-{\theta }_k\right)\left[f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)-f\left(x^{\text{*}},y\left(x^{\text{*}}\right)\right)\right]+\frac{\left(1-{\theta }_k\right){\mu }_f+{\lambda }_k}{4}{\Vert x-x_k\Vert }^2\\ -\frac{{\lambda }_k+{\mu }_f}{4}{\Vert x-x_{k+1}\Vert }^2+\frac{6{\theta }_k+{\mu }_f{\alpha }_k}{2{\mu }_f}{\Vert {\text{Δ}}_k^{md}\Vert }^2,\end{array}$

结合${\gamma }_k={\theta }_k$ ，并重新排列项后，可以得到：

$e_{k+1}\le \left(1-{\gamma }_k\right)e_k+\frac{{\lambda }_k}{4}\left[{\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2\right]+\frac{6{\theta }_k+{\mu }_f{\alpha }_k}{2{\mu }_f}{\Vert {\text{Δ}}_k^{md}\Vert }^2,$ (23)

其中$e_k:=f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)-f\left(x^{\text{*}},y\left(x^{\text{*}}\right)\right)+\frac{{\mu }_f}{4}{\Vert x-x_k\Vert }^2$ 。由引理2.4有：

$\Vert p_{k-1}-p_k\Vert \le \Vert p_{k-1}-p\left(x_k^{md}\right)\Vert +\Vert p_k-p\left(x_k^{md}\right)\Vert \le \left(1+{\rho }_k\right)\Vert p_{k-1}-p\left(x_k^{md}\right)\Vert ,$

因此

$\Vert y_k-y\left(x_k^{md}\right)\Vert \le \frac{\kappa \left(1+\sqrt{\sigma }\right)\left(1+{\rho }_k\right)}{c_k}\Vert p_{k-1}-p\left(x_k^{md}\right)\Vert ,$

联系(4)和(8)可以得到：

$\begin{array}{l}\Vert {\text{Δ}}_k^{md}\Vert =\Vert \overline{\nabla }f\left(x_k^{md},{\overline{y}}_k\right)-\nabla f\left(x_k^{md},y\left(x_k\right)\right)\Vert \\ \le \frac{L_1\kappa \left(1+\sqrt{\sigma }\right)\left(1+{\rho }_k\right)}{c_k}\Vert p_{k-1}-p\left(x_k^{md}\right)\Vert +\left(L_2+L_3\right)\Vert p_k-p\left(x_k^{md}\right)\Vert \\ \le \frac{L_1\kappa \left(1+\sqrt{\sigma }\right)\left(1+{\rho }_k\right)}{c_k}{\displaystyle \prod }_{i=k_0+1}^{k-1}{\rho }_i\Vert p_{k_0}-p\left(x_k^{md}\right)\Vert +\left(L_2+L_3\right){\displaystyle \prod }_{i=k_0+1}^k{\rho }_i\Vert p_{k_0}-p\left(x_k^{md}\right)\Vert \\ :=T_k.\end{array}$

对不等式(23)两边除以${\text{Γ}}_{k+1}$ ，并结合上式以及(13)，(7)和(4)，将它们求和后，得出(14)。

现在证明b)。如果$f$ 关于$x$ 是凸函数，将${\mu }_f=0$ 代入(21)再进行放缩，可以得到：

$\begin{array}{c}f\left(x_{k+1}^{ag},y\left(x_{k+1}^{ag}\right)\right)\le \left(1-{\theta }_k\right)\left[f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x_k^{ag}-x_k^{md}\rangle \right]\\ +{\theta }_k\left[f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x-x_k^{md}\rangle \right]-\frac{1}{2{\alpha }_k}{\Vert u-x_{k+1}^{ag}\Vert }^2\\ +\frac{{\lambda }_k}{4}\left[{\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2\right]+\langle {\text{Δ}}_k^{md},{\theta }_k\left(x_{k+1}-x\right)+x_{k+1}^{ag}-u\rangle \text{,}\end{array}$ (24)

对最后一个内积应用Cauchy-Schwarz不等式，有：

$\begin{array}{l}\langle {\text{Δ}}_k^{md},{\theta }_k\left(x_{k+1}-x\right)+x_{k+1}^{ag}-u\rangle \\ =\langle {\text{Δ}}_k^{md},{\theta }_k\left(x_{k+1}-x\right)\rangle +\langle {\text{Δ}}_k^{md},x_{k+1}^{ag}-u\rangle \\ \le {\theta }_k\Vert x-x_{k+1}\Vert \Vert {\text{Δ}}_k^{md}\Vert +\frac{{\alpha }_k}{2}{\Vert {\text{Δ}}_k^{md}\Vert }^2+\frac{1}{2{\alpha }_k}{\Vert x_{k+1}^{ag}-u\Vert }^2.\end{array}$ (25)

因为$f$ 是凸函数，根据凸函数的一阶条件，分别对变量$x_k^{ag}$ 和$x$ 有：

$\begin{array}{l}f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)\ge f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x_k^{ag}-x_k^{md}\rangle ,\\ f\left(x,y\left(x\right)\right)\ge f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),x-x_k^{md}\rangle .\end{array}$

将第一个不等式乘以$\left(1-{\theta }_k\right)$ ，第二个乘以${\theta }_k$ ，然后相加：

$\begin{array}{l}\left(1-{\theta }_k\right)f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)+{\theta }_{k}f\left(x,y\left(x\right)\right)\\ \ge \left(1-{\theta }_k+{\theta }_k\right)f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),\left(1-{\theta }_k\right)\left(x_k^{ag}-x_k^{md}\right)+{\theta }_k\left(x-x_k^{md}\right)\rangle \\ =f\left(x_k^{md},y\left(x_k^{md}\right)\right)+\langle \nabla f\left(x_k^{md},y\left(x_k^{md}\right)\right),\left(1-{\theta }_k\right)\left(x_k^{ag}-x_k^{md}\right)+{\theta }_k\left(x-x_k^{md}\right)\rangle .\end{array}$ (26)

将(25)和(26)代入(24)，可以得到：

$\begin{array}{c}f\left(x_{k+1}^{ag},y\left(x_{k+1}^{ag}\right)\right)\le \left(1-{\theta }_k\right)f\left(x_k^{ag},y\left(x_k^{ag}\right)\right)+{\theta }_{k}f\left(x,y\left(x\right)\right)\\ +\frac{{\lambda }_k}{4}\left[{\Vert x-x_k\Vert }^2-{\Vert x-x_{k+1}\Vert }^2\right]+{\theta }_k\Vert x-x_{k+1}\Vert \Vert {\text{Δ}}_k^{md}\Vert +\frac{{\alpha }_k}{2}{\Vert {\text{Δ}}_k^{md}\Vert }^2.\end{array}$

结合(13)以及$X$ 的有界性，与a)类似可以推导出(16)。 $\square$

接下来的结果中，通过选择适当算法参数来分析算法3的收敛速率。

推论3.1. 假设序列${\left\{{\overline{y}}_k,x_k,x_k^{md},x_k^{ag}\right\}}_{k\ge k_0}$ 由算法3生成，并且满足定理3.1的条件。对于每个$k$ 将$c_k$ 和${\rho }_k$ 固定为$\left\{c_k:=c_0\right\}$ 和$\left\{{\rho }_k:={\rho }_0\right\}$ 。步长选择满足如下条件：

${\alpha }_k=\frac{1}{3L_f},{\lambda }_k=\frac{4{\text{Γ}}_{k+1}}{{\alpha }_k},\forall k\ge k_0.$ (27)

a) 如果$f$ 关于$x$ 是强凸的且参数为${\mu }_f>0$ ，并且有：

${\theta }_k^2=\frac{{\alpha }_k{\mu }_f}{4}+{}_{\overline{\text{Γ}}},$ (28)

其中${}_{\overline{\text{Γ}}}={\text{Γ}}_k$，且选择${\gamma }_k={\theta }_k$ ，则对于任意的$N\ge k_0+1$ ，有：

$\begin{array}{l}f\left(x_N,y\left(x_N\right)\right)-f^{\text{*}}\\ \le {\left(1-\gamma \right)}^{N-k_0}\left[f\left(x_{k_0},y\left(x_{k_0}\right)\right)-f^{\text{*}}+\frac{{\mu }_f+12L_f}{4}{\Vert x^{\text{*}}-x_{k_0}\Vert }^2+\frac{7{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{2{\mu }_f{\rho }_0\left(1-{\rho }_0\right)}\right],\end{array}$ (29)

其中

${\gamma }_k=\gamma =\text{min}\left(\frac{1}{2}\sqrt{\frac{{\mu }_f}{3L_f}},1-{\rho }_0\right),\forall k\ge k_0.$ (30)

且$M=\underset{x\in X}{\text{max}}\Vert p_{k_0}-p\left(x_k\right)\Vert ,A=\frac{L_1\kappa \left(1+\sqrt{\sigma }\right)}{c_0},B=L_2+L_3$ 。

b) 如果$f$ 关于$x$ 是凸函数，$X$ 有界且${\gamma }_k={\theta }_k=\frac{1}{{\left(N-k\right)}^2}$ ，则对于任意$N\ge k_0+1$ ，有：

$\begin{array}{c}f\left(x_N,y\left(x_N\right)\right)-f^{\text{*}}\le {\left(1-\gamma \right)}^{N-k_0}[f\left(x_{k_0},y\left(x_{k_0}\right)\right)-f^{\text{*}}+\frac{{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{6L_f{\rho }_0\left(1-{\rho }_0\right)}\\ +12L_f{D}_X^2+\frac{\left(1-{\rho }_0\right){\pi }^2{D}_X}{6{\rho }_0}\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]],\end{array}$ (31)

Proof. 首先，证明步长的定义是良好的。结合(15)，(27)，(28)和(30)可知：

${\gamma }_k\le {\theta }_k,{}_{\overline{\text{Γ}}}\le {\text{Γ}}_{k+1},\frac{{\lambda }_k}{{\text{Γ}}_{k+1}}=\frac{4}{{\alpha }_k},\forall k\ge k_0$,

这确保了条件(12)和(13)的满足。因为${}_{\overline{\text{Γ}}}={\text{Γ}}_k$，且${\gamma }_k={\theta }_k$ ，所以：

${}_{\overline{\text{Γ}}}={\text{Γ}}_{k+1}=\left(1-{\gamma }_k\right){\text{Γ}}_k=\left(1-{\gamma }_k\right){}_{\overline{\text{Γ}}}=\left(1-{\theta }_k\right){}_{\overline{\text{Γ}}}$,

代入(28)，得到${\theta }_k^2=\frac{{\alpha }_k{\mu }_f}{4}+\left(1-{\theta }_k\right){}_{\overline{\text{Γ}}}$，这表明：

${\theta }_k=\frac{-{}_{\overline{\text{Γ}}}+\sqrt{{}_{\overline{\text{Γ}}}^k+4{}_{\overline{\text{Γ}}}+{\alpha }_k{\mu }_f}}{2},\forall k\ge k_0$,

并且有${\theta }_k\in \left(0,1\right)$ 。

定义$M=\underset{x\in X}{\text{max}}\Vert p_{k_0}-p\left(x_k\right)\Vert$ ，和$A=\frac{L_1\kappa \left(1+\sqrt{\sigma }\right)}{c_0}$ ，$B=L_2+L_3$ ，结合(15)和(30)有：

${\text{Γ}}_{k+1}={\left(1-\gamma \right)}^{k-k_0+1}\ge {\rho }_0^{k-k_0+1},T_k\le \left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]{\rho }_0^{k-k_0}.$ (32)

因此，可以从几何级数的求和公式和条件$0<{\rho }_0<1$ 中得到：

$\begin{array}{c}{\displaystyle \sum }_{k=k_0}^{N-1}\frac{{\alpha }_k{T}_k^2}{{\text{Γ}}_{k+1}}\le \frac{{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{3L_f}{\displaystyle \sum }_{k=k_0}^{N-1}\frac{{\rho }_0^{2k-2k_0}}{{\rho }_0^{k-k_0+1}}\\ =\frac{{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{3L_f}{\displaystyle \sum }_{k=k_0}^{N-1}{\rho }_0^{k-k_0-1}\\ =\frac{{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{3L_f}\left(\frac{1}{{\rho }_0}+\frac{1-{\rho }_0^{N-k_0-1}}{1-{\rho }_0}\right)\\ \le \frac{{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{3L_f}\left(\frac{1}{{\rho }_0}+\frac{1}{1-{\rho }_0}\right)\\ =\frac{{\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]}^2}{3L_f{\rho }_0\left(1-{\rho }_0\right)}.\end{array}$ (33)

将(27)和(33)代入(14)，注意到$6{\theta }_k+{\alpha }_k{\mu }_f\le 7$ 可以得出(29)。

其次，结合(32)，(33)和${\gamma }_k={\theta }_k=\frac{1}{{\left(N-k\right)}^2}$ ，得到：

$\begin{array}{c}{\displaystyle \sum }_{k=k_0}^{N-1}\frac{{\theta }_k{D}_X{T}_k}{{\text{Γ}}_{k+1}} \le \left(1-{\rho }_0\right)D_X\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right]{\displaystyle \sum }_{k=k_0}^{N-1}\frac{{\theta }_k{\rho }_0^{k-k_0}}{{\rho }_0^{k-k_0+1}}\\ \le \frac{\left(1-{\rho }_0\right){\pi }^2{D}_X}{6{\rho }_0}\left[AM\left(1+{\rho }_0\right){\rho }_0^{-1}+BM\right],\end{array}$ (34)

这些加上不等式(16)，就可以推导出(31)。

可以看出，此算法在目标函数关于外层变量强凸的情况时具有R-线性局部收敛速率，同时在处理关于外层变量凸的目标函数时，算法随着目标值接近局部极小值也达到了R-线性局部收敛速率。

4. 数值实验

本节的数值实验均在一台配备12代Intel(R) Core(TM) i5-1240P1.70GHz处理器和16 GB RAM的笔记本电脑上使用MATLAB R2018a实现，操作系统为Windows 11。基于文献[8]，采用以下自适应方法来控制$\sigma$ 。初始$\sigma$ 设置为0.99。如果在迭代到t步时，算法的起始点$y=y_{t-1}$ 已经满足误差标准，就将$\sigma$ 更新为$\sigma \leftarrow \sigma /10$ 。相反，如果内层循环未能在所需精度内找到子问题的解，就将$\sigma$ 更新为 $\sigma \leftarrow \text{min}\left\{0.99,10\sigma \right\}$ 。

接下来，考虑如下含有非线性约束的极小极大问题$\left({\text{P}}_1\right)$ ：

$\begin{array}{l}f\left(x,y\right)=\frac{1}{m}\left[-\frac{1}{2}{\Vert y\Vert }^2-b^{\text{T}}y+y^{\text{T}}Wx\right]+\frac{\lambda }{2}{\Vert x\Vert }^2,\\ g\left(x,y\right)=-c{\Vert x\Vert }^2+d{\Vert y\Vert }^2-e,\end{array}$

其中矩阵$W\in {ℝ}^{m\times n}$ 的行是从高斯分布$\mathcal{N}\left(0,I\right)$ 中生成的。参数$c,d$ 和$e$ 被限制在区间$\left(0,1\right)$ 内随机选取。在后续实验中，设置$n=m=10,b=0$ 和$\lambda =1/m$ 。

在这里，内层算法的迭代步长设置为0.4，外层迭代步长${\alpha }_k=0.2$ ，最大迭代数$K=1000$ 。固定参数${\mu }_f=1,{\lambda }_k=1$ ，$\left\{{\theta }_k\right\}$ 是生成的从0.5到1均匀递增的1000点序列。这样选取的理由如下：若目标函数$f$ 的强凸系数未知时，通常可设${\mu }_f=1$ 进行标准化，这样做既不影响算法收敛性分析且因为在增广拉格朗日框架下，${\mu }_f$ 与${\lambda }_k$ 共同调节梯度下降和惩罚项的权重，设为1可简化参数调节。同时若问题约束较温和或初始点$x_0$ 接近可行域，固定${\lambda }_k=1$ 可避免动态调整的复杂性。初始${\theta }_k=0.5$ 表示较弱动量，随着迭代逐步增至1，逐步增强加速效果，符合Nesterov加速梯度的理论框架，且均匀递增序列可避免突变导致的振荡，确保优化过程平稳收敛。

图1展示了aGBAL算法与GBAL算法相比解决问题$\left({\text{P}}_1\right)$ 更优越的性能。

Figure 1. The variation trends of the errors of the GBAL algorithm and the aGBAL algorithm in solving problem (P₁) with CPU time

图1. GBAL算法与aGBAL算法解决问题(P₁)的误差随CPU时间的变化趋势

5. 结论

我们通过对GBAL算法的外层迭代进行加速，提出了求解约束极小极大问题的隐式梯度加速算法。理论分析表明，在目标函数关于外层变量为凸的情况下，加速算法达到了R-线性收敛速率。这一改进使得算法在处理相关优化问题时更具竞争力。