Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems

In this paper we present several "infeasible-start" path-following and pote ntial-reduction primal-dual interior-point methods for nonlinear conic prob lems. These methods try to find a recession direction of the feasible set o f a self-dual homogeneous primal-dual problem. The methods under considerat ion generate an epsilon-solution for an epsilon-perturbation of an initial strictly (primal and dual) feasible problem in O(root nu ln nu/epsilon rho( f)) iterations, where nu is the parameter of a self-concordant barrier for the cone, epsilon is a relative accuracy and rho(f) is a feasibility measur e. We also discuss the behavior of path-following methods as applied to infeas ible problems. We prove that strict infeasibility (primal or dual) can be d etected in O(root nu ln nu/rho) iterations, where rho. is a primal or dual infeasibility measure.