A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION

doi:10.4208/jcm.1009-m3216

Based on a reformulation of the complementarity problem as a system of nonsmooth equations by using the generalized Fischer-Burmeister function, a smoothing trust region algorithm with line search is proposed for solving general (not necessarily monotone) nonlinear complementarity problems. Global convergence and, under a nonsingularity assumption, local Q-superlinear/Q-quadratic convergence of the algorithm are established. In particular, it is proved that a unit step size is always accepted after a finite number of iterations. Numerical results also confirm the good theoretical properties of our approach.

Key words: Nonlinear complementarity problem, Smoothing method, Trust region method, Global convergence, Local superlinear convergence

CLC Number:

90C33
90C30

[1] P.T. Harker, J.S. Pang, Finite dimensional variational inequality and nonlinear complementarityproblems: A survey of theory, algorithms and applications, Math. Program., 48(1990), 161-220.

[2] M.C. Ferris, J.S. Pang, Engineering and economic application of complementarity problems, SIAM Rev., 39 (1997), 669-713.

[3] H. Jiang, M. Fukushima, L. Qi, D. Sun, A trust region method for solving generalized complementarityproblem, SIAM J. Optimiz., 8 (1998), 140-157.

[4] J.-S. Chen, S. Pan, A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for P₀-NCPs, J. Comput. Appl. Math., 220 (2008), 464-479.

[5] J.-S. Chen, The semismooth-related properties of a merit function and a descent method for thenonlinear complementarity problem, J. Global Optim., 36 (2006), 565-580.

[6] F. Facchinei, J. Soares , A new merit function for nonlinear complementarity problems and arelated algorithm, SIAM J. Optimiz., 7 (1997), 225-247.

[7] C. Kanzow , Nonlinear complementarity as unconstrained optimization, J. Optimiz. Theory App.,88 (1996), 139-155.

[8] P. Tseng, Global behavior of a class of merit functions for the nonlinear complementarity problem,J. Optimiz. Theory App., 89 (1996), 17-37.

[9] L. Qi, Trust region algorithms for solving nonsmooth equation, SIAM J. Optimiz., 5 (1995),219-230.

[10] O. L. Mangasarian, Equivalence of the complementarity problem to a system of nonlinear equations,SIAM J. Appl. Math., 31 (1976), 89-92.

[11] J.J. Moré, Global methods for nonlinear complementarity problems, Math. Oper. Res., 21 (1996),589-614.

[12] B.C. Eaves, On the basic theorem of complementarity, Math. Program., 1 (1971), 68-75.

[13] F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.

[14] P.T. Harker, B. Xiao, Newton method for the nonlinear complementarity problem: A Bdifferentiableequation approach, Math. Program., 48 (1990), 339-357.

[15] S.M. Robinson, Homeomorphism conditions for normal maps of polyhedra, in Optimization andNonlinear Analysis, A.Loffe, M.Marcus and S.Reich(Eds.), Pitman Research Notes in MathematicsSeries 244, 1992, 240-248.

[16] S.M. Robinson, Sensitivity analysis of variational inequalities by normal-map techniques,in Nonlinear Variational Inequalities and Network Equilibrium Problems, F.Giannessi andA.Maugeri(Eds.), Plenum Press: New York, 1995, 257-269.

[17] L. Zhang, Z. Gao, Superlinear/quadratic one-step smoothing Newton method for P0-NCP withoutstrict complementarity, Math. Method. Oper. Res., 56 (2002), 231-241.

[18] X. Chen, L. Qi, D. Sun, Global and superlinear convergence of the smoothing Newton methodand its application to general box constrained variational inequalities, Math. Comput., 67 (1998),519-540.

[19] J.-S. Pang, A B-differentiable equations based, globally, and locally quadratically convergent algorithmfor nonlinear problems, complementarity and variational inequality problems, Math. Program.,51 (1991), 101-131.

[20] C. Kanzow, H. Pieper, Jacobian smoothing methods for general nonlinear complementarity problems,SIAM J. Optimiz., 9 (1999), 342-373.

[21] L. Qi, C-Differentiability, C-Differential Operators and Generalized Newton Methods, Tech. Report,School of Mathematics, The University of New South Wales, Sydney, Australia, January1996.

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

[23] J. Nocedal, Y.X. Yuan, Combining trust region and line search techniques, in: Y. Yuan (Ed.),Advances in Nonlinear Programming, Kluwer Academic Publishers, Boston, MA, 1998, 153-175.

[24] C. Kanzow, H.D. Qi, A QP-free constrained Newton-type method for variational inequality problems,Math. Program., 85 (1999), 81-106.

[25] L. Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper.Res., 18 (1993), 227-244.

[26] J.E. Dennis, R.B. Schnabel, Numerical Methods for Unconstrained Optimization and NonlinearEquations, Prentice-Hall, Englewood Cliffs, NJ, 1983(reprinted by SIAM, Philadelphia, 1996).

[27] F. Facchinei, J.-S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems,Vol. I and II. New York: Springer, 2003.

[28] B.H. Ahn, Iterative methods for linear complementarity problem with upperbounds and lowerbounds,Math. Program., 26 (1983), 265-315.

[29] J.-S. Pang, S.A. Gabriel, NE/SQP: A robust algorithm for the nonlinear Complementarity Problem,Math. Program., 60 (1993), 295-337.

[30] C. Kanzow, Some equation-based methods for the nonlinear complementarity problem, Optim.Method. Softw., 3 (1994), 327-340.

[31] H. Jiang, L. Qi, A new nonsmooth equations approach to nonlinear complementarity problems,SIAM J. Control Optim., 35 (1997), 178-193.

[32] S.P. Dirkse, M.C. Ferris, MCPLIB: A collection of nonlinear mixed complementarity problems,Optim. Method. Softw., 5 (1995), 123-156.

[1]	Mingming Zhao, Yongfeng Li, Zaiwen Wen. A STOCHASTIC TRUST-REGION FRAMEWORK FOR POLICY OPTIMIZATION [J]. Journal of Computational Mathematics, 2022, 40(6): 1004-1030.
[2]	Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[3]	Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[4]	Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.
[5]	Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704.
[6]	Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(6): 776-791.
[7]	Fan Jiang, Deren Han, Xiaofei Zhang. A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS [J]. Journal of Computational Mathematics, 2018, 36(3): 351-373.
[8]	Caixia Kou, Zhongwen Chen, Yuhong Dai, Haifei Han. AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY [J]. Journal of Computational Mathematics, 2018, 36(3): 331-350.
[9]	Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.
[10]	Liyan Qi, Xiantao Xiao, Liwei Zhang. A PARAMETER-SELF-ADJUSTING LEVENBERG-MARQUARDT METHOD FOR SOLVING NONSMOOTH EQUATIONS [J]. Journal of Computational Mathematics, 2016, 34(3): 317-338.
[11]	Jinkui Liu, Shengjie Li. SPECTRAL DY-TYPE PROJECTION METHOD FOR NONLINEAR MONOTONE SYSTEM OF EQUATIONS [J]. Journal of Computational Mathematics, 2015, 33(4): 341-355.
[12]	Hongru Xu, Kekun Huang, Shuilian Xie, Zhe Sun. RESTRICTED ADDITIVE SCHWARZ METHOD FOR A KIND OF NONLINEAR COMPLEMENTARITY PROBLEM [J]. Journal of Computational Mathematics, 2014, 32(5): 547-559.
[13]	Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490.
[14]	Fusheng Wang, Chuanlong Wang, Li Wang. A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM [J]. Journal of Computational Mathematics, 2012, 30(3): 262-278.
[15]	Lingfeng Niu and Yaxiang Yuan. A NEW TRUST-REGION ALGORITHM FOR NONLINEAR CONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2010, 28(1): 72-86.

Viewed

Full text

Abstract

A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION

扫码分享