Research On The Regularization Path-Following Algorithm For Complementarity Problems

The complementarity problem is one of the important interdisciplinary research topics between computational mathematics and optimization.On the one hand,the complementarity problem often appears in practical problem models of computational mathematics such as the stock option study in economics,the frictional contact force analysis in physics and the Nash equilibrium in operational research.On the other hand,the first-order optimality conditions(KKT conditions)for constrained optimization problems can be also transformed by complementarity problems.In other words,the study of complementarity problems can promote the further development of constrained optimization.In this paper,we consider the residual regularization path-following method with the trust-region updating strategy to solve the linear complementarity problem.For the non-negative constrained nonlinear equations transformed by the linear complementarity problem,in order to improve the robustness of the algorithm,we design a residual regularization parameter including the feasibility and complementarity residual of the linear complementarity problem based on the pathfollowing method.Then,for the continuous Newton flow with the regularization parameter,we revise the traditional continuous Newton method,and construct an ODE method based on implicit Euler method to trace the continuous Newton flow of nonlinear equations.And we use the explicit linear approximation for the continuous Newton flow to obtain the corresponding discrete iterative formula.We use the infeasible interior-point algorithm to preserve the non-negative constraint of linear complementarity problem.And then,we obtain a new continuous Newton method for nonlinear equations transformed by linear complementarity problems.After that,we introduce a time-stepping selection based on the trust-region updating strategy to overcome the shortcoming of the line search method,which consumes the unnecessary trial steps in the transient-state phase.This time-stepping selection further improvs the efficiency of the algorithm.Finally,we obtain a residual regularization path-following method,which has the global convergence of homotopy continuation methods and the local fast rate of convergence of traditional optimization methods.Numerical results show that the new algorithm is robust and efficient for the linear complementarity problem,especially for the dense cases.And it is more robust and faster than some state-ofthe-art solvers such as the built-in subroutines PATH and MILES of the commercial software GAMS v28.2(2019)environment.By combining with the research and design experience of linear complementarity problem algorithm,in this paper,we further consider the algorithm for the nonlinear complementarity problem.First of all,the nonlinear complementarity problem is directly transformed into nonlinear equations,whose Jacobian matrix is singular in the degenerate case.In order to overcome this shortcoming,we introduce the Fischer-Burmeister semi-smoothing function(the FB function)to construct the FB regeneration equation.Next,we further introduce the smoothing parameter to smooth the FB regeneration equation.The nonlinear equations based on the FB regeneration equation with the smoothing parameter has the good non-singular property.After that,we extend the residual regularization continuation Newton method for solving the above nonlinear equations.Finally,in the numerical experiments,we found that there exists a class of nonlinear complementarity problems with extremely ill-conditions.For the iteration points in solving such problems,even if the gap between the components of the initial point xk is small,the gap between the corresponding components of the point yk will be extremely great.In this case,the condition number of the Jacobian matrix of nonlinear equations will be large,which leads to numerical difficulties in solving the linear equations of the Newton flow.In order to overcome this difficulty,we design a scale preprocessing technique for this class of test problems with extremely ill-conditioned,this technique further promotes the robustness of the above algorithm.So far,we obtain a nonlinear complementarity problem algorithm(CNMFN)based on the FB regeneration equation and the scale preprocessing technique.Numerical results show that the algorithm(CNMFN)has better performance than PATH and MILES solvers for nonlinear complementarity problems,and has even better performance for some test problems with more complex nonlinear constraints.