On the Complexity of a Practical Interior-Point Method

By Stephen G. Nash and Ariela Sofer

The theory of self-concordance in convex optimization 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.

“On the Complexity of a Practical Interior-Point Method”,  SIAM Journal on Optimization, 8 (1998), pp. 833-849.

• Systems Engineering & Operations Research Dept.
• School of Information Technology and Engineering
• George Mason University

(snash@gmu.edu)