Smoothing Homotopy Algorithm For Solving Two Kinds Of Complementarity Problems

Complementarity problem is an important and basic class of mathematical optimization problem,which has wide applications in many field such as mechanics, economy, transportation, financial and so on.According to the different variables satisfy different conditions and complementary relationship in different forms, complementarity problem can be divided into a number of different types.In this paper, we mainly study two kinds of very important complementarity problems: the nonlinear complementarity problem and the second-order cone complementarity problem.At present, the research on these two kinds of complementarity problems has achieved remarkable success, whether in theoretical research or algorithm analysis. The most commonly used algorithms including the interior point method, smoothing newton method, semi-smooth newton method, benefit function method, homotopy methods and so on, But we find that it is hard to prove the global convergence of those methods or only under strong conditions to achieve global convergence. So we use two new smoothing homotopy methods to solve the nonlinear complementarity problems and second-order cone complementarity problems in this paper. The paper presents the important elements: smoothing homotopy methods based on CHKS functions and based on FB functions. A distinctive advantage of the homotopy method is that the global convergence of the algorithm can be proven for almost any starting point.Moreover, comparing with the existing homotopy methods based on KKT conditions.Some of them are proven to be globally convergent under weaker assumptions,and some of them have higher efficiency under the same globally convergent conditions.The main contents are as follows: First, we review the development situation of nonlinear complementarity problems and second-order cone complementarity problems and traditional methods for solving two problems. Secondly, by analyzing the nonlinear complementarity problems, we introduce the related basic concepts. Again, this paper presents the important elements: the smooth homotopy algorithm based on CHKS functions and the smooth homotopy algorithm based on FB functions. We also analyze the convergence of these two algorithms. Finally, numerical results indicate that our algorithm is quite promising and more efficient compared with other algorithms.