DOI:10.12677/aam.2024.139420,PDF,HTML,XML,被引量下载: 12浏览: 76
作者:张灵宇,张 杰,刘书宇：辽宁师范大学数学学院，辽宁 大连
关键词:垂直互补问题；投影；微分方程法；Vertical Complementarity Problem；Projection；Method of Differential Equations

文章引用：张灵宇, 张杰, 刘书宇. 求解垂直互补问题的一阶和二阶微分方程法[J]. 应用数学进展, 2024, 13(9): 4402-4416. https://doi.org/10.12677/aam.2024.139420

1. 引言

垂直互补问题(Vertical Complementarity Problem, VCP)属于互补问题的一个特殊分支。互补问题的概念起源于二十世纪中期，与线性规划和优化问题相关联，研究最初由L. Kantorovich和T.C. Koopmans关于资源分配和经济均衡研究中提出互补问题(Complementarity Problem, CP)的基本概念，而后又由G. Dantzig通过线性规划的方法进一步拓展了互补问题的应用，并在其线性规划理论中引入了互补条件。1960年代学者们[1]-[3]正式提出了线性互补问题(Linear Complementarity Problem, LCP)，并研究了其基本性质和算法，线性互补问题的形式化标志着互补问题研究的重要里程碑。1970年代随着非线性系统和非凸优化问题的深入研究，学者们开始广泛关注互补问题，包括垂直互补问题，研究重点也转向了非线性互补问题(Nonlinear Complementarity Problem, NCP)[4]。而垂直互补问题是非线性互补问题的一个特殊情况，强调的是向量函数和变量之间的互补性。Stampacchia等人在变分不等式领域的研究，特别是将变分不等式问题应用于互补问题的求解极大的推动了垂直互补问题的理论发展。变分不等式理论为处理垂直互补问题提供了新的工具和方法。变分不等式问题(Variational Inequality, VI)是一类非线性问题，最早是在研究力学中的接触问题[5][6]中被提出，并在演变后改写成变分不等式[7][8]。上世纪中后期又由Tampacchia[9]应用Lax-Milgram定理将变分不等式由Hilbert空间推广到非空闭凸子集，得到变分不等式问题的第一个解的存在且唯一的结论。

如今，垂直互补问题的理论研究主要集中在其解的存在性、唯一性和稳定性分析上。学者们利用变分不等式、非光滑分析和拓扑方法等数学工具深入探讨了垂直互补问题的基本性质。Agdeppa[10]等研究了在一定条件下求解交通均衡问题。利用变分不等式的成熟理论和算法处理垂直互补问题，不仅简化了垂直互补问题的求解，还提升了求解的效率和稳定性，将垂直互补问题的解等价于微分方程系统的平衡点，因此垂直互补问题的解收敛性等价于微分方程系统的平衡点稳定性。但学者们关于运用微分方程法求解特殊的三元极小化垂直互补问题并没有具体的方式以及准确的数值结果。本文主要是通过建立一个与垂直互补问题等价的变分不等式问题，运用投影算子建立的微分方程系统的平衡点即为垂直互补问题的解，将数值算法的收敛性问题转换为微分方程系统的平衡点稳定性的判别问题，将在学者们的研究基础上，研究此类特殊问题并给出数值结果以说明微分方程法的有效性以及此类问题下的关于垂直互补问题的微分方程法，而随着计算机算力的大幅加强，数值解以及算法的收敛性也成为了今后垂直互补问题的有意义的研究方向。

2. 垂直互补问题、变分不等式与投影算子理论基础

垂直互补问题：

找到一点 $x\in {\Re }^n$使得

$\{\begin{array}{l}f\left(x\right)\ge 0\hfill \\ x>0\hfill \\ f{\left(x\right)}^{\text{T}}x=0\hfill \end{array}$(1)

其中 $f:{\Re }^n\to {\Re }^n$是定义在实数域上的向量值函数。

Fichera-Karamardian[11][12]定理是垂直互补问题与变分不等式问题转换的基础之一，在适当条件下垂直互补问题可以转化为一个等价的变分不等式问题。通过如下步骤：

首先：定义映射F：将VCP中的函数 $f\left(x\right)$直接作为VIP中的映射 $F\left(x\right)$，即 $F\left(x\right)=f\left(x\right)$。

其次：定义凸集C：将非负正交锥 $K=\left\{x\in {\Re }^n|x\ge 0\right\}$作为VI中的凸集。

变分不等式问题 $VI\left(F,C\right)$：设C为空间 ${\Re }^n$上的非空闭凸子集， $F:C\to {\Re }^n$为非线性算子，找到一点 $x^{*}\in C$满足

$\langle F\left(x^{*}\right),y-x^{*}\rangle \ge 0,\forall y\in C.$(2)

Stampacchia[13]证明了在空间 ${\Re }^n$上的变分不等式问题空间(2)的解存在性定理。

定理1：设C为 ${\Re }^n$空间中的一个非空有界的闭凸子集，算子 $F:C\to R^n$是连续的，则存在 $x^{*}\in C$满足变分不等式(2)。

如果 $x^{*}\in C$是原问题(2)的解当且仅当有下式成立

即

$x^{*}={\Pi }_C\left(x^{*}-F\left(x^{*}\right)\right)$，

其中， ${\Pi }_C$表示集合C上的投影算子。

凸集合上的投影算子在垂直互补问题转换为变分不等式的等价交换上有着重要作用。

设C是一个闭凸集合，对任意的 $x\in {\Re }^n$，存在 $\hat{x}\in C$有 $\Vert x-\hat{x}\Vert =\min \left\{\Vert x-y\Vert |y\in C\right\}$，则点 $\hat{x}$称为点x到集合C上的投影，用 ${\Pi }_C\left(x\right)$表示，投影算子 ${\Pi }_C\left(x\right):{\Re }^n\to C$是定义在 ${\Re }^n$上的非扩张映射。

引理1：设H为Hilbert空间，且 $C\subset H$是一个闭凸集合。对于给定的 $z\in H,u\in C$满足 $\langle u-z,v-u\rangle \ge 0$， $\forall v\in C$，当且仅当 $u-{\Pi }_C\left(z\right)=0$。

微分方程系统

$\frac{\text{d}v\left(t\right)}{\text{d}t}=f\left(v\left(t\right)\right),v\left(t_0\right)=v_0\in {\Re }^n,$(3)

Zabczyk[14]给出了微分方程系统解的存在以及唯一性定理。

引理2：设 $F:{\Re }^n\to {\Re }^n$是循环单调映射且Lipschitz连续，其Lipschitz常数为L，对任意的 $v_1,v_2,v_3\in {\Re }^n$有不等式成立 $\langle F\left(v_1\right)-F\left(v_3\right),v_2-v_1\rangle \le 2L{\Vert v_3-v_2\Vert }^2$。

定理2[15]：设 $\Vert \nabla f\left(v\right)\Vert$是在 ${\Re }^n$有界。如果存在常数 $\alpha >0$和 $\tau >0$使得投影算子是非扩张的，则 $\mu \frac{\text{d}v}{\text{d}t}={\psi }_i(v^{*})$ $\left(i=1,2,3,4\right)$和 $\mu \frac{{\text{d}}^{2}v}{\text{d}{t}^2}+\beta \frac{\text{d}v}{\text{d}t}={\psi }_i(v^{*})$ $\left(i=1,2,3,4\right)$的平衡点是全局指数稳定的。

定理3[16][17]：设 $f:{\Re }^n\to {\Re }^n$是连续映射。对 $\forall t_0\ge 0$和 $v_0\in {\Re }^n$，系统(2)存在一个局部解 $v\left(t\right)$，其中 $t\in \left[t_0,\tau \right)$且 $\tau \ge t_0$；若f在 $v_0$处局部Lipschitz连续的，则上述解是唯一的；若f在 ${\Re }^n$上是Lipschitz连续的，则上述解唯一，且 $\tau$可以趋于 $\infty$。

3. 方程系统及理论证明

3.1. 一阶微分投影算子方程

本节内容将 $\min \Phi \left(v\right)=\min \left\{F\left(v\right),G\left(v\right),H\left(v\right)\right\}$转换为变分不等式问题 $VI(\Omega ,F)$求解 $v^{*}\in \Omega$使得

$\langle F(v^{*}),w-v^{*}\rangle \ge 0,\forall w\in \Omega .$(4)

其中 $F:{\Re }^n\to {\Re }^n$是循环单调映射， $\Omega \subseteq {\Re }^n$是非空闭凸集。

由引理1可以得到三元极小化垂直互补问题转换为变分不等式的问题(2)等价于 $v^{*}\in \Omega$满足等式：

${\Phi }_{\mu }(v):={\Pi }_{\Omega }(v-\alpha F(v))-v=0,$(5)

其中 $\alpha >0$且 ${\Pi }_{\Omega }(•)$为集合 $\Omega$上的投影算子。

对三元极小化垂直互补问题 $\text{min}\left\{F\left(v\right),G\left(v\right),H\left(v\right)\right\}=(\begin{array}{c}\min \left\{f_1(v),g_1(v),h_1(v)\right\}\\ \min \left\{f_2(v),g_2(v),h_2(v)\right\}\\ ⋮\\ \min \left\{f_n(v),g_n(v),h_n(v)\right\}\end{array})$基于方程(5)可以

构造一阶微分方程系统如下

$\mu \frac{\text{d}v}{\text{d}t}=(\begin{array}{c}{\Pi }_{R_{+}}\left\{h_1(v)-\min \left\{f_1(v),g_1(v)\right\}\right\}-h_1(v)\\ {\Pi }_{R_{+}}\left\{h_2(v)-\min \left\{f_2(v),g_2(v)\right\}\right\}-h_2(v)\\ ⋮\\ {\Pi }_{R_{+}}\left\{h_n(v)-\min \left\{f_n(v),g_n(v)\right\}\right\}-h_n(v)\end{array}),$(6)

下面证明一阶微分方程系统的轨迹收敛定理以及稳定性。

定理4：设垂直互补问题转换为变分不等式问题后 $\langle {\psi }_i(v^{*}),w-v^{*}\rangle \ge 0$的解集是非空的。 ${\psi }_i$是Lipschitz连续的，其中 ${\psi }_i(v^{*})={\Pi }_{R_{+}}\left\{h_i\left(v\right)-\min \left\{f_i\left(v\right),g_i\left(v\right)\right\}\right\}-h_i\left(v\right)$。常数为L。对任意的 $v_0\in {\Re }^n$，当 $0<\alpha <\frac{1}{2L}$时，一阶微分方程系统(6)的解的轨迹 $v\left(t\right)$的聚点是垂直互补问题的解。

证明：本定理以及证明解存在过程由陈星旭[18]的定理2.1启发，有以下

设原问题的解为 $v_i^{*}$，另 ${\omega }_i={\stackrel{\dot{}}{v}}_i+v_i$及在 $\langle {\stackrel{\dot{}}{v}}_i+\alpha {\psi }_i\left(v\right),{\omega }_i-{\stackrel{\dot{}}{v}}_i-v_i\rangle \ge 0$中令 ${\omega }_i=v_i^{*}$，可分别得到 $\langle {\psi }_i\left(v^{*}\right),{\stackrel{\dot{}}{v}}_i+v_i-v_i^{*}\rangle \ge 0$和 $\langle {\stackrel{\dot{}}{v}}_i+\alpha {\psi }_i\left(v_i\right),v_i^{*}-v_i-{\stackrel{\dot{}}{v}}_i\rangle \ge 0$。

经运算以及不等式性质引理2得到 $\langle {\stackrel{\dot{}}{v}}_i,v_i-v_i^{*}+{\stackrel{\dot{}}{v}}_i\rangle -2\alpha L{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\le 0$，

利用内积性质和 $\frac{\text{1}}{\text{2}}\frac{\text{d}}{\text{d}t}{\Vert v_i-v_i^{*}\Vert }^2=\langle {\stackrel{\dot{}}{v}}_i,v_i-v_i^{*}\rangle$整理后得不等式 $\frac{1}{2}\frac{\text{d}}{\text{d}t}{\Vert v_i-v_i^{*}\Vert }^2+\left(1-2\alpha L\right)\Vert {\stackrel{\dot{}}{v}}_i\Vert \le 0$。从 $t_0$到t上进行积分 $\frac{1}{2}{\Vert v_i-v_i^{*}\Vert }^2+\left(1-2\alpha L\right){\displaystyle {\int }_{t_0}^t{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\text{d}\tau }\le \frac{1}{2}{\Vert v_0-v_i^{*}\Vert }^2$其中 $v_0=v_i\left(t_0\right)$，可得 ${\Vert v_i\left(t\right)-v_i^{*}\Vert }^2\le {\Vert v_0-v_i^{*}\Vert }^2$和 ${\displaystyle {\int }_{t_0}^t{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\text{d}\tau }\le \infty$， $t\to \infty$。不等式 ${\displaystyle {\int }_{t_0}^t{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\text{d}\tau }\le \infty$， $t\to \infty$说明存在时序列 $\left\{t_j\right\}$使得 $\Vert \stackrel{\dot{}}{v}\left(t_j\right)\Vert \to 0\left(j\to \infty \right)$； $\left\{v\left(t_j\right)\right\}$也是有界的，得证解的存在性。

下证一阶微分方程解的稳定性：设 $v_i\left(t\right)=\frac{1}{2}{\Vert v_i\left(t\right)-v_i^{*}\Vert }^2$，则

${\stackrel{\dot{}}{v}}_i\left(t\right)=\langle v_i\left(t\right)-v_i^{*},{\stackrel{\dot{}}{v}}_i\left(t\right)\rangle =\langle v_i\left(t\right)-v_i^{*},-{\Pi }_{\Omega }\left(v_i\left(t\right)-\alpha F\left(v_i\left(t\right)\right)\right)\rangle ,$

由于投影算子是非扩张的，即对 $\forall x,y\in \Omega$，有

$\Vert {\Pi }_{\Omega }\left(x\right)-{\Pi }_{\Omega }\left(y\right)\Vert \le \Vert x-y\Vert .$

因此 ${\stackrel{\dot{}}{v}}_i\left(t\right)\le -\alpha {\Vert F\left(v_i\left(t\right)\right)\Vert }^2$表明 $v_i\left(t\right)$随时间递减，从而 $v_i\left(t\right)$收敛到 $v_i^{*}\left(i=1,2,3,4\right)$。

由定理2可知方程的解是稳定的。

3.2. 二阶微分投影算子方程

同样构造二阶微分方程系统如下

$\mu \frac{{\text{d}}^{2}v}{\text{d}{t}^2}+\beta \frac{\text{d}v}{\text{d}t}=(\begin{array}{c}{\Pi }_{R_{+}}\left\{h_1(v)-\min \left\{f_1(v),g_1(v)\right\}\right\}-h_1(v)\\ {\Pi }_{R_{+}}\left\{h_2(v)-\min \left\{f_2(v),g_2(v)\right\}\right\}-h_2(v)\\ ⋮\\ {\Pi }_{R_{+}}\left\{h_n(v)-\min \left\{f_n(v),g_n(v)\right\}\right\}-h_n(v)\end{array}),$(7)

其中 $\mu >0,\beta >0$是参数。由于当F是Lipschitz连续时，显然 ${\Pi }_{\Omega }$也是Lipschitz连续的。为简便，记 $\ddot{v}=\frac{{\text{d}}^{2}v}{\text{d}{t}^2}$， $\stackrel{\dot{}}{v}=\frac{\text{d}v}{\text{d}t}$。根据引理1微分方程系统可以转换为变分不等式形式

$\langle \mu {\ddot{v}}_i+\beta {\stackrel{\dot{}}{v}}_i+\alpha {\psi }_i\left(v\right),{\omega }_i-\mu {\ddot{v}}_i-\beta {\stackrel{\dot{}}{v}}_i-v_i\rangle \ge 0,\forall {\omega }_i\in \Omega .$

下面证明二阶微分方程系统(7)的轨迹收敛性定理以及稳定性。

定理5：设垂直互补问题转换为变分不等式后的解集是非空的。 ${\psi }_i$是Lipschitz连续的，其常数为L对任意的 $v_0\in {\Re }^n$，当 $0<\alpha <\frac{1}{2L}$和 $\frac{1}{2L}<\beta <\mu <K{\beta }^2$时，其中 $K=\left(1-2\alpha L\right)$，微分方程系统的轨迹 $v_i\left(t\right)$的聚点是垂直互补问题的解。

证明解存在过程同样由陈星旭[18]定理2.2启发，简写为

证明：设 $v_i^{*}$是循环单调映射变分不等式的解，令 ${\omega }_i=v_i+\mu {\ddot{v}}_i+\beta v_i$及 ${\omega }_i=v_i^{*}$，经过运算以及不等式性质引理2计算得不等式并利用内积性质和等式关系得

$\frac{1}{2}\mu \frac{{\text{d}}^2}{\text{d}{t}^2}{\Vert v_i-v_i^{*}\Vert }^2+\frac{1}{2}\beta \frac{\text{d}}{\text{d}t}{\Vert v_i-v_i^{*}\Vert }^2+\left(1-2\alpha L\right)\mu \beta \frac{\text{d}}{\text{d}t}{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2+\left(\left(1-2\alpha L\right){\beta }^2-\mu \right){\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2+\left(1-2\alpha L\right){\mu }^2{\Vert {\ddot{v}}_i\Vert }^2\le 0$

令 ${\phi }_i\left(v_i\right)=\frac{1}{2}{\Vert v_i-v_i^{*}\Vert }^2$，再对上式从 $t_0$到t积分整理后得 $\mu \frac{\text{d}}{\text{d}t}{\phi }_i\left(v_i\right)+\beta {\phi }_i\left(v_i\right)\le C_1$， $C_1=\mu {\phi }_i^1\left(v_0\right)+\beta {\phi }_i\left(v_0\right)+\left(1-2\alpha L\right)\mu \beta {\Vert {\stackrel{\dot{}}{v}}_0\Vert }^2$为常数。

求解常微分方程再积分得 ${\phi }_i\left(v_i\right)\le \frac{C_1}{\beta }+\left({\text{e}}^{\frac{\beta }{\mu }{t}_0}{\phi }_i\left(v_0\right)-\frac{C_1}{\beta }{\text{e}}^{\frac{\beta }{\mu }{t}_0}\right){\text{e}}^{\frac{\beta }{\mu }t}\le C_2$。

上式得证 ${\Vert v_i-v_i^{*}\Vert }^2$有界。

下证 ${\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2$有界。由 $\mu \frac{\text{d}}{\text{d}t}{\phi }_i\left(v_i\right)+\beta {\phi }_i\left(v\right)+\left(1-2\alpha L\right)\mu \beta {\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\le C_1$可得

$\mu \langle {\stackrel{\dot{}}{v}}_i,v_i-v_i^{*}\rangle +\frac{\beta }{2}{\Vert v_i-v_i^{*}\Vert }^2+\left(1-2\alpha L\right)\mu \beta {\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\le C_1,$

$\left[\left(1-2\alpha L\right)\mu \beta -\frac{\mu }{2}\right]{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\le C_1+\frac{1}{2}\left(\mu -\beta \right){\Vert v_i-v_i^{*}\Vert }^2,$

从而可得 $\frac{\text{d}}{\text{d}t}{\phi }_i\left(v_i\right)=\langle {\stackrel{\dot{}}{v}}_i,v_i-v_i^{*}\rangle$也是有界的。存在 $C_3$使得下式成立

$\left(1-2\alpha L\right){\mu }^2{\displaystyle {\int }_{t_0}^t{\Vert {\ddot{v}}_i\Vert }^2\text{d}\tau }+\left(\left(1-2\alpha L\right){\beta }^2-\mu \right){\displaystyle {\int }_{t_0}^t{\Vert {\stackrel{\dot{}}{v}}_i\Vert }^2\text{d}\tau }\le C_3.$

令 $t\to \infty$，则有 ${\displaystyle {\int }_{t_0}^t{\Vert \ddot{x}\Vert }^2\text{d}\tau }<\infty$， ${\displaystyle {\int }_{t_0}^t{\Vert \stackrel{\dot{}}{x}\Vert }^2\text{d}\tau }<\infty$。同样取时序列可以证明。根据致密性定理，必存在 $\left\{t_j\right\}$的子列 $\left\{t_{j_k}\right\}$使得 $x\left(t_{j_k}\right)\to x^1$， $k\to \infty$。则有 $\Vert \ddot{v}\left(t_{j_k}\right)\Vert \to 0$， $\Vert \stackrel{\dot{}}{v}\left(t_{j_k}\right)\Vert \to 0$。在二阶微分方程系统中取 $t=t_{j_k}$，令 $k\to \infty$有 ${\psi }_i\left(v_i\right)=0$。即证明完毕。

下证二阶微分方程解的稳定性：

定义Lyapunov函数为 $E_i\left(t\right)=\frac{1}{2}{\Vert {\stackrel{\dot{}}{v}}_i\left(t\right)\Vert }^2+\frac{\alpha }{2}{\Vert v_i\left(t\right)-v_i^{*}\Vert }^2$

计算其导数得

${\stackrel{\dot{}}{E}}_i\left(t\right)=\langle {\stackrel{\dot{}}{v}}_i\left(t\right),{\ddot{v}}_i\left(t\right)\rangle +\alpha \langle v_i\left(t\right)-v_i^{*},{\stackrel{\dot{}}{v}}_i\left(t\right)\rangle .$

利用二阶微分方程 ${\ddot{v}}_i\left(t\right)+\beta {\stackrel{\dot{}}{v}}_i\left(t\right)+\alpha {\Pi }_{\Omega }\left(v_i\left(t\right)-F\left(v_i\left(t\right)\right)\right)=0$得到

${\stackrel{\dot{}}{E}}_i\left(t\right)=\langle {\stackrel{\dot{}}{v}}_i\left(t\right),-\beta {\stackrel{\dot{}}{v}}_i\left(t\right)-\alpha {\Pi }_{\Omega }\left(v_i\left(t\right)-F\left(v_i\left(t\right)\right)\right)\rangle +\alpha \langle v_i(t)-v_i^{*},{\stackrel{\dot{}}{v}}_i\left(t\right)\rangle .$

由于 ${\Pi }_{\Omega }\left(v_i\left(t\right)-F\left(v_i\left(t\right)\right)\right)$是非扩张的，有 ${\stackrel{\dot{}}{E}}_i\left(t\right)\le -\beta {\Vert {\stackrel{\dot{}}{v}}_i\left(t\right)\Vert }^2$，表明Lyapunov函数随时间递减，从而 $v_i\left(t\right)$收敛到 $v_i^{*}\left(i=1,2,3,4\right)$。

由定理2同样可知方程的解是稳定的。

4. 数值实验及结论

本文用微分方程系统(6)和(7)分别求解两个三元极小化垂直互补凸优化问题。验证两个微分方程系统在不同的初始点条件下轨迹的收敛性以及稳定性。应用Matlab2019b软件进行计算，在实验求解过程中采用微分方程的求解函数ode45，其中对于三维的一阶的微分方程系统(6)中参数 $\mu =1.51$，二阶微分方程系统(7)中的参数 $\mu =1.51$， $\beta =1.52$。其中对于四维的一阶的微分方程系统(6)中参数 $\mu =1.02$，二阶微分方程系统(7)中的参数 $\mu =1.02$， $\beta =1.01$。

例1

$\text{min}\left\{F\left(v\right),G\left(v\right),H\left(v\right)\right\}=\left(\begin{array}{l}\min \left\{v_1^2\left(1+v_2^2\right)+v_3^3,v_1+v_2^3\left(1+v_3^2\right),v_1-\left(1+v_2^4\right)+v_3\right\}\\ \min \left\{v_1^2\left(1+v_2^2\right)+v_3^2,v_1\left(1+v_2^3\right)+v_3,v_1^3+\left(1+v_2^3\right)+v_3\right\}\\ \min \left\{v_1^3\left(1+v_2\right)+v_3^3,v_1+v_2\left(1+v_3\right),v_1+v_2+v_3\right\}\end{array}\right),$(8)

图1表示了三维三元极小化一阶以及二阶垂直互补微分方程系统解的轨迹的收敛性，即从随机的不同的初始点出发最终都会逐渐收敛且趋于稳定。

Figure 1.The trajectory convergence of the differential equation system (6) and (7)

图1.优化问题微分方程系统(6)和(7)的轨迹收敛性

例2

$\text{min}\left\{F\left(v\right),G\left(v\right),H\left(v\right)\right\}=(\begin{array}{c}\min \left\{v_2+3v_3,v_2{v}_4,v_1\right\}\\ \min \left\{v_3-2v_4,v_3{v}_4,v_2\right\}\\ \min \left\{v_2+v_4^2,v_1{v}_4,v_3\right\}\\ \min \left\{3v_1+v_3,v_1{v}_2,v_4\right\}\end{array}),$(9)

图2表示了四维三元极小化一阶以及二阶垂直互补微分方程系统解的轨迹的收敛性，即从随机的不同的初始点出发最终都会逐渐收敛且趋于稳定。

Figure 2.The trajectory convergence of the differential equation system (6) and (7)

图2.优化问题微分方程系统(6)和(7)的轨迹收敛性

在能源工厂以及物流管理[19]优化生产线中，需要解决最小化生产时间 $F\left(x\right)$，最小化生产成本 $G\left(x\right)$，最小化废品率 $H\left(x\right)$，利用本文的方式将三元极小化垂直互补问题转换并通过ode45进行求解，利用投影算子确保解的可行性。对于一阶微分方程系统而言，计算简单适合问题规模较大，初期探索每次迭代只需计算一阶导数，计算时间短，因此在过程中尽管移动较小，其整体收敛速度较于二阶往往更快。但如果垂直互补问题在非凸情况下极易陷入局部最优解且收敛速度较慢。而对于二阶微分方程系统而言，其过程利用了更准确的二阶导数信息，适合精细调整，步长选择更为复杂，在计算过程中步长的机械错误选择会导致收敛速度相较于一阶变慢。但二阶微分方程系统能有更好的收敛性和全局最优性质，有效避免局部最优，且对于较为复杂的多维问题具有更快地收敛速率并确保了稳定性。

在本文第一个实例中，当参数 $0<\mu <1.5$时，此时二阶微分方程系统无解，当参数 $\mu \ge 1.5$时一阶微分方程系统收敛速度要快于二阶微分方程系统。见图3~5。

在第一个实例的二阶微分方程系统中，参数 $0<\beta \le 1.5$时方程无解，取适当参数 $\mu$和一阶微分方程系统同样有解情况下， $\beta >1.5$时，二阶微分方程系统的收敛速度越来越慢。见图6、图7。

Figure 3.Example 1 of the differential equation system (6) and (7) where $\mu =1.5$

图3.例1的微分方程系统(6)和(7)其中 $\mu =1.5$

Figure 4.Example 1 of the differential equation system (6) and (7) where $\mu =2$

图4.例1的微分方程系统(6)和(7)其中 $\mu =2$

Figure 5.Example 1 of the differential equation system (6) and (7) where $\mu =4$

图5.例1的微分方程系统(6)和(7)其中 $\mu =4$

Figure 6.Example 1 of the differential equation system (7) where $\beta =2$, $\beta =2.5$

图6.例1的微分方程系统(7)其中 $\beta =2$， $\beta =2.5$

Figure 7.Example 1 of the differential equation system (7) where $\beta =3$, $\beta =5$

图7.例1的微分方程系统(7)其中 $\beta =3$， $\beta =5$

在本文第二个实例中，当参数 $\mu <1$时，方程有解但二阶微分方程系统计算速度较慢，并不能有效解决问题，在参数 $\mu \ge 1$时，二阶微分方程对应的收敛速度以及求解速度要快于一阶微分方程系统，也证明在实际更为复杂的非线性优化问题中，二阶微分方程系统更为适用。见图8~11。

在取适当参数使一阶二阶微分方程系统都有解时，对应的二阶微分方程中的参数 $\beta >0$时，随着其参数 $\beta$增大，二阶微分方程系统的收敛速度越来越快。见图12、图13。

选取不同的初始点，实验也验证其稳定性。

微分方程系统初始点分别为[0.01 0.01 0.01]、[0.01 0.01 0.01 0.01]。见图14。

微分方程系统初始点分别为[0.1 0.1 0.1]、[0.1 0.1 0.1 0.1]。见图15。

微分方程系统初始点分别为[0.5 0.5 0.5]、[0.5 0.5 0.5 0.5]。见图16。

微分方程系统初始点分别为[1 1 1]、[1 1 1 1]。见图17。

Figure 8.Example 2 of the differential equation system (6) and (7) where $\mu =1$

图8.例2的微分方程系统(6)和(7)其中 $\mu =1$

Figure 9.Example 2 of the differential equation system (6) and (7) where $\mu =1.5$

图9.例2的微分方程系统(6)和(7)其中 $\mu =1.5$

Figure 10.Example 2 of the differential equation system (6) and (7) where $\mu =2$

图10.例2的微分方程系统(6)和(7)其中 $\mu =2$

Figure 11.Example 2 of the differential equation system (6) and (7) where $\mu =3$

图11.例2的微分方程系统(6)和(7)其中 $\mu =3$

Figure 12.Example 2 of the differential equation system (7) where $\beta =0.5$, $\beta =1.5$

图12.例2的微分方程系统(7)其中 $\beta =0.5$， $\beta =1.5$

Figure 13.Example 2 of the differential equation system (7) where $\beta =3$, $\beta =5$

图13.例2的微分方程系统(7)其中 $\beta =3$， $\beta =5$

Figure 14.Examples 1 and 2 of the first- and second-order differential equation systems

图14.例1与例2的一阶与二阶微分方程系统

Figure 15.Examples 1 and 2 of the first- and second-order differential equation systems

图15.例1与例2的一阶与二阶微分方程系统

Figure 16.Examples 1 and 2 of the first- and second-order differential equation systems

图16.例1与例2的一阶与二阶微分方程系统

Figure 17.Examples 1 and 2 of the first- and second-order differential equation systems

图17.例1与例2的一阶与二阶微分方程系统

垂直互补问题作为运筹学领域中基本问题之一，本文关注的是在非线性问题中的特殊情况，将垂直互补问题转换为求解变分不等式，在建立微分方程系统的基础上，只需运用投影算子方程系统并证明系统解的轨迹收敛并通过构造函数，从微分方程系统本身以及变分不等式所涉及的函数性质以及特点就可以直接得到轨迹的聚点是垂直互补问题的解且解是稳定的。

致 谢

本论文的完成离不开许多人的支持和帮助，再次我想向所有在我研究期间给予指导、建议和支持的人表达衷心的感谢。首先由衷的感谢我的导师张杰教授对本论文的指导，在研究过程中提供了宝贵的建议和支持，他严谨的治学态度和深厚的专业知识使我受益匪浅。其次感谢学长侯彬、学姐杨妍娇和同学刘书宇在讨论和查询资料过程中提供的建议和帮助，对本论文的完成起了重要的作用。我还要感谢家人在攻读研究生期间给予的爱和支持，没有他们我无法顺利完成本篇论文。最后我要感谢所有在论文写作期间给予帮助和鼓励的同学，谢谢他们的支持与鼓励。

参考文献

[1]	Fichera, G. (1964) Problemi elastostatici con vincoli unilaterali: iI problema di Signorini con ambigu condizion al contorno. Memorie della Accademia Nazionale dei Lincei, Serie VIII, Vol. 7.
[2]	Hartman, P. and Stampacchia, G. (1966) On Some Non-Linear Elliptic Differential-Functional Equations.Acta Mathematica, 115, 271-310. https://doi.org/10.1007/bf02392210
[3]	Lions, J.L. and Stampacchia, G. (1967) Variational Inequalities.Communications on Pure and Applied Mathematics, 20, 493-519. https://doi.org/10.1002/cpa.3160200302
[4]	Cottle, R.W. (2008) Linear Complementarity Problem. In: Floudas, C. and Pardalos, P., Eds.,Encyclopedia of Optimization, Springer, 1873-1878. https://doi.org/10.1007/978-0-387-74759-0_333
[5]	Cottle, R.W., Pang, J. and Stone, R.E. (2009) The Linear Complementarity Problem. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898719000
[6]	Signorini, A. (1933) Sopra alcune questioni di elastostatica. Atti Soc. Ital. per il progressodelle Science.
[7]	Antipin, A.S. (2003) Minimization of Convex Functions on Convex Sets by Means of Differential Equations.Differential Equations, 30, 1365-1375.
[8]	Antipin, A.S. (2003) Feedback-Controlled Saddle Gradient Processes.Automation Remote Control, 55, 311-320.
[9]	Mancino, O.G. and Stampacchia, G. (1972) Convex Programming and Variational Inequalities.Journal of Optimization Theory and Applications, 9, 3-23. https://doi.org/10.1007/bf00932801
[10]	Agdeppa, R.P., Yamashita, N. and Fukushima, M. (2007) The Traffic Equilibrium Problem with Nonadditive Costs and Its Monotone Mixed Complementarity Problem Formulation.Transportation Research Part B: Methodological, 41, 862-874. https://doi.org/10.1016/j.trb.2007.04.008
[11]	Fichera, G. (1964) Problemi al contorno con dati discontinui: Le equazioni ellittico-lineari. In: Fichera, G., Ed.,Lezionisulletrasformazionilineari, Annali di Matematica Pura ed Applicata, 72-123.
[12]	Karamardian, S. (1972) The Complementarity Problem.Mathematical Programming, 2, 107-129. https://doi.org/10.1007/bf01584538
[13]	Stampacchia, G. (1964) Formes bilineaires ccoercitives surles ensembles convexes.ComptesRendusAcademieSciences Paris, 258, 4413-4416.
[14]	Zabczy, J. (2008) Mathematical Control Theory: An Introduction. Birkhauser.
[15]	Cheng, L., Hou, Z.-G. and Tan, M. (2008) A Neutral-Type Delayed Projection Neural Network for Solving Nonlinear Variational Inequalities.IEEE Transactions on Circuits and Systems II:Express Briefs, 55, 806-810. https://doi.org/10.1109/tcsii.2008.922472
[16]	Antipin, A.S. (2000) Solving Variational Inequalities with Coupling Constraints with the Use of Differential Equations.Differential Equations, 36, 1587-1596. https://doi.org/10.1007/bf02757358
[17]	Gwinner, J. (2007) On Differential Variational Inequalities and Projected Dynamical Systems-Equivalence and a Stability Result.Discrete and Continuous Dynamical Systems, 2007, 467-476.
[18]	陈星旭. 变分不等式问题的微分方程方法的研究[D]: [硕士学位论文]. 沈阳: 沈阳航空航天大学, 2022.
[19]	郑国华, 秦海斌. 基于变分不等式的物流服务网络业务分配均衡问题研究[J]. 工业技术经济, 2018, 37(9): 45-52.