The Smoothing Newton Algorithms For Solving Complementarity Problems

In the research area of optimization．there has a fundamental and im—portant problem———complementarity problems The subject made significantprogress and came forth various forms of complementarity problems It has awide range of important applications in mechanics，traffic，economics，finance，control and other fields The studies on complementarity problems include twoaspects：theory and algorithm The former mainly investigates the existence，uniqueness，stability and sensitivity analysis of solution；and the latter focuseson how to design effective algorithms However，it is difficult to solve this classof problems before 1990’S Various reformulation methods of complementarityproblems were proposed in the mid 1990’S．and obtained satisfactory compu—rational effect In particular，smoothing Newton algorithms is particularlyoutstanding in these methods We aim at the studies on smoothing Newtonalgorithm for solving complementarity problems The thesis is organized asfollows：Firstly，for the symmetric cone complementarity problems，by makinguse of the technique of Euclidean Jordan algebras，we do the following twoworks of research On the one hand．we first investigate a regularized CHKSsmoothing function in the context of symmetric cones and show that it is CO—ercive under suitable assumptions We then extend two generic frameworks ofsmoothing algorithms to solve the complementarity problems over symmetriccones，and prove the proposed algorithms are globally convergent under suit—able assumptions We also give a specific smoothing Newton algorithm whichis globally and locally quadratically convergent under suitable assumptionsPreliminary numerical results for second—-order cone complementarity prob—-lems are reported On the other hand，based on regularized CHKS smoothingfunction given above．we propose a one—parametric class of smoothing func—tions in the context of symmetric cones，and show that it is coercive under suitable assumptions Based on this class of smoothing functions．a smooth—ing Newton algorithm is extended to solve the complementarity problems oversymmetric cones，and it is proved that the proposed algorithm is globally andlocally superlinearly convergent under suitable assumptions Preliminary nu—merical results fOr randomly generated second—order cone programs and severalpractical second—order cone programs from the DIMACS library are reportedIn comparison with the numerical experiments in many papers，our algorithmiS much better to soiile extentSecondly．we propose a smoothing Newton algorithm fOr solving the non—linear complementarity problems with a non—monotone line search We showthat the proposed algorithm is globally and locally superlinearly convergentunder suitable assumptions Our algorithm is effective fOr the problems wetested In particular，the non—monotone version of algorithm is more effectivethan its monotone version fOr the problems we testedFinally．we present a modified version of the Huang—qi—Sun’S smoothingNewton algorithm algorithm given in[49]The new algorithm has the sameglobal convergence as the one in[49]and possesses the~llowing local fastconvergence properties：·For the Po-LCP，if an accumulation point of the iteration sequence satisfies a nonsingularity condition，then the whole iteration sequence converges to this accumulation point quadratically·For the P*-LCP，if the solution set of the LCP is nonempty and bounded；and an accumulation point of the iteration sequence sat—isfies a strict complementarity condition．then the whole iteration sequence converges to this accumulation point quadratically...