
232 Introduction to Linear Optimization and Extensions with MATLAB
R
6.3.3.1 Polynomial Complexity of Short-Step Path-Following
Methods
Now we develop the results leading to the polynomial complexity of a par-
ticular variant of a path-following method called the short-step primal-dual
path-following method as an illustration of use of the lemmas above to show
polynomial complexity for primal-dual interior point methods. We will refer
to this method in shorthand as SSPF. Recall that general primal-dual interior
point strategies follow the central path Γ in the direction of decreasing µ, and
in particular at an iteration k will generate a search direction ...