Primal-Dual Methods and Infeasibility Detectors for Nonlinear Programming Problems

In this paper we present several "infeasible-start" path-following and potential-reduction primal-dual interior-point methods for nonlinear conic problems. These methods try to find a recession direction of the feasible set of a self-dual homogeneous primal-dual problem. The methods under consideration generate an E -solution for an E- perturbation of an initial strictly (primal and dual) feasible problem in O [square root. v ln(v /e pf)] iterations, where v is the parameter of a self-concordant barrier for the cone, E is a relative accuracy and pf is a feasibility measure. We also discuss the behavior of path-following methods as applied to infeasible problems. We prove that strict infeasibility (primal or dual) can be detected in O [square root. v ln(v /p)] iterations, where p. is a primal or dual infeasibility measure.