变分不等式的两类新算法
|
摘要
变分不等式问题(VIP)是运筹学领域中的一个重要分支，广泛应用于自然科学、工程计算和经济均衡等诸多学科。特别是VIP的数值方法，近年来引起了众多学者的广泛兴趣。其中利用VIP的KKT条件来构造算法是一类重要方法，一般文献都采用Fischer-Burmeister将相应的KKT条件等价地转化为非光滑方程组形式。本文另辟蹊径，依据文献[6]～[9]中提出的互补问题的一种Lagrange乘子法思想，重新构造给出KKT条件两类新的等价形式。本文的具体工作如下：
1．首先利用Levenberg-Marquardt方法给出求解带约束非线性方程组的一类新方法，该方法扩大了文献[4]中参数的取值范围，进而弥补了参数取唯一值在具体问题中的缺陷。在不要求梯度矩阵非奇异的条件下得到了算法的全局收敛性。并且在适当的假设条件下，得到了算法的局部超线性收敛及局部二次收敛性。
2．根据变分不等式问题本身的特点，建立了变分不等式问题KKT条件与光滑带约束方程组的等价关系。该等价形式中的每个函数都是连续可微的，虽然引入了参数λ，但在每一个迭代步修正参数λ的方法非常简单。利用上述Levenberg-Marquardt的方法得到求解变分不等式问题的一种新算法。
3．在上述等价形式的基础上，减少了等价形式中方程的个数。与已有利用Fis-cher函数求解变分不等式问题KKT条件的数值方法相比，该等价形式更简单，算法更易实现。基于该等价形式，本文提出了一种阻尼牛顿类算法，有效地弥补了Levenberg-Marquardt方法中必须计算Jacobi矩阵乘法的缺陷。在适当条件下，证明了算法的全局收敛性、局部超线性收敛或二次收敛性。数值实验结果表明该算法效率较高。
The variational inequality problem (VIP) is an important branch in operationalresearch, which has widely applications in science, engineering and economics. Es-pecially, the numerical methods for VIP attracts many scholars' more attention inrecent years. An important numerical method for VIP is to construct algorithms forthe corresponding KKT conditions.In general, the KKT conditions for VIP is equiva-lently transformed as a system of nonsmooth equations by using Fischer-Burmeisterfunction. Different from the methods in literature, we proposed two new numericalmethods for VIP in the paper as follows:
1. At first, a revised Levenberg-Marquardt method was presented for constraintsmooth equations system, which overcome the drawbacks of the parameter in [4]must be a constant number. Same convergent results in [4] were obtained undermild assumptions.
2. A new equivalent reformulation of constraint smooth equations system to theKKT conditions for VIP was proposed, and a new Levenberg-Marquardt methodfor solving VIP was constructed by using above mentioned method. The convergentresults were shown under some suitable conditions.
3. A new equivalent reformulation of nonlinear equations system without con-straints condition to the KKT conditions for VIP was proposed. It has fewer vari-ables and simpler form, and the algorithm is easily implemented. A damped Newtontype algorithm was presented based on it, which needs not to compute the product ofJacobi matrix as in Levenberg-Marquardt method. Under some certain conditions,the global convergence, local superlinear or quadratical convergence were obtained.Numerical results suggested the method is efficient.
1．首先利用Levenberg-Marquardt方法给出求解带约束非线性方程组的一类新方法，该方法扩大了文献[4]中参数的取值范围，进而弥补了参数取唯一值在具体问题中的缺陷。在不要求梯度矩阵非奇异的条件下得到了算法的全局收敛性。并且在适当的假设条件下，得到了算法的局部超线性收敛及局部二次收敛性。
2．根据变分不等式问题本身的特点，建立了变分不等式问题KKT条件与光滑带约束方程组的等价关系。该等价形式中的每个函数都是连续可微的，虽然引入了参数λ，但在每一个迭代步修正参数λ的方法非常简单。利用上述Levenberg-Marquardt的方法得到求解变分不等式问题的一种新算法。
3．在上述等价形式的基础上，减少了等价形式中方程的个数。与已有利用Fis-cher函数求解变分不等式问题KKT条件的数值方法相比，该等价形式更简单，算法更易实现。基于该等价形式，本文提出了一种阻尼牛顿类算法，有效地弥补了Levenberg-Marquardt方法中必须计算Jacobi矩阵乘法的缺陷。在适当条件下，证明了算法的全局收敛性、局部超线性收敛或二次收敛性。数值实验结果表明该算法效率较高。
The variational inequality problem (VIP) is an important branch in operationalresearch, which has widely applications in science, engineering and economics. Es-pecially, the numerical methods for VIP attracts many scholars' more attention inrecent years. An important numerical method for VIP is to construct algorithms forthe corresponding KKT conditions.In general, the KKT conditions for VIP is equiva-lently transformed as a system of nonsmooth equations by using Fischer-Burmeisterfunction. Different from the methods in literature, we proposed two new numericalmethods for VIP in the paper as follows:
1. At first, a revised Levenberg-Marquardt method was presented for constraintsmooth equations system, which overcome the drawbacks of the parameter in [4]must be a constant number. Same convergent results in [4] were obtained undermild assumptions.
2. A new equivalent reformulation of constraint smooth equations system to theKKT conditions for VIP was proposed, and a new Levenberg-Marquardt methodfor solving VIP was constructed by using above mentioned method. The convergentresults were shown under some suitable conditions.
3. A new equivalent reformulation of nonlinear equations system without con-straints condition to the KKT conditions for VIP was proposed. It has fewer vari-ables and simpler form, and the algorithm is easily implemented. A damped Newtontype algorithm was presented based on it, which needs not to compute the product ofJacobi matrix as in Levenberg-Marquardt method. Under some certain conditions,the global convergence, local superlinear or quadratical convergence were obtained.Numerical results suggested the method is efficient.
引文
[1] 乌力吉．互补问题的乘子法[D]．博士学位论文，内蒙古大学，2004．
[2] JIN-YAN FAN AND YAXIANG YUAN. On the Quadratic Convergence of the Levenberg-Marquardt method without Nonsingularity Assumption [J]: Computing. 2005,74: 23-39.
[3] N. YAMASHITA AND M. FUKUSHIMA. On the rate of Convergence of the Levenberg-Marquardt method [J]: Computing. 2001,15: 237-249.
[4] C. KANZOW, N. YAMASHITA AND M. FUKUSHIMA. Levenberg-Marquardt method for constrained nonlinear equations with strong local convergence properities [J]: Journal of computational and aplied mathematics. 2004,172: 375-397.
[5] 袁亚湘，孙文瑜．最优化理论与方法[M]．北京：科学出版社，1997．
[6] 乌力吉，陈国庆．非线性互补问题的一类新的带参数价值函数及牛顿类算法[J]：计算数学．2004，26：315-328．
[7] 乌力吉，陈国庆．线性互补问题的一类新的带参数价值函数阻尼牛顿法[J]：应用数学．2005，18：33-39．
[8] 乌力吉，陈国庆．线性互补问题的一种新Lagrange乘子法[J]：高等学校计算数学学报．2004，26：162-171．
[9] 乌力吉，陈国庆．箱约束变分不等式的一个简单光滑价值函数和阻尼牛顿法[J]：应用数学和力学．2005，26：988-996．
[10] CHANGYU WANG AND NAIHUA XIU. convergence of the gradient projection method for generalized convex minimization[J]: computational optimization and applications. 2000,16: 111-120.
[11] P. T. HARKER AND J. S. PANG. Finite-dimensional variational and nonlinear complementarity problems: A survey of theory, algorithms and applications[J]: Math. Prog. 1990,48: 161-220.
[12] P. HARTMAN AND G. STAMPACCHIA. On some nonlinear elilptic differential functional equations [J]: Acta.Math. 1966,115: 153-188.
[13] O. MANCINO AND G. STAMPACCHIA. Convex programming and variational Inequalities[J]: J.Opti.Th.Appl. 1972,9: 3-23.
[14] J. S. PANG. A B-differentiable equation based globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems [J]: Math. Prog. 1991, 51: 101-131.
[15] J. S. PANG. Newton's method for B-differentiable equations [J]: Math.Oper.Res. 1990,15: 311-341.
[16] B. XIAO AND P.T. HARKER. A nonsmooth Newton method for variational inequalities, Ⅰ: Theory[J]: Math.Prog. 1994,64: 151-194.
[17] B. XIAO AND P.T. HARKER. A nonsmooth Newton Method for variational inequalities, Ⅱ: Numerical results [J]: Math. Prog. 1994,65: 195-216.
[18] P. MARCOTTE AND J. P. DUSSAULT. A note on a globally convergent Newton method for solving monotone variational inequalities [J]: Oper.Res.Lett. 1987,6: 35-42.
[19] M. FUKUSHIMA. Equivalent differentiable optimization problems and descent method for asymmetric variational inequality problems [J]: Math. Prog. 1992,53: 99-110.
[20] T. LARSSON AND M. PATRIKSSON. A class of gap functions for variational inequalities [J]: Math. Prog. 1994,64: 53-79.
[21] D. L. ZHu AND P. MARCOTTE. An extended descent framework for variational inequalities [J]: J. Opti. Th. Appl. 1994,80: 349-366.
[22] C. KANZOW AND H. JIANG. A continuation method for (strongly)monotone variational inequalities [J]: Math.Prog. 1998,81: 103-125.
[23] C. KANZOW AND How-Duo QI. A QP-free constrained Newton-type method for variational inequality problems [J]: Mth.Prog. 1999,85: 81-106.
[24] L. QI. AND H. JIANG. Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations [J]: Math. Oper.Res. 1997,22: 301-325.
[25] F. FACCHINEI, A. FISCHER AND C. KANZOW. Inexact Newton methods for semismooth equations with applications to variational inequality problems [C]: Nonlinear Optimization and Applications, Plenum Press,New York. 1996: 125-149.
[26] F. FACCHINEI, A. FISCHER AND C. KANZOW. Regularity properties of a sernisrnooth reformulation of variational inequalities[J]: SIAM J. Optim. 1998,8: 850-869.
[27] D. H. LI, N. YAMASHITA AND M. FUKUSHIMA. Nonsmooth equation based BFGS method for solving KKT systems in mathematical programming [J]: Journal of optimization theory and applications. 2001,109: 123-167.
[28] L. QI. Boundness and Regularity properties of semismooth reformulation of variational inequalities [J]: Journal of global optimization. 2006,35: 343-366.
[29] B. CHEN AND P. T. HARKER. A continuation method for monotone variational inequalities [J]: Math.Programming. 1995,69(2): 237-253.
[30] C. KANZOW AND H. JIANG. A continuation method for strongly monotone variational inequalities [J]: Math. Programming. 1998,81: 103-126.
[31] C. KANZOW AND H. JIANG. A continuation method for the solution of monotone variational inequality problems [J]: Institute of Applied Mathematics. 1998: 103-125.
[32] F.FACCHINEI AND J. S. PANG. Finite-dimensional variational inequalities and complementarity problems [M]. Springer- Verlag,New York,Berlin,Heidelberg, 2003.
[33] JINBAO JIAN. A combined feasible-infeasible point continuation method for strongly monotone variational inequalities [J]: Journal of Global Optimization. 1999,15(6): 197-212.
[34] 简金宝．单调变分不等式的可行与非可行点组合的连续算法[J]：运筹学学报．1997，1(1)：76-85．
[35] A. A. GOLDSTEIN. Convex programming in Hilbert space [J]: Bull. Amer. Math. Soc. 1964,70: 709-710.
[36] E. S. LEVITIN AND B. T. POLYAK. constrained minimization problems [J]: USSR Comput. Math.Phys. 1966,6: 1-50.
[37] D. P. BERTSEKAS AND E. M. GAFNI. Projection methods for variational inequalities with application to the traffic assignment problem[J]: Mathematical Programming Study. 1982,17: 139-159.
[38] D. P. BERTSEKAS AND J. N. TSITSIKLIS. Iterative methods of variational and complementarity problems[J]: Math.Programming. 1982,24(3):284-313.
[39] T. DE LUCA, M. C. FACCHINEI AND C. KANZOW. A theoretical and numerical of some semismooth algorithm for complementarity problems [J]: comput.Optim. Appl. 2000,16: 173-205.
[40] J. S. PANC AND L.QI. Nonsmooth equations: motivation and algorithm [J]: SIAM J.Optim. 1993,3: 443-465.
[41] B. C. EAVES. On the basic theorem of complementarity [J]: Math.Programming. 1971,1: 68-75.
[42] L. QI AND D.SUN. A nonsrnooth version of Newton's method [J]: Math.Programming. 1993,58: 353-367.
[43] G.M.KORPELEVICH. The extragradient method for finding saddle points and other problems [J]: Matecon. 1976,12: 747-756.
[44] D. SUN. An iterative method for solving variational inequality problems and complementarity problems [J]: Numer.Math.: J. Chin. Univ. 1994,16: 145-153.
[45] D. SUN. A projection and contraction method for the nonlinear comlementarity problems its extensions [J]: Math. Numer.Sinica. 1994,16: 183-194.
[46] P. TSENG. On linear convergence of iterative methods for the variational inequlity problem [J]: J.Omput. Appl. Math. 1995,60: 237-252.
[47] N. H. XIU,C. Y. WANG AND J.Z. ZHANG. convergence properties of projection and contraction methods for variational inequality problems [J]: Appl.Math.Optim.Sinica. 2001,43:147-168.
[48] A. N. IUSEM AND B.F. SVAITER. A variant of Korplevich's method for solving variational inequalities with a new search strategy [J]: Optimization. 1997, 42: 309-321.
[49] 黄沙日娜．互补问题的乘子法研究[D]．硕士学位论文，内蒙古大学，2006．
[50] 李飞．求解变分不等式问题的连续化方法及其灵敏性分析[D]．博士学位论文，西安交通大学，2000．
[51] Y.J. WANG,N. H. XIU,AND J. Z. ZHANG. Modified extragrdient method for variational inequalities and verification of solution existence [J]: J.Omput. Appl.Math. 2003, 119(1): 167-183.
[52] XI-MING LIANG AND JI-XIN QIAN. A predictor-corrector interion-point algorithm for monotone variational inequality problems [J]: Journal of zhejiang University SCIENCE. 2002, 3(3): 321-325.
[2] JIN-YAN FAN AND YAXIANG YUAN. On the Quadratic Convergence of the Levenberg-Marquardt method without Nonsingularity Assumption [J]: Computing. 2005,74: 23-39.
[3] N. YAMASHITA AND M. FUKUSHIMA. On the rate of Convergence of the Levenberg-Marquardt method [J]: Computing. 2001,15: 237-249.
[4] C. KANZOW, N. YAMASHITA AND M. FUKUSHIMA. Levenberg-Marquardt method for constrained nonlinear equations with strong local convergence properities [J]: Journal of computational and aplied mathematics. 2004,172: 375-397.
[5] 袁亚湘，孙文瑜．最优化理论与方法[M]．北京：科学出版社，1997．
[6] 乌力吉，陈国庆．非线性互补问题的一类新的带参数价值函数及牛顿类算法[J]：计算数学．2004，26：315-328．
[7] 乌力吉，陈国庆．线性互补问题的一类新的带参数价值函数阻尼牛顿法[J]：应用数学．2005，18：33-39．
[8] 乌力吉，陈国庆．线性互补问题的一种新Lagrange乘子法[J]：高等学校计算数学学报．2004，26：162-171．
[9] 乌力吉，陈国庆．箱约束变分不等式的一个简单光滑价值函数和阻尼牛顿法[J]：应用数学和力学．2005，26：988-996．
[10] CHANGYU WANG AND NAIHUA XIU. convergence of the gradient projection method for generalized convex minimization[J]: computational optimization and applications. 2000,16: 111-120.
[11] P. T. HARKER AND J. S. PANG. Finite-dimensional variational and nonlinear complementarity problems: A survey of theory, algorithms and applications[J]: Math. Prog. 1990,48: 161-220.
[12] P. HARTMAN AND G. STAMPACCHIA. On some nonlinear elilptic differential functional equations [J]: Acta.Math. 1966,115: 153-188.
[13] O. MANCINO AND G. STAMPACCHIA. Convex programming and variational Inequalities[J]: J.Opti.Th.Appl. 1972,9: 3-23.
[14] J. S. PANG. A B-differentiable equation based globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems [J]: Math. Prog. 1991, 51: 101-131.
[15] J. S. PANG. Newton's method for B-differentiable equations [J]: Math.Oper.Res. 1990,15: 311-341.
[16] B. XIAO AND P.T. HARKER. A nonsmooth Newton method for variational inequalities, Ⅰ: Theory[J]: Math.Prog. 1994,64: 151-194.
[17] B. XIAO AND P.T. HARKER. A nonsmooth Newton Method for variational inequalities, Ⅱ: Numerical results [J]: Math. Prog. 1994,65: 195-216.
[18] P. MARCOTTE AND J. P. DUSSAULT. A note on a globally convergent Newton method for solving monotone variational inequalities [J]: Oper.Res.Lett. 1987,6: 35-42.
[19] M. FUKUSHIMA. Equivalent differentiable optimization problems and descent method for asymmetric variational inequality problems [J]: Math. Prog. 1992,53: 99-110.
[20] T. LARSSON AND M. PATRIKSSON. A class of gap functions for variational inequalities [J]: Math. Prog. 1994,64: 53-79.
[21] D. L. ZHu AND P. MARCOTTE. An extended descent framework for variational inequalities [J]: J. Opti. Th. Appl. 1994,80: 349-366.
[22] C. KANZOW AND H. JIANG. A continuation method for (strongly)monotone variational inequalities [J]: Math.Prog. 1998,81: 103-125.
[23] C. KANZOW AND How-Duo QI. A QP-free constrained Newton-type method for variational inequality problems [J]: Mth.Prog. 1999,85: 81-106.
[24] L. QI. AND H. JIANG. Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations [J]: Math. Oper.Res. 1997,22: 301-325.
[25] F. FACCHINEI, A. FISCHER AND C. KANZOW. Inexact Newton methods for semismooth equations with applications to variational inequality problems [C]: Nonlinear Optimization and Applications, Plenum Press,New York. 1996: 125-149.
[26] F. FACCHINEI, A. FISCHER AND C. KANZOW. Regularity properties of a sernisrnooth reformulation of variational inequalities[J]: SIAM J. Optim. 1998,8: 850-869.
[27] D. H. LI, N. YAMASHITA AND M. FUKUSHIMA. Nonsmooth equation based BFGS method for solving KKT systems in mathematical programming [J]: Journal of optimization theory and applications. 2001,109: 123-167.
[28] L. QI. Boundness and Regularity properties of semismooth reformulation of variational inequalities [J]: Journal of global optimization. 2006,35: 343-366.
[29] B. CHEN AND P. T. HARKER. A continuation method for monotone variational inequalities [J]: Math.Programming. 1995,69(2): 237-253.
[30] C. KANZOW AND H. JIANG. A continuation method for strongly monotone variational inequalities [J]: Math. Programming. 1998,81: 103-126.
[31] C. KANZOW AND H. JIANG. A continuation method for the solution of monotone variational inequality problems [J]: Institute of Applied Mathematics. 1998: 103-125.
[32] F.FACCHINEI AND J. S. PANG. Finite-dimensional variational inequalities and complementarity problems [M]. Springer- Verlag,New York,Berlin,Heidelberg, 2003.
[33] JINBAO JIAN. A combined feasible-infeasible point continuation method for strongly monotone variational inequalities [J]: Journal of Global Optimization. 1999,15(6): 197-212.
[34] 简金宝．单调变分不等式的可行与非可行点组合的连续算法[J]：运筹学学报．1997，1(1)：76-85．
[35] A. A. GOLDSTEIN. Convex programming in Hilbert space [J]: Bull. Amer. Math. Soc. 1964,70: 709-710.
[36] E. S. LEVITIN AND B. T. POLYAK. constrained minimization problems [J]: USSR Comput. Math.Phys. 1966,6: 1-50.
[37] D. P. BERTSEKAS AND E. M. GAFNI. Projection methods for variational inequalities with application to the traffic assignment problem[J]: Mathematical Programming Study. 1982,17: 139-159.
[38] D. P. BERTSEKAS AND J. N. TSITSIKLIS. Iterative methods of variational and complementarity problems[J]: Math.Programming. 1982,24(3):284-313.
[39] T. DE LUCA, M. C. FACCHINEI AND C. KANZOW. A theoretical and numerical of some semismooth algorithm for complementarity problems [J]: comput.Optim. Appl. 2000,16: 173-205.
[40] J. S. PANC AND L.QI. Nonsmooth equations: motivation and algorithm [J]: SIAM J.Optim. 1993,3: 443-465.
[41] B. C. EAVES. On the basic theorem of complementarity [J]: Math.Programming. 1971,1: 68-75.
[42] L. QI AND D.SUN. A nonsrnooth version of Newton's method [J]: Math.Programming. 1993,58: 353-367.
[43] G.M.KORPELEVICH. The extragradient method for finding saddle points and other problems [J]: Matecon. 1976,12: 747-756.
[44] D. SUN. An iterative method for solving variational inequality problems and complementarity problems [J]: Numer.Math.: J. Chin. Univ. 1994,16: 145-153.
[45] D. SUN. A projection and contraction method for the nonlinear comlementarity problems its extensions [J]: Math. Numer.Sinica. 1994,16: 183-194.
[46] P. TSENG. On linear convergence of iterative methods for the variational inequlity problem [J]: J.Omput. Appl. Math. 1995,60: 237-252.
[47] N. H. XIU,C. Y. WANG AND J.Z. ZHANG. convergence properties of projection and contraction methods for variational inequality problems [J]: Appl.Math.Optim.Sinica. 2001,43:147-168.
[48] A. N. IUSEM AND B.F. SVAITER. A variant of Korplevich's method for solving variational inequalities with a new search strategy [J]: Optimization. 1997, 42: 309-321.
[49] 黄沙日娜．互补问题的乘子法研究[D]．硕士学位论文，内蒙古大学，2006．
[50] 李飞．求解变分不等式问题的连续化方法及其灵敏性分析[D]．博士学位论文，西安交通大学，2000．
[51] Y.J. WANG,N. H. XIU,AND J. Z. ZHANG. Modified extragrdient method for variational inequalities and verification of solution existence [J]: J.Omput. Appl.Math. 2003, 119(1): 167-183.
[52] XI-MING LIANG AND JI-XIN QIAN. A predictor-corrector interion-point algorithm for monotone variational inequality problems [J]: Journal of zhejiang University SCIENCE. 2002, 3(3): 321-325.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |