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.
Contact: [email protected]
Technical Report No. 1156, School of Operations Research and
Industrial Engineering,
Cornell University, Ithaca, NY 14853-3801.
![[POSTSCRIPT]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)