Infeasible-start 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 ε-solution for an ε-perturbation of an initial strictly (primal and dual) feasible problem in O(√(ν) ln ν/ερf) iterations, where ν is the parameter of a self-concordant barrier for the cone, ε is a relative accuracy and ρf 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(√(ν) ln ν/ρ.) iterations, where ρ. is a primal or dual infeasibility measure.