一种求解二阶锥互补问题的神经网络方法

A Neural Network Approach for Solving Second-Order Cone Complementarity Problem

摘要: 本文提出了一种用于求解二阶锥互补问题(SOCCP)的Hopfield型神经动力学框架。通过引入单参数族的平滑价值函数，将SOCCP重构为无约束优化问题，并采用微分方程进行求解。理论分析表明，该方法能保证在适当条件下实现指数稳定性。同时数值实验验证了该方法的可行性，MATLAB仿真结果表明，该神经网络模型具有优异的稳定性和适应性。

Abstract: This paper introduces a Hopfield-type neural dynamic framework designed to address the second-order cone complementarity problem (SOCCP). By introducing a single-parametric class of smooth merit functions, the SOCCP is reformulated as an unconstrained optimization problem and solved via differential equations. Theoretical results confirm that the proposed approach guarantees exponential stability under appropriate conditions. Numerical experiments validate the feasibility of the method, demonstrating that, the neural network model exhibits super stability and adaptability in MATLAB simulations.

1. 引言

二阶锥互补问题(SOCCP)广泛存在于工程与管理科学领域的优化问题中，在结构力学系统的动态分析、振动与声学系统建模、电路仿真、流体动力学计算以及力学接触问题等多个实际工程领域展现出重要的应用价值[1]。

本文采用的神经网络的优化方法自Hopfield和Tank于20世纪80年代提出以来，因其并行处理和全局搜索能力，已成为求解复杂优化问题的重要工具。近年来，神经网络方法已在二阶锥规划、二阶锥约束变分不等式[2]、线性互补问题[3] [4]及广义垂直线性互补问题[5]中取得成功应用，显示出其在结构化优化问题中的良好适应性和求解潜力。

尽管传统方法如Fukushima等人提出的光滑化函数法[6]、张雷洪等人的Krylov子空间方法[7]、万仲平的幂罚函数法[8]、刘三阳等人的光滑牛顿法[9]以及潘少华的近端梯度下降法[10]等在SOCCP求解中取得了重大进展，为本文提供了重要理论基础，但现存这些方法仍普遍存在对初始点较敏感、计算复杂度较高、耗时较长以及难以并行实现等局限，在一定程度上限制了SOCCP在实时优化场景中的应用。因此，发展一种能够高效稳定并适用于实时计算的方法具有迫切的理论和实际意义。针对上述问题，本文提出一种神经网络动力学系统的求解框架，基于经典的Fischer-Burmeister函数，引入光滑化参数构造出连续可微的价值函数，从而避免了传统非光滑优化中复杂的次梯度计算。进一步地，通过构建相应的Hopfield型神经网络动力系统，利用其固有的并行性与全局收敛特性，以期提高解的稳定性和算法适用性，拓展SOCCP在实际工程中的应用范围。

2. 预备知识

二阶锥互补问题可以表述为：寻找$\left(x,y\right)\in R^n\times R^n$ 使得

$\langle x,y\rangle =0,x\in K,y\in K,y=F\left(x\right)$ (1)

其中$\langle \cdot ,\cdot \rangle$ 代表欧几里得内积，$F:R^n\times R^n\to R^n$ 是一个连续可微函数，且$K=K^{n_1}\times K^{n_2}\times \cdots \times K^{n_m}$ 满足$m,n_1,n_2,\cdots ,n_m\ge 1$ 和$n_1+n_2+\cdots +n_m=n$ 。

为便于在$K^n$ 中进行计算，我们引入约旦积。对给定向量$x=\left(x_1,x_2\right)\in R\times R^{n-1}$ 和$y=\left(y_1,y_2\right)\in R\times R^{n-1}$ ，其约旦积定义为

$x\circ y:=\left[\begin{array}{l}\langle x,y\rangle \\ y_1{x}_2+x_1{y}_2\end{array}\right]$ 。

对于任意向量$x=\left(x_1,x_2\right)\in R\times R^{n-1}$ ，其行列式由

$\det \left(x\right):=x_1^2-{\Vert x_2\Vert }^2$

给出。此外，对任意向量$x=\left(x_1,x_2\right)\in R\times R^{n-1}$ ，定义线性表示矩阵

$L_x:=\left[\begin{array}{cc}{x}_1& x_2^{\text{T}}\\ x_2& x_{1}I\end{array}\right]$ 。

当$L_x$ 可逆时，其逆矩阵可显式表示为[11]

$L_x^{-1}=\frac{1}{\det \left(x\right)}\left[\begin{array}{cc}{x}_1& -x_2^{\text{T}}\\ -x_2& \frac{\det \left(x\right)}{x_1}I+\frac{1}{x_1}{x}_2{x}_2^{\text{T}}\end{array}\right]$ 。(2)

定义1：[12]设$F:R^n\to R^n$ 是定义在$F:R^n\to R^n$ 上的一个函数，如果对于任意的$x,y\in R^n$ 且$x\ne y$ ，满足

$\underset{\underset{x_i\ne y_i}{i\in N}}{\max }\left(x_i-y_i\right)\left[F_i\left(x\right)-F_i\left(y\right)\right]\ge 0$ ，

则称$F$ 是$P_0$ 函数。

一阶微分方程系统可以表述为，对于给定函数$H:R^n\to R^n$ ，

$\frac{\text{d}u\left(t\right)}{\text{d}t}=H\left(u\left(t\right)\right)$ ，$u\left(t_0\right)=u_0\in R^n$ 。(3)

定义2：[13]对于(3)中的孤立平衡点$u^{*}$ ，若存在常数$w<0$ ，$\kappa >0$ 和$\delta >0$ ，使得对任意满足初始条件

$u\left(t_0\right)=u_0$ ，$\Vert u_0-u^{*}\Vert <\delta$

的解$u\left(t\right)$ 满足

$\Vert u\left(t\right)-u^{*}\Vert \le \kappa {\text{e}}^{\omega t}\Vert u_0-u^{*}\Vert$ ，

则称该平衡点$u^{*}$ 是指数稳定的。

3. 神经网络模型

本论文旨在找到一种价值函数$\psi :R^n\times R^n\to R_{+}$ 满足

$\psi \left(x,y\right)=0\iff \langle x,y\rangle =0,x\in K,y\in K,y=F\left(x\right)$ ，

使得SOCCP可以转化为一类无约束优化问题。

考虑下面单参数的函数[14]-[16]

${\psi }_{\tau }\left(x,y\right):=\frac{1}{2}{\Vert H\left(x,y\right)\Vert }^2=\frac{1}{2}{\Vert {\Phi }_{\tau }\left(x,y\right)\Vert }^2+\frac{1}{2}{\Vert F\left(x\right)-y\Vert }^2$ ，

其中${\Phi }_{\tau }\left(x,y\right)$ 是一个分量为光滑标量函数的向量函数，定义为

${\Phi }_{\tau }\left(x,y\right)=\left[\begin{array}{c}{\varphi }_{\tau }\left(x_1,y_1\right)\\ ⋮\\ {\varphi }_{\tau }\left(x_n,y_n\right)\end{array}\right]$ ，

这里${\varphi }_{\tau }\left(x_i,y_i\right):={\left[{\left(x_i-y_i\right)}^2+\tau \left(x_i\circ y_i\right)\right]}^{1/2}-\left(x_i+y_i\right)$ ，$\tau \in \left(0,4\right)$ 。

不难发现$H\ge 0$ 对于任意的$u:=\left(x,y\right)\in R^n\times R^n$ ，$u$ 是SOCCP的解当且仅当$H\left(u\right)=0$ 。所以，解决SOCCP等价于找到无约束优化问题的全局极小值，即

$\underset{u\in R^n}{\min }{\psi }_{\tau }\left(u\right)$ 。

所以，求解二阶锥互补问题的神经网络系统可定义如下：

$\{\begin{array}{l}\frac{\text{d}u}{\text{d}t}=-\lambda \nabla {\psi }_{\tau }\left(u\right),\lambda >0\\ u\left(t_0\right)=u_0\end{array}$ 。 (4)

4. 稳定性分析

命题1：[17] SOCCP的任意解都是系统(4)的平衡点。反过来，如果$\left(x,y\right)\in R^n\times R^n$ 是系统(4)的平衡点，且$F\left(x\right)$ 是一个$P_0$ 函数，则$\left(x,y\right)$ 是SOCCP的解。

为了证明指数稳定性，本文受文献[18]启发推导出有效的充分条件，并运用文献[5]中定理5.5的方法完成了该定理的证明。

命题2：如果$u^{*}=\left(x^{*},y^{*}\right)$ 对于系统(4)是一个正则解，则存在一个$u^{*}$ 的邻域$B\left(u^{*},\delta \right)$ 和一个常数$C$ ，使得对于任意的$u\in B\left(u^{*},\delta \right)$ ，$\nabla H\left(u\right)$ 是非奇异的。

定理1：如果$u^{*}=\left(x^{*},y^{*}\right)$ 是(4)中的一个正则解，则$u^{*}$ 对于系统(4)是指数稳定的。

证明：根据泰勒展开式，

$H\left(u\left(t\right)\right)=H\left(u^{*}\right)+\nabla H{\left(u\right)}^{\text{T}}\left(u-u^{*}\right)+o\left(\Vert u-u^{*}\Vert \right)$ ，$\forall u\left(t\right)\in \Omega \backslash \left\{u^{*}\right\}$ 。

令$f\left(u\left(t\right)\right)={\Vert u\left(t\right)-u^{*}\Vert }^2$ ，$t\in \left[t_0,\infty \right)$ ，

$\begin{array}{c}\frac{\text{d}f\left(u\left(t\right)\right)}{\text{d}t}=2{\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\frac{\text{d}u\left(t\right)}{\text{d}t}\\ =-2\lambda {\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\nabla {\psi }_{\tau }\left(u\left(t\right)\right)\\ =-2\lambda {\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\nabla H\left(u\left(t\right)\right)\cdot H\left(u\left(t\right)\right)\\ =-2\lambda {\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\nabla H\left(u\left(t\right)\right)\left(H\left(u^{*}\right)+\nabla H\left(u\left(t\right)\right)\left(u-u^{*}\right)+o\left(\Vert u-u^{*}\Vert \right)\right)\\ =-2\lambda {\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\nabla H\left(u\left(t\right)\right)\nabla H{\left(u\left(t\right)\right)}^{\text{T}}\left(u-u^{*}\right)+o\left({\Vert u-u^{*}\Vert }^2\right)\end{array}$ 。

由命题2可知，$\nabla H\left(u\right)$ 是非奇异的，则存在一个常数$k>0$ ，使得

${\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\nabla H\left(u\right)\nabla H{\left(u\right)}^{\text{T}}{\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\ge k{\Vert u\left(t\right)-u^{*}\Vert }^2$ 。 (5)

否则，若${\left(u\left(t\right)-u^{*}\right)}^{\text{T}}\nabla H\left(u\right)\nabla H{\left(u\right)}^{\text{T}}{\left(u\left(t\right)-u^{*}\right)}^{\text{T}}=0$ ，那么将推出$\nabla H{\left(u\left(t\right)\right)}^{\text{T}}\left(u\left(t\right)-u^{*}\right)=0$ 。由已知$\nabla H\left(u\right)$ 是非奇异的，所以$u\left(t\right)-u^{*}=0$ ，即$u\left(t\right)=u^{*}$ ，这就与$u^{*}$ 是孤立平衡点矛盾。因此，(5)成立。

对于$o\left({\Vert u\left(t\right)-u^{*}\Vert }^2\right)$ ，存在$\epsilon >0$ ，使得$o\left({\Vert u\left(t\right)-u^{*}\Vert }^2\right)\le \epsilon {\Vert u\left(t\right)-u^{*}\Vert }^2$ ，所以可得，

$\frac{\text{d}f\left(u\left(t\right)\right)}{\text{d}t}\le \left(-2\lambda k+\epsilon \right){\Vert u\left(t\right)-u^{*}\Vert }^2=\left(-2\lambda k+\epsilon \right)f\left(u\left(t\right)\right)$ ，

进而

$f\left(u\left(t\right)\right)\le {\text{e}}^{\left(-2\lambda k+\epsilon \right)t}f\left(u\left(t_0\right)\right)$ ，

$\Vert u\left(t\right)-u^{*}\Vert \le {\text{e}}^{-\lambda k+\frac{\epsilon }{2}}\Vert u\left(t_0\right)-u^{*}\Vert$ 。

得证。

5. 数值实验

例1：考虑一个定义在$K^5$ 上的线性SOCCP，函数$F$ 定义如下：

$F\left(x\right)=\left(\begin{array}{c}15x_1-5x_2-x_3+4x_4-5x_5\\ 5x_2+x_5\\ -x_1-3x_2+8x_3+2x_4-3x_5\\ 2x_1-4x_2+2x_3+9x_4-4x_5\\ -5x_2+10x_5-1\end{array}\right)$ ，$K:=K^5$ 。

例1采取本文提出的神经网络系统(4)求解，对不同的初始值进行数值仿真得到结果如表1，解轨迹图像如图1所示，其中参数取定为$\tau =0.001$ 和$\lambda =0.5$ 。

Table 1. Numerical results for example 1

表1. 例1的数值实验结果

$T$	$\tau$	$x_0$	$x^{*}$
30	10^−^3	(10^−^1, 10^−^1, 10^−^1, 10^−^1, 10^−^1)^T	(0.0246, −0.0054, 0.0298, 0.0280, 0.0956)^T
30	10^−^3	(10^−^2, 10^−^2, 10^−^2, 10^−^2, 10^−^2)^T	(0.0112, −0.0286, 0.0059, 0.0171, 0.0757)^T
30	10^−^3	(10^−^3, 10^−^3, 10^−^3, 10^−^3, 10^−^3)^T	(0.0026, −0.0449, 0.0013, 0.0042, 0.0562)^T

t

Figure 1. Solution trajectory diagram for example 1

图1. 例1的解轨迹图像

以上数值实验结果表明，采取适当的参数时，本论文提出的神经网络方法具有可行性以及解的稳定性。

致 谢

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