• Original Articles •

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

Xuebin Wang, Changfeng Ma, Meiyan Li

1. School of Mathematics and Computer Science, Fujian Normal University, Fuzhou 350007, China; School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin 541004, China
• Received:2009-09-27 Revised:2010-03-22 Online:2011-05-15 Published:2011-05-15
• Supported by:

The work was supported by the National Natural Science Foundation of China (11071041) and Fujian Natural Science Foundation (2009J01002).

Xuebin Wang, Changfeng Ma, Meiyan Li. A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION[J]. Journal of Computational Mathematics, 2011, 29(3): 261-286.

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.

CLC Number:

 [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 P0-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] 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. [2] 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. [3] 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. [4] Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704. [5] Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM [J]. Journal of Computational Mathematics, 2018, 36(6): 776-791. [6] 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. [7] 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. [8] Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422. [9] 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. [10] 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. [11] 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. [12] 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. [13] 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. [14] Lingfeng Niu and Yaxiang Yuan. A NEW TRUST-REGION ALGORITHM FOR NONLINEAR CONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2010, 28(1): 72-86. [15] Duoquan Li. A NEW SQP-FILTER METHOD FOR SOLVING NONLINEAR PROGRAMMING PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 609-634.
Viewed
Full text

Abstract