Research On Predictor-corrector Algorithms For Complementarity Problems

Complementarity problem is a kind of important mathematical programmingproblem. It exists in real life widely. As the complementary problem is closely linkedwith mathematical branches, such as optimization theory, variational inequalities,balance problems, generalized equations and game theory, so this issue attractedmany scholars’ attention, and they researched it intensively. The study ofcomplementary problem is divided into two aspects of theory and algorithm.Theoretical research is to study the problem of the existence, uniqueness, stability ofsolutions and error analysis. Algorithm focuses on how to construct effectivealgorithms and analyze the local convergence, the global convergence and thecomplexity of the algorithm and so on.Predictor-corrector algorithm is a widely used algorithm which is to solve conicprogramming. This paper focuses on completing the following tasks based on thepredictor-corrector algorithm of complementary problem:Firstly, we briefly introduce the background, significance, mathematical modelsof complementary problems. At the same time, this paper also describes the researchprogress and status of linear complementarity problems and symmetric conecomplementarity problems.Then, Ai wen-bao[31] presents a neighborhood following algorithm for linearprogramming, Chang-he Liu[32] adds a second-order corrector step based on Aiwen-bao[31] and presents the Mehrotra-type predictor-corrector algorithm for linearprogramming. This paper extends Chang-he Liu algorithm to monotone linearcomplementarity problem and proposes a Mehrotra-type predictor-corrector algorithmfor monotone linear complementarity problems. As the the iterative direction ofmonotone linear complementarity problems is not orthogonal, so the theoreticalanalysis of algorithm is complicated. By analyzing the algorithm, we show thealgorithm with complexity.Finally, we serve the modified Newton step as the predictor step of thepredictor-corrector algorithm based on [34], and add a corrector step, we conduct apredictor-corrector algorithm based on modified Newton for solving, we select themodified Newton step as predictor step, With full NT step to iterate, corrector steps areused to make iterative points near the center of the path and reduce the duality gap, the algorithm is repeated until we find approximate solutions. By analyzing the algorithm,if the starting point is feasible, the iteration of the algorithm will terminate after at most.