 Operations Research and Fuzziolgy 运筹与模糊学, 2012, 2, 19-24 http://dx.doi.org/10.12677/orf.2012.22003 Published Online May 2012 (http://www.hanspub.org/journal/orf) A Class of Modified Generalized Quasi-Newton Algorithms for Solving Complementarity Problem Wei Wang, Zongwei Jia, Yongchuang Han School of Mathematics, Liaoning Normal University, Dalian Email: wei_0713@sina.com, jiazongwei88@163.com Received: Jan. 6th, 2012; revised: Jan. 14th, 2012; accepted: Feb. 13th, 2012 Abstract: Since the complementarity problem is proposed, people have done series of research, propose a lot of efficient algorithms, more used methods are projection method, interior-point method, smooth (nonsmooth) Newton method, etc. In thi s paper, complementarity problem i s convert into unconstrained optim i z at ion by using Fischer-Burmeister function, then unconstrained optimization is solved by modified generalized quasi-Newton algorithm. the improved algori thm has good num erical results verified by numerical experim ents. Keywords: Complementarity Problem; Unconstrained Optimization Problem; Generalized Quasi-Newton Algorithms 一类修正的广义拟牛顿法解互补问题 王 炜，贾宗伟，韩永闯 辽宁师范大学数学学院，大连 Email: wei_0713@sina.com, jiazongwei88@163.com 收稿日期：2012 年1月6日；修回日期：2012 年1月14日；录用日期：2012 年2月13 日 摘 要：互补问题自被提出至今，人们对它进行了一系列研究，提出了许多有效算法，比较常用的有 投影法、内点法、光滑(非光滑)牛顿法等。本文利用 Fischer-Burmeister 函数将互补问题转化为无约束 优化问题，再利用修正的广义拟牛顿算法求解。改进后的算法经数值实验验证有良好的数值效果。 关键词：互补问题；无约束优化问题；广义拟牛顿算法 1. 引言 互补问题在工程和经济领域中的应用非常广泛，如力学中的弹塑性分析问题、接触问题、蠕变问题、土力 学问题、润滑力学问题等都可以转化为如下的互补问题来求解[1-4]：对于 :nn F xR R，求一点 n x R使得 0, 0,0 T xF xxF x . 互补问题的研究过程中，涌现出了许多求解算法。光滑牛顿法简单优越，但是即使一个线性互补问题，转化后 的方程往往是线性的，且非线性程度较高，导致理论和计算的复杂化；投影类算法法每次迭代运算量少，存储 量少，保稀疏性，但其收敛速率被认为是最多线性的；无约束优化法较为成熟，因此本文算法只需选取适当的 势函数将互补问题转化为无约束优化问题，再对其求解。Mangasarian 和Soldow 给出一个可微的势函数，并且 证明了解势函数与解互补问题的等价性，为以后的研究工作做了理论基础[5]。对于无约束优化问题，BYRD R. H. 做了非拟牛顿算法的研究[6,7]，随后陈兰平提出一种基于 Broyden 族的非拟牛顿算法，并证明了非拟牛顿凸族的 收敛性[8]。陈兰平提出的拟牛顿方程只有目标函数梯度信息[8]，本文对其做了改进，使它不仅包含目标函数梯度 Copyright © 2012 Hanspub 19  王炜 等 一类修正的广义拟牛顿法解互补问题 信息，还包含目标函数的信息，具有更广泛的形式。数值实验中，不仅验证了改进的算法的可行性，并且讨论 了算法计算速度较快时参数的取值。 在第 2章，讲述了互补问题转化成无约束问题的具体过程，并给出了修正的拟牛顿迭代公式；在第 3章， 给出了本文修正广义拟牛顿算法的步骤；在第 4章，对算法全局收敛性和超线性收敛性进行了论述证明；在第 5章，数值实验表明，本文的算法是有效的。 2. 预备知识 :nn F xR R，求一点 n x R使得 0, 0,0 T xF xxF x . (1) 当 F x为线性函数时，称(1)为线性互补问题，记为 ,LCP M q；否则，称(1)为非线性互补问题，记为 NCP F。 本文的方法是利用互补函数把互补问 题转化为无约束最 优化问题[9]，再用广义拟牛顿法求解，转化过程如下： 12 ,,, T n xx x ,,,T ，12 n x F xFxFx Fx，取适当的互补函数令 ,ab ，令 11 , , nn xFx xM x Fx ， 2 1 2 f x x，其中 为向量 2-范数。 互补函数 要满足：；推广之，可得到以下成立 ,ab ,00, 0,0aba bab * x 是 NCP F的解 * x 是 x 的解。 于是，互补问题最终转化为无约束优化问题 x，其中 11 2 , 1, 2, nn xFx fxx xM x Fx 。本文 f min 所用的互补函数是 Fischer-Burmeister 函数 22 ,ababa b 。 对于无约束最优化问题 min, n f xx R，拟牛顿方程为 1kk k y B，其 中 f x是二阶连续可微的， 1k B 为 Hessian 阵 的一个近似， 21 k fx 11 ,, ,, kkkk kkkkkkkk s xxgfxygx gxgfxffx , 搜索方向 ， kk dgHk 1 kk H B。 本文采用的广义拟牛顿迭代公式如下： 1 TT T kkk kkk kk k T k kkk yyss VV Qt yy HH HH Hk . (2) 其中 12 Tkkk kkkk TT kkk kk sy Vyy ys yy H HH ， k Qt是T kk y s和 的凸组合， k R 1,0, T kkk k Qt tystRt 1， 11 2kkT T kkk Rffgsg kk s. 当 时，(2)式即为 Broyden族校正公式；当1t 0, 1t，(2)式是非拟的拟牛顿校正公式。 3. 修正的广义拟牛顿算法 给定初始点 0n x R，初始矩阵 。 1 000 , nn nn RR BHB 选择充分小的 0 ， ，令 0,1 ,0,1 0k 。 Copyright © 2012 Hanspub 20  王炜 等 一类修正的广义拟牛顿法解互补问题 1) 确定下降方向 。 kk dgHk 2) 取步长 k m k ，其中， 是满足下式的最小非负整数， k m ,0,1,0,1 mmT kkk kk fxd fgd . 3) 求1 , kkk kk x xx d 。 4) 若k g ，则停止；否则，转 5)。 5) 利用校正公式 1 1 0 0 T kk TT kTT kkk kkk kk kkkk T k kkk ys yyssVVy s Qt yy k ， 若 ，若 H HHH HH H . 计算 1k H ，令 ，转 1)。 1kk 4. 全局收敛性和超线性收敛性 假设 1 1) f x在 上二阶连续可微；2) n R f x在水平集内是一致凸函数。 假设 2 1) f x在 上二阶连续可微；2) n R f x在局部极小值点* x 的Hessian 矩阵 * x G正定；3) 存在 * x 点的一个邻域 *,Nx ，使得 x G在该邻域内 Lipschitz 连续。 引理 1 设k H 正定，则校正公式 2)使1k Η 保持正定。 证明：将k H 分解为 ，对，令，则有下面三个不等式成立 T kk LLHk0T k , n zRz , T kkkk aLzbLs 2 0 T Tkk TT kkk k kkk TT kkk kk ab yy zzaa yy bb HH HH , 2 11 () T Tk TT T kk kk kkk k kk zs ss ztystRz tystR Qt Qt 0 0 T ys z (限定 ), kk 20 TT T kk k zVVz zV , 且三个等号不能同时成立，故 大于零。即 1 T k z H1k H 为正定矩阵。 定理 1 设 是由修正的校正公式产生的非奇异矩阵序列，在假设 1条件下，迭代序列 k B k x 收敛到 f x的 极小值点。 证明：记, TT kkk k kk TT kk kk ys yy mM s ys ，引理 5.71[10]，存在与 k无关的正常数 ，使得。 ,mM , kk mmM M 对修正的校正公式 12 T T kkkT kkk k kk k TT kkkkk Qtyy ss VV ss ys BB BB Bk ， 两边求迹得 22 2 12 kkkk kk TT kkkkk sQy tr trV ss ys B BB Bk 。 为求 1k B 的行列式，我们先给出一个有关秩-2校正矩阵行列式的计算式和求矩阵逆公式： det 1 TT I uvu v , 11 11 1 1 T T T A uv A Auv AvAu . 推广之： 12341234142 3 det1 1 TT TTTT I uu uuuuuuuuuu ， 1 122 detdetdet det TT TT kkkk kkk kkkkkk k kk k TT TT kkkkkk kk kk QtyyQt yy ss ss I ss ss ys ys B BB B BB B BB . Copyright © 2012 Hanspub 21  王炜 等 一类修正的广义拟牛顿法解互补问题 记 1 123 2 ,,, kkk TT k kk k TT kkkkk Qt y s uusu u ss ys B B B4 y ， 12 1 T Tkkk T kkk ss uu ss B B, 1 23 2 T kkkkk k T T Tkk kk Qtsy Qt uu ys ys BB , 14 T Tkk T kkk ys uu s s B. 因此 1 2 det T T kkkk k kk k TT T kkkkkk kk Qt yyQt ss I s sss ys B B BB ， 1 detdet k kk T kkk Qt s s BB B 。 令cos , TT kkkkkk kk T kkk kk s ss q ss s s s BB B ， 1 det detdetdet TT kk k kk kkk kk kk TTTT k kkkkkkkkkkkk Qt QtQt ys ssm q ss ysssss ys BB BB BB T , 22 2 22 22 2 2 () 22 cos cos T kkk Tkkk kkkk TTT T kk kkk kkkkk TTT kkk kkkkkkkkkkkk k TT TTT kkk kkkkkkkkk kkk ys ys Vss ys ys ssss ys ssss ysMMqq q mm ysssysyss s B B B BB B BB B , 其中 2cos TT kkkkkkkk T kk kk kk ys ys M q m ys ms BB 。 122 2 cos cos cos kk kkkk kk k T kkk kkkk MQt qMMq tr trq mm y k q BB . 对对称正定矩阵 B，定义函数 In dettr B BB，则 0 B。 设12 ,,, n 为B的n个特征根，则 1 In detIn0 ii i tr n BB B 。 函数在 上非正。 1Inhtt t 0, 111 22 2 In det 2 In cos cos cos 2 In111cos kk k kk k kkkkkk kk T T kkk k kkkkkk kkkk kk k k TT k kk kkk tr MQ tQ t qMMqqm q mm q ys ys Qtm MQtqM q m ys ys BB B B B 22 2 In cos In1 1cos2coscos 111In 1cos kk k kk kkkk kTT kk kk kkkkkkk k k kk Mq q m Qtm MQt ys ys mMM m qq m B . 假设 。则，有 2 0 limcos 0 k k 11 0,kkk 21 cos 1 2 k 。 令 2 2 1cos 1cos k k k T 。则 2 2 1,InIn2 Incos 2cos kk k TT k 。 Copyright © 2012 Hanspub 22  王炜 等 一类修正的广义拟牛顿法解互补问题 1 2 In1111 In In11In1In In11In2Incos kkkk kk kk k TT kk kk kkkk kkk k TT kk kk kkkk k k TT kk kk Qtm MQtqT q ys ys Qtm MQtqT q ys ys Qtm MQt ys ys BB B B 2 . 由假设知：对上述的 有 12 1 ,0,kk kkk 22 In cosIn11In2 1 kkkk kTT kkkk Qtm MQt ys ys . 代入上不等式，有 1 2 In11In2 1In11In2 kkkk kk TT kk kk kkkk kTT kk kk Qtm MQt ys ys Qtm MQt kk ys ys BB B . 不等式右端趋近于负无穷，矛盾，假设不成立。 这样便存在 k x 的无穷子列 0 k N x和00 ，使得对 00 ,cos k kN 。在 假设1条件下，定理 2.3.1成立 [10]，利用 Zoutendijk 条件可以推出数列 0 kN g0。由于 f x在水平集上是一致凸函数，稳定点与最小值点 是一致的，也是唯一的。这样便可推出点列 k x 收敛到目标函数的唯一极小值点。 定理 2 在假设 2下，若迭代点列 k x 收敛到最优解* x ，步长有界且 k x 满足 * 1k k xx ，则 k x 超线 性收敛到 * x 。 证明：类似于文献[6,11,12]中Broyden族算法超线性收敛的证明，可得结论成立。因证明过长在此略。 5. 数值实验 本节在数学软件 matlab 7.0环境下对互补问题进行数值实验，下面是一个经典的非线性互补算例。 22 112234 22 11234 22 112 234 22 1234 32 236 2102 3229 3233 xxxxxx xxxxx Fx xxxxx x xxxx 2 9 . 实验中都取 0.4 ，0.5 ，，表 1中取 5 10 0.55, 0.5t 。 Table 1. Effectiveness of the algorithm 表1. 算法有效性 初始点 最优点 迭代次数 最优值 (2,1,1,1)T (1.2247,0.0000,0.0000,0.5000)T 30 2.8568e–011 (1,4,5,1)T (1.0000,0.0000,3.0000,0.0000)T 24 2.0025e–013 (4,1,1,6)T (1.2247,0.0000,0.0000,0.5000)T 34 1.2085e–012 (100,0.5,0.1,10 )T (1.2247,0.0000,0.0000,0.5000)T 32 3.1677e–012 (10,0.5,10,1)T (1.0000,0.0000,3.0000,0.0000)T 26 6.5622e–013 此互补问题有两组解 62,0,0,1 2T和，所 取 的5个初始点能够求得这两组解，表 1可验证本文 1, 0,3, 0T Copyright © 2012 Hanspub 23  王炜 等 一类修正的广义拟牛顿法解互补问题 Copyright © 2012 Hanspub 24 算法的有效性和全局收敛性。 表2取初始点 ，格中上一行是最优值，下一行是迭代次数。格中*表示求得解 ，不加*表示求得解 。 1, 4, 5,1T 00,0.50001.2247,0.0000,0.00 T1.0000,0.0000,3.0000,0.0000 T Table 2. Exploration of the calculation speed 表2. 计算速度探索 ρ t 0.3 0.45 0.5 0.6 0.75 0.9 0.3 6.9099e–014 41 6.9754e–011 46 1.3940e–012 46 7.4963e–013 36 2.1207e–012 31 0.0630 125 0.45 4.0898e–012 52 1.2922e–011 37 8.9246e–013 32 8.8529e–015 33 4.0264e–013 24 1.1747e–012 201 0.5 3.7457e–012 59 3.3100e–014 38 6.5403e–012 31 4.2646e–012 25 8.5990e–013 24 1.4983e–013 138 0.6 1.6075e–012 53 1.2108e–013 39 2.8874e–012 33 2.1244e–013 29 3.8813e–013 26 1.3273e–012 112* 0.75 1.1007e–012 42 2.9526e–013 32 1.0549e–012 31 2.6751e–013 26 8.2304e–014 24 4.4525e–012 81* 0.9 1.6216e–013 37 4.7631e–013 29 1.0725e–011 25 1.6679e–013 25 1.3665e–013 26 4.0754e–012 51* 1 2.5390e–012 30 1.1277e–013 30 3.0698e–013 27 1.4660e–014 24 6.6347e–013 26 8.9073e–016 61 由表 2可知，变化t和 的值，算法的计算速度也会不同。当 0.9, 0.3t 时，最优值是 0.0630，明显不 是恰当的最优值，因此线搜索中 的取值也会影响收敛速度的大小。t的值固定， 在0.6~0.75之间时，计算 速度相对是较快的； 的值固定，t在0.75~1之间时，计算速度相对较快。 通过实验数据分析表明，改进算法具有有效性和全局收敛性，并且具有良好的数值效果和较快的收敛速度， 将参数 和t分别限定在某个范围时，收敛速度达到最快。 6. 结论 本文利用互补函数将互补问题转化为无约束优化问题，再利用修正的广义拟牛顿算法求解。改进后的算法 经数值实验验证有良好的数值效果。本文算法的校正公式中参数 取值时和 Broyden 族校正公式类似，某些取 值可能比 BFGS算法的数值效果更好，还有待深入探索。 参考文献 (References) [1] G. Maier. A matrix structural theory of piecewise linear elastopl as tic it y with interacting yield planes. Meccanica, 1970, 5(1): 54-66. [2] 陈万吉, 陈国庆. 接触问题的互补变分原理及非线性互补模型[J]. 计算结构力学及其应用, 1996, 13(2): 138-146. [3] F. Tin-Loi, S. H. Xia. Nonholonmic elastoplastic ana1ysis involving unilateral frictionless contact as a mixed complementarity problem. Com- puter Methods in Applied Mechanics and Engineering, 2001, 190(35-36): 4551-4568. [4] 何素艳, 李建字, 张洪武等. 工程力学中的互补问题: 模型[J]. 计算力学学报, 2004, 21(2): 185-190. [5] O. L. Mangasarian, M. V. Soldow. Nonlinear complementarity as unconstrained and constrained minimization. Mathematical Programming, 1993, 62(1-3): 277-297. [6] R. H. Byrd, J. Nocedal and Y. Yuan. Global convergence of a class of quasi-Newton methods on convex problems. SIAM Journal of Numeri- cal Analysis, 1987, 24(5): 1171-1189. [7] R. H. Byrd, J. Nocedal. A tool for the analysis of quasi-Newton methods with application to unconstrained minimization. SIAM Journal on Numerical Analysis, 1989, 26(3): 727-739. [8] 陈兰平, 焦宝聪. 一类非拟 Neston算法及其收敛性[J]. 应用数学与计算数学学报, 1997, 11(2): 9-17. [9] C. Kanzow. Nonlinear complementarity as unconstrained optimization. Journal of Optimization Theory and Applications, 1996, 88(1): 139- 155. [10] 王宜举, 修乃华. 非线性规划理论与算法[M]. 西安: 陕西科学技术出版社, 2008. [11] D. Sun, L. Qi. On NCP-functions. Computational Optimization and Applications, 1999, 13(1-3): 201-220. [12] J. Y. Han, D. F. Sun. Newton and quasi-Newton method for normal maps with polyhedral sets. Journal of Optimization Theory and Applica- tions, 1997, 94(3): 659. |