变分不等式的几类求解方法

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 　　收稿: 1997206203. 修回: 1997210220. 国家自然科学基金 (19801009)和广西区自然科学基金 (9811023)资助项目. 高校应用数学学报 第14卷A 辑第2期 A pp l. M ath. —JCU V o l114 Ser. A N o. 2 变分不等式的几类求解方法 简金宝 (西安交通大学理学院; 广西大学理学院) 　 赖炎连 (中国科学院应用数学研究所) 　　摘　要　本文较为系统地分析和概述了变分不等式问题中几类占有重要地位 的求解方法, 包括方法产生的背景, 主要结果及应用等. 这几类算法分别为连续算 法, (拟)牛顿型算法, 一般迭代模型, 投影算法, 投影收缩算法等. 关键词　变分不等式, 最优化问题, 求解方法, 连续算法, (拟) 牛顿算法, 投影 算法. 分类号　 (中图) O 22112; (1991M R ) 90C33, 65K10, 65H 10. §1　引　言 变分不等式问题 (V IP) 是应用数学中一个十分重要的研究领域, 这不仅仅是由于V IP 在非线性最优化中具有相当广泛的应用, 而且在微分方程、力学、控制论、对策论、经济平衡 理论、社会和经济模型等许多方面都有着重要的应用. 有兴趣的读者可参阅文献[ 1～ 3 ]. 关 于V IP, 大致可分为理论和算法两大研究方向, 理论方面的研究焦点集中于V IP 解的存在 性、唯一性等. 而算法方面主要是研究如何引进和借助于各种技术、概念和思想等以建立各 种类型的V IP 的具体求解方法. 近几年来,V IP 进一步受到广泛和高度的重视, 引起许多学者, 尤其是国外学者浓厚的 研究兴趣, 无论是理论研究还是算法研究都取得了长足的进展. 仅就算法方面来看, 研究不 仅十分活跃, 优秀成果也很丰富[ 4～ 38 ]. 例如, 连续算法[ 4～ 9 ], (拟)牛顿型算法[ 39～ 43 ], 投影算法[ 13, 15, 19～ 29 ], 投影收缩算法[ 18, 31～ 37 ]等, 它们都是V IP 具有重要意义和代 性的求解方法. 国内关于V IP 的研究, 目前除部分学者发表了一些较有价值的研究成果外, 与其它方 向相比却相对簿弱. 为了让更多的学者对V IP 的研究动态和最近有代表性的研究成果有一 个比较系统深入的了解, 从而吸引更多的有志者投身于这一具有重要意义和广阔前景的研 究领域, 本文结合作者近期关于V IP 的一些研究工作, 将所搜集到的较新颖和优秀的方法 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 和思想进行分析、归类、整理, 比较系统地概述了连续算法, 迭代法的一般模型, (拟) 牛顿型 算法, 投影算法, 投影收缩算法等几类算法产生的背景、基本思想、主要结果等. 文中最后探 讨性地提出V IP 算法一些新的研究方向, 以供有志于V IP 研究的读者和学者参考. 受篇幅 和资料所限, 本文没能更多地介绍国内外其它学者关于V IP 的研究成果, 深表遗憾. §2　概念、V IP 与最优化和互补问题的关系 首先给出V IP 的一些常用概念, 分析V IP 的一些背景、应用, 阐述V IP 与最优化和互 补问题之间的关系. 设X 为 n 维欧氏空间 Rn 中的非空子集, F (x ) 为 Rn 到 Rn 的向量值函 数. 定义211　称在 X 中求得一点 x 3 使以下不等式 (211) 成立的问题为变分不等式问题 (V IP) , X 称为V IP (X , F )的可行集, V IP (X , F )　　F (x 3 ) T (x - x3 ) ≥ 0, Π x ∈X . (2. 1) 　　定义212　 (1) 称 F (x )为X 上的单调函数, 如果 (F (x 1) - F (x 2) ) T (x 1 - x 2) ≥ 0, 　Π x 1, x 2 ∈X . (2. 2) 又如对任意 x 1, x 2∈X , x 1≠x 2, 不等式 (2. 2)严格成立, 称 F (x )为 X 上的严格单调函数. (2) 称 F (x )为 X 上 (以 Α为模数)的强 (或一致)单调函数, 如存在常数 Α> 0使得 (F (x 1) - F (x 2) ) T (x 1 - x 2) ≥ Αúx 1 - x 2ú 2, 　Π x 1, x 2 ∈X . (2. 3) 　　定义213　 (1) 称 F (x )在X 上为 (以 c 为模数)上强制的 (coercive) , 如存在常数 c> 0使 得 (F (x 1) - F (x 2) ) T (x 1 - x 2) ≥ cúF (x 1) - F (x 2) ú 2, 　Π x 1, x 2 ∈X . (2. 4) 　　 (2) 称 F (x )在 X 上为 ∆2上强制的 (∆2coercive) , 如存在常数 ∆> 0, c> 0使得 (F (x 1) - F (x 2) ) T (x 1 - x 2) ≥ cúF (x 1) - F (x 2) ú 2, 　Π x 1, x 2 ∈X , úx 1 - x 2ú ≤ ∆. (2. 5) 　　定义214　称 F (x )在X 上为L ip sch itz 函数, 如存在常数L > 0使得úF (x 1) - F (x 2) ú ≤L úx 1 - x 2ú , 　Π x 1, x 2 ∈X . (2. 6) 　　定义215　设 X 为 Rn 的非空闭凸集, G 为 n 阶正定阵, u∈Rn , 记ú uú = (uT u ) 12 , ú uúG = (uTGu) 1 2 , 如 u3 满足: u3 ∈X , úu3 - uúG= m in{úx - uúG ûx∈X }, 则称 u3 为向量 u 关于模úuúG 在 X 上的投影, 记为 u3 = P X G (u) ; P X (u)表示向量 u 在 X 上的投影. 定义216　设 x3 为V IP (X , F ) 的解, 如 x3 满足以下条件 (a) 和 (b) , 则称 x 3 为V IP (X , F )的正则解. (a) 存在 x3 的一个邻域N 及常数 ∆> 0, 使得对于每一个满足úyú< ∆的 y , 摄动线性变 分不等式V IP (X , F y)在N 中有唯一解 x (y) , 其中 F y (x ) = F (x 3 ) + y + ∃F (x3 ) (x - x 3 ) ; 　　 (b) 解函数 x (y)关于变量 y 是L ip sch itz 连续的, 即存在常数L > 0使得úx (y) - x (z) ú ≤L úy - zú , 　Π y , z: úyú < ∆, úzú < ∆. 　　以上概念可查阅文献[ 2, 4, 25, 44 ], 它们的关系是 891 高 校 应 用 数 学 学 报 第14卷A 辑 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 定理217　 (1) 如 F (x )为强单调和L ip sch itz 函数, 则 F (x )为上强制的. (2) 如 X 为凸集, 则 F (x )为上强制的当且仅当 F (x )为 ∆2上强制的 (见[ 25 ]引理213). (3) 强单调函数必是严格单调函数, 严格单调函数必是单调函数, 上强制函数必是单调 函数. (4) 如 X 为紧集, 则 F (X )为强单调的当且仅当 F (X )为严格单调的. 定理218　如 F (x )连续可微, 记 F (x )的 Jacob i 矩阵为 ∃F (x ) T , 则 (1) F (x )在 X 上严格单调的充要条件为 ∃F (x )为正定阵 (Π x∈X ). ( 2) F (x ) 在 X 上强单调的充要条件为{ ∃F (x ) , x∈X }一致正定, 即存在 a> 0使得: dT ∃ F (x ) d≥aúdú 2, Π x∈X , Π d∈Rn. 定义219　称寻找点 x ∈Rn 使得以下 (217)式成立的问题为非线性互补问题 (N CP) N CP (F )　　x ≥ 0, F (x ) ≥ 0, F (x ) T x = 0. (2. 7) 　　关于V IP (X , F )与N CP (F )和非线性方程组的关系, 我们有 定理2110 [2, 4 ]　 (1) 如 X 为 Rn 中开集, 则V IP (X , F )等价于非线性方程组 F (x ) = 0. (2) 如 X = Rn+ ÷= {x∈Rnûx≥0}, 则V IP (X , F )等价于N CP (F ). 在许多实际应用问题中,V IP (X , F )的可行集X 为闭凸集, 且具有以下结构形式 X = X 0 ÷= {x ∈ Rnûg (x ) ≥ 0, h (x ) = 0}, (2. 8) 　　其中 g (x ) = (g 1 (x ) , ⋯, gm (x ) ) T , h (x ) = (hm + 1 (x ) , ⋯, hm + r (x ) ) T , g i (x ) : Rn→R1, i∈I÷= {1, ⋯, m }, 为连续可微凹函数, h j (x ) = a Tj x - b j: Rn→R1, j∈J ÷= {m + 1, ⋯, m + r}为线 性函数, 即 h (x )为仿射线性函数. 关于V IP (X , F )和非线性规划 (N P)之间的关系, 有 定理 2111 [2, 4, 5 ]　 (1) 如 F (x )为某个实值函数 f (x ) : Rn→R1 的梯度 ∃f (x ) , 则V IP (X , F )等价于非线性规划m in{f (x ) û x∈X }的平稳条件; 进一步, 如 f (x ) 是伪凸 (pesudo2con2 vex)函数, X 为凸集, 则V IP (X , F )的每一个解都是该非线性规划的整体最优解. (2) 当可行集 X 取 X 0, 且满足某种约束规格时, 如线性无关, 则V IP (X 0, F ) 等价于以 下 KKT 条件, 即混合线性互补问题N CP: F (x ) - ∃g (x ) y - ∃h (x ) z = 0. (2. 9) g i (x ) ≥ 0, y i ≥ 0, y ig i (x ) = 0, 　i ∈ I; h j (x ) = 0, j ∈ J . (2. 10) 其中 ∃g (x ) = ( ∃g i (x ) , i∈I ) , ∃h (x ) = ( ∃h j (x ) , j∈J ) ; 特别当 F (x ) = ∃f (x ) 时, (219)～ (2110)为非线性规划N P (X 0, f ) : m in {f (x ) û x∈X 0}的 KKT 条件, 即V IP (X 0, F ) 等价于 N P (X 0, f )的 KKT 条件. 通常称满足 (219)～ (2110)的点为V IP (X , F )的 KKT 点. 定理2111较好地刻划了V IP 和N P 之间的内在联系, 即V IP 虽然在许多不同分支里有 着十分广泛的应用, 但它也只能反映N P 的一个侧面. 作为本节的结束, 给出关于V IP (X , F )解的存在性和唯一性的一个结果, 这方面比较全面的结果可参考[ 2 ]. 定理2112 [2, 5 ] 　如 X 为 Rn 中的非空闭凸集, F (x ) 在 X 上是连续和强单调的, 则 V IP (X , F ) 有唯一解. 991第 2 期 简金宝等: 变分不等式的几类求解方法 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net §3　V IP (X 0, F )的连续算法 本节主要介绍研究和求解V IP (X 0, F ) 的一种有效方法——连续型算法, 包括方法的基 本思想和近期主要成果. 所谓连续方法 (con t inuat ion m ethods) 是研究某类问题 P 与其含有 某种参变量 Ε的摄动问题 P (Ε) 之间的关系, 其中 P= P (0). 连续方法的研究很丰富, 例 如, 基于原始问题 P 的信息, 分别就 Ε充分大和充分小分析摄动问题 P (Ε) 的性质; 探索和研 究通过序列摄动问题 P (Ε) 的求解获得原问题 P 的解的有效求解方法, 等等. 在此我们主要 介绍后一方面的几个较有意义的新近研究成果, 且设可行集X 取形如 (218)的 X 0. 由定理2111之 (2) 知, 在一定的约束规格下, V IP (X 0, F ) 与 (219)～ (2110) (N CP) 等价, 因此我们完全从 (219)及 (2110)入手研究和建立V IP (X 0, F )的连续算法. 311　单调 V IP 非可行点的连续算法 I[4 ] 我们知道 (219)～ (2110) 求解的一个困难是非负性和线性互补性及 (219) 的 Jacob ian 阵的奇异性. 为此在 F (x ) 为单调函数的假设下, [ 4 ]考虑N CP 的如下形式的序列摄动问题 PV IP (X 0, F , Ε, Λ) : F (x ) + Ε1x - ∃g (x ) y - ∃h (x ) z = 0, (3. 1) g i (x ) + Ε2y i > 0, 　y i > 0, 　y i (g i (x ) + Ε2y i) = Λ, i ∈ I; h j (x ) + Ε3z j = 0, j ∈ J , (3. 2) 其中参变量 Ε= (Ε1, Ε2, Ε3) > 0, Λ> 0. 通过求解以 y i 为变量的二次方程 y i (g i (x ) + Ε2y i) = Λ, 并注意到严格非负性, 得到 2Ε2y i + g i (x ) + g 2i (x ) + 4Ε2Λ = 0, 　i ∈ I. 　　定理311 [4 ]　 (1) (x ΕΛ, y ΕΛ, z ΕΛ) 为 PV IP (X 0, F , Ε, Λ) 的解当且仅当它是以下非线性方程 组 (313)～ (314)的解, 记该方程组为 J (x , y , z; Ε, Λ) = 0: F (x ) + Ε1x - ∃g (x ) y - ∃h (x ) z = 0, (3. 3) 2Ε2y i + g i (x ) + g 2i (x ) + 4Ε2Λ = 0, i ∈ I; h j (x ) + Ε3z j = 0, 　j ∈ J . (3. 4) 　　 (2) 设 F (x )为单调函数, 则对任意参数 Ε> 0, Λ> 0及任意 (x , y , z) ∈Rn×Rm+ ×Rr, 函数 J (x , y , z; Ε, Λ)的 Jacob ian 阵 ( ∃J (x , y , z; Ε, Λ) ) T 均是非奇异的. 以方程组 J (x , y , z; Ε, Λ) = 0为基础形成求解V IP (X 0, F )的连续算法 I: 步骤01 给定终止准则 :> 0及单调下降趋于零的严格正的摄动参数列{Εk1, Εk2, Εk3, Λk }, k = 0, 1, 2, ⋯, 任选初始点w 0= (x 0, y0, z0)∈Rn×Rm ×Rr. 令 k= 0, 进入步骤1. 步骤11 以w k = (x k , yk , zk ) 为初始点, 求方程组 J (x , y , z; Εk , Λk ) = 0的 (近似) 解w k+ 1 = (x k+ 1, y k+ 1, zk+ 1). 步骤21 如误差函数值 err (w k+ 1) < :, 停, 否则令 k ÷= k + 1, 转回步骤 1. 误差函数 err (w ) 可根据 (219) , (2110)构造, 方法很多, 可参考[ 4 ]. 由 (312)易见, 相应的迭代点 x k 一般不落在V IP (X 0, F ) 的可行集 X 0 内, 因而近似解满 足不了某些实际问题对可行性的严格要求, 故称之为非可行点 (外点)连续算法. 关于算法É 002 高 校 应 用 数 学 学 报 第14卷A 辑 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 的主要结果如下. 定理 312　设 F (x )为单调函数, 则 (1) 对任意的 Ε> 0, Λ> 0, PV IP (X 0, F , Ε, Λ) , 即方程组 J (x , y , z; Ε, Λ) = 0, 有唯一解. (2) 算法É 产生的序列{w k }的每一个极限点都是 PV I(X 0, F )的解. (3) 如算法É 的摄动参数序列{Εk1, Εk2, Εk3, Λk }满足: lim k→∞ Εk2Εk1 = c2 > 0, limk→∞ Εk3Εk1 = c3 > 0, limk→∞ ΛkΕk1 = c > 0. 则算法É 产生的序列{w k }有界当且仅当V IP (X 0, F )有解. 不难发现, 算法É 引进摄动参数有两个目的, 一是要将非负性及互补条件转化为方程组 (利用 Ε2, Λ) , 二是保证 Jacob ian 阵 ( ∃J (x , y , z; Ε, Λ) ) T 非奇异及 (313)～ (314) 解的存在. 另 外, Kanzow (1994)也对非可行点连续算法进行研究, 有兴趣的读者可参阅[ 5 ]. 312　强单调 V IP 可行点的连续算法Ê [6 ] 假设 F (x ) 为强单调和 J = Á (不考虑等式约束) , x3 是V IP (X 0, F ) 的唯一解 (由定理 2112) , 并设可行集 X 0在 x 3 处满足线性无关条件. 从而N CP 有唯一解 (x3 , y3 ). 文[ 6 ]中引 入N CP 的如下只含一个参数 Λ> 0的摄动变分不等式问题 PV IP (X 0, F , Λ) : F (x ) - ∃g (x ) y = 0; g i (x ) - z i = 0, i ∈ I. (3. 5) y i ≥ 0, z i ≥ 0; y iz i = Λ, i ∈ I. (3. 6) 　　文[ 6 ]主要借助于以下关系式将 (316)转换为等价的非线性方程组. a ≥ 0, b ≥ 0, ab = Λ Ζ ΥΛ(a , b) ÷= a + b - (a - b) 2 + 4Λ = 0. (3. 7) 　　定理 313　任意 Λ> 0, (x , y , z) 为 PV IP (X 0, F , Λ) 的解当且仅当 (x , y , z) 为以下方程组 (318)的解 F Υ(x , y , z; Λ) ÷= F (x ) - ∃g (x ) yg (x ) - zΥΛ (y , z) = 0. (3. 8) 其中 ΥΛ (y , z) ÷= (ΥΛ(y i, z i) , i∈I ). 以方程组 F Υ(x , y , z; Λ) = 0 为基础形成V IP (X 0, F )的连续算法Ê : 步骤 01 选定单调下降严格正的趋于零的摄动参数列{Λk }, 任选初始点w 0= (x 0, y0, z0) ∈Rn×Rm ×Rm. 令 k = 0, 进入步骤 1. 步骤 11 如 F Υ(w k; 0) = 0, 停, w k 为V IP (X 0, F )的解. 步骤 21 求方程组 F Υ(x , y , z; Λk+ 1) = 0 的 (近似) 解w k+ 1= (x k+ 1, yk+ 1, zk+ 1). 令 k ÷= k + 1, 转回步骤 1. 由 (315) , (316)知, g i (x k ) = z ki > 0, i∈I. 故{x k }< X 0, 算法Ê 属于可行点 (内点) 类方法. 与算法É 相比, 由于 F (x )为强单调, 这使得引进的参数简单, 另外它们在将非负性和互补条 件转化为等价方程组的技术处理上也不尽相同, 算法É [4 ]形成的方程组要比算法Ê [6 ]简单. 有关算法Ê 的主要结果是 定理 314　设 F (x )为强单调函数, Λ> 0. 则 102第 2 期 简金宝等: 变分不等式的几类求解方法 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 　　 (1) 对任意的w = (x , y , z) ∈Rn×Rm+ ×Rm , F Υ(w; Λ) 的 Jacob ian 阵 ∃F Υ(w; Λ) 都是非奇 异的. (2) PV IP (X 0, F , Λ) , 即方程组 F Υ(x , y , z; Λ) = 0, 有唯一解. ( 3) 算法Ê 产生的序列{x k , yk }, {x k }分别收敛于N CP 和V IP (X 0, F ) 的解 (x3 , y3 ) 和 x 3 . 313　单调 V IP 可行点的连续算法Ë [7 ] 借助文[ 4 ]的摄动技巧和[ 6 ]内点法思想, [ 7 ]进一步将算法Ê 推广到一般单调V IP. 文 [ 7 ]引入N CP 的含两个参数的摄动变分不等式 PV IP (X 0, F , Ε, Λ) : F (x ) + Εx - ∃g (x ) y = 0, g i (x ) - z i = 0, i ∈ I. (3. 9) y i ≥ 0, z i ≥ 0, y iz i = Λ, i ∈ I. (3. 10) 利用 (317)同样有 定理315　任意 Ε≥0, Λ≥0, (x , y , z) 为 PV IP (X 0, F ) 的解当且仅当 (x , y , z) 为以下方程 组 (3. 11)的解5 (w; Ε, Λ) ÷= 5 (x , y , z; Ε, Λ) ÷= F (x ) + Εx - ∃g (x ) yg (x ) - zΥΛ(y , z) = 0. (3. 11) 　　以方程组 (3111)为基础, 给出求解V IP (X 0, F )的连续算法Ë : 步骤 01 选定单调下降严格正的趋于零的摄动参数列{Εk , Λk }, 任选初始点w 0= (x 0, y 0, z 0)∈Rn×Rm ×Rm. 令 k= 0, 进入步骤 1. 步骤 11 如 5 (w k; 0, 0) = 0, 停, w k 为V IP (X 0, F )的解. 步骤 21 求方程组 5 (w; Εk+ 1, Λk+ 1) = 0 的 (近似) 解w k+ 1= (x k+ 1, yk+ 1, zk+ 1). 令 k ÷= k + 1, 转回步骤 1. 由 (319) , (3110) 知, g i (x k ) = z ki > 0, i∈I. 故 (x k ) < X 0, 算法Ë 仍属于可行点类方法. 有 关算法Ë 的主要结果是 定理 316 (1) 假设V IP (X 0, F ) 有解 x3 , 且在 x3 处线性无关条件和强二阶充分条件成 立. 则对任意 Λ> 0 和充分小的 Ε> 0, PV IP (X 0, F , Ε, Λ) 有唯一解w (Ε, Λ) ÷= (x (Ε, Λ) , y (Ε,Λ) , z (Ε, Λ) ) , 并且当 (Ε, Λ) → (0, 0) 时, {x (Ε, Λ) }和{w (Ε, Λ) }分别收敛于V IP (X 0, F ) 和N CP 的 (唯一)解 x 3 和w 3 = (x 3 , y3 , z3 = g (x 3 ) ). (2) 如V IP (X 0, F )有解 x 3 , 且对任意 x∈X 0, 线性无关条件成立. 则对任意 (Ε, Λ) > 0, PV IP (X 0, F , Ε, Λ) 有唯一解; 又如存在 Α> 0 使得 Λk≤ΑΕk (k 充分大) , 则算法Ë 产生的点列 {w k }至少存在一个聚点, 而且每一个聚点wδ= (xδ, yδ, zδ= g (xδ) ) 都是V IP (X 0, F ) 的 KKT 点, 相应的 xδ为V IP (X 0, F )的解. 314　强单调 V IP 的可行点与非可行点组合的连续算法Ì [8 ] 由以上分析可见, 算法É , Ê 分别在可行集X 0 的外部和内部迭代. 最近[ 8 ]通过放宽对 摄动参数的要求, 研究强单调V IP 的迭代既可在 X 0 内部进行, 也可在 X 0 外部进行的组合 式的连续算法, 在一定程度上将 [ 4, 6 ]的算法统一处理. 假设 J = Á , 文 [ 8 ]考虑N CP, 即 202 高 校 应 用 数 学 学 报 第14卷A 辑 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net V IP (X 0, F ) 的 KKT 条件 (219)～ (2110)如下形式的 PV IP (X 0, F , Ε, Λ) : g i (x ) + Εy i > 0, y i > 0, (g i (x ) + Εy i) y i = Λ, i ∈ I. (3. 12) F (x ) - ∃g (x ) y = 0. (3. 13) 　　文[ 8 ]全文仅要求摄动参数 Ε≥0, Λ> 0. 对 (3112) 的等式作适当的变形和运算, 或借助 (317) , 可知 (3112)等价于 (1 + Ε) y i + g i (x ) - 4Λ + ( (1 - Ε) y i - g i (x ) ) 2 = 0, i ∈ I. (3. 14) 　　定理317　设 F (x )为强单调的, 则对任意 Ε≥0, Λ> 0 (1) (x , y)为 PV IP (X 0, F , Ε, Λ) 的解当且仅当 (x , y ) 为方程组 (3113)～ (3114) 的解. 记 该方程组为 7 (x , y; Ε, Λ) = 0 (2) 对任意 (x , y )∈Rn×Rm+ , 7 (x , y; Ε, Λ)的 Jacob ian 阵 ( ∃7 (x , y; Ε, Λ) ) T 是非奇异的. 以方程组 7 (x , y; Ε, Λ) = 0为基础, 可建立组合型的连续算法Ì [8 ]: 步骤01 给定终止准则 :> 0, 任意选取满足以下条件的摄动参数序列{Εk , Λk }:Εk ≥ 0, lim k→∞ Εk = 0; 　Λk > 0, lim k→∞ Λk = 0. 任选初始点w 0= (x 0, y0)∈Rn×Rm. 令 k= 0, 进入步骤1. 步骤11 以w k = (x k , yk ) 为初始点, 求方程组 7 (x , y; Εk , Λk ) = 0的 (近似) 解w k+ 1= (x k+ 1, yk+ 1). 步骤21 如误差函数值 err (w k+ 1) < :, 停; 否则令 k ÷= k+ 1, 转回步骤 1. 显然, Εk = 0 时, x k+ 1∈X 0; Εk > 0 时, x k+ 1一般不属于X 0, 且此时算法Ì 与É 仍有区别. 因 此算法Ì 是可行点与非可行点两类连续算法的有机组合. 有关算法Ì 的主要结果是 定理 318　假设 F (x )为强单调的, 线性无关条件在V IP (X 0, F ) 的解 x3 处成立, Ε≥0, Λ > 0, 则 (1) PV IP (X 0, F , Ε, Λ)有唯一解, 且解关于 Λ连续. ( 2) 算法Ì 产生的点列{w k }和{x k }分别整列收敛于V IP (X 0, F ) 的 KKT 点 (即N CP 的 解)和V IP (X 0, F )的 (唯一)解. 315　单调 V IP 的可行点与非可行点组合的连续算法Í [9 ] 在文[ 9 ]中, 借助文[ 8, 4 ]的处理技巧, 进一步将算法Ì 推广到一般单调V IP, 即 F (x ) 为 单调函数. 我们将N CP 摄动成如下 PV IP (X 0, F , Ε, Λ) : F (x ) + Ε1x - ∃g (x ) y - ∃h (x ) z = 0. (3. 15) g i (x ) + Ε2y i > 0, y i > 0, y i (g i (x ) + Ε2y i) = Λ, 　i ∈ I; h j (x ) + Ε3z j = 0, j ∈ J . (3. 16) 其中摄动参数 Ε= (Ε1, Ε2, Ε3) , (Ε1, Λ) > 0, (Ε2, Ε3)≥0. 定理319　假设 (Ε1, Λ) > 0, (Ε2, Ε3)≥0, F (x )是单调的. 则 (1) (x , y , z)为 PV IP (X 0, F , Ε, Λ)的解当且仅当 (x , y , z)是以下方程组 (3117)的解 302第 2 期 简金宝等: 变分不等式的几类求解方法 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net # (x , y , z; Ε, Λ) ÷= F (x ) + Ε1x - ∃g (x ) y - ∃h (x ) z(1 + Ε2) y i + g i (x ) - 4Λ + ( (1 - Ε2) y i - g i (x ) ) 2 , i ∈ I h j (x ) + Ε2z j , j ∈ J = 0. (3. 17) 　　 (2) 对任意 (x , y , z)∈Rn×Rm+ ×Rr, # (x , y , z; Ε, Λ)的 Jacob ian 矩阵是非奇异的. 算法Í : 步骤 01 给定终止准则 :> 0, 任意选取满足以下条件的摄动参数序列{Εk = (Εk1, Εk2, Εk3) }, {Λk }: {Εk1, Λk} > (0, 0) , (Εk2, Εk3) ≥ (0, 0) ; lim k→∞ (Εk , Λk ) = 0. 任选初始点w 0= (x 0, y0, z0)∈Rn×Rm ×Rr. 令 k = 0, 进入步骤 1. 步骤 11 以w k = (x k , y k , zk )为初始点, 求方程组 # (x , y , z; Εk+ 1, Λk+ 1) = 0 的 (近似)解w k+ 1 = (x k+ 1, y k+ 1, zk+ 1). 步骤 21 如误差函数值 err (w k+ 1) < :, 停; 否则令 k ÷= k+ 1, 转回步骤 1. 由 (3116)可知, 当 Εk2= Εk3= 0 时, x k∈X 0, 否则 x k | X 0. 故算法Í 是单调V IP 的可行点与 非可行点两类连续算法的统一, 在一定程度上是[ 4, 8 ]算法的系统化. 有关算法Í 的主要结 果是 定理 3110　假设 F (x )是单调的, (Ε1, Λ) > 0, (Ε2, Ε3)≥0. 则 (1) PV IP (X 0, F , Ε, Λ) , 即方程组 # (x , y , z; Ε, Λ) = 0, 有唯一解. (2) 算法Í 产生的点列{w k }有界当且仅当V IP (X 0, F ) 有解, 且{w k }的每一聚点wδ= (xδ, yδ, zδ)都是V IP (X 0, F )的 KKT 点, 即为N CP 的解. 作为本节的结束, 我们将连续算法É —Í 的思想统一为两个层次, 第一层是将N CP 摄 动为 (3115)～ (3116) 组成的一般含参问题 PV IP (X 0, F , Ε, Λ) , 参数 Ε≥0, Λ> 0, Ε的选取依 赖于函数 F (x ) 的单调性. 第二层是将 (3116) 转化为等价的方程组. 当 Ε2, Ε3 取不同的值时, 产生内点法、外点法、组合型各种连续算法. §4　迭代方法、(拟)牛顿型算法和投影算法 迭代方法或称为数值方法, 是研究V IP 求解方法的又一有力工具, 其中投影法、线性逼 近法、(拟) 牛顿法、松弛法等都是比较有效的方法. 本节主要介绍V IP 迭代法的一般模型、 (拟)牛顿算法和投影法近期的部分研究成果. 411　迭代法的一般模型 求解V IP 的迭代法研究较早, 成果也很丰富, 较详细的资料可查阅[ 10～ 18 ]. [ 16 ]用一 个较为一般的模型概括了V IP 的迭代法, 并统一处理了整体收敛性. 大多数迭代法的基本 思想是构造各种形式的具体映射 g (x , y) : X ×X →Rn , g (x , y)满足最基本的条件: ( i) g (x , y)连续且 g (x , x ) = F (x ) , Π x∈X . V IP (X , F )迭代法的一般模型É [16 ]: 步骤 01 任选初始点 x 0∈X , 充分小的终止精度 Ε> 0, k = 0. 402 高 校 应 用 数 学 学 报 第14卷A 辑 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 步骤 11 求解以下变分不等式 (411)的解 x k+ 1 x k+ 1 ∈X , g (x k+ 1, x k ) T (x - x k+ 1) ≥ 0, Π x ∈X . (4. 1) 　　步骤 21 如‖x k+ 1- x k‖≤Ε, 停1; 否则令 k ÷= k+ 1, 转步骤 1. 　　1原文没有终止准则, 此终止准则为本文加入. 　　由以上模型可见, 迭代法的每一轮迭代仍然依赖于一个变分不等式 (411) 的求解, 但对 绝大多数可行集X , (411)的求解往往要比原V IP (X , F )容易得多, 如采用投影方法等, 这正 是迭代法的重要思想和成功之处. 另一方面, 由基本条件 (i) 和 (411) 不难发现, 如迭代点列 {x k }有聚点 x3 , 而整个点列不收敛时, 一般很难保证 x 3 为V IP (X , F )的解, 因此分析收敛性 时, 需对函数 g (x , y)作一些假设, 以使{x k }为Cauchy 序列. 模型É 有以下收敛性结果. 定理 411　假设 g (x , y )满足条件 ( i)和以下 ( ii)～ ( iii) , ( ii) X 为紧凸集, g (x , y)可微, 且对任意 (x , y)∈X ×X , g (x , y)关于 x 的 Jacob ian 矩阵 ∃ x g (x , y)是对称正定的. ( iii) 记û‖·û‖为 Rn 中欧氏模下矩阵的标准算子模, 假设û‖ ( ∃x g (x 1, y 1) ) - 12 ∃y g (x 2, y 2) ( ∃x g (x 3, y 3) ) - 12 û‖ < 1. (4. 2) 则模型É 产生的点列{x k }为 Cauchy 序列, 即{x k }收敛. 此时由 (411) 立即可知{x k }收敛于 V IP (X , F )的解. 模型É 的收敛速度一般说来比较慢, [ 17 ]采用加速步的方法改进模型É , 提出V IP (X , F )迭代法的另一个一般模型Ê [17 ]: 步骤 0, 1 同模型É , 但将 (411)的解记为 xζk. 步骤 21 如‖xζk - x k‖≤Ε, 停. 否则当 k 为偶数或零时, 进入步骤 3; 当 k 为奇数时, 令 x k+ 1 = xζk , k ÷= k+ 1, 转步骤 1; 步骤 31 求下列一维变分不等式问题的解 Α3 ∈[ 0, 1 ], F ( (1 - Α) x k + Αxζk ) T (xζk - x k ) (Α- Α3 ) ≥ 0, Π Α∈ [ 0, 1 ]. 令 x k+ 1= (1- Α3 ) x k + Α3 xζk , k ÷= k + 1, 转步骤 1. 定理 412　除定理 411 的条件 ( i)～ ( iii)外, 再设以下条件 ( iv)成立, ( iv) û‖ ( ∃x g (x 1, y1) ) - 12 [ ∃x g (x 2, y 2) - ∃x g (x 3, y 3) ] ( ∃x g (x 4, y 4) ) - 12 û‖< ∞, Π x i, y i ∈X . 则模型Ê 产生的点列{x k }整列收敛于V IP (X , F )的解. 模型É , Ê 是两类相当一般的迭代法框架, 当 g (x , y )取适当形式时, 许多现有的方法都 可看作其特例. 最近[ 38 ]将V IP 转化为等价的序列最优化问题, 然后借助于这些序列优化问题再次研 究单调V IP 下降算法的一般框架, 进一步推广了模型É , Ê 的结果. 412　迭代法的线性模型与 (拟)牛顿型算法 迭代模型中, 映射 g (x , y ) 一种较为简单的形式是取函数 F 在当前迭代点 x k 处的某种 近似的线性逼近, 即 g (x , y) = F (y) + A (y ) (x - y) , g (x , x k ) = F (x k ) + A (x k ) (x - x k ). (4. 3) 502第 2 期 简金宝等: 变分不等式的几类求解方法 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 由于 g (x , x k )是 x 的仿射线性函数, 称之为迭代法的线性模型, 其中A (x k ) 为 n 阶矩阵. 当 A (x k )取各种形式时, 形成不同的V IP 求解方法. (1) A (x k ) = ∃F (x k ) , 形成求解V IP 的牛顿算法; (2) A (x k )≈ ∃F (x k ) , 形成求解V IP 的拟牛顿算法; (3) A (x k ) = 12 [ ∃ F (x k ) + ∃F (x k ) T ], 形成求解V IP 的对称牛顿算法; V IP 牛顿型算法是求解V IP 的一类相当重要的方法, 因为它有二阶 (二次) 收敛速度, 这方面的结果有 定理413[39 ] (局部收敛) 　设X 为非空闭凸集, F 为一阶连续可微函数,V IP (X , F ) 有正 则解 x3 . 则存在 x3 的某个邻域N 使得, 当初始迭代点 x 0∈N 时, V IP 的N ew ton 法产生的 点列{x k }有定义, 且lim k→∞ x k = x 3 ; 此外, 如 ∃F (x3 )在 x3 附近是L ip sch itz 连续的, 则 x k 的收敛 速度是二阶 (二次)的, 即存在常数 c> 0使得 k 充分大时, 有úx k+ 1 - x 3 ú ≤ cúx k - x 3 ú 2. 　　关于迭代法线性模型更为详细的收敛性结果, 有兴趣的读者可参阅[ 15 ]; 有关拟牛顿算 法较早的收敛性结果见文[ 40 ]. V IP 另一有效的研究途径是将之转换成各种等价的最优化问题, 进而采用各种变形的 拟牛顿方法研究V IP 的快速收敛算法. 设G 为 n 阶对称正定阵, 定义最优值函数 f (x ) = m ax - (y - x ) T F (x ) - 12 úy - xú 2G ûy ∈X . (4. 4) 求最优值函数 f (x )的根与V IP 的求解是等价的 (见[ 41 ]). Fuku sh im a 等在文[ 41 ]中将牛顿 法与最优化问题的下降搜索相结合, 给出一个具有全局收敛的牛顿型算法, 概括如下: 整体收敛的牛顿法 (GCNM ) [41 ]: (0) 选 x 0∈X , Β, Χ, Ρ∈ (0, 1) ; k= 0. (1) (牛顿步)求线性变分不等式V IP (F k , X )的解 z (x k ) , 其中 F k = F k (x ) = F (x k ) + ∃ F (x k ) T (x - x k ). 令方向 d k = z (x k ) - x k. ( 2) (线搜索) 如 f (x k + d k ) ≤Χf (x k ) , 令 Αk = 1; 否则求{1, Β, Β2, ⋯, Βm , ⋯}中满足以下 (415)的最大值 Αk: f (x k + Αd k ) - f (x k ) ≤ ΡΑ ∃f (x k ) T d k. (4. 5) 　　 (3) 令 x k+ 1= x k + Αkd k , k ÷= k + 1, 转回 (1). 关于以上算法的性质和收敛性, 有 定理 414　假设 X 为非空闭凸集, F 是连续可微并以 Λ为模的强单调函数, 正定阵 G 满足: ‖G‖< 2Λ. 则 ( 1) f (x ) 是连续可微的, ∃f (x ) = F (x ) - [ ∃F (x ) - G ] (P X G (x - G - 1F (x ) ) - x ) , 方向 d k 为 f (x )在 x k 处的可行下降方向, 其中 P X G (õ)为投影算子, 见定义215. ( 2) 对任意的初始点 x 0∈X , GCNM 产生的点列{x k }< X , 且{x k }整列收敛到V IP (F , X )的唯一解 x 3 , 即 GCNM 是整体收敛的; (3) 又如 X 为多面凸集, ∃F 在V IP (X , F ) 的唯一解 x3 的某个邻域N 内是L ip sch itz 602 高 校 应 用 数 学 学 报 第14卷A 辑 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 连续的, 严格互补条件在 x 3 处成立. 则当 k 充分大时, 步长 Αk≡1, 且{x k }二阶收敛于 x3 , 即 GCNM 是二阶收敛的. 在 GCNM 中, 等价优化问题的目标函数 f (x ) 能保持函数 F (x ) 的光滑性, 但在更多的 等价优化问题中, 目标函数 f (x ) 的 H essian 阵并不存在, 因此最近文 [ 42 ]引进一种可计算 的广义H essian 阵 (CGH ) 研究V IP 的牛顿型算法. 在[ 43 ]中运用CGH 的思想进一步研究 了V IP 的拟牛顿算法. 413　投影算法 投影算法是V IP 的一类相当有效的求解方法, 许多学者, 尤其是国外学者进行了大量 的研究, 并取得丰富和优秀的成果[ 13, 15, 19～ 29 ]. 投影方法的基本思想是据算子 F (x ) 构 造上述介绍的V IP 的迭代模型中各种具体的映射 g (x , y ) , 使得能借助于 (在可行集 X 上) 投影技术较容易地求出 (411) 的解, 并分析和建立各种收敛性条件, 这是投影方法研究的主 要内容. 在众多的投影算法中, 如文[ 10, 11, 13, 25, 27, 28 ], 都采用如下的 g (x , y) : g (x , y ) = F (y) + Σ(y) - 1G (x - y) , (4. 6) 其中G 为 n 阶待定正定矩阵 (不一定是对称的) , Σ(y) > 0为待定参 (函) 数. 此时迭代方法的 主步 (411)变为 x k+ 1 ∈X , [F (x k ) + Σ- 1k G (x k+ 1 - x k ) ]T (x - x k+ 1) ≥ 0, Π x ∈X . (4. 7) 　　当G 为对称阵时, 称由 (417)迭代的算法为对称投影法, 否则称之为非对称投影法. 当G 对称时, (417)的解可表示为投影方程 x k+ 1 = PX G (x k - ΣkG - 1F (x k ) ). (4. 8) 　　由 (417) 易见, 如{Σ- 1k }有界, 当 (418) 产生的点列{x k }整列收敛于 x3 时, x 3 为V IP (X , F ) (即 (211) ) 的解. 因此许多投影方法工作的焦点都集中在研究由 (418) 产生的点列{x k }的 各种收敛性条件, 我们用以下定理部分地阐述有关结果. 定理415　设G 为对称正定阵, 以下各条件是 (418)产生的点列{x k }收敛的充分条件. (1) [16 ] Σk≡Σ> 0, Σ充分小, X 为紧凸集, F (x )为连续可微的严格单调函数. (2) [27, 29 ] Σk≡Σ> 0, Σ充分小, F (x )在 X 上为强单调函数. (3) [26, 29 ]取G 为单位阵, Σk = Θk öúF (x k ) ú , 其中序列{Θk } 满足: ∑∞ k= 1 Θk = ∞, ∑∞ k= 1 Θ2k < ∞. F (x ) 在X 上强单调有界. ( 4) [25 ] F (x ) 是以 c 为模数的上强制函数, Σk≡Α< 2cΚm in (G ) , 此处 Κm in (G ) 表示矩阵G 的 最小特征值. 关于非对称投影法, 文[ 25 ]对线性变分不等式进行了研究, 即算子 F (x ) = A x+ b, A 为 n 阶半正定阵 (不一定对称). 设D 为一个对称正定阵,B = (A T - A ) ö2, 取 Σk≡Α, G = D - ΑB. 则 (417)变为 x k+ 1 ∈X , F (x k ) + 1Α (D - ΑB ) (x k+ 1 - x k ) T (x - x k+ 1) ≥ 0, Π x ∈X . (4. 9) 　　定理416 [25 ]　如0< Α< 2Κm in (D ) öúA ú. 则由 (419) 产生的序列{x k }收敛于V IP (X , F ) 的 解. 对于以上线性变分不等式问题, 还可采用分解技术研究可分解的非对称投影算法, 有兴 702第 2 期 简金宝等: 变分不等式的几类求解方法 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 趣的读者可查阅文[ 25