On the Complexity of a Practical Interior-Point Method
Stephen G. Nash and Ariela Sofer
The theory of self-concordance has been used to analyze
the complexity of interior-point methods based on
Newton's method. For large problems, it may be
impractical to use Newton's method; here we analyze a
truncated-Newton method, in which an approximation to
the Newton search direction is used. In addition,
practical interior-point methods often include
enhancements such as extrapolation that are absent
from the theoretical algorithms analyzed previously.
We derive theoretical results that apply to such an
algorithm, an algorithm similar to a sophisticated
computer implementation of a barrier method. The
results for a single barrier subproblem are a
satisfying extension of the results for Newton's
method. When extrapolation is used in the overall
barrier method, however, our results are more limited.
We indicate (by both theoretical arguments and
examples) why more elaborate results may be
difficult to obtain.
to appear in SIAM Journal on Optimization
Contact: [email protected]
![[PS]](../../InteriorPoint/gif/PS.gif)
![[IP PAGE]](../../InteriorPoint/gif/HOME.gif)
![[SEARCH AGAIN]](../../InteriorPoint/gif/SEARCH.gif)