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

Yurii Nesterov, Yinyu Ye, and Michael Todd

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 $\epsilon$-solution for an $\epsilon$-perturbation of an initial strictly (primal and dual) feasible problem in $O(\sqrt{\nu} \ln {\nu \over \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 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(\sqrt{\nu} \ln {\nu \over \rho_{\cdot}})$ iterations, where $\rho_{\cdot}$ is a primal or dual infeasibility measure.


Technical Report No. 1156, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY 14853-3801.