凸约束变分不等式的基于LQP方法的算法

凸约束变分不等式的基于LQP方法的算法 An LQP-Based Method for Solving a Class of Convex Constrained Variational Inequalities first-author 吴德运，男，硕士生，现从事最优化理论与算法方面的研究. E-mail：wudeyun@whu.edu.cn 吴德运，男，硕士生，现从事最优化理论与算法方面的研究. E-mail： wudeyun@whu.edu.cn wudeyun@whu.edu.cn corresp E-mail:cchuang@whu.edu.cn E-mail:cchuang@whu.edu.cn cchuang@whu.edu.cn 武汉大学 数学与统计学院, 湖北 武汉 430072 武汉大学 数学与统计学院, 湖北 武汉 430072 School of Mathematics and Statistics, Wuhan University, Wuhan 430072, Hubei, China School of Mathematics and Statistics, Wuhan University, Wuhan 430072, Hubei, China 利用 KKT 条件将一类凸约束变分不等式问题转化为线性约束变分不等式问题，在证明了构成函数在特定区域具有单调性的基础上，提出了一种新的基于 LQP (logrithmic-quadratic proximal)方法的算法，给出了相应算法的全局收敛性证明和数值实验结果. This paper proposes an LQP-Based(logrithmic-quadratic proximal) method for solving the equivalent linearization of convex constrained variational inequalities. The proof of global convergence and numerical experiment results of the new method is provided based on the monotonicity of composite function in a specific area. 凸约束变分不等式 凸优化 logrithmic-quadratic proximal算法 单调算子 convex constrained variational inequalities convex optimization logrithmic-quadratic proximal method monotone operators 引 言 1 定义1(单调) [ 1 1 ] 如果映射 H : D ⊆ R n 在 D 0 ⊆ D 上满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464710&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464710&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464710&type=middle 则称 H 在 D 0 上单调. 定义2(Slater约束规格) [ 2 2 ] 对于凸优化问题 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464720&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464720&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464720&type=middle 若存在 x ∈relint D ，这里relint D 是 D 的相对内部， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464929&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464929&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464929&type=middle 使得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464731&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464731&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464731&type=middle 则称优化问题满足Slater约束规格. 考虑变分不等式问题VI(Ω,F)，即求 x * ∈Ω，使 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464737&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464737&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464737&type=middle Ω={ x ∈ R n + | g( x ) ≤0}，这里F：Ω→ R n 连续单调， g( x ) =( g 1 ( x ), g 2 ( x ),…, g 3 ( x )) T ，且 g i : R n + → R 是可微凸函数. 易证 x * 是变分不等式问题 VI(Ω,F) 的解的充分必要条件是 x * 是问题 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464936&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464936&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464936&type=middle 的最优解.假设这个优化问题满足Slater条件，由约束最优性条件参考文献 [ 2 2 ] ，则必存在乘子向量 λ * ， μ * 使得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464746&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464746&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464746&type=middle 在(3)中消去 μ * ，问题归结为求互补问题 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464754&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464754&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464754&type=middle 令 ω= ( x,λ ) T , http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464940&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464940&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464940&type=middle ，问题(4)与变分不等式(5)等价. http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464761&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464761&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464761&type=middle 本文将设计算法求解变分不等式(5)，文献 [ 3 3 ] 在 G(ω) 单调并且零点存在时，通过添加一个临近正则项ω－ ω k ，将求变分不等式(5)转化为求解方程组 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464768&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464768&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464768&type=middle 其中 ξ k 是一个误差序列，满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464944&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464944&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464944&type=middle 是适当参数序列， η k ∈(0, L )这里 L > 0，它的精确形式是 ξ k =0, k =1,2,….可以证明{ ω k }最终收敛于 G(ω) 的一个零点，这个算法被称作临近点算法. 当 G(ω) 在 R n + × R m + 上零点不存在时，需要对临近点算法做一些改进，通常的做法是使用一个非线性项 φ(ω, ω k ) 替换 ω － ω k ，文献 [ 4 4 ] 中作者采用了正则项ω－ ω k + μ ( ω － Ω 2 k ω －1 ),Ω k = diag( ω k 1 , ω k 2 ,…, ω k n+m ), ω －1 =( ω －1 1 , ω －1 2 , ω －1 n+m ) T ，它是函数 f 的梯度 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464775&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464775&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464775&type=middle 这种方法被称为“对数二次临近点” (logrithmic-quadratic proximal,LQP)方法 [ 5 5 ] .若 ω k+1 是新产生的点，则必为内点.算法满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464947&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464947&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464947&type=middle 时才能收敛于变分不等式(5)的一个解，由于 ω k+1 的值在 ξ k 给定后才能计算出，因此这个条件在实际应用中难以控制.为克服这个困难，本文在“算法”部分给出上述算法的一种改进算法，并在“数值实验”部分给出验证结果. 算 法 1 文献 [ 6 6 ~ 8 8 6~8 ] 中假设向量值函数 G(ω) 各分量为单调函数，据此给出基于LQP方法的交替方向法.本文只证明了 G(ω) 在 R n + × R m + 中单调，虽不满足各分量均为单调函数，但可以参考它们对参数的处理方法，算法中用对角矩阵 R 替换 η k ，由于 R 的对角元素可以不同，比用单一 η k 更加灵活.另外我们在算法中使用了预测——校正技术 [ 9 9 , 10 10 ] ，证明了算法每一步都是可行的，并且只要初始点 ω 0 > 0，算法都将收敛于变分不等式(5)的解，下面是具体的算法. 1) 初始化：给定ε > 0,μ∈(0,+∞), ω 0 =( x 0 , λ 0 ) T > 0，令 k ：=0； 2) 预估：求解下列方程组得到解 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464949&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464949&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464949&type=middle http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464779&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464779&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464779&type=middle R,S为适当选取的正定对角矩阵， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464952&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464952&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464952&type=middle 且满足 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464784&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464784&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464784&type=middle 3) 收敛性检验：如果 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464955&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464955&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464955&type=middle 停止，否则进行下一步； 4) 校正：取θ > 0，求解下列方程组得到解 ω k+1 =((x k+1 ) T ,( λ k +1 ) T ) T http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464788&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464788&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464788&type=middle 令 k ：= k +1，返回第一步. 引理1 假设R=diag( r 1 , r 2 ,…, r n )为正定对角矩阵，向量函数 q(u) 在 R n + 上关于u单调，对于任意的μ > 0,u k =( u k 1 , u k 2 ,…, u k n ) T > 0，如果U k =diag( u k 1 , u k 2 ,…, u k n )，那么方程组 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464790&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464790&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464790&type=middle 有且仅有惟一正解 u .对于任意的 v ≥0 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464792&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464792&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464792&type=middle 证 第一个结论在文献 [ 4 4 ] 的推论2中有详细论证，这里略过证明.后面部分证明如下 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464794&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464794&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464794&type=middle 引理2 G(ω) 在 R n × R m + 上关于 ω 单调. 证 对于 ω 1 , ω 2 ∈ R n × R m + http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464796&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464796&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464796&type=middle 故 G(ω) 在 R n × R m + 上关于 ω 单调. 定理1 若 ω k > 0，则预估方程组(7)存在惟一正解 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464956&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464956&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464956&type=middle ，对于这个 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464958&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464958&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464958&type=middle ，校正方程组(8)也存在惟一正解 ω k+1 . 证 由引理 2知 G(ω) 在 R n + × R m + 上单调，应用引理 1可知，方程组(7)存在惟一正解.同理，方程组(8)是(7)的特殊情况，所以也存在惟一正解. 这样我们就证明了算法的每一步都可以惟一确定，下面我们来证明算法的收敛性. 定理2 给定 ω k > 0， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464959&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464959&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464959&type=middle 是预估方程组(7)的解， ω k+1 是校正方程组(8)的解.那么对于变分不等式(5)的解 ω * 有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464798&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464798&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464798&type=middle 这里 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464960&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464960&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464960&type=middle . 证 对于方程组(7)令 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464962&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464962&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464962&type=middle ，应用引理 1得到 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464799&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464799&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464799&type=middle 对于方程组(8)令 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464965&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464965&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464965&type=middle ，可得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464801&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464801&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464801&type=middle 由不等式组(10)可知 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464805&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464805&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464805&type=middle 因为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464970&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464970&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464970&type=middle ，由引理2得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464808&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464808&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464808&type=middle 又因为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464811&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464811&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464811&type=middle 由不等式(9)和等式(13)得到 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464816&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464816&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464816&type=middle 这里〈 x,y 〉= x T My , x , y ∈ R n .结合不等式(12)和(14)由不等式(11)得： http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464819&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464819&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464819&type=middle 令 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464975&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464975&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464975&type=middle ，则 Ψ(θ) =－ a k θ 2 +2b k θ+c k 是一个二次函数且在 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464822&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464822&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464822&type=middle 时取得最大值，下面证明Ψ( θ * )具有有限下界 定理3 给定 ω k > 0，由预估方程组(7)产生 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464977&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464977&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464977&type=middle ，则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464825&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464825&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464825&type=middle 证 应用Cauchy-Schwarz不等式得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464829&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464829&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464829&type=middle 并且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464835&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464835&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464835&type=middle 所以 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464841&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464841&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464841&type=middle 由不等式(16)和(17)得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464846&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464846&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464846&type=middle 定理4 给定 ω k > 0， ω * 是变分不等式(5)的解， ω k 是预估方程组(7)的解， ω k+1 是校正方程组(8)的解，则 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464982&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464982&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464982&type=middle 均有界且 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464849&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464849&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464849&type=middle 这里 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464852&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464852&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464852&type=middle 证 由定理2和定理 3显然有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464857&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464857&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464857&type=middle 因为 ρ > 0，因此得到 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464864&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464864&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464864&type=middle 所以序列{ ω k }有界.由不等式(19)得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464869&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464869&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464869&type=middle 因此 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464873&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464873&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464873&type=middle 又因为{ ω k }有界，所以{ http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464986&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464986&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464986&type=middle 也有界. 定理5 由算法产生的序列{ ω k }收敛于变分不等式问题(5)的一个解. 证 由定理1可知， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464993&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464993&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464993&type=middle ，令 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464997&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464997&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464997&type=middle 应用引理1得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464875&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464875&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464875&type=middle 整理上式，并应用Cauchy-Schwarz不等式得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464878&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464878&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464878&type=middle 由定理 4知， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465003&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465003&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465003&type=middle 是有限维空间中的有界序列，所以存在收敛子列，设 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464880&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464880&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464880&type=middle 是它的一个收敛子列，那么 ω ∞ ≥0，由不等式(21)可知 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464883&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464883&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464883&type=middle 因此 ω ∞ 是变分不等式(5)的一个解.又因为 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464901&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464901&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464901&type=middle 所以对于 ε > 0，分别存在 N 1 , N 2 ∈ N +使得当 k > N 1 和 k i > N 2 时分别有 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464906&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464906&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464906&type=middle 对上述ε，存在 N = N 1 + N 2 ，对于任意的k > N，令 k > k i > max{ N 1 , N 2 }并结合不等式(20)得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464909&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464909&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464909&type=middle 故{ ω k }收敛于变分不等式问题(5)的解 ω ∞ . 数值结果 1 我们接下来通过数值实验来验证算法确实是可行的. 例1 Fx =2 Ax －2 b ，其中 A ∈ R n × n 为一对称正定矩阵， b ∈ R n 为一向量，考虑变分不等式问题.求 x * ∈ Ω 使得 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464911&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464911&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464911&type=middle 为了测试上述结论的正确性，取 μ = s =0.25， θ =0.8， λ 0 =1. A =( aij ) n × n 和 R =( rij ) n × n 为对角矩阵， b 和 x 0 为 n 维列向量，它们的元素值在{1,2}中随机取得，精度 ε =1.0×10 －8 . 预估步可以使用matlab中的solve和fsolve函数求解方程组(7)，fsolve使用数值方法求解方程组，每次只能求出一组与初始值有关的解.当这组解不满足迭代条件时，可以使用solve函数求方程组(7)的解析解，solve函数使用符号运算，可以求出方程组的所有解，但是求解速度比fsolve慢.在校正步中，由于 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465009&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465009&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465009&type=middle 已知，相应方程组可以转化为二次方程组，直接求出解的显式表示， http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464913&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464913&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4464913&type=middle 这里 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465013&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465013&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465013&type=middle ， 表 1 表 1 是我们的测试结果,通过分析 表 1 表 1 我们发现实验结果与理论是相符的，第一种算法多了求数值解的步骤，在问题不是很大时，可加快求解速度.但是当问题规模比较大时，求出的解往往是不满足迭代条件的，从而增加了求解时间. 图 1 图 1 是二维情形的散点图， 图 2 图 2 是 图 1 图 1 在收敛点附近的情况.这里A=diag(2,2)，R=diag(2,1)，b=(2,2) T ， x 0 =(2,2) T .算法最终收敛于点(0.707 106 77，0.707 1067 7)，可以认为与理论上的点( http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465016&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465016&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465016&type=middle 是相符的.算例中当A为任意正定对称矩阵时，对角化后类似处理即可.文献 [ 11 11 ] 中提到了解非线性方程组(7)的一种数值解法，由于已经证明 http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465020&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465020&type=small http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4465020&type=middle ，可以令 x i = l i λ , l i > 0, i =1,2,…, n .方程组(7)中可以消去 λ ，得到关于 l i , i =1,2,…, n 的 n 元方程组.依此方法继续，最终得到一元非线性方程，可运用二分法求相应方程，得到解后做相应替换，就可得到所需的非线性方程组(7)的解.在方程组(7)的解析解不存在的情况下可以考虑使用此方法，以上算例说明我们的算法在实际应用中是可行的.本文没有考虑R在迭代过程中变化的情况，也没有与其他算法做比较，这是我们接下来要做的工作. 2 n 2 预估步求解析解或数值解 2 预估步求解析解 迭代次数 程序运行时间/s 迭代次数 程序运行时间/s 1 5 9.158807 5 39.158807 2 17 17.184336 22 84.899419 5 27 21.686879 30 121.867827 50 63 120.234096 55 178.211716 200 144 352.221893 106 308.755732 1000 275 1789.348995 227 1399.348972 参考文献 ORTEGA J M, RHEINBOLDT W C. Iterative Solution of Nonlinear Equations in Several Variables[M]. New York-London: Academic Press, 1970. BOYD S, VANDENBERGH L. Convex Optimization[M]. New York: Cambridge University Press, 2009. AUSLENDER A, TEBOULLE M. Lagrangian duality and related multiplier methods for variational inequality problems[J]. Siam Journal on Optimization, 2000, 10(4): 1097-1115. HE B S, LIAO L Z, HAN D R, et al. A new inexact alternating directions method for monotone variational inequalities[J]. Mathematical Programming, 2002, 92(1): 103-118. AUSLENDER A, TEBOULLE M, BEN-TIAB S. A logarithmic-quadratic proximal method for variational inequalities[J]. Computational Optimization&Applications, 1999, 12(1-3): 31-40. YUAN X M. The prediction-correction approach to nonlinear complementarity problems[J]. European Journal of Operational Research, 2007, 176(3): 1357-1370. YUAN X M, LI M. An LQP-based decomposition method for solving a class of variational inequalities[J]. Siam Journal on Optimization, 2011, 21(4): 1309-1318. BNOUHACHEM A, XU M H. An inexact LQP alternating direction method for solving a class of structured variational inequalities[J]. Computers&Mathematics with Applications, 2014, 67(3): 671-680. NOOR M A. Some developments in general variational inequalities[J]. Applied Mathematics&Computation, 2004, 155(1): 199- 277. FACCHINEI F, PANG J S. Finite-Dimensional Variational Inequalities and Complementarity Problems Vol. I[M]. New York: Springer-Verlag, 2003. 周亚南. 非线性代数方程组的一种数值解法[J]. 应用数学进展, 2014, 3(2): 91-97. ZHOU Y N. A numerical method for solving the nonlinear algebraic equations[J]. Advances in Applied Mathematics, 2014, 3(2): 91-97(Ch). 10.14188/j.1671-8836.2016.05.012 O 29 whdxxblxb-62-5-477 国家自然科学基金（71231007）资助项目 2015-11-03 2016-10-24 2020-12-10 版权所有 © 《武汉大学学报(理学版)》编辑部 Copyright © 2016 Journal of Wuhan University（Natural Science Edition). All rights reserved. 2016 武汉大学学报(理学版) 5 62