一种用于求解等式约束鞍点问题的递归神经网络

A Recurrent Neural Network for Solving Equality-Constrained Saddle Point Problems

摘要: 鞍点问题在工程优化、经济决策、信号处理、智能控制等诸多领域中具有广泛的应用背景，本文针对等式约束下的鞍点问题，提出了一种新型递归神经网络模型。通过构建相应的动力学方程，分析了该神经网络在Lyapunov意义下的稳定性，并证明了其平衡点与原问题最优解的等价性。

Abstract: Saddle point problems have broad applications in various fields such as engineering optimization, economic decision-making, signal processing, and intelligent control. This paper proposes a novel recurrent neural network model for solving equality-constrained saddle point problems. By constructing the corresponding dynamic equations, the stability of the neural network in the Lyapunov sense is analyzed, and the equivalence between its equilibrium point and the optimal solution of the original problem is proven.

1. 引言

鞍点问题是数学规划与计算数学中的一个核心课题，其一般形式可表述为：${\min }_x{\max }_{y}f\left(x,y\right)$ ，也称为min-max问题，该问题的解$\left(x^{*},y^{*}\right)$ 被称为鞍点。这类问题在众多科学与工程领域有着广泛的应用背景。例如，在鲁棒优化中，为了应对数据的不确定性，决策者在最坏情况下做出最优决策，这直接导出了一个min-max问题[1]；在现代机器学习中，生成对抗网络(GANs)的训练过程本质上是一个鞍点优化问题[2]，而分布式机器学习中的对偶优化方法[3]、公平分类[4]以及对抗性训练[5]等核心问题，也都可归结为求解鞍点问题；在经济学与博弈论中，市场均衡分析中的Nash均衡点也常表现为鞍点形式[6]。再加上各种约束，特别是等式约束的引入，使得这类带约束的鞍点问题具有更加重要的研究价值。

在传统优化方法中，交替梯度下降–上升法[7]、乐观梯度下降法[8]和交替方向乘子法[3] [9]等方法被广泛用于处理鞍点问题。然而，这些传统方法的收敛速度与迭代步长的选择紧密相关，且通常需要进行多次迭代才能获得高精度解。这在需要在线或实时求解的应用场景(如实时优化决策、机器人在线路径规划等)之中可能并不适用。

为解决上述问题，众多学者致力于基于神经网络的优化问题求解方法的研究，并取得了丰硕的成果[10]-[26]。早期工作中，Tank与Hopfield [21]提出了用于线性规划Hopfield网络，开创了神经网络求解优化问题的先河。随后，Kennedy与Chua [22]提出了用于非线性规划的神经网络模型，进一步推动了该领域的发展。在约束处理方面，Zhang与Constantinides [23]提出了拉格朗日神经网络，Xia与Wang [24]提出了投影神经网络，分别用于处理等式与不等式约束问题。

特别地，基于动力系统的递归神经网络(RNN)方法因其能够并行处理的能力与硬件的可实现性，近年来受到了广泛学者的关注[17] [18]。与传统的迭代算法相比，RNN通过构建连续时间动力学系统，能够实现高效、实时的优化求解，特别适用于高维、大规模问题[19] [20] [25]。例如，针对以下带等式约束的优化问题(1)，Qin等人[25]提出了一种单层递归神经网络，证明了其平衡点与原问题最优解的等价性，并建立了系统的Lyapunov稳定性与全局收敛性。

$\begin{array}{cc}\min & f\left(x\right),\\ \text{s}\text{.t}.& Ax=b,\end{array}$ (1)

然而，现研究的许多神经网络模型主要针对的是带等式或不等式约束的单目标优化问题，以及不等式约束下的min-max问题，很多都未涉及等式约束下的鞍点问题。鉴于此，本文在Qin等人[25]的工作基础上，将其研究的单目标等式约束优化问题拓展至等式约束下的min-max问题，并构建了一种新型递归神经网络模型，用于求解带有线性等式约束的鞍点优化问题。

本文的主要贡献包括：(1) 建立了一种用于求解等式约束鞍点问题的新型递归神经网络动力学方程，并证明了其平衡点与鞍点问题最优解的等价性；(2) 分析了神经网络Lyapunov意义下的稳定性，证明了当初始点不在可行域内时其状态向量将指数收敛于可行域，并给出了两个神经网络在Lyapunov意义下全局收敛到鞍点问题最优解的充分条件；(3) 通过数值实验验证了所提神经网络在高维复杂问题中的有效性与快速收敛性。

本文的主要结构如下：第2节介绍相关预备知识；第3节建立问题模型与神经网络动力学方程，介绍与问题模型最优解的等价条件；第4节进行所提神经网络的稳定性和收敛性分析；第5节通过两个数值算例来验证所提理论的有效性和可行性；第6节总结全文并提出未来的研究方向。

2. 预备知识

在本文中，设$R^n$ 为$n$ 维实欧几里得空间。$\langle \cdot ,\cdot \rangle$ 表示$R^n$ 的内积，$\Vert \cdot \Vert$ 表示其对的范数，对于任意的$x\in R^n$ ，用${\rm T}$ 表示向量的转置，有$\Vert x\Vert =\sqrt{\langle x,x\rangle }=\sqrt{x^{\text{T}}x}$ 。函数f在$\left(x_0,y_0\right)$ 处关于$x$ 和$y$ 的梯度分别记为${\nabla }_{x}f\left(x_0,y_0\right)$ 和${\nabla }_{y}f\left(x_0,y_0\right)$ 。

Lyapunov稳定性和收敛性的相关定义请参考文献[27]。

定义2.1 [28]：设$S\subset R^n$ 是非空凸集，$\alpha \in \left(0,1\right)$ ，f是定义在S上的函数，如果对任意x₁，$x_2$ $\in S$ ，有

$f\left(\alpha x_1+\left(1-\alpha \right)x_2\right)\le +\alpha f\left(x_1\right)+\left(1-\alpha \right)f\left(x_2\right),$

则称函数f是S上的凸函数。

定义2.2 [29]：设X、Y是两个集合，$T:X\to Y$ 是一种对应法则，如果对任意$x\in X$ ，通过T有Y中的一个子集$T\left(x\right)$ 与之对应，则称T是X到Y的一个集值映射。

定义2.3 [29]：设E是实Banach空间，$E^{*}$ 是E的共轭空间，$D\subset E$ ，$T:D\to E^{*}$ ，$\forall x$ ，$y\in D$ 。若T满足

$\langle Tx-Ty,x-y\rangle \ge 0,$

则称T是单调算子。

3. 问题描述和模型建立

在本节中，本文将单目标优化问题(1)拓展成一个鞍点问题，并讨论其等价表述。

考虑以下具有等式约束的鞍点问题：

$\begin{array}{cc}\underset{x}{\min }\underset{y}{\max }& f\left(x,y\right),\\ \text{s}\text{.t}.& Ax=b,\\ & Cy=d,\end{array}$ (2)

其中$x={\left(x_1,x_2,\cdots ,x_m\right)}^{\text{T}}\in R^m$ ，$y={\left(y_1,y_2,\cdots ,y_n\right)}^{\text{T}}\in R^n$ ，$f:R^m\times R^n\to R$ 是双变量实值函数，$A\in R^{p\times m}$ ，$C\in R^{q\times n}$ ，$b\in R^p$ ，$d\in R^q$ 。在本文中，记可行域$E=\left\{{\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}|Ax=b,Cy=d\right\}$ ，若点${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}\in E$ 满足对任意${\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in E$ ，都有

$f\left(x^{*},y\right)\le f\left(x,y^{*}\right),$

则称${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}$ 是函数f在可行域E上的鞍点。

若${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}\in E$ 是问题(2)的鞍点，根据上述定义，易知，对于任意的$x\in X\left(y^{*}\right)$ ，$y\in Y\left(x^{*}\right)$ ,有

$f\left(x^{*},y\right)\le f\left(x^{*},y^{*}\right)\le f\left(x,y^{*}\right),$

其中$X\left(y^{*}\right)=\left\{x|Ax=b\right\}$ ，$Y\left(x^{*}\right)=\left\{y|Cy=d\right\}$ 。

假设1：(1) f在可行域E上是连续可微的，且在$X\left(y^{*}\right)$ 上是关于x的凸函数，在$Y\left(x^{*}\right)$ 是关于y的凹函数；

(2) A，C均为行满秩矩阵，即$rank\left(A\right)=p\le m$ ，$rank\left(C\right)=q\le n$ 。

定理3.1：若假设1成立，${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}$ 是问题(2)的最优解，即满足$\forall {\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in E$ ，有$f\left(x^{*},y\right)\le f\left(x^{*},y^{*}\right)\le f\left(x,y^{*}\right)$ ，当且仅当存在${\lambda }^{*}\in R^p$ ，$\mu \in R^q$ ，使得${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}$ 满足下列方程：

$\{\begin{array}{l}{\nabla }_{x}f\left(x^{*},y^{*}\right)+A^{\text{T}}{\lambda }^{*}=0,\hfill \\ -{\nabla }_{y}f\left(x^{*},y^{*}\right)+C^{\text{T}}{\mu }^{*}=0,\hfill \\ A{x}^{*}=b,\hfill \\ C{y}^{*}=d.\hfill \end{array}$ (3)

证明：假设${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}$ 是问题(2)的最优解，则有${\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}\in E$ (即$A{x}^{*}=b$ ，$C{y}^{*}=d$ )。一方面固定$y^{*}$ ，由假设1可知f在$X\left(y^{*}\right)$ 上是关于x的凸函数，于是f在$x^{*}\in X\left(y^{*}\right)$ 处取最小值，有

$-{\nabla }_{x}f\left(x^{*},y^{*}\right)\in N_{X\left(y^{*}\right)}\left(x^{*}\right),$

其中$N_{X\left(y^{*}\right)}\left(x^{*}\right)=\left\{v\in R^m:v^{\text{T}}\left(x^{*}-x\right)\ge 0,\forall x\in X\left(y^{*}\right)\right\}$ 。

由于$X\left(y^{*}\right)$ 是中的仿射子空间，则

$N_{X\left(y^{*}\right)}\left(x^{*}\right)=\left\{A^{\text{T}}\lambda |\lambda \in R^p\right\},$

故存在一个${\lambda }^{*}\in R^p$ ，使得当$A^{\text{T}}{\lambda }^{*}\in N_{X\left(y^{*}\right)}\left(x^{*}\right)$ 时，有

${\nabla }_{x}f\left(x^{*},y^{*}\right)+A^{\text{T}}{\lambda }^{*}=0.$ (4)

同理固定$x^{*}$ ，由假设1可知f在$Y\left(x^{*}\right)$ 是关于y的凹函数，于是f在$y^{*}\in Y\left(x^{*}\right)$ 处取最大值，类似上述证明过程，存在一个${\mu }^{*}\in R^q$ ，有

$-{\nabla }_{y}f\left(x^{*},y^{*}\right)+C^{\text{T}}{\mu }^{*}=0.$ (5)

根据$A{x}^{*}=b$ ，$C{y}^{*}=d$ 和(4)，(5)可知，满足(3)中所有方程，即必要性得证。

另一方面，假设存在${\lambda }^{*}\in R^p$ ，${\mu }^{*}\in R^q$ ，使得(3)成立，则有

$\{\begin{array}{l}{\nabla }_{x}f\left(x^{*},y^{*}\right)=-A^{\text{T}}{\lambda }^{*},\hfill \\ {\nabla }_{y}f\left(x^{*},y^{*}\right)=C^{\text{T}}{\mu }^{*}.\hfill \end{array}$ (6)

由假设1可知f在可行域E上是连续可微的，且在$X\left(y^{*}\right)$ 上是关于x的凸函数，在$Y\left(x^{*}\right)$ 是关于y的凹函数，根据凸函数和凹函数的性质，可得

$\{\begin{array}{l}f\left(x,y^{*}\right)-f\left(x^{*},y^{*}\right)\ge {\nabla }_{x}f{\left(x^{*},y^{*}\right)}^{\text{T}}\left(x-x^{*}\right),\forall x\in X\left(y^{*}\right),\hfill \\ f\left(x^{*},y\right)-f\left(x^{*},y^{*}\right)\le {\nabla }_{x}f{\left(x^{*},y^{*}\right)}^{\text{T}}\left(y-y^{*}\right),\forall y\in Y\left(x^{*}\right).\hfill \end{array}$ (7)

结合(6)，(7)，可得

$\{\begin{array}{l}f\left(x,y^{*}\right)-f\left(x^{*},y^{*}\right)\ge {\left(-{\lambda }^{*}\right)}^{\text{T}}A\left(x-x^{*}\right)=0,\forall x\in X\left(y^{*}\right),\hfill \\ f\left(x^{*},y\right)-f\left(x^{*},y^{*}\right)\le {\left({\mu }^{*}\right)}^{\text{T}}C\left(x-x^{*}\right)=0,\forall y\in Y\left(x^{*}\right),\hfill \end{array}$

即

$f\left(x^{*},y\right)\le f\left(x^{*},y^{*}\right)\le f\left(x,y^{*}\right),\forall {\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in E.$

故f在$\left(x^{*},y^{*}\right)\in E$ 处取得最优解，即充分性得证。

基于定理3.1，本文在文献[25]中提出的神经网络模型的基础上，将其神经网络框架拓展至等式约束下的鞍点问题(2)，构建了一种用于求解鞍点问题(2)的新型递归神经网络模型，并在定理4.2中证明了该神经网络的平衡点和问题(2)的等价性。本文构造的神经网络动力学方程如下：

$\{\begin{array}{l}\frac{\text{d}x}{\text{d}t}=-\left(I_m-P_x\right){\nabla }_{x}f\left(x,y\right)-A^{\text{T}}\left(Ax-b\right),\hfill \\ \frac{\text{d}y}{\text{d}t}=\left(I_n-P_y\right){\nabla }_{y}f\left(x,y\right)-C^{\text{T}}\left(Cy-d\right),\hfill \end{array}$ (8)

其中，$P_y=C^{\text{T}}{\left(C{C}^{\text{T}}\right)}^{-1}C$ ，$\left(I_m-P_x\right)$ 表示将向量投影到矩阵A的零空间上，$\left(I_n-P_y\right)$ 表示将向量投影到矩阵C的零空间上。

由于x的可行域$\left\{x|Ax=b\right\}$ 和y的可行域$\left\{y|Cy=d\right\}$ 是仿射集，故当x和y在可行域内移动时，只有零空间中的方向移动才不会违反约束$Ax=b$ 和$Cy=d$ 。$-{\nabla }_{x}f\left(x,y\right)$ ，${\nabla }_{y}f\left(x,y\right)$ 分别沿着函数值$f\left(\cdot ,y\right)$ 下降最快的方向和函数值$f\left(x,\cdot \right)$ 上升最快的方向进行移动，$\left(I_m-P_x\right)$ 和$\left(I_n-P_y\right)$ 分别对梯度进行投影，使得网络沿着负(或正)梯度方向在可行域的切空间上移动以优化目标函数。而${\Vert Ax-b\Vert }^2$ 和${\Vert Cy-d\Vert }^2$ 分别衡量了当前点x和y违反约束的程度，当x和y不在可行域内时，$-A^{\text{T}}\left(Ax-b\right)$ 和$-C^{\text{T}}\left(Cy-d\right)$ 为负梯度方向，分别推动状态x和y朝着满足约束$Ax=b$ 和$Cy=d$ 的可行域E快速收敛。

为方便阅读，本文将采用下列记号来简化神经网络模型(8)，记：

$\begin{array}{lll}z={\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}},\hfill & I=\left(\begin{array}{cc}{I}_m& 0\\ 0& I_n\end{array}\right),\hfill & P=\left(\begin{array}{cc}{P}_x& 0\\ 0& P_y\end{array}\right),\hfill \\ F\left(z\right)=\left(\begin{array}{c}{\nabla }_{x}f\left(x,y\right)\\ -{\nabla }_{y}f\left(x,y\right)\end{array}\right),\hfill & G=\left(\begin{array}{cc}{A}^{\text{T}}A& 0\\ 0& C^{\text{T}}C\end{array}\right),\hfill & H=\left(\begin{array}{c}{A}^{\text{T}}b\\ C^{\text{T}}d\end{array}\right).\hfill \end{array}$

神经网络(8)中的两个方程简化为如下：

$\frac{\text{d}z}{\text{d}t}=\left(\begin{array}{c}\frac{\text{d}x}{\text{d}t}\\ \frac{\text{d}y}{\text{d}t}\end{array}\right)=-\left(I-P\right)F\left(z\right)-Gz+H.$ (9)

定义3.1：$z^{*}$ 被称为神经网络(9)的平衡点，如果$z^{*}$ 满足以下方程：

$0=-\left(I-P\right)F\left(z\right)-Gz+H.$

4. 收敛性分析

在本节中，本文将分析神经网络(9)在Lyapunov意义下的稳定性和全局收敛性。首先证明若初始点不在可行域E中，则神经网络(9)的状态$z\left(t\right)$ 将指数收敛到E，其次证明神经网络(9)的平衡点与问题(2)的最优解是等价的，最后证明神经网络(9)在Lyapunov意义下是稳定的，并参考文献[26]，给出了两个充分条件，使得神经网络(9)全局收敛到问题(2)的一个最优解。

定理4.1：若假设1成立，当初始点$z\left(0\right)=z_0={\left(x_0^{\text{T}},y_0^{\text{T}}\right)}^{\text{T}}\notin E$ 时，神经网络(9)的状态$z\left(t\right)={\left(x{\left(t\right)}^{\text{T}},y{\left(t\right)}^{\text{T}}\right)}^{\text{T}}$ 将指数收敛到可行域E中。此外，如果初始点$z_0\in E$ ，则对于$\forall t\ge 0$ ，有$z\left(t\right)\in E$ 成立。

证明：构造以下函数：

$B\left(z\right)=B\left(x,y\right)=\frac{1}{2}{\Vert Ax-b\Vert }^2+\frac{1}{2}{\Vert Cy-d\Vert }^2,$ (10)

易知$B\left(z\right)$ 是一个可微的凸函数，且

${\nabla }_{x}B\left(z\right)=A^{\text{T}}\left(Ax-b\right),{\nabla }_{y}B\left(z\right)=C^{\text{T}}\left(Cy-d\right).$

根据复合函数的链式法则可得

$\begin{array}{c}\frac{\text{d}B\left(z\left(t\right)\right)}{\text{d}t}={\nabla }_{x}B{\left(z\left(t\right)\right)}^{\text{T}}\frac{\text{d}x\left(t\right)}{\text{d}t}+{\nabla }_{y}B{\left(z\left(t\right)\right)}^{\text{T}}\frac{\text{d}y\left(t\right)}{\text{d}t}\\ ={\left(Ax-b\right)}^{\text{T}}A\left[-\left(I_m-P_x\right){\nabla }_{x}f\left(x,y\right)-A^{\text{T}}\left(Ax-b\right)\right]\\ +{\left(Cy-d\right)}^{\text{T}}C\left[\left(I_n-P_y\right){\nabla }_{y}f\left(x,y\right)-C^{\text{T}}\left(Cy-d\right)\right].\end{array}$ (11)

由假设1，A是行满秩矩阵，易得矩阵$A{A}^{\text{T}}$ 为对称正定矩阵，则

$\{\begin{array}{l}A\left(I_m-P_x\right)=A\left(I_m-A^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}A\right)=A-A=0,\hfill \\ C\left(I_n-P_y\right)=C\left(I_n-C^{\text{T}}{\left(C{C}^{\text{T}}\right)}^{-1}C\right)=C-C=0.\hfill \end{array}$

令${\lambda }_A$ 为矩阵$A{A}^{\text{T}}$ 的最小特征值，${\lambda }_C$ 为矩阵$C{C}^{\text{T}}$ 的最小特征值，且$\lambda =\min \left\{{\lambda }_A,{\lambda }_C\right\}$ ，显然$\lambda >0$ 。于是根据(11)，可得

$\begin{array}{c}\frac{\text{d}B\left(z\left(t\right)\right)}{\text{d}t}=-{\left(Ax-b\right)}^{\text{T}}A{A}^{\text{T}}\left(Ax-b\right)-{\left(Cy-d\right)}^{\text{T}}C{C}^{\text{T}}\left(Cy-d\right)\\ \le -{\lambda }_A{\Vert Ax-b\Vert }^2-{\lambda }_C{\Vert Cy-d\Vert }^2\\ \le -2\min \left\{{\lambda }_A,{\lambda }_C\right\}\left(\frac{1}{2}{\Vert Ax-b\Vert }^2+\frac{1}{2}{\Vert Cy-d\Vert }^2\right)\\ =-2\lambda B\left(z\left(t\right)\right),\end{array}$ (12)

即

$B\left(z\left(t\right)\right)\le {\text{e}}^{-2\lambda t}B\left(z_0\right).$

所以，当初始点$z\left(0\right)=z_0=\notin E$ 时，神经网络(9)的状态向量$z\left(t\right)={\left(x{\left(t\right)}^{\text{T}},y{\left(t\right)}^{\text{T}}\right)}^{\text{T}}$ 将指数收敛到可行域E中。

另一方面，如果$z_0\in E$ ，则恒有$B\left(z_0\right)=0$ 成立，故

$0\le B\left(z\left(t\right)\right)\le {\text{e}}^{-2\lambda t}B\left(z_0\right)\le 0,$

即对于$\forall t\ge 0$ ，

$B\left(z\left(t\right)\right)=0.$

所以当初始点$z_0\in E$ 时，对于$\forall t\ge 0$ ，有$z\left(t\right)\in E$ 成立。

定理4.2若假设1成立，则神经网络(9)的平衡点与问题(2)的最优解等价。

证明：假设$z^{*}={\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}$ 是神经网络(9)的平衡点，根据定义3.1可知

$0=-\left(I-P\right)F\left(z^{*}\right)-G{z}^{*}+H,$ (13)

即

$\{\begin{array}{l}0=-\left(I_m-P_x\right){\nabla }_{x}f\left(x^{*},y^{*}\right)-A^{\text{T}}\left(A{x}^{*}-b\right),\hfill \\ 0=\left(I_n-P_y\right){\nabla }_{y}f\left(x^{*},y^{*}\right)-C^{\text{T}}\left(C{y}^{*}-d\right).\hfill \end{array}$ (14)

根据定理4.1，若初始点$z\left(0\right)=z_0\notin E$ ，则神经网络(9)的状态$z\left(t\right)$ 将指数收敛到可行域E中，若初始点$z_0\in E$ ，则对于$\forall t\ge 0$ ，有$z\left(t\right)\in E$ 成立。因此，可知$z^{*}\in E$ ，由(14)可得

$\{\begin{array}{l}0=\left(I_m-P_x\right){\nabla }_{x}f\left(x^{*},y^{*}\right),\hfill \\ 0=\left(I_n-P_y\right){\nabla }_{y}f\left(x^{*},y^{*}\right),\hfill \\ A{x}^{*}=b,\hfill \\ C{y}^{*}=d,\hfill \end{array}$ (15)

根据(15)，可知

$\{\begin{array}{l}0=\left(I_m-P_x\right){\nabla }_{x}f\left(x^{*},y^{*}\right)={\nabla }_{x}f\left(x^{*},y^{*}\right)-A^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}A{\nabla }_{x}f\left(x^{*},y^{*}\right),\\ 0=\left(I_n-P_y\right){\nabla }_{y}f\left(x^{*},y^{*}\right)={\nabla }_{y}f\left(x^{*},y^{*}\right)-C^{\text{T}}{\left(C{C}^{\text{T}}\right)}^{-1}C{\nabla }_{y}f\left(x^{*},y^{*}\right).\end{array}$

令${\lambda }^{*}={\left(A{A}^{\text{T}}\right)}^{-1}A{\nabla }_{x}f\left(x^{*},y^{*}\right)$ ，${\mu }^{*}={\left(C{C}^{\text{T}}\right)}^{-1}C{\nabla }_{y}f\left(x^{*},y^{*}\right)$ ，根据定理3.1可知，$z^{*}$ 是问题(2)的最优解。

另一方面，假设$\overline{z}={\left({\overline{x}}^{\text{T}},{\overline{y}}^{\text{T}}\right)}^{\text{T}}$是问题(2)的最优解，则$\overline{z}\in E$ (即$A\overline{x}=b$ ，$C\overline{y}=d$ )。由定理3.1可知

$\{\begin{array}{l}-\left(I_m-P_x\right){\nabla }_{x}f\left(\overline{x},\overline{y}\right)-A^{\text{T}}\left(A\overline{x}-b\right)=\left(I_m-P_x\right)A^{\text{T}}\overline{\lambda }-A^{\text{T}}\left(A\overline{x}-b\right)=0,\hfill \\ \left(I_n-P_y\right){\nabla }_{y}f\left(\overline{x},\overline{y}\right)-C^{\text{T}}\left(C\overline{y}-d\right)=\left(I_n-P_y\right)C^{\text{T}}\overline{\mu }-C^{\text{T}}\left(C\overline{y}-d\right)=0,\hfill \end{array}$(16)

即

$-\left(I-P\right)F\left(\overline{z}\right)-G\overline{z}+H=0.$

根据定义3.1可知，$\overline{z}$ 是神经网络(9)的平衡点。

定理4.3：若假设1成立，神经网络(9)的状态$z\left(t\right)$ 在Lyapunov意义下是稳定的。此外，若满足下列条件之一[26]：

(A) 设$z^{*}\in E^{*}=\left\{{\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in E|{\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}是f\left(x,y\right)的鞍�\right\}$ ，$\forall z\in E$ ，存在一个函数$k\left(z,z^{*}\right)\ge 0$ ，使得

${\left(z-z^{*}\right)}^{\text{T}}F\left(z\right)=0\Rightarrow F\left(z\right)=k\left(z,z^{*}\right)F\left(z^{*}\right);$

(B) 设$z^{*}\in E^{*}$ ，$\forall z\in E$ ，使得

${\left(z-z^{*}\right)}^{\text{T}}F\left(z\right)=0\Rightarrow z\in E^{*}.$

对于任意初始值$z_0={\left(x_0^{\text{T}},y_0^{\text{T}}\right)}^{\text{T}}\in E$ ，神经网络(9)的状态$z\left(t\right)$ 全局收敛到它的一个平衡点。

证明：首先，证明神经网络(9)的状态$z\left(t\right)$ 在Lyapunov意义下是稳定的。假设$z^{*}={\left({\left(x^{*}\right)}^{\text{T}},{\left(y^{*}\right)}^{\text{T}}\right)}^{\text{T}}$ 是鞍点问题(2)的最优解，则有$z^{*}\in E$ ，由定理4.2可知，$z^{*}$ 是神经网络(9)的平衡点，于是有下列式子成立：

$0=-\left(I-P\right)F\left(z^{*}\right)-G{z}^{*}+H=\left(I-P\right)F\left(z^{*}\right).$ (17)

构造下列Lyapunov函数：

$V\left(z\right)=\frac{1}{2}{\Vert z-z^{*}\Vert }^2,$ (18)

显然，对于$\forall z\in E$ ，$V\left(z\right)\ge 0$ 。此外，对于$\forall {\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}\in E$ ，有

$\{\begin{array}{l}{\left(x-x^{*}\right)}^{\text{T}}{P}_x={\left(x-x^{*}\right)}^{\text{T}}{A}^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}A={\left(Ax-A{x}^{*}\right)}^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}A=0,\hfill \\ {\left(y-y^{*}\right)}^{\text{T}}{P}_y={\left(y-y^{*}\right)}^{\text{T}}{C}^{\text{T}}{\left(C{C}^{\text{T}}\right)}^{-1}C={\left(Cy-C{y}^{*}\right)}^{\text{T}}{\left(C{C}^{\text{T}}\right)}^{-1}C=0,\hfill \end{array}$

即对于$\forall z\in E$ ，

$\begin{array}{c}{\left(z-z^{*}\right)}^{\text{T}}P={\left(\begin{array}{c}x-x^{*}\\ y-y^{*}\end{array}\right)}^{\text{T}}\left(\begin{array}{cc}{P}_x& 0\\ 0& P_y\end{array}\right)\\ =\left(\begin{array}{cc}{\left(x-x^{*}\right)}^{\text{T}}{P}_x& {\left(y-y^{*}\right)}^{\text{T}}{P}_y\end{array}\right)\\ =0.\end{array}$ (19)

根据(17)，(19)，可知

$\begin{array}{c}{\left(z-z^{*}\right)}^{\text{T}}F\left(z^{*}\right)=\left[{\left(z-z^{*}\right)}^{\text{T}}P+{\left(z-z^{*}\right)}^{\text{T}}\left(I-P\right)\right]F\left(z^{*}\right)\\ ={\left(z-z^{*}\right)}^{\text{T}}\left(I-P\right)F\left(z^{*}\right)\\ =0,\end{array}$ (20)

由于$F\left(z\right)$ 是单调算子[30]，满足下列方程：

${\left(z-z^{*}\right)}^{\text{T}}F\left(z\right)-{\left(z-z^{*}\right)}^{\text{T}}F\left(z^{*}\right)\ge 0,$ (21)

则根据(20)，(21)，可知，对于$\forall z\in E$ ，有

${\left(z-z^{*}\right)}^{\text{T}}F\left(z\right)\ge 0.$

于是，对Lyapunov函数$V\left(z\right)$ 求导，可得

$\begin{array}{c}\frac{\text{d}V}{\text{d}t}={\left(x-x^{*}\right)}^{\text{T}}\frac{\text{d}x}{\text{d}t}+{\left(y-y^{*}\right)}^{\text{T}}\frac{\text{d}y}{\text{d}t}\\ =-{\left(x-x^{*}\right)}^{\text{T}}\left(I_m-P_x\right){\nabla }_{x}f\left(x,y\right)+{\left(y-y^{*}\right)}^{\text{T}}\left(I_n-P_y\right){\nabla }_{y}f\left(x,y\right)\\ =-{\left(z-z^{*}\right)}^{\text{T}}\left(I-P\right)F\left(z\right)\\ =-{\left(z-z^{*}\right)}^{\text{T}}F\left(z\right)\\ \le 0,\end{array}$ (22)

即神经网络在Lyapunov意义下是稳定的。

其次证明，对于任意初始值$z_0={\left(x_0^{\text{T}},y_0^{\text{T}}\right)}^{\text{T}}\in E$ ，神经网络(9)的状态$z\left(t\right)$ 全局收敛到它的一个平衡点。令$H\left(z\right)={\left(z-z^{*}\right)}^{\text{T}}F\left(z\right)$ ，由条件假设可知：

(a) 若$H\left(z\right)=0$ ，$\forall z\in E$ ，根据条件(A)可得$F\left(z\right)=k\left(z,z^{*}\right)F\left(z^{*}\right)$ ，则

$\frac{\text{d}z}{\text{d}t}=-\left(I-P\right)F\left(z\right)=-k\left(z,z^{*}\right)\left(I-P\right)F\left(z^{*}\right)=0;$

(b) 若$H\left(z\right)=0$ ，$\forall z\in E$ ，根据条件(B)可得$z\in E^{*}$ ，即z是问题(2)的一个最优解，根据定理4.2可知，z是神经网络(9)的一个平衡点。

因此，由给出的两个条件之一即可得，当$H\left(z\right)=0$ 时，z为神经网络(9)的平衡点。此外，根据(22)，对于任意初始点$z\left(t_0\right)\in E$ ，有$V\left(z\left(t\right)\right)$ 随着$t\to +\infty$ 非递增，且当$z\to +\infty$ 时，根据(18)，易得$V\left(z\right)\to +\infty$ ，即$V\left(z\right)$ 是正定无界的。上述表明：

$0\le V\left(z\left(t\right)\right)\le V\left(z\left(0\right)\right)<+\infty .$ (23)

由(23)可知，$z\left(t\right)$ 是有界的，根据(9)可知，$\Vert \dot{z}\left(t\right)\Vert$ 也是有界的($\exists M\ge 0$ ，$\Vert \dot{z}\left(t\right)\Vert \le M$ )，此外，存在一个极限点$\overline{z}$ 和一个收敛序列

$\left\{t_k|0<t_1<t_2<\cdots <t_k<t_{k+1}<\cdots \right\},$ (24)

当$k\to +\infty$ 时，$t_k\to +\infty$ ，使得$z\left(t_k\right)\to \overline{z}$ ，显然，$\overline{z}\in E$ 。

接下来将证明$H\left(\overline{z}\right)=0$ ，则$\overline{z}$ 是神经网络(9)的一个平衡点。假设$H\left(\overline{z}\right)>0$ ，由$H\left(z\right)$ 的连续性可知，存在一个$\epsilon >0$ 和$\delta >0$ ，当$\Vert z-\overline{z}\Vert <\delta$ 时，有

$H\left(z\right)>\epsilon .$ (25)

由(24)，存在一个正整数N，使得$\Vert z\left(t_k\right)-\overline{z}\Vert <\frac{\delta }{2}$ 对于所有的$k>N$ 成立，所以当$t\in \left[t_k-\frac{\delta }{4M},t_k+\frac{\delta }{4M}\right]$ 且$k>N$ 时，有

$\Vert z\left(t\right)-\overline{z}\Vert \le \Vert z\left(t\right)-z\left(t_k\right)\Vert +\Vert z\left(t_k\right)-\overline{z}\Vert \le M\left|t-t_k\right|+\frac{\delta }{2}\le \delta .$ (26)

根据(25)可知，当$t\in \left[t_k-\frac{\delta }{4M},t_k+\frac{\delta }{4M}\right]$ 且$k>N$ 时，有$H\left(z\left(t\right)\right)>\epsilon$ 。一方面，由于${\cup }_{k>N}\left[t_k-\frac{\delta }{4M},t_k+\frac{\delta }{4M}\right]$ 的测度是无限的，可得

${\displaystyle {\int }_0^{+\infty }H}\left(z\left(t\right)\right)\text{d}t>{\displaystyle {\int }_0^{+\infty }\epsilon \text{d}t}=+\infty .$ (27)

另一方面，由(22)，(23)可知，$V\left(z\left(t\right)\right)$ 单调递减且有界，即存在一个常数$V_0$ ，使得$\underset{t\to +\infty }{\lim }V\left(z\left(t\right)\right)=V_0$ 。根据(22)，有

$\begin{array}{c}{\displaystyle {\int }_0^{+\infty }H}\left(z\left(t\right)\right)\text{d}t=\underset{t\to +\infty }{\lim }{\displaystyle {\int }_0^{t}H}\left(z\left(s\right)\right)\text{d}s\\ =-\underset{t\to +\infty }{\lim }{\displaystyle {\int }_0^t\dot{V}}\left(z\left(s\right)\right)\text{d}s\\ =-\underset{t\to +\infty }{\lim }\left[V\left(z\left(t\right)\right)-V\left(z\left(0\right)\right)\right]\\ =V\left(z\left(0\right)\right)-V_0\\ <+\infty ,\end{array}$(28)

与(27)矛盾，所以$H\left(\overline{z}\right)=0$ ，即$\overline{z}$ 是神经网络(9)的一个平衡点。

最后，证明$\underset{t\to \infty }{\lim }z\left(t\right)=\overline{z}$ ，类似$V\left(z\right)$ 的定义，定义另一个Lyapunov函数：

$W\left(z\right)=\frac{1}{2}{\Vert z-\overline{z}\Vert }^2.$ (29)

参考前面的证明，可以证明得到$\frac{\text{d}W}{\text{d}t}\le 0$ ，$W\left(\overline{z}\right)=0$ 且$W\left(z\right)$ 是径向无界的。根据函数$W\left(z\right)$ 的连续性，对于任意$\epsilon >0$ ，存在$\delta >0$ ，使得$\Vert z-\overline{z}\Vert \le \delta$ ，$W\left(z\right)<\frac{\epsilon }{2}$ 。同时，由(24)可知，$z\left(t_k\right)\to \overline{z}$ ，并且存在一个正整数$t_N$ ，使得$\Vert z\left(t_N\right)-\overline{z}\Vert <\delta$ ，有

$W\left(z\left(t_N\right)\right)=\left|W\left(z\left(t_N\right)\right)-W\left(\overline{z}\right)\right|<\frac{\epsilon }{2},$ (30)

根据$W\left(z\left(t\right)\right)$ 的单调非递增性和(29)，(30)，可知，对于$\forall t>t_N$ ,

${\Vert z\left(t\right)-\overline{z}\Vert }^2=2W\left(z\left(t\right)\right)\le 2W\left(z\left(t_N\right)\right)<\epsilon ,$

即

$\underset{t\to \infty }{\lim }z\left(t\right)=\overline{z}.$

因此对于任意初始点$z_0={\left(x_0^{\text{T}},y_0^{\text{T}}\right)}^{\text{T}}\in E$ ，神经网络(9)的状态向量$z\left(t\right)$ 将全局收敛到它的一个平衡点。

5. 数值模拟

本节对前面的理论分析提供两个数值算例来进行验证，展示本文所提出的神经网络的有效性和可行性。与文献[25]相比，本文不仅在单目标优化问题的研究基础上拓展成了min-max的鞍点问题，而且还继承了文献[25]中神经网络的指数收敛性和有效时间内收敛的特性。本节的所有数值实验均在 MATLAB 编程环境下进行。

例5.1：考虑如下等式约束的鞍点优化问题：

$\begin{array}{ll}\underset{x}{\min }\underset{y}{\max }\hfill & f\left(x,y\right)=x_1^2+2x_2^2+3x_3^2+x_1{y}_1-x_2{y}_1+x_3{y}_2-\left(y_1^2+2y_2^2\right),\hfill \\ \text{s}\text{.t}.\hfill & Ax=b,\hfill \\ \hfill & Cy=d,\hfill \end{array}$ (31)

其中$x\in {ℝ}^3$ ，$y\in {ℝ}^2$ ，A，C均为行满秩矩阵，令：

$A=\left(\begin{array}{ccc}1& 1& 1\end{array}\right),b=1,C=\left(\begin{array}{cc}1& -1\end{array}\right),d=0.$

显然，问题(31)的目标函数f关于x是凸函数(由于Hessian矩阵${\nabla }_{xx}^{2}f=\text{diag}\left(2,4,6\right)$ 正定)，关于y是凹函数(Hessian矩阵${\nabla }_{yy}^{2}f=\text{diag}\left(-2,-4\right)$ 负定)，满足本文假设条件。通过求解KKT条件方程组，可得问题(31)的理论鞍点为$x^{*}={\left[0.569,0.241,0.190\right]}^{\text{T}}$ ，$y^{*}={\left[-0.086,-0.086\right]}^{\text{T}}$ ，目标函数的最优解为$f\left(x^{*},y^{*}\right)=0.481$ 。

接下来本文将采用文中所描述的神经网络来进行求解，则与问题(31)所对应的神经网络方程(8)可改写为如下方程：

$\{\begin{array}{l}\frac{\text{d}x}{\text{d}t}=-\left(I_3-P_x\right){\nabla }_{x}f\left(x,y\right)-A^{\text{T}}Ax+A^{\text{T}}b,\\ \frac{\text{d}y}{\text{d}t}=\left(I_2-P_y\right){\nabla }_{y}f\left(x,y\right)-C^{\text{T}}Cy+C^{\text{T}}d,\end{array}$ (32)

其中

$\begin{array}{ll}{P}_x=A^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}A=\frac{1}{3}\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right),\hfill & P_y=C^{\text{T}}{\left(C{C}^{\text{T}}\right)}^{-1}C=\frac{1}{2}\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right),\hfill \\ {\nabla }_{x}f\left(x,y\right)=\left(\begin{array}{c}2x_1+y_1\\ 4x_2-y_1\\ 6x_3+y_2\end{array}\right),\hfill & {\nabla }_{y}f\left(x,y\right)=\left(\begin{array}{c}{x}_1-x_2-2y_1\\ x_3-4y_2\end{array}\right).\hfill \end{array}$

根据神经网络模型(32)，在MATLAB环境下进行仿真实验，随机生成10组初始点$z_0={\left(x_0^{\text{T}},y_0^{\text{T}}\right)}^{\text{T}}$ ，其中$x_0\in {ℝ}^3$ ，$y_0\in {ℝ}^2$ ，仿真时间$t\in \left[0,2\right]$ 。数值结果如图1和图2所示。

Figure 1. The convergence behavior plot of the objective function in Example 5.1

图1. 例5.1中的目标函数收敛过程图

图1展示了例5.1中的目标函数值$f\left(x\left(t\right),y\left(t\right)\right)$ 从不同初始值均收敛到最优值$f^{*}$ 的过程。

Figure 2. Convergence trajectories plot of each component of the state variables in Example 5.1

图2. 例5.1中状态变量的每个分量收敛轨迹图

图2中的左右两图分别展示了x，y分量的收敛轨迹，10条不同颜色的轨迹线从随机初始点出发，均收敛到点$x^{*}$ 和点$y^{*}$ 。可以看出，尽管初始点分布在较广的范围内，所有轨迹均能快速收敛到理论最优值，验证了神经网络的全局收敛特性。

例5.2：为了进一步验证神经网络(9)在处理复杂问题时的性能，本文考虑如下较高维度的鞍点问题：

$\begin{array}{l}\underset{x}{\min }\underset{y}{\max }f\left(x,y\right)=2x_1^2+3x_2^2+x_3^2+x_1{x}_2-2x_2{x}_3+2x_1{y}_1-x_2{y}_2+3x_3{y}_3\\ -\left(y_1^2+2y_2^2+y_3^2\right)+y_1{y}_2-y_2{y}_3,\\ \text{s}\text{.t}Ax=b,\\ Cy=d,\end{array}$ (33)

其中$x\in {ℝ}^3$ ，$y\in {ℝ}^3$ ，A，C均为行满秩矩阵，令：

$A=\left(\begin{array}{ccc}1& 2& -1\\ 3& -1& 2\end{array}\right),b=\left(\begin{array}{c}4\\ 1\end{array}\right),C=\left(\begin{array}{ccc}2& -1& 1\\ 1& 3& -2\end{array}\right),d=\left(\begin{array}{c}3\\ -2\end{array}\right).$

与例5.1中的问题(31)相比，问题(33)中目标函数的自变量相对维数更高一些，包含交叉项以及更复杂的非线性结构，更具有研究性，且关于x是凸函数，关于y是凹函数，满足本文的假设条件。通过求解KKT系统，得到该问题的理论鞍点为$x^{*}={\left[1.293,0.845,-1.017\right]}^{\text{T}}$ ，$y^{*}={\left[0.976,-0.878,0.171\right]}^{\text{T}}$ ，目标函数f的最优解为$f\left(x^{*},y^{*}\right)=8.8457$ 。

将文中所提的神经网络(9)应用到问题(33)上，令$z={\left(x^{\text{T}},y^{\text{T}}\right)}^{\text{T}}$ 可得：

$\frac{\text{d}z}{\text{d}t}=-\left(I-P\right)F\left(z\right)-Gz+H,$ (34)

其中

$\begin{array}{l}I-P=\left(\begin{array}{cc}\frac{1}{83}\left(\begin{array}{ccc}9& -15& -21\\ -15& 25& 35\\ -21& 35& 49\end{array}\right)& 0\\ 0& \frac{1}{75}\left(\begin{array}{ccc}1& -5& -7\\ -5& 25& 35\\ -7& 35& 49\end{array}\right)\end{array}\right),\\ F\left(z\right)=\left(\begin{array}{c}4x_1+x_2+2y_1\\ 6x_2+x_1-2x_3-y_2\\ 2x_3-2x_2+3y_3\\ -2x_1+2y_1-y_2\\ x_2+4y_2-y_1+y_3\\ -3x_3+2y_3+y_2\end{array}\right),G=\left(\begin{array}{cccccc}10& -1& 5& 0& 0& 0\\ -1& 5& -4& 0& 0& 0\\ 5& -4& 5& 0& 0& 0\\ 0& 0& 0& 5& 1& 0\\ 0& 0& 0& 1& 10& -7\\ 0& 0& 0& 0& -7& 5\end{array}\right),H=\left(\begin{array}{c}7\\ 7\\ -2\\ 4\\ -9\\ 7\end{array}\right).\end{array}$

同样，本文用改写后的神经网络(34)在MATLAB环境下采取随机生成10组初始点来进行数值模拟，数值仿真结果如图3和图4所示。与例5.1相比，该问题具有更高的维度和更复杂的动力学特性，但本文提出的神经网络仍能有效收敛。

Figure 3. The convergence behavior plot of the objective function in Example 5.2

图3. 例5.2中的目标函数收敛过程图

图3展示了例5.2中的目标函数值$f\left(x\left(t\right),y\left(t\right)\right)$ 从不同初始值$z_0={\left(x_0^{\text{T}},y_0^{\text{T}}\right)}^{\text{T}}$ 均收敛到最优值$f^{*}$ 的过程。

Figure 4. Convergence trajectories plot of each component of the state variables in Example 5.2

图4. 例5.2中状态变量的每个分量收敛轨迹图

图4的左右两图分别展示了x和y分量的收敛轨迹，所有轨迹线从鞍点附近的扰动初始点出发，快速收敛到理论鞍点，验证了神经网络的快速收敛特性。

综上，本文对比了上面两个例子，表1总结了两个算例的收敛性能指标，包括平均迭代步数、约束精度和计算时间等。

Table 1. Comparison of neural network convergence performance

表1. 神经网络收敛性能比较

算例	变量为度	平均收敛步数	约束精度	计算时间(s)	收敛速率
5.1	3 × 2	124	1.2 × 10^−^6	0.45	指数收敛
5.22	3 × 2	89	8.7 × 10^−^7	0.38	指数收敛

数值实验表明，本文提出的递归神经网络为等式约束鞍点问题提供了一种有效的求解方法，具有收敛快、精度高、易于实现等优点。

6. 总结

基于非线性规划在工程与经济等领域的重要应用背景，本文聚焦于等式约束下的鞍点问题这一核心课题。相较于Qin等人[25]针对单目标伪凸优化提出的递归神经网络，本文将其框架拓展至更具挑战性的min-max鞍点问题场景，实现了从单一优化到鞍点问题的理论跨越。本文构建了一种新的神经网络模型，在适当的假设下，证明了神经网络平衡点与鞍点问题最优解的等价性。进一步地，证明了神经网络在Lyapunov意义下是稳定的，在一些附加条件下，神经网络全局收敛到鞍点问题的最优解，为之后鞍点问题的研究提供了一种新的理论支持。

本文的理论分析基于若干关键假设，这些假设在保证理论严密性的同时，也带来了一定的应用局限性，例如本文对目标函数的凸–凹结构和光滑性有较强的依赖。在此基础上，如何将此RNN框架扩展到非凸–非凹问题(可能需要引入更复杂的动态或正则化项)，以及如何处理非光滑的目标函数成为了未来的研究方向之一。