Researches On The Predictor-corrector Interior-point Algorithm

In 1984, Karmarkar presented a new algorithm for linear programming—Karmarkar's algorithm. It is not only a algorithm with polynomial complexity, superior to the simplex method in theory, but also more efficient than the simplex method in practice. A very important thing was that it established the connection between linear programming and nonlinear programming. Different from the simplex method, which chooses the solution along the boundary of the feasible region, Karmarkar's algorithm is based on the structure of the simplex method, which starts from an originally feasible interior-point, moves in the feasible region to the optional solution following the steepest descent direction. So Karmarkar's algorithm is also called interior-point method.This thesis is devoted to researching on the predictor-corrector interior-point algorithm. Firstly, we make this algorithm be easily applied to linear programming and convex quadratic programming with box constraints. Secondly, we give some new ideas to the algorithm; By taking the modified centered Newton direction in the corrector step, it not just shows the method is a polynomial-time algorithm but reduces the duality gap at each iteration.In this thesis, we separately present a polynomial predictor-corrector interior-point algorithm for linear programming with box constraints and convex quadratic programming with box constraints based on [46] and [48]. In the predictor step, we take the Newton direction. However, the direction in the corrector step is a modified centered Newton direction. And it is shown that the method is a polynomial-time algorithm and the iteration complexity is O{n^1/2ln ε^-1) . In addition, numerical tests are included at the base of MATLAB. The numerical examples are small on size, but the results show the algorithm is efficient and effective.