求解非线性互补问题的混合光滑型算法

倪铁, 李永利, 邵良杉

系统工程理论与实践 ›› 2014, Vol. 34 ›› Issue (10) : 2656-2665.

PDF(454 KB)
PDF(454 KB)
系统工程理论与实践 ›› 2014, Vol. 34 ›› Issue (10) : 2656-2665. DOI: 10.12011/1000-6788(2014)10-2656
论文

求解非线性互补问题的混合光滑型算法

    倪铁1, 李永利2, 邵良杉3
作者信息 +

A mixed smoothing type algorithm for solving nonlinear complementarity problems

    NI Tie1, LI Yong-li2, SHAO Liang-shan3
Author information +
文章历史 +

摘要

光滑型算法已经成功地用来求解各种优化问题. 基于一类新的光滑函数族, 提出了一个带有混合线搜 索的光滑型算法求解非线性互补问题. 在适当的条件下, 证明了算法是适定的, 且保持全局 收敛性和局部超线性收敛性. 最后对提出的算法进行了数值计算. 数值结果显示出该算法的有效性.

Abstract

The smoothing-type algorithm has been successfully applied to solve various optimization problems. Based on a new class of smoothing functions, in this paper, we propose a smoothing-type algorithm with a mixed line search for solving the nonlinear complementarity problem. Under suitable conditions, the proposed algorithm is well-defined and maintains global convergence and local superlinear convergence. Preliminary numerical results are also reported and demonstrate the efficiency of the proposed algorithm.

关键词

非线性互补问题 / 光滑函数族 / 混合线搜索 / 光滑型算法 / 收敛性

Key words

nonlinear complementarity problem / a class of smoothing functions / mixed line search / smoothing type algorithm / convergence

引用本文

导出引用
倪铁 , 李永利 , 邵良杉. 求解非线性互补问题的混合光滑型算法. 系统工程理论与实践, 2014, 34(10): 2656-2665 https://doi.org/10.12011/1000-6788(2014)10-2656
NI Tie , LI Yong-li , SHAO Liang-shan. A mixed smoothing type algorithm for solving nonlinear complementarity problems. Systems Engineering - Theory & Practice, 2014, 34(10): 2656-2665 https://doi.org/10.12011/1000-6788(2014)10-2656
中图分类号: O221.2   

参考文献

[1] Facchinei F, Pang J S. Finite-dimensional variational inequalities and complementarity problems[M]. New York: Springer Verlag, 2003.
[2] Ferris M C, Pang J S. Engineering and economic applications of complementarity problems[J]. SIAM Review, 1997, 39(4): 669-713.
[3] Burke J, Xu S. The global linear convergence of a non-interior path-following algorithm for linear complementarity problems[J]. Mathematics of Operations Research, 1998, 23(3): 719-734.
[4] Chen B, Chen X. A global and local superlinear continuation-smoothing method for P0+R0 and monotone NCP[J]. SIAM Journal on Optimization, 1999, 9(3): 624-645.
[5] Chen B, Xiu N H. A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions[J]. SIAM Journal on Optimization, 1999, 9(3): 605-623.
[6] Huang Z H. The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP[J]. IMA Journal of Numerical Analysis, 2005, 25(4): 670-684.
[7] Huang Z H, Gu W Z. A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties[J]. Applied Mathematics and Optimization, 2008, 57(1): 17-29.
[8] Huang Z H, Qi L, Sun D. Sub-quadratic convergence of a smoothing Newton algorithm for the P0- and monotone LCP[J]. Mathematical Programming, 2004, 99(3): 423-441.
[9] Huang Z H, Xu S W. Convergence properties of a non-interior-point smoothing algorithm for the P_*-NCP[J]. Journal of Industrial and Management Optimization, 2007, 3(3): 569-584.
[10] Qi L, Sun D, Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems[J]. Mathematical Programming, 2000, 87(1): 1-35.
[11] Facchinei F, Jiang H, Qi L. A smoothing method for mathematical programs with equilibrium constraints[J]. Mathematical Programming, 1999, 85(1): 81-106.
[12] Huang Z H, Sun D, Zhao G Y. A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming[J]. Computational Optimization and Applications, 2006, 35(2): 199-237.
[13] Huang Z H, Zhang Y, Wu W. A smoothing-type algorithm for solving system of inequalities[J]. Journal of Computational and Applied Mathematics, 2008, 220(1-2): 355-363.
[14] Qi H D. A regularized smoothing Newton method for box constrained variational inequality problems with P0-functions[J]. SIAM Journal on Optimization, 2000, 10(2): 315-330.
[15] Qi H D, Liao L Z. A smoothing Newton method for extended vertical linear complementarity problems[J]. SIAM Journal on Matrix Analysis and Applications, 2000, 21(1): 45-66.
[16] Qi L, Zhou G. A smoothing Newton method for minimizing a sum of Euclidean norms[J]. SIAM Journal on Optimization, 2000, 11(2): 389-410.
[17] Wang P, Zhao N. Finite termination of a smoothing-type algorithm for the monotone affine variational inequality problem[J]. Applied Mathematics and Computation, 2009, 211(1): 177-184.
[18] Zhou G, Sun D, Qi L. Numerical experiments for a class of squared smoothing Newton methods for box constrained variational inequality problems[M]//Fukushima M, Qi L. Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods. Kluwer Academic Publishers, Boston, 1999: 421-441.
[19] Huang Z H, Han J, Chen Z. A predictor-corrector smoothing Newton algorithm, based on a new smoothing function, for solving the nonlinear complementarity problem with a P0 function[J]. Journal of Optimization Theory and Applications, 2003, 117(1): 39-68.
[20] Chen B, Harker P T. A non-interior-point continuation method for linear complementarity problem[J]. SIAM Journal on Matrix Analysis and Applications, 1993, 14(4): 1168-1190.
[21] Kanzow C. Some noninterior continuation methods for linear complementarity problems[J]. SIAM Journal on Matrix Analysis and Applications, 1996, 17(4): 851-868.
[22] Smale S. Algorithms for solving equations[C]//Proceedings of the International Congress of Mathematicians (Berkeley, 1986), Providence, RI: American Mathematics Society, 1987: 172-195.
[23] Huang Z H, Ni T. Smoothing algorithms for complementarity problems over symmetric cones[J]. Computational Optimization and Applications, 2010, 45(3): 557-579.
[24] Ni T, Liu X H, Gu W Z. Convergence of a smoothing Newton algorithm for linear programming over symmetric cones[R]. Technique Report, Department of Mathematics, School of Science, Tianjin University, China, 2009.
[25] Ni T, Gu W Z. Smoothing Newton algorithm for symmetric cone complementarity problems based on a one-parametric class of smoothing functions[J]. Journal of Applied Mathematics and Computing, 2011, 35(1-2): 73-92.
[26] Kojima M, Megiddo N, Noma T. Homotopy continuation methods for nonlinear complementarity problems[J]. Mathematics of Operations Research, 1991, 16(4): 754-774.
[27] Gowda M S, Tawhid M A. Existence and limiting behavior of trajectories associated with P0 equations[J]. Computational Optimization and Applications, 1999, 12(1-3): 229-251.
[28] Palais R S, Terng C L. Critical point theory and submanifold geometry[M]. Berlin: Springer-Verlag, 1988.
[29] Facchinei F, Kanzow C. Beyond monotonicity in regularization methods for nonlinear complementarity problems[J]. SIAM Journal on Control and Optimization, 1999, 37(4): 1150-1161.
[30] 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(7): 2207-2214.
[31] Jiang H, Qi L. A new nonsmooth equations approach to nonlinear complementarity problems[J]. SIAM Journal on Control and Optimization, 1997, 35(1): 178-193.
[32] Kanzow C. Some equation-based methods for the nonlinear complementarity problems[J]. Optimization Methods and Software, 1994, 3(4): 327-340.
[33] Chen X, Ye Y. On smoothing methods for the P0 matrix linear complementarity problem[J]. SIAM Journal on Optimization, 2000, 11(2): 341-393.
[34] Huang Z H, Miao X H, Wang P. A revised cut-peak function method for box constrained continuous global optimization[J]. Applied Mathematics and Computation, 2007, 194(1): 224-233.
PDF(454 KB)

240

Accesses

0

Citation

Detail

段落导航
相关文章

/