Researches On The Predictor-corrector Smoothing Method

The classical method for the solution of linear programs is Dantzig's simplex algorithm and interior-point methods. Although the simplex method is efficient in practical application, it is not the polynomial time algorithm and has the lower calculation efficiency in theory, which led to the research on polynomial algorithm for the linear programming problem. In 1978 the first polynomial algorithm for the linear programming problem, the ellipsoidal method, was presented by L.G Khachiyan. In 1984, N.Karmarkar found a new algorithm for linear programming—Karmarkar's algorithm. Different from the simplex method, which choose the optimal point along the boundary of the feasible region, Karmarkar's algorithm is based on the constructure of the simplex method, which starts from the originally feasible interior-point, walks up in the feasible region to the optimal 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.Because interior-point methods have to start from the interior of the feasible region and guarantee the positivity of the primal and dual variables by an appropriate line search,so it is very difficult to find the initial point. More recently, so-called non-interior point methods(also called smoothing-type methods)have been investigated, from which the most typically one is non-interior-point path-following algorithm. Smoothing functions have been joined in these methods, using the properties of the smoothing functions, these methods do not necessarily belong to positive orthant.This thesis is devoted to researching on the predictor-corrector smoothing methods. A predictor-corrector smoothing method for convex quadratic programs is proposed. The method first reformulate the central path conditions as a nonlinear system of equations and then apply Newton's method to this reformulated system. In this way, smoothing method avoid the explicit inequality constraints, and therefore the iterates generated by this method do not necessarily belong to the positive orthant. It is very easy to find the initial point for the method. The global convergence and local quadratic convergence results for these algorithms are established and some numerical test also included.