Study On A Sub-problem In The Two-step-size Primal-dual Interior Point Algorithm

R.W.Cottle proposed the "Complimentarity problem" in his PhD degree paper "Nonlinear Programs with Positively Bounded Jacobians"in 1964. This problem was first referred to as "composite problem", "fundamental problem" or "complementarity pivot problem". Karmarkar proposed an interior point method for linear problem in 1984. This method not only has a polynomial complexity, but also is highly efficient in practice. After 20 years of hard work of many mathematicians, interior point method has achieved great improvement. Because linear programming is just a special case of Complimentarity problem, interior point method is generalized to solve it.The aim of this paper is to analyze the two-step-size problem, which was presented in a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. The new algorithm treats the classical Newton direction as the sum of two other directions, and the two directions will be equipped with different step sizes, which are denoted respectively byα₁ andα₂. In this paper, the new algorithm and the properties ofα₁ andα₂ will be introduced first. After the introduction, we discuss two ways which are used to find out the step sizes. Two Matlab programs about the algorithm will be given in the fourth chapter . Based on the numerical results we get from the operation of the programs, we can say that the method in which we setα₂ = 1, and then use bisection to obtainα₁ is feasible.