Algorithms For Solving Linear And Nonlinear Complementarity Problems

Complementarity problems are closely related with the linear programming and nonlinear programming problems, have found wide applications, such as in mechanics, engineering, economics, operations research, finance. Theoretically, we should study the solution existence and uniqueness of the complementarity problems. Algorithmically, we should design some efficient algorithms to find its solution, particularly, based on the existent technique of smooth optimization, it is expected to. construct some different smoothing functions for the complementarity problems such that the corresponding smoothing algorithm is developed.The main contributions in this paper are as follows.1. For the linear complementarity problems with special matrices, we present some results on the solution existence and uniqueness. The existent form and identifying methods of equilibrium solution to the linear complementarity problems were considered from the perspective of convex decomposition. Based the analysis of the complementarity matrix, we obtain the necessary and sufficient conditions of equilibrium solution to the linear complementarity problems. A direct algorithm was designed to solve the linear complementarity problems. Some examples are solved to show the efficiency of the algorithm.2. We obtain a smoothing function from general derivative function of the absolute value function and analysis the good properties of the smoothing function. Based on the smoothing function, we provide an inexact smoothing Newton method for solving nonlinear complementarity problems. Under the assumption that the level set is bounded, we prove the global convergence and local superlinear convergence of the algorithm. Some numerical experiments indicate that our algorithm is effective for the given problems.3. A smoothing function is obtained by disturbing last items of the original smoothing function, and we analysis the degree of approximation of the smoothing function. A new disturbing term is added to get the nonsingular of the smoothing function. We modified the original algorithm by increasing of nonsingular judgment. Some numerical experiments show that our algorithm is feasibility. We analysis the inexact parameter in the inexact smoothing Newton method through numerical experiments.