求解非线性P0互补问题的非单调磨光算法

doi:10.12286/jssx.2014.1.35

计算数学 ›› 2014, Vol. 36 ›› Issue (1): 35-50.DOI: 10.12286/jssx.2014.1.35

求解非线性P₀互补问题的非单调磨光算法

袁敏, 万中

中南大学数学与统计学院, 长沙 410083

收稿日期:2013-01-13 出版日期:2014-02-15 发布日期:2014-02-12
通讯作者: 万中
基金资助:
国家自然科学基金资助（基金号：71221061，71071162）项目；湖南省自然科学基金（基金号：13JJ3002）项目.

PDF ( 880 ) 引用

袁敏, 万中. 求解非线性P₀互补问题的非单调磨光算法[J]. 计算数学, 2014, 36(1): 35-50.

Yuan Min, Wan Zhong. NON-MONOTONE SMOOTHING ALGORITHM FOR SOLVING NONLINEAR P₀ COMPLEMENTARITY PROBLEMS[J]. Mathematica Numerica Sinica, 2014, 36(1): 35-50.

NON-MONOTONE SMOOTHING ALGORITHM FOR SOLVING NONLINEAR P₀ COMPLEMENTARITY PROBLEMS

Yuan Min, Wan Zhong

School of Mathematics and Statistics, Central South University, Changsha 410083, China

Received:2013-01-13 Online:2014-02-15 Published:2014-02-12

提出了一种新的磨光函数，在分析它与已有磨光函数不同特性的基础上，研究了将它用于求解非线性P₀互补问题时，其磨光路径的存在性和连续性，进而设计了求解一类非线性P₀互补问题的非单调磨光算法. 在适当的假设条件下，证明了该算法的全局收敛性和局部超线性收敛性. 数值算例验证了算法的有效性.

关键词： 互补问题, 磨光算法, 全局收敛性, 超线性收敛性

In this paper, a new smoothing function is constructed, and on the basis of its properties, the existence and the continuity of smoothing path are investigated when this smoothing function is employed to solve a nonlinear P₀ complementarity problem. Then, a non-monotone smoothing algorithm is developed to solve the nonlinear P₀ complementarity problems. Under suitable assumptions, both global convergence and super-linear convergence are established for the developed algorithm. Numerical experiments show that the algorithm is efficient.

Key words: Complementarity Problems, Smoothing method, Global Convergence, Superlinear Convergence

MR(2010)主题分类:

90C25
90C30

分享此文:

[1] Huang N,Ma C F. The numerical study of a regularized smoothing Newton method for solving P₀- NCP based on the generalized smoothing Fischer-Burrmeister function[J]. Applied Mathematics and Computation, 2012, 218: 7253-7269.

[2] Zhang L P, Wu S Y, Gao T. Improved smoothing Newton methods for P₀ nonlinear complementarity problems[J]. Applied Mathematics and Computation, 2009, 215: 324-332.

[3] Revindran G, Gowda M S. Regularization of P₀-functions in box variational inequality problems[J]. SIAM Journal on Optimization, 2000, 11: 748-760.

[4] Zhu J G, Liu H W, Li X L. A regularized smoothing-type algorithm for solving a system of inequalities with a P₀ - function[J]. Journal of Computational and Applied Mathematics, 2010, 233:2611-2619.

[5] Zhang Y, Huang Z H. A nonmonotone smoothing-type algorithm for solving a system of equalities and inequalities[J]. Journal of Computational and Applied Mathematics, 2010, 233: 2312-2321.

[6] Yin H X, Zhang J Z. Global convergence of a smooth approximation method for mathematical programs with complementarity constraints[J]. Math. Meth. Oper. Res., 2006, 64: 255-269.

[7] Ni T, Wang P. A smoothing-type algorithm for solving nonlinear complementarity problems with a non-monotone line search[J]. Applied Mathematics and Computation, 2010, 216: 2207-2214.

[8] Tang J, Liu S Y, Ma C M. One-step smoothing Newton method for solving the mixed complementarity problem with a P₀ function[J]. Applied Mathematics and Computation, 2009, 215: 2326-2336.

[9] Tang J, Liu S Y. A new smoothing Broyden-like method for solving the mixed complementarity problem with a P₀-function: Nonlinear Analysis[J]. Real World Applications, 2010, 11: 2770-2786.

[10] Chen B, Harker P T. Smooth Approximations to Nonlinear Complementarity Problems[J]. SIAM J. Optim, 1997, 7(2): 403-420.

[11] Kanzow C. Some Noninterior Continuation Methods for Linear Complementarity Problems[J]. SIAM J. Matrix Anal Appl, 1996, 17(4): 851-868.

[12] Chen X, Qi L. A parameterized Newton method and a Broyden-like method for solviing nonsmooth equations[J]. Comput Optim Appl, 1995, 5: 97-138.

[13] Tseng P, Analysis of a non-interior continuation method based on Chen-Mangasarian smoothing functions for complementarity problems. In: Fukushima M, Qi L. Reformulation-Nonsmooth. Piecewise Smooth. Semismooth and Smoothing Methods. Boston: Kluwer Academic Publishers, 1999, 381-404.

[14] Gowda M S, Tawhid M A. Existence and limiting behavior of trajetories associated with P₀- equations[J]. Comput Optim Appl, 1999, 12(1-3): 229-251.

[15] Qi H D, Liao L Z. A smoothing Newton method for extended vertical linear complementarity problems[J]. SIAM J Matrix Anal Appl, 1999, 21(1): 45-66

[16] Moré J J, Rheinboldt W C. On P- and S-functions and related classes of n-dimensional nonlinear mappings[J]. Linear Algebra Appl, 1973, 6: 45-68.

[17] Kojima M, Negiddo N, Noma T, Yoshise A. A unified approach to interior point algorithms for linear complementarity problems: lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, 1991.

[18] Jiang H, Qi L. A new nonsmooth eqations approach to nonlinear complementarity problems[J]. SIAM Journal on Control and Optimization, 1997, 35(1): 178-193.

[19] Pang J S, Gabriel S A. NE/SQP: A robust algorithm for the nonlinear complementarity problem[J]. Mathematical Programming, 1993, 60: 295-337.

[20] Yamashita N, Fukushima M. Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems[J]. Mathematical Programming, 1997, 76: 469-491.

[21] Yu H D, Pu D G. Smoothing Levenberg-Marquardt method for general nonlinear complementarity problems under local error bound[J]. Applied Mathematical Modelling, 2011, 35: 1337-1348.

[22] Qi L, Sun J. A nonsmooth version of Newton's method[J]. Math. Program., 1993, 58: 353-367.

[23] Pieraccini S, Gasparo M G, Pasquali. Global Newton-type methods and semismooth reformulations for NCP[J]. Appl. Number. Math., 2003, 44: 367-384.

[24] Fathi Y. Computational complexity of LCPs associated with positive definite symmetric matrices[ J]. Mathematical Programming, 1979, 17: 335-344.

[1]	胡雅伶, 彭拯, 章旭, 曾玉华. 一种求解非线性互补问题的多步自适应Levenberg-Marquardt算法[J]. 计算数学, 2021, 43(3): 322-336.
[2]	张丽丽, 任志茹. 改进的分块模方法求解对角占优线性互补问题[J]. 计算数学, 2021, 43(3): 401-412.
[3]	丁戬, 殷俊锋. 求解一类非线性互补问题的松弛two-sweep模系矩阵分裂迭代法[J]. 计算数学, 2021, 43(1): 118-132.
[4]	尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[5]	吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[6]	张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[7]	李枝枝, 柯艺芬, 储日升, 张怀. 二阶锥线性互补问题的广义模系矩阵分裂迭代算法[J]. 计算数学, 2019, 41(4): 395-405.
[8]	罗刚, 杨庆之. 一类张量特征值互补问题[J]. 计算数学, 2019, 41(4): 406-418.
[9]	戴平凡, 李继成, 白建超. 解线性互补问题的预处理加速模Gauss-Seidel迭代方法[J]. 计算数学, 2019, 41(3): 308-319.
[10]	李郴良, 田兆鹤, 胡小媚. 一类弱非线性互补问题的广义模系矩阵多分裂多参数加速松弛迭代方法[J]. 计算数学, 2019, 41(1): 91-103.
[11]	郑华, 罗静. 一类H矩阵线性互补问题的预处理二步模基矩阵分裂迭代方法[J]. 计算数学, 2018, 40(1): 24-32.
[12]	王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.
[13]	刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[14]	刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.
[15]	简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424.

阅读次数

全文

摘要