一种求解半定线性互补问题的神经网络方法

A Neural Network Approach for Solving Semi-Definite Linear Complementarity Problem

摘要: 本文提出了一种新颖的投影神经网络方法，用于求解半定线性互补问题(SDLCP)。理论分析表明，在特定条件下，所提方法能够保证指数稳定性。并且通过MATLAB仿真实验给出了数值算例，充分证明了所提投影神经网络模型的有效性。本文提出的神经网络框架为求解半定线性互补问题提供了一种具有前景且切实可行的方法，具有广阔的应用潜力。

Abstract: This paper proposes a novel projection neural network method for solving the Semi-Definite Linear Complementarity Problem (SDLCP). Theoretical analysis shows that under specific conditions, the proposed method can guarantee exponential stability. Moreover, an example is presented through MATLAB simulation experiments, which fully demonstrates the effectiveness of the proposed projection neural network model. The neural network framework proposed in this paper provides a promising and practical approach for solving the Semi-Definite Linear Complementarity Problem, with broad application potential.

1. 引言

互补问题最早由数学家莱姆克和豪森于1964年在研究博弈论中的纳什均衡时提出。近年来，由于具备并行性、动态演化能力以及易于硬件实现等优势，神经网络方法已被广泛应用于各类互补问题的求解。廖立志等人[1]首次提出了一种基于无约束极小化重构的神经网络模型，用于求解线性互补问题(LCP)。此后，他们将这一框架扩展到了非线性互补问题(NCP)的场景中[2]。侯彬等人[3]聚焦于一类更具一般性的广义垂直互补问题(GVCP)，并提出了一种基于对数–指数平滑函数的神经网络模型。这些研究充分体现了神经网络在处理各类互补问题时的适应性与方法多样性。

对于半定线性互补问题，以往最常用内点法进行求解。有些学者基于新核函数的原始对偶内点法求解半定线性互补问题，但非正交方向增加分析难度，部分参数下内迭代次数偏高。也有基于Chen-Mangasarian类平滑函数和光滑Fischer-Burmeister函数的非内点连续方法，但缺点是线性搜索耗时、部分问题迭代次数多。据我们所知，利用神经网络方法求解半定线性互补问题(SDLCP)的研究仍极为有限。

在此背景下，本文旨在采用投影神经网络模型来求解SDLCP。

2. 预备知识

2.1. SDLCP定义

设$S^n$ 表示所有$n\times n$ 实对称矩阵构成的空间，$S_{\text{+}}^n$ 表示$S^n$ 中对称半正定矩阵构成的锥。给定一个线性变换$L:S^n\to S^n$ 及一个矩阵$Q\in S^n$ ，半定线性互补问题[4]是要找到一个矩阵$X\in S^n$ ，使得

$X\in S_{+}^n,F\left(X\right)\doteq L\left(X\right)+Q\in S_{+}^n,\langle X,F\left(X\right)\rangle =0$ ，(1)

其中$\langle X,F\left(X\right)\rangle$ 表示矩阵乘积$XF\left(X\right)$ 的迹。

2.2. 投影算子

设$P_{S_{+}^n}:S^n\to S_{+}^n$ 为一个投影算子，其定义为

$P_{S_{+}^n}=\arg \underset{Y\in S_{+}^n}{\min }{\Vert X-Y\Vert }_F$ ，

其范数为Frobenius范数。

2.3. 谱分解

考虑对角矩阵$D=diag\left(d_1,d_2,\cdots ,d_n\right)$ ，定义$D^{+}\doteq diag\left(d_1^{+},d_2^{+},\cdots ,d_n^{+}\right)$ ，确保所有对角元素均为非负。对于$X\in S^n$ ，假设$X=UD{U}^{{\rm T}}$ 是谱分解，其中$U$ 是正交矩阵，$D$ 是对角矩阵，定义$X^{+}\doteq U{D}^{+}{U}^{{\rm T}}$ 。本文中将对$P_{S_{+}^n}$ 进行谱分解处理，如下

$P_{S_{+}^n}\left(X\right)=X^{+}$ 。

2.4. 矩阵向量化

将矩阵$X\in S_{+}^n$ 的向量化定义为按列堆叠其元素得到$R^{n^2}$ 中的一个向量，记为$vec\left(X\right)$ ，

$vec\left(X\right)=\left(\begin{array}{c}{X}_{11}\\ X_{21}\\ ⋮\\ X_{n1}\\ X_{12}\\ X_{22}\\ ⋮\\ X_{nn}\end{array}\right)\in R^{n^2}$ 。

定义1：设$F:S^n\to S_{+}^n$ 是定义在$S^n$ 上的一个映射。若存在常数$\mu >0$ ，使得对于所有$X,Y\in S^n$ ，不等式

$\langle F\left(X\right)-F\left(Y\right),X-Y\rangle \ge \mu {\Vert X-Y\Vert }_F^2$

成立，则称映射$F\left(X\right)$ 是强单调的，其中$\mu$ 称为强单调常数。

引理1：[5]对任意$X\in S^n,Y\in S_{+}^n$ ，

$\langle X-P_{S_{+}^n}\left(X\right),P_{S_{+}^n}\left(X\right)-Y\rangle \ge 0$

成立，并且对于任意$U,V\in S^n$ ，有

${\Vert P_{S_{+}^n}\left(U\right)-P_{S_{+}^n}\left(V\right)\Vert }_F\le {\Vert U-V\Vert }_F$ 。

引理2：[6]设$S_{+}^n\subseteq S^n$ 为非空闭凸集，$X^{*}\in S_{+}^n$ ，$F:S^n\to S_{+}^n$ 为连续映射，则

$\langle X-X^{*},F\left(X^{*}\right)\rangle \ge 0,\forall X\in S_{+}^n$

与

$X^{*}=P_{S_{+}^n}\left(X^{*}-\alpha F\left(X^{*}\right)\right)$

等价，其中$\alpha >0$ 。

引理3：[7]设$\tilde{F}:D\subset R^{n^2}\to R^{n^2}$ 在开凸集$D$ 上可微，定义函数$g$ ：

$g\left(x\right)={\displaystyle {\int }_0^1{\left(x-x_0\right)}^{{\rm T}}\tilde{F}\left(x_0+t\left(x-x_0\right)\right)\text{d}t}$。

若$\tilde{F}\left(x\right)$ 是对称的，则$Jg\left(x\right)=\tilde{F}\left(x\right)$ 。

命题1：[8]若对于任意初始点$x\left(t_0\right)\in R^{n^2}$ ，如果对于$\forall t\ge t_0$ ，满足条件

$\Vert x-x^{*}\Vert \le c_0\Vert x\left(t_0\right)-x^{*}\Vert \exp \left(-\eta \left(t-t_0\right)\right)$ ，

其中$c_0$ 和$\eta$ 是与初始点无关的正常数，那么该系统是全局指数稳定的。

3. 投影神经网络的构造

模型构造

用于求解半定线性互补问题(SDLCP)的投影神经网络可定义如下：

$\frac{\text{d}X}{\text{d}t}=P_{S_{+}^n}\left(X-\alpha F\left(X\right)\right)-X$ ，

其中$\alpha$ 是正常数。投影操作利用前文提及的谱分解来处理，如下所示：

$P_{S_{+}^n}\left(X-\alpha F\left(X\right)\right)={\left(X-\alpha F\left(X\right)\right)}^{+}$ 。

为便于后续对神经网络稳定性的证明与计算，我们引入以下定义：

$x=vec\left(X\right),x^{*}=vec\left(X^{*}\right)$ ，

$\tilde{F}\left(x\right)=vec\left(F\left(X\right)\right)$ ，

${\tilde{P}}_{S_{+}^n}\left(x-\alpha F\left(x\right)\right)=P_{S_{+}^n}\left(X-\alpha F\left(X\right)\right)$ 。

在这些定义下，神经网络可表示为：

$\frac{\text{d}x}{\text{d}t}={\tilde{P}}_{S_{+}^n}\left(x-\alpha F\left(x\right)\right)-x$。 (2)

4. 指数稳定性证明

定理1：设$\tilde{F}\left(x\right)$ 的雅可比矩阵对称且满足利普希茨条件。如果$\tilde{F}\left(x\right)$ 在$R^{n^2}$ 上是强单调的，那么神经网络(2)是指数稳定的。

证明：定义如下李雅普诺夫函数：

$V\left(x\right)={\displaystyle {\int }_0^1{\left(x-x^{*}\right)}^{{\rm T}}\left[G\left(x^{*}+t\left(x-x^{*}\right)\right)-G\left(x^{*}\right)\right]\text{d}t}$ ，

其中

$G\left(x\right)=x+\tilde{F}\left(x\right)$ 。

因此，可以得到

$\frac{\text{d}V\left(x\right)}{\text{d}x}=x+\alpha \tilde{F}\left(x\right)-x^{*}-\alpha \tilde{F}\left(x^{*}\right)$。

由中值定理可得

$G\left(x+t\left(x-x^{*}\right)\right)-G\left(x^{*}\right)={\displaystyle {\int }_0^{1}JG\left(x+st\left(x-x^{*}\right)\right)}\left(x-x^{*}\right)s\text{d}s$ 。

因此，我们有

$V\left(x\right)={\displaystyle {\int }_0^1{\displaystyle {\int }_0^1{\left(x-x^{*}\right)}^{{\rm T}}JG\left(x+st\left(x-x^{*}\right)\right)}}\left(x-x^{*}\right)s\text{d}s\text{d}t$ 。

因为$J\tilde{F}\left(x\right)$ 满足李普希兹条件，所以$J\tilde{F}\left(x\right)$ 在$R^{n^2}$ 上是有界的。因此存在$L>0$ ，使得$\Vert J\tilde{F}\left(x\right)\Vert \le L$ 。因此，我们有

$V\left(x\right)\le \left(1+L\right){\displaystyle {\int }_0^1{\displaystyle {\int }_0^1{\Vert x-x^{*}\Vert }^{2}s\text{d}s\text{d}t}}\le \frac{1+L}{2}{\Vert x-x^{*}\Vert }^2$ 。

根据文献[9]中的(9)，我们有

${\left[P_{S_{\text{+}}^n}\left(x-F\left(x\right)\right)-x^{*}\right]}^{{\rm T}}F\left(x^{*}\right)\ge 0$ 。 (3)

在引理2.1中，令$X=x-\alpha \tilde{F}\left(x\right)$ ，$Y=x^{*}$ ，我们有

${\left[P_{S_{+}^n}\left(x-F\left(x\right)\right)-x^{*}\right]}^{{\rm T}}\left[x-\alpha \tilde{F}\left(x\right)-{\tilde{P}}_{S_{+}^n}\left(x-F\left(x\right)\right)\right]\ge 0$ 。 (4)

由(3)和(4)可得

${\left[{\tilde{P}}_{S_{+}^n}\left(x-\alpha F\left(x\right)\right)-x^{*}\right]}^{{\rm T}}\left[-\alpha \tilde{F}\left(x\right)+\alpha \tilde{F}\left(x^{*}\right)-{\tilde{P}}_{S_{+}^n}\left(x-\alpha F\left(x\right)\right)+x\right]\ge 0$ 。

因此，

$\begin{array}{l}{\left[x-x^{*}+\alpha \tilde{F}\left(x\right)-\alpha \tilde{F}\left(x^{*}\right)\right]}^{{\rm T}}\left[{\tilde{P}}_{S_{+}^n}\left(x-\alpha F\left(x\right)\right)-x\right]\\ \le -\alpha {\left(x-x^{*}\right)}^{{\rm T}}\left[\tilde{F}\left(x\right)-\tilde{F}\left(x^{*}\right)\right]-{\Vert x-{\tilde{P}}_{S_{+}^n}\left(x-\alpha F\left(x\right)\right)\Vert }^2.\end{array}$

由$\tilde{F}\left(x\right)$ 的强单调性，我们有

$\begin{array}{c}\frac{\text{d}V\left(x\right)}{\text{d}t}=\frac{\text{d}V\left(x\right)}{\text{d}x}\frac{\text{d}x}{\text{d}t}\\ ={\left[x-x^{*}+\alpha \tilde{F}\left(x\right)-\alpha \tilde{F}\left(x^{*}\right)\right]}^{{\rm T}}\left[{\tilde{P}}_{S_{+}^n}\left(x-F\left(x\right)\right)-x\right]\\ \le -\alpha {\left(x-x^{*}\right)}^{{\rm T}}\left[\tilde{F}\left(x\right)-\tilde{F}\left(x^{*}\right)\right]-{\Vert x-{\tilde{P}}_{S_{+}^n}\left(x-F\left(x\right)\right)\Vert }^2\\ \le -\alpha {\left(x-x^{*}\right)}^{{\rm T}}\left[\tilde{F}\left(x\right)-\tilde{F}\left(x^{*}\right)\right]\\ \le -k_1{\Vert x-x^{*}\Vert }^2\\ \le -kV\left(x\right),\end{array}$

其中$k=\frac{2k_1}{1+L}$ 。进一步，

$V\left(x\right)\le V\left(x_0\right){\text{e}}^{-k\left(t-t_0\right)},\forall t\ge t_0$ 。

另一方面，

$\begin{array}{c}V\left(x\right)={\displaystyle {\int }_0^1{\displaystyle {\int }_0^1{\left(x-x^{*}\right)}^{{\rm T}}\left(I_n+\alpha J\tilde{F}\left(x+st\left(x-x^{*}\right)\right)\right)\left(x-x^{*}\right)s\text{d}s\text{d}t}}\\ \ge {\displaystyle {\int }_0^1{\displaystyle {\int }_0^1{\Vert x-x^{*}\Vert }^{2}s\text{d}s\text{d}t}}\\ =\frac{1}{2}{\Vert x-x^{*}\Vert }^2.\end{array}$

因此，我们有

${\Vert x\left(t\right)-x^{*}\Vert }^2\le \sqrt{2V\left(x_0\right)}{\text{e}}^{-k\frac{t-t_0}{2}},\forall t\ge t_0$ 。

综上所述，神经网络(2)指数稳定。

5. 数值实验

例1：在SDLCP中，取$L\left(X\right)=AX{A}^{{\rm T}}$ ，其中

$A=\left(\begin{array}{ccccc}17.25& -1.75& -1.75& -1.75& -1.75\\ -1.75& 16.25& -2& 0& 0\\ -1.75& -2& 16.25& -2& 0\\ -1.75& 0& -2& 16.25& -2\\ -1.75& 0& 0& -2& 16.25\end{array}\right)$ ，

$Q=\left(\begin{array}{ccccc}-9.25& 1.25& 1.25& 1.25& 1.25\\ 1.25& -8.25& 1.5& 0& 0\\ 1.25& 1.5& -8.25& 1.5& 0\\ 1.25& 0& 1.5& -8.25& 1.5\\ 1.25& 0& 0& 1.5& -8.25\end{array}\right)$ 。

取初始值为

$X_0=\left(\begin{array}{ccccc}0.0620& 0& 0& 0& 0\\ 0& 0.0620& 0& 0& 0\\ 0& 0& 0.0620& 0& 0\\ 0& 0& 0& 0.0620& 0\\ 0& 0& 0& 0& 0.0620\end{array}\right)$ 。

我们在MATLAB中实现了该模型，并采用ODE45方法对投影神经网络进行求解，从而模拟解轨迹的演化过程如图1所示。

Figure 1. The evolution of $x_i\left(t\right)$ over time

图1. $x_i\left(t\right)$ 随时间的轨迹图

从数值实验的图像可以看出，$x_i\left(t\right)$ 的轨迹收敛，充分证明了文章所提出的投影神经网络的有效性与可行性。

6. 总结

本文针对半定线性互补问题(SDLCP)，提出新颖的投影神经网络求解方法。先以投影算子、谱分解等为基础构建模型，再通过李雅普诺夫函数证明其在特定条件下的指数稳定性，最后经MATLAB实验验证了方法的有效性。未来可将模型拓展至非线性SDLCP，优化稳定性判定条件，结合硬件提升计算效率，还可探索其在控制理论、量子化学等领域的实际应用。

致 谢

感谢张杰老师对本论文的悉心指导。