The Large-update Primal-dual Interior-point Algorithms For A Class Of Complementarity Problems Based On Kernel Functions

Complementarity problem is a class of the mathematical problems widely used in economic analysis and traffic equilibrium. Its research has important theoretical value and practical significance. Interior-point algorithm for solving various optimization problems is an efficient algorithm. Since the first practical polynomial interior-point algorithm was presented in 1984, interior-point algorithm has become one of the active areas of research. After 20 years of hard work, interior-point method has achieved fruitful results. At present, some of them have become the base of software package.This article majors in discussing an important class of complementarity proble-ms—P* (κ) complementarity problem. New algorithms are designed for P* (κ) linear complementarity problem and P* (κ) nonlinear complementarity problems, respectively.Based on two different kernel functions, the favorable polynomial iteration complexity for new methods is proved.Full-text is divided into four chapters, the concrete contents are arranged as follows. The first chapter introduces the preliminary knowledge and the research situations of the interior point methods. The second chapter designs two new methods for P* (κ) linear complementarity. By means of two different kernel functions, it gives the proof of the complexity. The extension of the second algorithm in the second chapter for P* (κ) nonlinear complementarity problems is studied in third chapter. With the assumption of the Relative Lipschitz Condition, it obtains the polynomial complexity. Finally, a conclusion and some further researches are made in fourth chapter.