On the Complexity of a Practical Interior-Point Method.
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, one 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.
Introduction
. In their 1993 book [16], Nesterov and Nemirovsky derive complexity
results for convex optimization problems. Their basic algorithm is an interior-point
method where each subproblem is solved using a damped Newton method. If a
nonlinear optimization problem is large (and hence complexity is an important issue)
then Newton's method is not normally used because of its computational costs, so
these results might be considered primarily of theoretical interest. Our goal in this
paper is to derive comparable complexity results for algorithms that more closely resemble
practical interior-point algorithms for large-scale optimization (see, e.g., [1, 9,
10, 11, 13, 19, 23]).
The interior-point method we analyze is strongly related to the barrier method
in [13]. The essential features of this algorithm are that each barrier subproblem is
solved approximately using a truncated-Newton method; then the solutions to the
subproblems are extrapolated to obtain an initial guess for a new subproblem. Many
of the enhancements discussed in [13]-such as preconditioning, a specialized matrix-vector
product, and a numerically stable formula for the search direction-fit into the
theoretical framework used here. The major exception is the line search (see below).
We derive a bound on the number of truncated-Newton iterations required to
solve a barrier subproblem to within some tolerance. Each truncated-Newton iteration
involves the approximate solution of the Newton equations via (say) the conjugate-gradient
method, requiring at most O(n 3 ) computations in exact arithmetic, although
typically the number of computations would be O(n) or O(n 2 ), in problems where the
Hessian matrix is sparse. In the algorithm analyzed here, a prescribed step length is
used, so there is no line search. (Here is where the theoretical and practical algorithms
*Received by the editors Month? Date?, 199?; accepted for publication (in revised form) Month?
1997.
yOperations Research and Engineering Department, George Mason University, Fairfax, VA
22030. The work of this author was supported by National Science Foundation grant DMI-9414355.
zOperations Research and Engineering Department, George Mason University, Fairfax, VA
22030. The work of this author was supported by National Science Foundation grant DMI-9414355.
G. NASH AND ARIELA SOFER
differ, since a practical method would likely use an adaptive line search based on
minimizing a one-dimensional approximation to the barrier function.) Ignoring the
computations for evaluating the gradient and Hessian, the algorithm determines the
solution to within a tolerance in a number of operations that is polynomial
in M and the problem dimensions. If polynomial algorithms exist to evaluate the
gradient and Hessian, the overall algorithm for the barrier subproblem is polynomial
in the dimensions of the optimization problem.
The theoretical result that we obtain reduces to the result for Newton's method
if the inner convergence tolerance for the truncated-Newton method is set to zero.
For this reason, we consider this result to be a satisfying extension of the theory for
Newton's method.
In the second major part of the paper we analyze how a simple linear extrapolation
scheme can accelerate the algorithm by providing improved initial guesses for each
subproblem. We show that improved performance can be achieved by an algorithm
based on linear extrapolation, when barrier subproblems are solved exactly. We also
indicate, via an example, that it may be difficult to derive complexity results either
when subproblems are solved inexactly, or when higher-order extrapolation is used.
Our analysis is based on the framework established in Nesterov and Nemirovsky
(1993) and Nemirovsky (1994) as adapted by us in our book [14]. In the rest of the
paper we cite theoretical results for an algorithm based on Newton's method. These
results are due to Nesterov and Nemirovsky, although we frequently cite [14] because
our discussion here more closely follows the organization and notation of that book.
(Related discussions can be found in [3, 8, 22].)
In the barrier method, we assume that the barrier function is "self concordant,"
a property that we define below. Self-concordant barrier functions were introduced in
[16]; recent work on this topic includes [4, 6, 7, 8, 17]. For linear programs and convex
quadratic programs, the ordinary logarithmic barrier function can be used. Related
barrier functions can be used for semi-definite programming [18, 20, 21, 24]. It is
possible to prove that, for any convex feasible region with the properties we specify
below, there exists an appropriate self-concordant barrier function, although in general
it may not be practical for computation. Thus the results we describe here provide a
general theoretical approach for solving convex programming problems.
Two major results are required to prove that the overall algorithm is a polynomial
algorithm. The first states that if the truncated-Newton method is applied to a single
barrier subproblem, and the initial guess is "close" to the solution, then the number
of iterations required to find an approximate solution of this subproblem is bounded.
This is the topic of Section 3. The second states that the linear extrapolation can
improve the initial guess for the next subproblem. This topic is addressed in Section
4.
These two results are less obvious than they might at first seem. If any constraint
in the convex programming problem is binding at the solution, then the solution will
be on the boundary of the feasible region where the barrier function has a singular-
ity. Since standard convergence results for Newton-type methods assume that the
Hessian at the solution has a bounded condition number, a traditional analysis is not
appropriate.
To analyze the behavior of Newton-type methods in this case, we must in some
manner take this singularity into account. To do this, we define a norm k\Deltak x in terms of
the Hessian of the barrier function evaluated at a point x. We will measure "closeness"
in terms of this norm.
This norm depends on the Hessian, and changes as the variables change. For this
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 3
norm to be useful, the rate of change of the Hessian matrix must not be "too great."
This reasoning leads to the imposition of a bound on the third derivatives of the barrier
function in terms of the Hessian (see Section 2). This bound is all that is required to
prove the first major result corresponding to the behavior of the truncated-Newton
method on a single barrier subproblem.
To prove that the approximate solution of one subproblem will not be too far
from the solution of the next subproblem, it is necessary that the values of the barrier
functions not change "too quickly" as the barrier parameter changes. To guarantee
this, we impose a bound on the first derivatives of the barrier functions in terms of
the Hessian (see Section 4). By measuring all quantities in terms of the Hessian, we
are able to circumvent the difficulties associated with the singularity of the barrier
function at the solution.
If the barrier function has these properties, then an interior-point method can be
designed so that the optimal solution of a convex programming problem can be found
(to within some tolerance) using a polynomial number of truncated-Newton iterations.
Practical experience suggests that an improved barrier method can be obtained if
the approximate solutions to the subproblems are extrapolated to produce an initial
guess for the next subproblem. We analyze this idea in Section 4. We are able to
derive some theory to support this idea in the case when linear extrapolation is used,
and when the subproblems are solved exactly. Through an example, we suggest that
it may be difficult to obtain a comparable result for either a more elaborate algorithm
(with higher-order extrapolation) or a more realistic algorithm (with the subproblems
solved inexactly).
2. Basics. In this section, we define self concordance and establish some basic
lemmas. An extensive discussion of the theory of self concordance is given in the book
by Nesterov and Nemirovski [16]. The presentation here parallels our book [14].
Let S be a bounded, closed, convex subset of ! n with nonempty interior int S.
(The assumption that S is bounded is not that important, since we could modify the
optimization problem by adding artificial, very large bounds on the variables.) Let F
be a convex function defined on the set S, and assume that F has three continuous
derivatives. Then F is self concordant on S if:
(i) (barrier property) F along every sequence f x i g ae int S converging
to a boundary point of S.
(ii) (differential inequality) F satisfies
for all x 2 int S and all
In this definition,
that is, it is a third-order directional derivative of F .
As an example, the logarithmic barrier function
log(a T
is self concordant on the set
\Psi .
4 STEPHEN G. NASH AND ARIELA SOFER
The constant 2 in the definition is arbitrary. If instead
for some constant C, then the scaled function -
concordant. The
number 2 is used in the definition so that the function F log x is self concordant
without any scaling.
We make several assumptions to simplify our discussion. They are not essential;
in fact, almost identical results can be proved without these assumptions. We assume
that r 2 F (x) is nonsingular for all x 2 int S. (See Theorem 2.1.1 in [16] for an approach
that avoids this assumption.) This allows us to define a norm as follows:
We also assume that F has a minimizer x   2 int S. Because F is convex, these
assumptions guarantee that x   is the unique minimizer of F in S.
The following lemmas indicate some basic properties of self-concordant functions.
The first shows that the third-order directional derivative can be bounded using this
norm.
Lemma 1. If F is self-concordant on S then
for all x 2 int S and for all
Proof. See [8] or [16].
The next lemma bounds how rapidly a self-concordant function F (x) and its
Hessian can change if a step is taken whose norm is less than one. The first result is
an analog of a Taylor series expansion for a self-concordant function. The second is a
bound on how rapidly the norm can change when x changes.
Lemma 2. Let F be self concordant on S. Let x 2 int S and suppose that khk x !
1. Then x
where
The lower bound in (1) is satisfied even if khk x - 1. Furthermore, for any g 2 ! n ,
Proof. See [16].
Our convergence results for a barrier subproblem are phrased in terms of a quantity
called the "Newton decrement." It is defined below. The Newton decrement
measures the norm of the Newton direction, but indirectly it can be interpreted as a
"proximity measure" for the distance to the barrier trajectory. We use the Newton
decrement in place of more traditional measures of convergence, such as
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 5
If x 2 int S and pN is the Newton direction for F at x, then the Newton decrement
of F at x is
Consider the Taylor series approximation to F
The Newton direction pN minimizes this approximation and is the solution to
The optimal value of the Taylor series approximation is
indicating why ffi (F; x) is called the Newton decrement.
We have the following lemma.
Lemma 3. The Newton decrement satisfies
Proof. See [16].
We will obtain bounds on F
in terms of the Newton
decrement, and we will also measure the progress at each iteration of the truncated-
Newton method in terms of the Newton decrement. Thus, statements about the
convergence of the method in terms of the Newton decrement will indirectly provide
us with information about convergence as measured in the more traditional ways.
3. Convergence of a Truncated-Newton Method. We now study the consequences
of using a truncated-Newton method, rather than Newton's method, to
minimize a self-concordant function:
minimize
where S and F are as in the previous section.
In the truncated-Newton method, a search direction p will be computed that
satisfies the acceptance criterion
where x is the current estimate of the solution to the barrier subproblem, pN is the
Newton direction, and ffl is some tolerance. For simplicity, we assume that the tolerance
ffl is fixed, although similar results could be derived in the case where ffl varied from
iteration to iteration.
It is not that important how the search direction is computed, as long as the number
of arithmetic operations is polynomial in the dimensions of the problem. Practical
truncated-Newton methods often use the conjugate-gradient method which, in exact
arithmetic, is guaranteed to converge to the Newton direction in a finite number of
operations. Thus, in exact arithmetic, this would be an appropriate procedure.
6 STEPHEN G. NASH AND ARIELA SOFER
The acceptance criterion (2) is impractical since it involves the Newton direction
pN . It is, however, closely related to practical rules for terminating the inner iteration
of a truncated-Newton method. If we define
to be the value of the quadratic model for F (x) at p, then
x
x
In [12] it is recommended that the inner iteration of a truncated-Newton method be
terminated based on the value of the quadratic model, and the barrier method in [13]
uses a related rule.
Other practical acceptance rules are based on the value of the relative residual,
and have the form
for some tolerance j [2]. It is straightforward to derive thatp cond 2 (r 2 F (x))
where is the condition number of r 2 F (x) in the 2-norm. These inequalities
provide a further demonstration of the relationship of (2) with practical
termination rules for the inner iteration of the truncated-Newton method.
Some useful consequences of the acceptance criterion (2) are stated in the following
lemma.
Lemma 4. Suppose that the acceptance criterion (2) is satisfied at x. then
and
Proof. The first result is a straightforward consequence of (2). The second is
obtained by squaring the acceptance criterion:
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 7
The function F will be minimized using a "damped" truncated-Newton method,
that is, a step is taken along the truncated-Newton direction but with a specified step
length that is less than one. If we denote the search direction at x by p, then the
method is defined by
p:
The reason for including this step length is that the resulting displacement will always
have norm less than one, so that Lemma 2 applies. It also guarantees that the damped
truncated-Newton step is well-defined, in the sense that the iterates remain in int S.
As the method converges and the truncated-Newton direction approaches zero,
the step length approaches one, so that (asymptotically) rapid rates of convergence
can be attained. The rest of this section develops the properties of the damped
truncated-Newton method.
The next lemma gives a lower bound on how much the function F will be decreased
by a step of the damped truncated-Newton method.
Lemma 5. If x+ is the result of the damped truncated-Newton iteration, then
Proof. Let be the step length. Using Lemma 2 and (4) we
obtain
x
The desired result is just a re-arrangement of this last inequality.
The lemma provides a lower bound for F The lower bound is zero
when kpk and is positive and strictly increasing for kpk x ? 0. (The derivative of
the right-hand side with respect to kpk x is positive.) The result gives a lower bound on
how much progress is made at each truncated-Newton iteration. Figure 1 illustrates
this lower bound for various values of ffl.
If kpk x remains large, then the truncated-Newton method must decrease the value
of F (x) by a nontrivial amount. Since the function is bounded below on S, this cannot
go on indefinitely, and kpk x must ultimately become small.
The next theorem analyzes the convergence of the method in the case where
are related by (3), these two results provide a
bound on the number of truncated-Newton iterations required to solve the optimization
problem to within some tolerance. (This argument is made precise in Theorem
7.) The theorem also determines a bound on kx \Gamma x   k x
in terms of ffi (F; x), and thus
shows that if ffi (F; x) is small, then the norm of the error is small as well.
Theorem 6. If x 2 int S then
Let x   be the minimizer of F in S, and assume that ffi
8 STEPHEN G. NASH AND ARIELA SOFER

Figure
Bound on F various values of ffl.
bound
bound
bound
bound
Proof. The proof is in two parts, proving each of the results in turn.
Part 1: We will derive the bound on ffi (F; x+ ). Let p be the truncated-Newton
direction at x, pN be the Newton direction at x, and
ffp. For any h 2 ! n we define
This function is twice continuously differentiable for
By Lemma 1 and Lemma 2 we have
x+tp
x
Note that Z ffh Z
x d-
x
Then
x d-
dt
x
x khk x
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 9
x khk x
x
x khk x
x
Since this is true for all h we have
This completes Part 1 of the proof.
Part 2: The proof of
can be found in [14] or
[15].
We conclude with a summary theorem. It provides a bound on the number of
truncated-Newton iterations required to minimize F to within a tolerance.
Theorem 7. Let S be a bounded, closed, convex subset of ! n with non-empty in-
terior, and let F (x) be a convex function that is self concordant on S. Given an initial
guess x0 2 int S, the damped truncated-Newton method is defined by the recurrence
where p is an approximation to the Newton direction pN at
for some tolerance 0
F
At some iteration i we must have
and then for every j - i we have
G. NASH AND ARIELA SOFER
The number of truncated-Newton steps required to find a point x
bounded by
for some constant C that depends on ffl and that decreases as ffl ! 0. If then the
number of steps is bounded by
for some constant -
C.
Proof. The bound on F derived in [16]. The remaining conclusions
are consequences of the earler results. The formulas for the constants C and -
C can
be derived as follows. Let be the first iteration for which
Such an index i must exist, since F is bounded below on S. If
then by (3)
It follows from Lemma 5 that
Thus the number of initial iterations i is at most
The progress of the later iterations is described by Theorem 6. If j - i, then
Hence the number of later iterations is at most
Summing these two bounds determines the constant C.
then at the later iterations
and a similar analysis determines -
C.
and the truncated-Newton method computes the Newton direction, then
the theorem is the same as that reported for Newton's method in [14, 15]. It establishes
the polynomiality of the truncated-Newton method applied to a barrier subproblem
(see Section 1 for details).
4. Extrapolation. In Section 3 we analyzed the behavior of a truncated-Newton
method when applied to a single barrier subproblem. We now consider the overall
interior-point method based on solving a sequence of subproblems. Our main concern
is with the effects of extrapolating the (approximate) solutions of several subproblems
to obtain an improved initial guess for the next subproblem.
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 11
The complexity results for the overall method depend on an additional assump-
tion, that is, a bound on the first-derivative of the barrier function. Although we do
not make much direct use of this assumption in this paper, it underlies many of our
comments, and so we state it here.
Let S be a set with the same properties as in Section 3. Following [16], a self-
concordant function F on S is a self-concordant barrier function for S if, for some
for all x 2 int S and all h 2 ! n . We may assume, without loss of generality, that
- 1.
The function F
barrier function with
the function
log(a T
is a self-concordant barrier function with for the set
\Psi .
A self-concordant barrier function exists for any closed convex set S [16]; evaluating
such a barrier function may not be computationally practical, however.
We also assume that the convex program is written in the following standard
subject to x 2 S
where c 6= 0. An optimization problem with a general nonlinear objective function
can be converted to this form by adding an additional variable and constraint.
The problem (P) will be solved using a path-following method of the following
form. For ae ? 0 we define
where F is a self-concordant barrier function for the set S with parameter - 1, and
where the Hessian of F is nonsingular for all x 2 int S. (The nonsingularity assumption
is not essential; see [16].) Let x   (ae) be the minimizer of F ae (x) for x 2 int S. Our
method will generate x
A complexity result for a particular algorithm based on this approach and Theorem
7 can be proved as in [14, 15]. In this algorithm, x i 2 int S is accepted as an
approximate minimizer of F ae i if
for some
2 , and then x i is used as an initial guess for minimizing F ae i+1 .
Theorem 8. Suppose that we solve the problem (P) on a bounded, closed, convex
domain S using the path-following method described above, where F is a self-
concordant barrier function with parameter - 1. Let 1be the parameter in
the acceptance test, and assume that the penalty parameters are updated via
G. NASH AND ARIELA SOFER
Assume that the method is initialized with ae 0 and x0 2 int S where x0
satisfies the acceptance test for F ae 0
. Then
ae 0
If a truncated-Newton method based on (2) is used to minimize F ae i to within proximity
-, then the number of truncated-Newton iterations required to find an approximate
solution to subproblem i does not exceed a constant N -;';ffl depending only on -, ', and
ffl. In particular, the total number of truncated-Newton iterations required to find an x
satisfying c T bounded above by
log
with constant C -;';ffl depending only on -, ', and ffl.
It is possible that a better initial guess for a subproblem (and hence a better
algorithm) can be obtained by extrapolation of previous solutions. The technique
of extrapolation-initially proposed by Fiacco and McCormick [5]-approximates the
barrier trajectory x(ae) by a polynomial of degree q. The coefficients of the polynomial
are computed from the solutions of q subproblems, and are then used to predict
the solution of the barrier subproblem for the new value of ae. The results in [5] indicate
that extrapolation is a powerful computational tool. Our own computational
experiments [13] also indicate that better initial guesses (and better overall perfor-
mance) can be obtained by extrapolating the solutions of a sequence of subproblems.
An example illustrating the usefulness of extrapolation is summarized in Table 1; for
details, see [13]. In this case, the use of cubic extrapolation reduces the number of
truncated-Newton iterations by a factor of 2.1, and the number of gradient evaluations
by a factor of 2.7.
(Complexity results for a predictor-corrector method can be found in [15]; this
predictor-corrector method is a form of extrapolation, but appears to be less practical
for large nonlinear programs than the technique used here. It is not clear that
this predictor-corrector approach can be extended effectively to a truncated-Newton
method.)
The lemma below gives theoretical support to these computational results. The
technique of extrapolation may have limitations, however, as we shall discuss in the
latter part of this section.
We first examine linear extrapolation and assume that x
linear extrapolation predicts that
where
More generally, \Delta i can be considered as a "search direction" along the barrier tra-
jectory, as in the lemma below. The result shows that linear extrapolation can be
used to produce initial guesses that are at least as good as when extrapolation is not
used. For simplicity, we choose fl i j fl for all i, although it would be easy to extend
the result to the case where the fl i 's are not constant. (The lemma uses our general
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 13

Table
Effect of Cubic Extrapolation (iter = number of truncated-Newton iterations,
ng = number of gradient evaluations). Based on [13] with elaborate
barrier algorithm, test problem 51, 1000 variables.
Extrapolation No Extrapolation
ae iter ng iter ng
28 277
Totals 51 367 107 982
assumption that r 2 F is positive definite. If r 2 F is only positive semi-definite, then
the lemma is still true under the assumption that c T \Delta i 6= 0.)
Lemma 9. Let ae assume that x
Define the linear extrapolation direction
If
then
that is, \Delta i is a descent direction for F i+1 at x i . We define
with a more specific upper bound provided by (1).
Proof. We first prove that c T x series expansion gives
Because x i 6= x positive definite, the last term is positive. Since
14 STEPHEN G. NASH AND ARIELA SOFER
which implies that
F
Similarly, by switching the roles of x i and x i\Gamma1 , we obtain
If we multiply the first of these inequalities by ae i , the second by ae i\Gamma1 , and rearrange,
then
Combining this with the above results
We now use this result to prove that \Delta i is a descent direction. Since x
Using these results, we obtain
This completes the first part of the proof.
The second part of the proof relies on (1). Using the formulas above, the upper
bound in (1) becomes
Note that by the assumptions in the lemma.
If we solve OE 0 we obtain the solution
It is straightforward to verify that OE 00 (ff so that this is a local minimizer of OE.
we obtain that
and so x
Since the upper bound on F i+1 is decreasing at
is a local minimizer of the upper bound, this completes the proof.
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 15
This result could be extended to the case where the subproblems are not solved
exactly, as long as the magnitudes of
were sufficiently small so as not
to interfere with the inequalities in the lemma. It appears to be difficult to generalize
the above result greatly, however, as the discussion below indicates.
Lemma 9 shows that an appropriate step along the extrapolation direction can
produce a decrease in the objective value of the barrier function for the updated
barrier parameter. However taking the "full" extrapolation step (fl i =fl
guaranteed to be beneficial, no matter how slight the change in the barrier parameter.
This is true even when the subproblems are solved exactly. To see this, let
and consider the extrapolated point
The effect of extrapolation is described by
Now
d
d
0:
Thus, for a small change in the barrier parameter (i.e., as to first order
there is no improvement in the objective value of the new barrier function at the
extrapolated point.
Somewhat more insight can be obtained by analyzing / 00 (0):
The second term is positive by convexity, but the first term is less than or equal to
zero (see Lemma 9). If we define
then we can write
From (5) and our comments above we obtain
G. NASH AND ARIELA SOFER
If kvk x i
- then the lower bound on / 00 (0) is positive, and hence no improvement
in the objective value is obtained. Thus the full extrapolation step is not guaranteed
to be useful.
So far, we have only considered linear extrapolation. We now indicate via an
example that higher-order extrapolation may lead to predicted solutions that are far
worse than those obtained without extrapolation. In this example, we consider both
exact and approximate solutions to subproblems. As above, an approximate solution
x i to a barrier subproblem will be accepted if x i 2 int S and if
for some - 0.
Consider the one-variable problem
subject to x - 0:
This problem is already in standard form, and log(x) can be used as a barrier function
with
It is easy to analyze this example. The solution to the optimization problem is
The solution to the barrier subproblem is x   1=ae. The norm has the
value jh=xj. The Newton decrement is xaej. The solution to
a subproblem is accepted if
The penalty parameter is updated via ae
Here we use four values of 0:5. The choice
corresponds to solving the subproblems exactly. We initialize the penalty
parameter with ae In each case, the approximate solution to the subproblem
is chosen at the upper bound of the acceptable range. This choice is consistent with
the class of theoretical algorithms that we study in this paper, and is plausible for a
practical algorithm.
In

Figure

2 we show the results of applying quadratic extrapolation on this prob-
lem. The exact solutions of the first seven barrier subproblems are marked with \Theta.
The vertical bars indicate the range of x values that satisfy the acceptance criterion for
a subproblem. The dotted lines show the path of extrapolated approximate solutions,
with a * used to indicate the extrapolated initial guess.
In each of the four cases, the extrapolated values are exceedingly poor initial
guesses for the next subproblem. In fact, the extrapolation paths move away from,
rather than toward, the solution of the next subproblem.
In

Figure

3 we show the results of applying linear extrapolation. In this case,
the approximate solutions are chosen as the lower bound of acceptable values for the
first subproblem, and the upper bound for the second subproblem. This is allowed
by the theory, but we think it unlikely that a practical algorithm could produce such
approximate solutions.
In this case, even with linear extrapolation, the extrapolated points can (when
- is sufficiently large) point away from the solution of the next subproblem. Hence
extrapolation is worse than doing nothing. As mentioned, we do not expect these
circumstances to arise for a practical algorithm. Nevertheless, any complexity theory
COMPLEXITY OF A PRACTICAL INTERIOR-POINT METHOD 17

Figure
Quadratic Extrapolation of Approximate Solutions.
rho
x
Quadratic: kappa=0
rho
x
Quadratic: kappa=.1
rho
x
Quadratic: kappa=.25
rho
x
Quadratic: kappa=.5

Figure
Linear Extrapolation of Approximate Solutions.
rho
x
rho
x
rho
x
rho
x
for such an algorithm would have to rule out this possibility, and hence would have to
be based on a more elaborate theoretical framework than that used here.
This example suggests that an algorithm that uses extrapolation must monitor
the effectiveness of the extrapolation scheme, and must not use it blindly. It also
suggests that the algorithm would have to be carefully designed so that inaccuracies
in the solutions of barrier subproblems did not interfere with the performance of the
extrapolation scheme.
We have not been able to derive complexity results for a more elaborate algorithm
of this type. This example leads us to think that this would be a difficult enterprise.
G. NASH AND ARIELA SOFER



--R

Computational experience with penalty/barrier methods for nonlinear programming

Interior Point Approach to Linear
A sufficient condition for self-concord- ance
Sequential Unconstrained Minimization Techniques
Osman G- uler
Two interior-point algorithms for a class of convex programming problems
Interior point methods via self-concordance or relative Lipschitz condition
A practical interior-point method for convex pro- gramming
An unconstrained optimization technique for large-scale linearly constrained minimization problems

Assessing a search direction within a truncated-Newton method
A barrier method for large-scale constrained optimiza- tion
Linear and
Interior point polynomial time methods in convex programming


Homogeneous interior-point algorithms for semidefinite program- ming
An infinitely summable series implementation of interior-point methods
On the long step path-following method for semidefinite programming

Complexity Issues
Interior methods for constrained optimization
Extending primal-dual interior point algorithms from linear programming to semidefinite programming
--TR
convex programming;interior-point method;truncated-Newton method;self-concordance;large-scale optimization;complexity