沈阳航空航天大学学报

沈阳航空航天大学学报 >

2023 , Vol. 40 >Issue 5: 90 - 96

DOI: https://doi.org/10.3969/j.issn.2095-1248.2023.05.012

基础科学和工程

带扰动项的二阶微分方程方法求解变分不等式问题

  • 贾丹娜 , 1 ,
  • 王莉 , 1 ,
  • 孙菊贺 1 ,
  • 庄慧婷 1 ,
  • 袁艳红
展开
  • 1. 沈阳航空航天大学 理学院，沈阳 110136
  • 2. 太原理工大学 经济管理学院，太原 030024

贾丹娜(1999-),女,河北保定人,硕士研究生,主要研究方向:运筹学与控制论,E-mail:

王莉(1978-),女,辽宁葫芦岛人,副教授,博士,主要研究方向:运筹学与控制论,E-mail: 。

收稿日期: 2023-04-10

  网络出版日期: 2023-12-22

基金资助

国家自然科学基金(11901422)

收起

The second⁃order differential equation method with perturbation terms for solving variational inequality problem

  • Danna WANG Li JIA , 1 ,
  • Juhe SUN , 1 ,
  • Huiting ZHUANG 1 ,
  • Yanhong YUAN 1
Expand
  • 1. College of Science，Shenyang Aerospace University，Shenyang 110136，China
  • 2. College of;Economic and Management，Taiyuan University of Technology，Taiyuan 030024，China

Received date: 2023-04-10

  Online published: 2023-12-22

Fold

摘要

利用带扰动项的二阶微分方程方法求解变分不等式问题，并讨论其解的收敛性和收敛速度。首先，通过对原始变分不等式问题所对应的Karush⁃Kuhn⁃Tucker（KKT）条件进行等价转换后，借助光滑化的互补函数，等价转化成求解光滑方程组 S ε , x , μ , λ = 0，进一步等价于求解一个无约束优化问题；其次，建立带扰动项的二阶微分方程系统来求解最终的无约束优化问题，并在一定的约束条件下，得到了该二阶微分方程系统的解稳定性及收敛速度，即得到了所求的变分不等式问题的收敛性和解的收敛速度；最后，给出数值实验说明所提出的微分方程方法求解变分不等式的有效性。

关键词： 变分不等式; 二阶微分方程; 扰动项; Karush⁃Kuhn⁃Tucker条件; 稳定性

本文引用格式

贾丹娜 , 王莉 , 孙菊贺 , 庄慧婷 , 袁艳红 . 带扰动项的二阶微分方程方法求解变分不等式问题[J]. 沈阳航空航天大学学报, 2023 , 40(5) : 90 -96 . DOI: 10.3969/j.issn.2095-1248.2023.05.012

Abstract

The second-order differential equations with perturbation terms to solve variational inequality problem were focused on and discussed the convergence of its solution and the speed of the convergence. Firstly，the Karush-Kuhn-Tucker （KKT） conditions of the original variational inequality problem were equivalently transformed into a system of smoothing equations by using a smoothing complementary function，and it was furtherly equivalent to an unconstrained optimization problem. Secondly，a system of second-order differential equations with perturbation terms was established to solve the final unconstrained optimization problem and discuss the stability of the differential equation system and the speed of convergence under the certain conditions. The convergence and the speed of the convergence for the solution to the original variational inequality problem was discussed. Finally，numerical experiments were given to show the effectiveness of the differential equation method for solving the variational inequality problem.

Key words： variational inequality; second-order differential equation; perturbation term; Karush-Kuhn-Tucker conditions; stability

作为最优化理论与算法的重要研究分支之一，变分不等式广泛应用于物理、工程、经济、 交通、互补问题和控制问题等诸多领域，其中研究一般变分不等式问题的算法主要包括投影算法、内点算法、半光滑牛顿算法、光滑化牛顿算法、神经网络算法等。
本文将考虑下面的变分不等式，求解 x * ∈ C满足
F x * , y - x * ≥ 0， ∀ y ∈ C
式中：约束集合 C表示为
C = x ∈ R n | h x = 0 , - g x ≥ 0，
⋅ , ⋅表示欧式空间的内积，且 h : R n → R l和 g : R n → R m都是连续可微的， R n表示为 n维实向量空间。
变分不等式问题（1）的KKT条件为
L x , μ , λ = 0 h x = 0 g x ⊥ λ
式中： L x , μ , λ是变分不等式问题（1）的Lagrange函数，具体形式为
L x , μ , λ = F x + J h x T μ + J g x T λ
且 μ ∈ R l和 λ ∈ R m是拉格朗日乘子。
本文将运用微分方程法求解变分不等式问题（1），该问题最早由Arrow等［1］提出，主要用微分方程来研究最优性条件中的约束规范问题。微分方程方法的思想是将最优化问题转化为微分方程系统，从而对最优化问题的求解就等价于讨论微分方程平衡点的存在问题；对最优化问题的解的收敛性分析就转化为该微分方程系统平衡点的稳定性分析。
近年来，变分不等式问题的微分方程方法受到许多学者的关注。自1980年起，一系列基于微分方程系统的人工网络方法陆续被Hopfield［2］和Tank等［3］提出，并用来求解互补问题和变分不等式问题。2000年，Antipin［4］重点介绍用微分方程系统求解变分不等式问题；He等［5］根据投影算子和压缩方法，提出了非对称线性变分不等式问题的微分方程系统。2005年Gao等［6］根据投影算子理论提出可求解带有线性和非线性约束的变分不等式的微分方程模型。2010年，Sun等［7］将神经网络方法应用于求解二阶锥约束变分不等式问题，提出了两种神经网络模型。2011年，王莉［8］进一步解决了具有循环单调映射的变分不等式的微分方程方法。Attouch等［9-11］又提出了用二阶微分方程系统来解决凸优化问题。
受上述研究工作的启发，本文在Attouch用二阶微分方程系统解决凸优化思想的启发下，构造一个带扰动项的二阶微分方程系统求解经典的变分不等式问题（1）。借助光滑的互补函数，将变分不等式问题（1）的KKT条件转化为光滑的方程组问题，并引入价值函数将其转化为无约束优化问题，使得所建立的带扰动项的二阶微分方程系统的平衡点等价于变分不等式（1）的解，并讨论该微分方程系统的稳定性，从而得到原变分不等式（1）的解的收敛性质。

1 预备知识

为了完成变分不等式问题的KKT条件与光滑方程组问题之间的转化，运用互补函数对其进行光滑化。所谓互补函数是指对于 φ : R m × R m → R m，满足 φ ( a , b ) = 0当且仅当 a ⊥ b成立。本文将运用式（3）的光滑化互补函数［12］
φ N R ε ( x , y ) = x - ϕ ( ε , x - y )，
式中：对于 ( ε , x - y ) ∈ R + × R m，关于函数 ϕ : R + × R m → R m有：
ϕ ( ε , x - y ) = 1 2 x - y + ε 2 e + ( x - y ) 2 ，
其中 e表示 R m的单位向量。
从而，变分不等式（1）的KKT条件（2）等价于
S ε , x , μ , = ε L x , μ , λ h x φ N R ε - g x , λ = 0
φ N R ε - g x , λ = φ N R ε - g m 1 x , λ m 1 φ N R ε - g m 2 x , λ m 2 ⋮ φ N R ε - g m p x , λ m p = 0
式中： g m i , λ m i ∈ R m i及 ∑ i = 1 p m i = m。
接下来，引入价值函数 Φ ε , x , μ , λ ［13］
Φ ε , x , μ , λ = 1 2 S T ε , x , μ , λ S ε , x , μ , λ = 1 2 S ε , x , μ , λ 2
从以上分析可见，变分不等式（1）的KKT条件（2）等价于以下无约束优化问题
m i n Φ ε , x , μ , λ = m i n 1 2 S ε , x , μ , λ 2
令 z = ε , x , μ , λ ∈ R × R n × R l × R m，则上述无约束优化问题可以简化成为
m i n Φ z = m i n 1 2 S z 2

2 带扰动项的二阶微分方程系统

本节将要讨论运用带扰动项的二阶微分方程系统来求解变分不等式（1）的方法。
为求解变分不等式（1），建立二阶微分方程系统，与 Attouch等的研究［9］相似，对于最终转化成的无约束优化问题（6），建立一个与无约束优化问题（6）相关联的带系统外部扰动项 g t的二阶微分方程系统，具体如式（7）所示 ε ¨ t x ¨ t μ ¨ t λ ¨ t + γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t + β t ∇ ε S z T S z ∇ x S z T S z ∇ μ S z T S z ∇ λ S z T S z =
g t
式中： γ t表示为阻尼惯性系数； β t为时间缩放参数，且 γ 、 β在 t 0 , + ∞上是非负连续函数； g t视为对系统的外部作用，称为扰动控制项。
由文献［9］可知该系统的解是存在的，并且系统对应的平衡点是变分不等式（1）的解。当系统外部扰动项 g t满足一定条件时，基于对阻尼惯性系数 γ t和时间缩放参数 β t的调整，将分析该带扰动项的二阶微分方程系统解轨迹的全局收敛性。
首先，在初始情形 Φ ε , x , μ , λ = 0且 g t = 0的情况下，对二阶微分方程系统（7）直接积分，可以得到
p t = e ∫ t 0 t γ u d u
假设其满足以下条件
H 0 : ∫ t 0 + ∞ d u p u < + ∞
在 H 0条件下，定义函数 Γ : t 0 , + ∞如式（8）所示
Γ t = p t ∫ t + ∞ d u p u
通过对式（8）进行求导，可以得到
Γ ˙ t = γ t Γ t - 1
最后，定义全局能量函数
W t = 1 2 ε ˙ t x ˙ t μ ˙ t λ ˙ t 2 + β t Φ ε t , x t ,
μ t , λ t - m i n Φ
以及锚函数
h t = 1 2 ε t x t μ t λ t - ε * x * μ * λ * 2
其中， ε * x * μ * λ * ∈ a r g m i n Φ，解集 a r g m i n Φ非空。全局能量函数 W t和锚函数 h t是用于稳定性分析的能量函数 ξ : t 0 , + ∞的基本组成部分，且 ξ t是一个非负函数，定义如式（12）所示
ξ t = Γ t 2 W t + h t + Γ t h ˙ t
即
ξ t =
Γ t 2 β t Φ ε t , x t , μ t , λ t - m i n Φ + 1 2 ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t 2
定理1 假设 Φ : R → R是一个凸函数，且解集 a r g m i n Φ非空。时间缩放参数 β : t 0 , + ∞和阻尼惯性系数 γ : t 0 , + ∞均是连续的函数，并且满足假设条件 H 0及下面的增长条件
H γ , β : Γ t β ˙ t ≤ β t 3 - 2 γ t Γ t
而扰动控制项 g : t 0 , + ∞是局部可积的，且满足
H g : ∫ t 0 + ∞ Γ t g t d t < + ∞
则带扰动项的微分方程系统（7）的轨迹 ε t x t μ t λ t和 Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t在 t 0 , + ∞上是有界的，并且当 t → + ∞时的收敛速率为：
Φ ε t , x t , μ t , λ t - m i n Φ = O 1 β t Γ t 2
证明：为方便计算，记 m = m i n Φ。
首先，根据式（12），对能量函数 ξ t进行求导，可以得到
ξ ˙ t = 2 Γ t Γ ˙ t β t + Γ t 2 β ˙ t ⋅ Φ ε t , x t , μ t , λ t - m +
Γ t 2 β t ∇ Φ ε t x t μ t λ t T , ε ˙ t x ˙ t μ ˙ t λ ˙ t +
d d t ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t ,                   ( 15 ) ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t = 2 Γ t Γ ˙ t β t + Γ t 2 β ˙ t ⋅                               ( 16 ) Φ ε t , x t , μ t , λ t - m + Γ t g t , ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t - Γ t β t ∇ Φ ε t x t μ t λ t T , ε t x t μ t λ t - ε * x * μ * λ *
根据柯西不等式以及函数 Φ的凸性，可以推断出以下不等式
ξ ˙ t ≤ 2 Γ t Γ ˙ t β t + Γ t 2 β ˙ t . Φ ε t , x t , μ t , λ t - m +
Γ t g t ⋅ ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t
进而有
ξ ˙ t ≤ Γ t g t ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t
≤ 2 Γ t g t ξ t 通过对上述不等式进行积分，并结合假设条件 H g，有式（18）关系成立。
ξ t ≤ ξ t 0 + 1 2 ∫ t 0 + ∞ Γ s g s d s = C t e < + ∞
显然，根据不等式（18），能够得到能量函数 ξ t是有界的，结合 ξ t的定义（12），可以得到作为 ξ t的基本组成部分之一的 ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t 2也是有界的，则有
ε t x t μ t λ t - ε * x * μ * λ * 2 + 2 Γ t ε t x t μ t λ t - ε * x * μ * λ * , ε ˙ t x ˙ t μ ˙ t λ ˙ t ≤ C
结合锚函数的定义（11），可知
h ˙ t = ε t x t μ t λ t - ε * x * μ * λ * , ε ˙ t x ˙ t μ ˙ t λ ˙ t，
从而不等式（18）等价于
h t + Γ t h ˙ t ≤ 1 2 C
对上述不等式积分可以得到解轨迹是有界的。
结合 ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t 2的有界性，可以推断出 Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t在 t 0 , + ∞也是有界的。
最后由不等式（18），已知能量函数 ξ t是有界的，并且 ξ t ≤ ξ t 0在 t , t 0上是成立的。最终根据 ξ t的定义（12），对于任意的 t ≥ t 0，都有
Φ ε t , x t , μ t , λ t - m i n Φ ≤ ξ t 0 β t Γ t 2 ,
即为
Φ ε t , x t , μ t , λ t - m i n Φ = O 1 β t Γ t 2
定理1 得证。
同时，为了实现解快速收敛到0，在定理1的增长条件 H γ , β中加入了参数 ρ，即有
H γ , β + : Γ t β ˙ t ≤ β t 3 - ρ - 2 γ t Γ t
式中： ρ > 0。
定理2 假设函数 g : t 0 , + ∞是局部可积且满足假设条件 H g，当带扰动项的微分方程系统的任意解满足假设条件 H γ , β +，可以推断得出
∫ t 0 + ∞ β t Γ t Φ ( ε ( t ) , x ( t ) , μ ( t ) , λ ( t ) ) - m i n Φ d t < + ∞
证明：由定理1，已知 ξ t是有界的，则作为 ξ t的基本组成部分之一的 ε t x t μ t λ t - ε * x * μ * λ * + Γ t ε ˙ t x ˙ t μ ˙ t λ ˙ t 2也是有界的，并结合不等式（17），则有 ∃ C > 0使得
ξ ˙ t ≤ 2 Γ t Γ ˙ t β t + Γ t 2 β ˙ t
Φ ε t , x t , μ t , λ t - m + C Γ t g t
在 t 0 , + ∞上对上述不等式进行积分，结合假设条件 H γ , β +可以得到以下不等式条件
∫ t 0 + ∞ β t Γ t Φ ε t , x t , μ t , λ t - m d t ≤
1 ρ ξ t 0 + C ∫ t 0 + ∞ Γ t g t d t < + ∞
定理2得证。

3 数值实验

本节讨论数值实验结果，将通过两个算例来证明带扰动项的二阶微分方程系统求解变分不等式问题的有效性，程序由MATLAB编写并在普通PC机上运行。算法中的相关参数取为 γ t = α t， β t ≡ 1， g t ≤ 0.02为有界扰动，其中 α = 25。
例1 研究一个非线性变分不等式问题［14］，设
F x = 2 x 1 + 0.2 x 1 3 - 0.5 x 2 + 0.1 x 3 - 4 - 0.5 x 1 + x 2 + 0.1 x 2 3 + 0.5 0.5 x 1 - 0.2 x 2 + 2 x 3 - 0.5，
C = x ∈ R 3 x 1 2 + 0.4 x 2 2 + 0.6 x 3 2 - 1 ≤ 0
该问题具有唯一最优解 x * = 1,0 , 0 T。带扰动的二阶微分方程系统（7）解的收敛轨迹如图1所示。图2为基于一个随机初始点的 x t - x *的收敛轨迹。仿真结果显示带扰动的二阶微分方程系统（7）的解的轨迹总是收敛到原问题的最优解。
图1 例1中带扰动项的二阶微分方程系统的解 x t的收敛轨迹
图2 例1中带扰动项的二阶微分方程系统的 x t - x *的收敛轨迹
例2 考虑（1）中的一个非线性约束变分不等式问题［6］
F x = 2 x 1 + 2 x 2 + 0.004 x 1 3 - 8 2 x 2 + x 3 + 0.007 x 2 3 - 6 2 x 1 + x 3 + 0.005 x 3 3 - 4 ,
约束集合 C = x ∈ R 3 g x ≤ 0，其中 g x = - x 1 + x 2 + x 3 2 - 2 + x 1 2 - x 2，且该问题有唯一最优解 x * = 1.0834,0.8261,0.5071 T。图3为带扰动的二阶微分方程系统（7）的解 x t的收敛轨迹，图4为从随机初始点出发的 x t - x *的收敛轨迹。
图3 例2中带扰动项的二阶微分方程系统的解 x t的收敛轨迹
图4 例2中带扰动项的二阶微分方程系统的 x t - x *的收敛轨迹

4 结论

本文借助光滑互补函数和价值函数，将变分不等式问题的KKT条件转化为无约束优化问题，并构造了一个带扰动项的二阶微分方程系统求解转化后的无约束优化问题，从而求解了原变分不等式问题。本文基于微分方程系统的稳定性理论，通过对阻尼惯性系数 γ t和时间缩放参数 β t的调整，且在扰动控制项 g t满足假设条件 H g的情况下，证明了带扰动项的二阶微分方程系统的解的全局收敛性，并通过数值算例验证了该微分方程系统的平衡点能够收敛到原始变分不等式问题的最优解且不依赖于初始点的选择。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
1
Arrow K J， Hurwicz L.Reduction of constrained maxima to saddle-point problems［M］// Traces and Emergence of Nonlinear Programming.Basel：Birkhäuser，2014：61-80

2
Hopfield J J.Neurons with graded response have collective computational properties like those of two⁃state neurons［J］.Proceedings of the National Acade my of Sciences，1984，81（10）：3088-3092.

3
Tank D， Hopfield J.Simple neural optimization networks： an a/d converter，signal decision circuit，and a linear programming circuit［J］.IEEE Transactions on circuits and systems 1986，33（5）：533-541.

4
Antipin A.S.Solving variational inequalities with coupling constraints with the use of differential equations［J］.Differential Equations，2000，36（11）：1587-1596.

5
He B S， Yang H.A neural network model for monotone linear asymmetric variational inequalities［J］.IEEE Transactions on Neural Networds，2000，11（1）：3-16.

6
Gao X B， Liao L Z， Qi L.A novel neural network for variational inequalities with linear and nonlinear constraints［J］.IEEE Transactions on Neural Networks，2005，16（6）：1305-1317.

7
Sun J H， Chen J S， Ko C H.Neural networks for solving second⁃order cone constrained variational inequality problem［J］.Compu tational Optimization and Applications，2012，51（2）：623-648.

8
王莉.变分不等式的微分方程方法与增广Lagrange 方法［D］.大连：大连理工大学，2011.

9
Attouch H， Chbani Z， Riahi H.Fast convex optimization via time scaling of damped inertial gradient dynamics［J/OL］.Mathematics.（2019-05-24）［2021-03-03］.

10
Attouch H， Cabot A.Asymptotic stabilization of inertial gradient dynamics with time⁃dependent viscosity［J］.Journal of Differential Equations，2017，263（9）：5412-5458.

11
Attouch H， Chbani Z， Peypouquet J，et al.Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity［J］.Mathematical Programming，2018，168（1）：123-175.

12
Sun J H， Fu W C， Alcantara J H，et al.A Neural Network Based on the Metric Projector for Solving SOCCVI Problem［J］.IEEE Transactions on Neural Networks and Learning Systems，2021，32（7）：2886-2900.

13
孙菊贺.锥约束变分不等式问题的数值方法的研究［D］.大连：大连理工大学，2008.

14
Fukushima M.A relaxed projection method for variational inequalities［J］.Mathematical Programming，1986，35（1）：58-70.

15
Sun J H， Zhang L W.A globally convergent method based on fischer-burmeister operators for solving second-order cone constrained variational inequality problems［J］.Computers & Mathematics with Applications，2009，58（10）：1936-1946.

Options
文章导航

/

〈 〉

网站版权 © 《沈阳航空航天大学学报》编辑部
地址：沈阳市沈北新区道义南大街37号沈阳航空航天大学学报编辑部　
邮编：110136
电话：024-89723779　
传真：024-89723779　
E-mail：shxbok@163.com
本系统由北京玛格泰克科技发展有限公司设计开发