Researches On The Combined Homotopy Interior Point Method

In 1947,Danzig presented the conception of linear programming and the famous simplex algorithm. Although the simplex method is efficient in practical application, it is not the polynomial time algorithm and has the lower calculation efficiency in theory. In 1978 the first polynomial algorithm for the linear programming problem, the ellipsoidal method, was presented by L.G Khachiyan. But unfortunately the practical implementations of the algorithm have been irremediable inefficient than the simplex method. It resulted in great impact on the theory of complexity so that many scholars tried to design a polynomial algorithm with better calculation efficiency for solving linear programming. In 1984, with the skill of the potential function and the projection transform, Karmarkar studied a new algorithm for linear programming— Karmarkar's algorithm. Karmarkar's algorithm not only has a better polynomial complexity than the ellipsoid method, but is also a challenging competitor of the simplex method in practice, especially for large scale problems. Different from the simplex method, which choose the optional point along the boundary of the feasible region, Karmarkar's algorithm is based on the structure of the simplex method, which starts from the originally feasible interior-point, walks up in the feasible region to the optional point following the steepest descent direction. So Karmarkar's algorithm is also called interior-point method. Since the publication of Karmarkar's paper, interior point methods theory has been a very active research direction in mathematical programming.In this thesis we research on the combined homotopy interior-point method and present the combined homotopy interior-point method based on predictor-corrector algorithm for linear programming and linear complementarity problem . Among the former path-following algorithms, we required the logarithm barrier function satisfied the condition of strictly convex. But this condition is too difficult to apply in nonlinear programming problem. In the thesis, we combine homotopy method with interior-point method and gain better results. The numerical experimentation using in MATLAB indicates our algorithm is convergent.