A Strongly Sub-Feasible Primal-Dual Interior Point Algorithm For Nonlinear Inequality Constrained Optimization

In this thesis, we consider the nonlinear inequality constrained optimization problems. We know that primal-dual interior point methods are one of the important methods of feasible directions for solving this kind of problems. At each iteration, the methods only need to solve linear equation systems in stead of QP subproblem to obtain feasible and descent direction. And "working set" technique for determining the active set is often used to reduce computational cost. At the same time, strongly sub-feasible direction methods are one of effective methods for solving the problems starting with an infeasible initial point.In this work, combining the properties of primal-dual interior point methods and the strongly sub-feasible method, by means of a new "working set" technique, we present a new primal-dual interior point algorithm for inequality constrained optimization. The main properties of the new algorithm are described as follows: (i) At each iteration, the algorithm solves only two or three reduced systems of linear equations with a common coefficient matrix; (ii) The initial iteration point can be chosen arbitrarily and the coefficient matrix is uniformly nonsingular. After finite iterations, the iterate becomes an interior point of the feasible set, then the searching direction is feasible and the objective function is monotone decreasing; (iii) Under suitable assumptions, the proposed algorithm possesses global and superlinear convergence. In particular, the positive definiteness assumption on the Hessian estimate is relaxed. Finally, promising numerical results are reported.