Infeasible Start Interior-Point Primal-Dual Methods in Nonlinear Programming

In this paper we present several infeasible start path-following and potential-reduction primal-dual interior-point methods for nonlinear conic problems. These methods are trying to find a recession direction of a shifted homogeneous primal-dual problem. The methods under consideration generate an E-solution for an E-perturbation of the initial strictly feasible primal-dual problem in O [ (square root v) ln (V/ sigma E ], where V is a parameter of a self-concordant barrier for the cone, E is a relative accuracy and [sigma] is a "feasibility measure". We discuss also the behavior of the path-following schemes as applied to infeasible problems. We consider two types of infeasibility: strongly infeasible problems and strictly ill-posed problems. We prove that the strong infeasibility can be detected in O [ (square root v) ln (V/ sigma E ] iterations of a path-following scheme, where [sigma] is the degree of infeasibility.