Probabilistic Analysis of An Infeasible-Interior-Point Algorithm for Linear Programming.
We consider an infeasible-interior-point algorithm, endowed with a finite termination scheme, applied to random linear programs generated according to a model of Todd. Such problems have degenerate optimal solutions, and possess no feasible starting point. We use no information regarding an optimal solution in the initialization of the algorithm. Our main result is that the expected number of iterations before termination with an exact optimal solution is O(n ln(n)).
Introduction
A number of recent papers have attempted to analyze the probabilistic behavior of interior
point algorithms for linear programming. Ye (1994) showed that a variety of algorithms,
endowed with the finite termination scheme of Ye (1992) (see also Mehrotra and Ye 1993),
obtain an exact optimal solution with "high probability" (probability approaching one as
1) in no more than O(
iterations. Here n is the number of variables in a standard
form primal problem. Several subsequent works - Huang and Ye (1991), Anstreicher, Ji,
and Ye (1992), and Ji and Potra (1992) - then obtained bounds on the expected number
of iterations until termination, using various algorithms and termination methods. The
analysis in each of these latter papers is based on a particular random linear programming
model from Todd (1991) (Model 1 with - e, see Todd 1991, p.677), which has a
known initial interior solution for the primal and dual problems, and is nondegenerate with
probability one. Unfortunately, we eventually realized that these three papers all suffer from
a fatal error in conditional probability, and consequently do not provide correct analyses of
the probabilistic behavior of interior point algorithms. The error is basically the following:
Todd (1991, Theorem 3.6) determines the distribution of the components of a primal basic
feasible solution for this case of his Model 1, and similar analysis can be used to obtain
the distribution of the components of a dual basic feasible solution. What is required in
the probabilistic analysis is the distribution of the positive components of the primal and
dual optimal solutions. However, conditioning on optimality is equivalent to conditioning
on primal and dual feasibility, and these are not independent of one another. (Theorem 3.6
of Todd (1991) itself contains an error which will be addressed in a forthcoming erratum to
that paper, and which is further discussed in Section 4.)
A variant of Todd's Model 1 which allows for degeneracy is given in Todd (1991, Section
4). Throughout the paper we will refer to this model as "Todd's degenerate model.'' Todd's
degenerate model controls the degree of degeneracy by specifying optimal primal and dual
solutions, but provides no feasible starting point. This presents a difficulty for most interior
point methods, which require feasible primal and/or dual solutions for initialization. One way
around this difficulty is to use a combined primal-dual feasibility problem, as in Ye (1994).
Another approach would be to use an artificial variable, with "M " objective coefficient, and
increase M as necessary to insure feasibility. Interior point algorithms which employ such
a strategy have been suggested by Ishihara and Kojima (1993), and Kojima, Mizuno, and
Yoshise (1993). In fact, for Todd's degenerate model the required value of M could be
inferred from the known optimal dual solution, but the use of such information is clearly
"cheating," since a general linear programming algorithm cannot take as input properties of
a (usually unknown) optimal solution. Finally, one could attempt a probabilistic analysis
of a combined Phase I - Phase II algorithm, for example Anstreicher (1989, 1991) or Todd
(1992, 1993).
In practice, another algorithm, the primal-dual "infeasible-interior-point" method, has
been very successful for problems which have no initial feasible solution (see for example
Lustig, Marsten, and Shanno 1989). A theoretical analysis of this method proved to be
elusive for many years. Finally Zhang (1994) showed that a version of the infeasible-interior-
point algorithm is globally convergent, and is actually an O(n 2 L) iteration (hence polynomial
time) method if properly initialized. Here L is the bit size of a linear program with integer
data. Unfortunately, however, this "polynomial time" initialization requires essentially the
value of M which would be needed if an artificial variable were added to the problem. Mizuno
subsequently obtained an O(n 2 L) bound for the infeasible-interior-point algorithm of
Kojima, Megiddo, and Mizuno (1993), while Mizuno (1994) and Potra (1994, 1996) obtain an
improved O(nL) iteration result for infeasible-interior-point predictor-corrector algorithms.
The purpose of this paper is to obtain a probabilistic result for an infeasible-interior-
point algorithm, endowed with the finite termination scheme of Ye (1992), applied to instances
of Todd's degenerate model. As mentioned above, an infeasible-interior-point algorithm
is a natural solution technique for instances of the degenerate model since these
problems possess no initial feasible solution. A very important feature of our analysis is
that we use no information regarding an optimal solution in the initialization of the algo-
rithm. In particular, because the optimal solution is known for instances of the model, it
would be easy to use a "polynomial time" initialization which would greatly simplify our
analysis. However, as mentioned in the discussion of M above, such an approach is clearly
cheating. Instead, we use a "blind" initialization of the algorithm, which could be applied to
any linear program. In the initial version of the paper, our main result was that for Zhang's
algorithm applied to Todd's degenerate model, the expected number of iterations
before termination with an exact optimal solution is O(n 2 ln(n)). For the final version of the
paper we have modified our original analysis to obtain an improved O(n ln(n)) bound, using
the infeasible-interior-point predictor-corrector algorithm of Potra (1994) in place of Zhang's
method. At the end of the paper we also describe how our analysis can be applied to other
infeasible-interior-point methods. The methodology used to obtain these results is relatively
complex, for a number of reasons. First, the analysis of finite termination is complicated
by the infeasibility of the iterates. Second, properties of the initial solution, such as "gap"
and amount of infeasibility, are random variables. Third, due to our blind initialization, the
global linear rate of improvement for the algorithm is itself a random variable. Fourth and
finally, this random rate of improvement is dependent on other random variables connected
with the initial solution, and finite termination criterion, resulting in product terms which
cannot be simply factored (as would be the case with independence) in the expected value
computation.
Subsequent to the initial version of this paper, an O(
was devised by Ye, Todd and Mizuno (1994). The method of Ye, Todd, and Mizuno is
based on an ingenious "homogenous self-dual" formulation for LP problems. The resulting algorithm
is "infeasible" in the sense that iterates are infeasible for the original LP being solved,
but is fundamentally different from the other infeasible-interior-point algorithms discussed
above because the iterates are feasible for the homogenous self-dual problem. Anstreicher et
al. (1992a) uses a number of results from this paper to obtain a bound of O(
the expected number of iterations before termination with an exact optimal solution, for the
algorithm of Ye, Todd, and Mizuno (1994) applied to instances of Todd's degenerate model.
2. The Infeasible-Interior-Point Algorithm
In this section we describe the main features of the infeasible-interior-point algorithm of
Potra (1994). We assume familiarity with Potra's paper, and give major theoretical results
concerning the algorithm without proof. Our notation generally follows Potra's, with a few
minor changes to avoid conflicts with notation used in our later analysis. Throughout the
paper, if x 2 R n , then X is used to denote the diagonal matrix
and S, etc. We use e to denote a vector of varying dimension with each component equal
to one, and k \Delta k to denote k \Delta k 2 . Consider then primal and dual linear programs:
where A is an m \Theta n matrix with independent rows. We assume throughout that n - 2.
A problem equivalent to the linear programs LP and LD, is then the LCP: F (x; s;
F (x; s; y) =@ Xse
The algorithm is initiated with a point which is not assumed
to satisfy the equality constraints of LCP. The algorithm generates a solution sequence
On iteration k, in the predictor step, a predictor-
direction vector (u; v; w) is obtained by solving the Newton system
A step is then taken to a new point (-x; -
s; -
y), where for 0 -
s; -
In the corrector step, we first find the solution (-u; - v; -
w) of the linear system
and define (~x; ~
s; ~
s; -
s=n. Next we find the solution (~u; ~ v; ~
of the linear system
~
wA =@ ~
and finally set
s; ~
Note that the two linear systems solved in the corrector step have the same coefficient
matrix, so that only one matrix factorization is needed for the corrector step. Potra's
predictor-corrector algorithm is a generalization of the Mizuno-Todd-Ye (1993) predictor-corrector
algorithm, designed so that both "optimality" and "feasibility" are improved at
the same rate, in the sense that with the algorithm
obtains
Given constants ff and fi such that
the steplength -
' k is chosen by a specific rule (see Potra 1994) that guarantees that
In (2.3), -
x(') and - s(') represent the predictor step parameterized by the steplength
s(')=n, and - =n. The parameters ff and fi in (2.3) enforce centering
conditions on all iterates of the algorithm, i.e., all iterates are forced to lie in two cones around
the central path. Clearly Throughout the remainder
of the paper, we will use this choice of ff and fi so as to simplify the exposition . We will
also assume throughout that the initial solution has the form
scalar ae - 1. Note that (2.3) implies that unless the steplength -
leads directly to a solution of LCP. Suppose LP and LD have optimal solutions, say -
x and
s). Potra's analysis uses several scalar parameters, which for the particular
ff, and fi considered here specialize to:
major component in Potra's analysis of global convergence is
the following result, which follows from his Lemmas 3.2 and 3.3, specialized for the particular
case considered here:
Proposition 2.1. If - x and - s are optimal solutions of LP and LD, then there is a feasible
steplength -
oe
From Proposition 2.1, and the fact that it is clear that the key quantity in
the analysis of the algorithm is -. In general - is a fixed finite number, implying that the
algorithm globally converges with a linear rate. Now let -
for an optimal solution
s). Note that k -
p n-ae. It is then immediate that
if the parameter ae that defines the starting point enough, in the sense that
ae=
\Omega\Gamma2 =n) and therefore the algorithm attains O(nL)
polynomial time complexity. Unfortunately, however, specifying ae in this manner requires
knowledge of -
ae, which is tantamount to knowledge of the required value of M when LP
is solved by simply adding an artificial variable. Our analysis of the algorithm will not
require such knowledge, but will instead use the fact that (2.4) implies that so long as
3. Finite Termination
In this section we consider the issue of finite termination of the infeasible-interior-point algorithm
of Section 2, using the projection termination scheme of Ye (1992) (see also Mehrotra
and Ye 1993). As in Ye (1992), our analysis requires the assumption that optimal solutions
of LP and LD exist. We require a careful derivation of the technique, modified to deal with
infeasibility of the iterates, for our probabilistic analysis in Section 5. The bounds obtained
in this section are not necessarily the simplest, or tightest, possible, but are specifically
chosen for applicability in our probabilistic analysis.
To begin, let (-x; - s; -
y) be an optimal strictly complementary solution of LP/LD, that is,
s k. Let -
0g. We refer to - oe as
the "optimal partition." As in the previous section, we assume that
where ae - 1. Our goal is to use the iterates of the infeasible primal-dual algorithm
to eventually identify the optimal partition, and generate exact optimal solutions of LP and
LD. To begin, we characterize at what point the algorithm can correctly identify
oe. In the
following analysis it is convenient to define /
' k is the steplength
used on the predictor step of the algorithm in iteration k.
Lemma 3.1. In order to obtain s k
oe, and x k
suffices to have
3n
ae=
n)
Proof: From (2.1) we have (Ax
from which it follows that
together imply that
which can be re-written as
Using the facts that
then obtain
ae
Now assume that (3.1) holds. Note that -
-, so
ae
ae
ae=
From (3.1) and (3.2), for j 2 - oe we then have
ae=
ae=
n)
On the other hand, (3.2) implies that
ae=
Applying (2.3),
ae=
ae=
n)
ae=
n)
Combining (3.3) and (3.4), we have x k
oe. The argument for
Next we consider the problem of generating an exact optimal solution to LP. (The
analysis for obtaining a solution to LD is similar, and is omitted in the interest of brevity.)
Given an iterate denote the columns of A having x k
denote the corresponding components of x. Similarly let N and xN denote the remaining
columns of A and components of x. The projection technique of Ye (1992) attempts to
generate an optimal solution of LP by solving the primal projection problem
A similar projection problem can be defined for the dual. Clearly if B corresponds to the
optimal partition - oe, and the solution x
B of PP is nonnegative, then
is an
optimal solution of LP. In what follows, we will choose k large enough so that, by Lemma
3.1, B does in fact correspond to the optimal partition - oe. Let B 1 be any set of rows of
having maximal rank (B the rows of B are independent). Let N 1 , A 1 , and b 1
denote the corresponding rows of N and A, and components of b. Let B 11 denote any square,
nonsingular submatrix of B 1 .
Theorem 3.2. The solution of PP generates an optimal solution of LP whenever
ae=
where A 1j denotes the jth column of A 1 .
Proof: Note that if the assumption of the theorem is satisfied, then B corresponds to the
optimal partition - oe by Lemma 3.1. Clearly PP is equivalent to the problem
The solution to PP, x
x
Next we consider the two terms in (3.5). First, we have
2-oe
2-oe
ae=
n)
where the first inequality uses the fact that u ?
for any conforming vector u, and the last inequality uses (3.2) as in the proof of Lemma 3.1.
To bound the second term of (3.5), we use x and the fact that
iterates k, to obtain
2-oe
Using n), we then certainly have
ae=
2-oe
Substituting (3.6) and (3.7) into (3.5), using -
ae -
ae=
2-oe
Finally (3.4) implies that if
ae=
n)
then x
and the hypothesis of the theorem imply (3.9), and the
proof is complete.
4. Random Linear Programs
In this section we describe the random linear programming model to be used in our probabilistic
analysis. We also describe an alternative version of the model, and briefly discuss
the technical problems that arise if an analysis using the second version is attempted.
Todd's Degenerate Model, Version 1
each component of A is i.i.d. from the N(0; 1)
distribution. Let
where the components of -
xB and - s N are i.i.d. from the j N(0; 1) j distribution. Let
y, where the components of -
y are i.i.d. from any distribution with O(1)
mean and variance.
TDMV1 is a special case of Model 1 from Todd (1991). The simplest choice for - y in the
model is -
Note that in any case -
is an optimal, strictly complementary solution for LP/LD. If and LD are
nondegenerate with probability one, but results in a degenerate optimal solution for
LP, and results in a degenerate optimal solution for LD.
In the sequel we will analyze the behavior of the IIP algorithm of Section 2 applied to
problems generated according to TDMV1, using the finite termination scheme of Section 3.
In preliminary versions of the paper we also considered the following degenerate version of
Todd's Model 1.
Todd's Degenerate Model, Version 2 (TDMV2): Let
A i is
each component of A is i.i.d.
from the N(0; 1) distribution. Let
where the components of - x 1 and - s 3 are i.i.d. from the j N(0; 1) j distribution. Let
y, where the components of -
y are i.i.d. from any distribution with O(1)
mean and variance.
TDMV2 is described in Todd (1991, Section 4). Note that in TDMV2, (-x; -
s) are clearly
optimal solutions for LP/LD , but are not strictly complementary. Since our analysis of
the finite termination scheme of Section 3 is based on a strictly complementary solution, to
analyze the performance of our IIP algorithm on an instance of TDMV2 we would first need
to characterize the properties of a strictly complementary solution (x   ; s   ). One approach
to this problem, based on Section 7 of Ye (1994), proceeds as follows. As in Section 3, let
B denote the columns of A corresponding to the optimal partition -
oe, and let N denote the
remaining columns of A. From Todd (1991, Proposition 4.2) we have either
Consider the case of
A 2 ). Then the system
is feasible, and with probability one has a solution with adjusting the signs of
columns of -
A 1 to form a new matrix ~
A 1 , we can assume that the system
~
is feasible, and with probability one has a solution with In Ye (1994, Lemma
it is shown that if (4.2) is feasible then (4.2) must have a certain "basic feasible partition."
Moreover, using a result of Todd (1991), the distribution of a solution to (4.2) given by a
basic feasible partition can easily be determined (see the proof of Ye 1994, Theorem 4). Such
a solution can then be used to construct an x   so that (x   ; -
s) are strictly complementary
solutions to LP/LD. Unfortunately it was eventually pointed out to us by Mike Todd (private
communication) that the above line of reasoning is incorrect, for a rather subtle reason.
Essentially the problem is that taking a given basic partition for (4.2), and conditioning
on that partition's feasibility, does not provide a valid distribution for a solution to (4.2)
conditional on (4.2) being feasible. A similar problem occurs in a simpler context in Todd
(1991, Theorem 3.6), and will be described in a forthcoming erratum to that paper.
Because of the above, references to results in earlier versions of this paper using TDMV2,
in Anstreicher et al. (1992a) and Ye (1997), are incorrect. In particular, Proposition 4.1 of
Anstreicher et al. (1992a), which is the basis of the probabilistic analysis in that paper, is
invalid. However, it is very easy to modify the statement and proof of Lemma 4.2 of Anstre-
icher et al. (1992a) to apply using TDMV1 instead of TDMV2. As a result, Theorem 4.3,
the main result of Anstreicher et al. (1992a), holds exactly as stated if "Todd's degenerate
model" in the statement of the theorem is taken to be TDMV1, rather than TDMV2. Similarly
the analysis of TDMV2 in Section 7 of Ye (1994) is incorrect, but Theorem 6, the main
result of that section, can easily be shown to hold using TDMV1 in place of TDMV2.
5. Probabilistic Analysis
In this section we consider the performance of the infeasible-interior-point algorithm of Section
2, equipped with the finite termination criterion of Section 3, applied to the random
linear program TDMV1 of Section 4. Given an instance of LP, we first obtain A b, the
minimum norm solution of a procedure which requires O(n 3 ) total operations.
We then set
0). The algorithm is then applied until the projection technique of
Section 3 yields an exact optimal solution of LP. Let
ae=
From Theorem 3.2, the algorithm will certainly terminate once -
from Proposition 2.1, - k - so to obtain - k - ffl it certainly suffices
to have
where the last inequality uses \Gammaffi. Finally, from (2.5) we have
ae 2 ), so termination of the algorithm definitely occurs on some iteration K, with
By (5.2), to obtain bounds on E[K] we require bounds on E[(n
We obtain these bounds via a series of lemmas, below. Throughout we use k A k
to denote the Frobenius norm of a matrix A: k A
i;j a 2
It is then well
known that for any matrix A and conforming vector x, k Ax k - k A k k x k. We also use
(d) to denote a - 2 random variable with d degrees of freedom.
Lemma 5.1. For an instance of TDMV1, E[-ae
Proof: Note that -
with mean n and variance 2n. Let Q denote a random variable
with the - 2 (n) distribution. Then
where the last inequality uses the fact that ln(1 + a) - a for a - 0. The proof is completed
by noting that
Lemma 5.2. For an instance of TDMV1, E[(n
Proof: Note that
x k. Moreover
y, so k c k - k - s
y k.
immediately have
Finally, we use the fact that ln(1 to obtain
Now -
n). Finally -
y k, and k A k are independent of one another. Combining all
these facts with (5.3), and using E[ln(X)] - ln(E[X]) for any random variable X, we obtain
Lemma 5.3. For an instance of TDMV1, E[\Gamma -
Proof: By definition we have
It is also easily shown (see Lemma A.2
of the Appendix) that E[\Gamma ln( -
O(n). The lemma follows
immediately.
Lemma 5.4. For an instance of TDMV1, E[ln(1
Proof: An application of the Cauchy-Schwarz inequality results in
2-oe
2-oe
2-oe
Results of Girko (1974) and Todd (1991) imply that for each
oe, we may write
Therefore
2-oe
2-oe
2-oe
~
where ~
2-oe ~
Combining (5.4) and (5.5) we obtain
2-oe
However, in Lemmas A.2 and A.3 of the Appendix it is shown that
Lemma 5.5. For an instance of TDMV1, E[\Gamma(n
Proof: From (5.1), we have
ae=
2-oe
Note that 1
ae=
O(n ln(n)), from Lemma 5.1. Furthermore E[\Gamma ln( -
O(n ln(n)), from Lemma 5.3. Finally E[ln(1+
from Lemma 5.4, and moreover
11 A 1j k is independent of -
ae. Combining these facts
with (5.6) we immediately obtain E[\Gamma(n
Combining Lemmas 5.2 and 5.5 with (5.2), we arrive at the major result of the paper:
Theorem 5.6. Assume that the infeasible-interior-point algorithm of Section 2, equipped
with the finite termination technique of Section 3, is applied to an instance of TDMV1. Then
the expected number of iterations before termination with an exact optimal solution of LP
is O(n ln(n)).
Note that our analysis of E[K] for our IIP algorithm applied to TDMV1 is complicated
by dependencies between -
ae and ae, and between -
ae and ffl. These dependencies would not affect
a simpler "high probability" analysis (see for example Ye 1994), since if a fixed collection of
events each holds with high probability, then the joint event also holds with high probability,
regardless of dependencies. (The events of interest here are that -
ae, ln(ae), and ln(ffl), satisfy
certain bounds.) In the interest of brevity we omit the details of a high probability analysis
of K, which also obtains a bound of O(n ln(n)) iterations using TDMV1.
6. Application to Other Algorithms
A large literature on the topic of infeasible-interior-point methods for linear programming,
and related problems, has developed since this paper was first written. See for example
Bonnans and Potra (1994) for a discussion of the convergence properties for a broad class of
such methods. In this section we describe the key features of Potra's (1994) algorithm that
are exploited in our probabilistic analysis, and discuss the extent to which our analysis can
be applied to a number of other infeasible-interior-point methods.
To begin, as described in Section 2, the algorithm of Potra (1994) satisfies
it is straightforward to verify that the analysis of finite termination, in Section 3, continues
to hold if the conditions in (6.1) are relaxed to
The conditions in (6.2) are satisfied by almost all primal-dual infeasible-interior-point algo-
rithms, and consequently the analysis in Section 3 applies very generally to these methods.
(For simplicity we used throughout the paper, but obviously the analysis in Section 3
can be adapted to other ff.) In Section 5, the important feature of Potra's (1994) algorithm,
for our purposes, is that if
then on each iteration k we have
are any primal and dual optimal solutions. An initialization of
the form (6.3) is quite standard for primal-dual infeasible-interior-point methods. The exact
relationship between the initial normalization (6.4), and the lower bound on the steplength
(6.5), does not carry over immediately to other methods. However, similar relationships
between ae and the convergence rate do hold for many other algorithms. For example, in the
original version of this paper we used the fact that if ae - k u
for any F whose rows span the nullspace of A, and ae
=\Omega\Gamma351 then Zhang's (1994) method
achieves
' k is the steplength used on iteration k. (The analysis of Zhang's algorithm is actually
complicated somewhat by the fact that his proofs are based on the decrease of a
"merit
rather than decrease in the individual
components k. Consequently a lower bound on the steplength must
be translated into a lower bound on the decrease in the merit function.) Note that here again
an initialization similar to (6.4) fits the analysis well, since we can take
where c. The difference between (6.5) and (6.6) results in a bound of
O(n 2 ln(n)) on the expected number of iterations before termination when Zhang's (1994)
algorithm is applied to Todd's degenerate model. Our analysis could similarly be used to
obtain an O(n 2 ln(n)) expected iteration bound for the algorithms of Wright (1994), Zhang
and Zhang (1994), and Wright and Zhang (1996). These three papers modify the method
of Zhang (1994) to add asymptotic superlinear convergence to the algorithm. (The paper
of Wright and Zhang obtains superquadratic convergence.) It is worth noting that applying
the probabilistic analysis devised here to these methods ignores their improved asymptotic
behavior. An interesting line of further research would attempt to exploit the superlinear
convergence of these algorithms in the probabilistic analysis.
Our analysis could also be applied to the algorithms of Mizuno (1994), whose work
is based on the infeasible-interior-point method of Kojima, Megiddo, and Mizuno (1993).
Mizuno's algorithms include a termination condition that halts the iterative process if it can
be proved that
for all optimal solutions (x   ; s   ). With a "polynomial time" initialization, involving a very
large ae, (6.7) has no effect when the algorithm is applied to a problem having an optimal so-
lution. However, to perform an analysis similar to the one here one would need to bound the
probability of termination due to (6.7), and possibly consider restarting the algorithm with
a larger ae, following termination(s) due to (6.7), until the finite projection technique yielded
exact optimal solutions. A probabilistic analysis involving such restarts is undoubtedly pos-
sible, but we have not attempted to work out the details. Infeasible-interior-point potential
reduction algorithms are devised by Mizuno, Kojima, and Todd (1995). These methods are
quite similar to other primal-dual infeasible-interior-point methods, except that a potential
function is used to motivate the search directions, and prove convergence. The algorithms
developed by Mizuno, Kojima, and Todd (1995) also use the added termination condition
(6.7). As a result, to apply our probabilistic analysis to these methods one would again
need to bound the probability of termination due to (6.7), and possibly consider a "restart"
strategy as described above. In addition, Algorithms II and III of Mizuno, Kojima, and
Todd (1995) do not explicitly enforce the "feasibility before optimality" condition -
in (6.2), and therefore our analysis of finite termination, in Section 3, would not immediately
apply to these methods.
Freund (1996) devises an infeasible-interior-point method that uses search directions
based on a primal barrier function, as opposed to the primal-dual equations used by all the
methods mentioned above. Freund's complexity analysis is also given in terms of explicit
measures of the infeasibility and nonoptimality of the starting point. A probabilistic analysis
of this algorithm would require substantial modifications of the techniques used here. Potra
also shows that the complexity of his method can be improved if the infeasibility of
the initial point is sufficiently small, but our analysis based on the initialization (6.3)-(6.4)
ignores this refinement.

Acknowledgement

We are very grateful to the referees for their careful readings of the paper, and numerous
comments which substantially improved it. We are indebted to Mike Todd for pointing out
the error in our original analysis using the second version of his degenerate model for linear
programming.


Appendix


In this appendix we provide several simple probability results which are required in the
analysis of Section 5. Throughout, x 2 R k is a random vector whose components are not
assumed to be independent of one another. We begin with an elementary proposition whose
proof is omitted.
Proposition A.1. Let x i , be continuous random variables, with sample space
1). Define the new random variables
g. Then for any u - 0, f - (u) -
(u), and f i (u) -
is the p.d.f. of a random variable X.
Lemma A.2. Let x
Proof:
Z 1k
Applying Proposition A.1, with each x j having p.d.f
and therefore E[\Gamma Using Proposition A.1 in a similar way,
Finally, from Jensen's inequality and Proposition A.1,
Z 1uf(u) du
Lemma A.3. Let x 2 R k , where each x
Proof: This follows from the same analysis used to bound E[ln(i)] in Lemma A.2, but
letting f(\Delta) be the p.d.f. of the - 2 (d) distribution, and recalling that the expected value of
a - 2 (d) random variable is d.



--R

A combined phase I-phase II projective algorithm for linear programming
A combined phase I-phase II scaled potential algorithm for linear programming


of Management Sciences
Infeasible path following algorithms for linear complementarity problems
An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
On the distribution of solution of systems of linear equations with random coefficients.
On the average number of iterations of the polynomial interior-point algorithms for linear programming
On the big M in the affine scaling algorithm.

A primal-dual infeasible-interior-point algorithm for linear programming
A little theorem of the big M in interior point algorithms.
Computational experience with a primal-dual interior point method for linear programming
Finding an interior point in the optimal face of linear programs.
Polynomiality of infeasible-interior-point algorithms for linear program- ming

On adaptive-step primal-dual interior-point algorithms for linear programming
A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
An infeasible interior-point predictor-corrector algorithm for linear programming
Probabilistic models for linear programming.
On Anstreicher's combined phase I-phase II projective algorithm for Todd
An infeasible interior point algorithm for linear complementarity prob- lems
A superquadratic infeasible-interior-point algorithm for linear complementarity problems
On the finite convergence of interior-point algorithms for linear programming
Towards probabilistic analysis of interior-point algorithms for linear program- ming
Interior Point Algorithms: Theory and Analysis.
An O( p nL)
On the convergence of a class of infeasible interior-point algorithms for the horizontal linear complementarity problem
Superlinear convergence of infeasible-interior-point methods for linear programming
--TR

--CTR
Asa Ben-Hur , Joshua Feinberg , Shmuel Fishman , Hava T. Siegelmann, Probabilistic analysis of a differential equation for linear programming, Journal of Complexity, v.19 n.4, p.474-510, August
Petra Huhn , Karl Heinz Borgwardt, Interior-point methods: worst case and average case analysis of a phase-I algorithm and a termination procedure, Journal of Complexity, v.18 n.3, p.833-910, September 2002
infeasible-interior-point algorithm;linear programming;average-case behavior