Probabilistic analysis of two complexity measures for linear programming problems ^{∗}

M. J. Todd ^{†}  Levent Tunçel^{‡}  Yinyu Ye^{§}

September 28, 1998

Abstract

This note provides a probabilistic analysis of χ̄_{A}, a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A ∈ IR^{m×n}. We show that if A is a standard Gaussian matrix, then E(ln χ̄_{A}) = O(min{m ln n, n}). Thus, the expected running time of linear programming is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. We show that the same bound holds for E(ln σ(A)), where σ(A) is another condition number of A arising in complexity analyses of linear programming problems.

∗This work was done while the authors were visiting the Mathematical Sciences Research Institute, UC Berkeley, USA.

†School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853. E-mail: miketodd@cs.cornell.edu. This author was supported in part by NSF through grant DMS-9805602 and ONR through grant N00014-96-1-0050, and also by the Mathematical Sciences Research Institute, UC Berkeley, USA.

‡Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada. E-mail: ltuncel@math.uwaterloo.ca. This author’s research was supported in part by Tokyo Institute of Technology and research grants from NSERC of Canada.

§Department of Management Sciences, The University of Iowa, Iowa City, IA 52242. E-mail: yinyu-ye@uiowa.edu. This author was supported in part by NSF Grants DMI-9522507 and DMS-9703490, and also by the Mathematical Sciences Research Institute, UC Berkeley, USA.

Keywords: Linear Programming, Interior-Point Methods, Probabilistic Analysis.

1 Introduction

Consider the linear programming (LP) problems in primal-dual form:

Primal: minimize c^{T} x
subject to Ax = b,
x ≥ 0,

(1)

and

Dual: maximize b^{T} y
subject to s = c − A^{T} y ≥ 0,

(2)

where c ∈ IR^{n} and b ∈ IR^{m} are given vectors, A ∈ IR^{m×n} is a given matrix of rank m, and x ∈ IR^{n} and y ∈ IR^{m} are unknown vectors.

Recently, Vavasis and Ye [14] proposed a primal-dual “layered-step” interior point (LIP) algorithm for linear programming with data given by real numbers (also see Megiddo, Mizuno and Tsuchiya [7] for a modification of the LIP algorithm). This algorithm follows the central path, either with short steps or with a new type of step called a “layered least squares” (LLS) step. The algorithm returns an exact optimum after a finite number of steps—in particular, after O(n^{3.5}c(A)) Newton iterations, where

c(A) = ln χ̄_{A} + ln n

and χ̄_{A} is a function of the coefficient matrix A. (We state the definition of χ̄_{A} and derive some of its properties in Section 2.) This is in contrast to all previous interior methods, whose complexity depends on b and c as well as A. This is important because there are many classes of problems in which A is “well-behaved” but b and c are arbitrary vectors.

In this short note, we prove that, if A is a standard Gaussian matrix, i.e., each component of A is independently and identically distributed (i.i.d.) from the N(0, 1) distribution, then

E(ln χ̄_{A}) = O(min{m ln n, n}).

Thus, the expected running time of linear programming is bounded by a polynomial in m and n for any right-hand side b and objective coefficient vector c when A is randomly generated in this way. We provide a similar bound on E(| ln σ(A)|), where σ(A) is another function of A relevant to the complexity of linear programming algorithms (see Section 3).

2 What is χ̄_{A}?

Let us define D to be the set of all positive definite n × n diagonal matrices. Then, χ̄_{A} is defined by

χ̄_{A} = sup{∥A^{T} (ADA^{T})^{−1}AD∥ : D ∈ D}.

(We use the 2-norm and the induced operator norm.) This quantity is always finite. It appears that Dikin [3] first proved this result, using the Cauchy-Binet formula. Later independent proofs were given by Ben-Tal and Teboulle [2], Stewart [9], and Todd [10]. Forsgren [4] describes the history and gives some extensions of this result.

Since (ADA^{T})^{−1}ADc minimizes ∥D^{1/2}(A^{T} y − c)∥, an equivalent way to define these parameters is in terms of weighted least squares:

χ̄_{A} = sup \{\frac{∥A^{T} y∥}{∥c∥} : y minimizes ∥D^{1/2}(A^{T} y − c)∥ for some c ∈ IR^{n}, D ∈ D\} .

(3)

Observe that this parameter is invariant when A is scaled by a constant. More generally, it is invariant if A is replaced by RA for any m × m nonsingular matrix R. This means that χ̄_{A} actually depends on the nullspace of A rather than on A itself.

We first prove the following simple result. This can be obtained from Dikin’s result algebraically, but we sketch a simple geometric proof based on the arguments of Todd [10].

Lemma 1 Let B denote the set of all bases (nonsingular m×m submatrices) of A. Then,

χ̄_{A} ≤ max{∥A^{T} B^{−T} ∥ : B ∈ B}.

Proof. We use the characterization (3) and analyze those vectors y that are candidates for the solution of the least-squares problems there. Fix c and consider the polyhedral subdivision of IR^{m} induced by the hyperplanes a_{j}^{T} y = c_{j}, j = 1, …, n. A least-squares solution y must lie in one of these polyhedra. If it lies in a bounded polyhedron, it can be written as a convex combination of the vertices of the subdivision. If not, it can be expressed as the sum of a convex combination of vertices of the subdivision and a nonnegative combination of extreme rays of the subdivision. But removing the second summand, if present, moves y closer to at least one of the hyperplanes and no further from any of them, and so decreases the least-squares objective no matter what D is. Thus all least-squares solutions lie in the convex hull of the vertices of the subdivision. Each such vertex has the form B^{−T} c_{B} for some basis, where c_{B} is the corresponding subvector of c, and thus

∥A^{T} y∥/∥c∥ ≤ max{∥A^{T} B^{−T} c_{B}∥/∥c∥} ≤ max{∥A^{T} B^{−T} ∥}.

The following lemma is from Vavasis and Ye [14]:

Lemma 2 Let B be a basis of A. Then, ∥A^{T} B^{−T} ∥ ≤ χ̄_{A}.

Proof. Let D_{ϵ} be the matrix with ones in positions corresponding to B and 0 < ϵ << 1 (very small) in the remaining diagonal positions. In the limit as ϵ → 0^{+}, we have that AD_{ϵ}A^{T} tends to BB^{T}. Since B is invertible, (AD_{ϵ}A^{T})^{−1} tends to (BB^{T})^{−1}. Also, AD_{ϵ} tends to a matrix with a copy of B, and the remaining columns filled in by zeros. The resulting product in the definition in the limit is precisely [A^{T} B^{−T} , 0].

Combining the two lemmas, we have:

Theorem 1 Let B denote the set of all bases of A. Then

χ̄_{A} = max{∥B^{−1}A∥ : B ∈ B}.

Let B be a basis of A, and, without loss of generality let A = [B, N] = [B, a_{B1}, a_{B2}, ..., a_{B(n−m)}]. Then,

B^{−1}AA^{T} B^{−T} = I + B^{−1}NN^{T} B^{−T} ,

where I is the identity matrix in IR^{m×m}. Thus,

∥B^{−1}A∥^{2} ≤ m + trace(B^{−1}NN^{T} B^{−T})
= m + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{2}

≤ (m^{1/2} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥)^{2} .

Therefore, we have

Corollary 1 Let B denote the set of all bases of A. Then,

χ̄_{A} ≤ ∑_{B∈B} (m^{1/2} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥) .

We will use this corollary to bound the expected value of ln χ̄_{A} in Section 4.

First, we relate χ̄_{A} to another measure of A, so that our bound gives information about the latter also.

3 Another Condition Measure of A

We now describe another function of A (due to Ye, see for instance [15]) also arising from computational complexity considerations in LP algorithms. Let S denote the range of A^{T}, so that S^{⊥} is the nullspace of A. Consider the following pair of feasibility problems (see [13]):

(P) \{ \begin{matrix}x & ∈ & S^{⊥}, \\ ∥x∥_{1} & = & 1, \\ x & ≥ & 0. \end{matrix}

(D) \{ \begin{matrix}s & ∈ & S, \\ ∥s∥_{1} & = & 1, \\ s & ≥ & 0. \end{matrix}

If we assume that both (P) and (D) have feasible solutions, then there exist a proper partition [B, N] of {1, 2, …, n} and a feasible pair (x, s) such that x ∈ S^{⊥}, x_{N} = 0, x_{B} > 0, s ∈ S, s_{N} > 0, s_{B} = 0. Note that (P) and (D) cannot both be infeasible. If (P) is infeasible then N = {1, 2, …, n} and if (D) is infeasible then B = {1, 2, …, n}.

Ye’s measure for this feasibility pair is defined as follows:

σ(S^{⊥}) := min_{j∈B} max_{x∈S^{⊥}:∥x∥_{1}=1,x≥0} {x_{j}} ,

σ(S) := min_{j∈N} max_{s∈S:∥s∥_{1}=1,s≥0} {s_{j}} ,

σ(A) := min {σ(S), σ(S^{⊥})} ,

where we define σ(S) (or σ(S^{⊥})) to be 1 if the corresponding problem is infeasible. A pair of feasible solutions or a strictly feasible solution to one (and hence a witness that the other is infeasible) can be found in O(\sqrt{n}(| ln σ(A)|+ ln n)) iterations (see [15, 13]), so we are again interested in bounding the expected value of | ln σ(A)|.

Let us define for v ∈ IR^{n}, J ⊆ {1, 2, …, n},

v_{J}^{+} := \{ \begin{matrix}−∞ & if v_{J} ≤ 0 \\ max_{i∈J}\{v_{i}\} & otherwise, \end{matrix}

and v_{J}^{−} := − (−v)_{J}^{+}. Next we state a dual characterization of σ(S) due to Tunçel [12].

Proposition 1 Let [B,N] be the strictly complementary partition defined by A. Suppose S^{⊥} contains no unit vector and B ≠ ∅. Then,

σ(S^{⊥}) := min_{i∈B} max ; \begin{matrix}x ∈ S^{⊥} \\ ∥x∥_{1} = 1 \\ x ≥ 0 \end{matrix} \{x_{i}\} = min ; \begin{matrix}γ ∈ S \\ 0 < γ_{B}^{+} < 1 \\ γ_{B}^{+} − γ_{B}^{−} = 1 \end{matrix} γ_{B}^{+}.

The statement above is slightly different than the one in [12] (there, [B, N] is assumed to be a proper partition; however, its proof only uses B ≠ ∅).

In this section, we relate χ̄_{A} to the minimum of the σ measure of various matrices closely related to A. It is convenient to work with the inverse of χ̄_{A}, so we define

ρ(S) := \frac{1}{χ̄_{A}} .

(Recall that χ̄_{A} depends only on the nullspace S^{⊥} of A, so any choice for A yields the same result.) We use the following characterization of ρ(S), due to O’Leary[8]:

Proposition 2 Let J denote a nonempty subset of the index set {1, 2, …, n} and J̄ be its complement. Then considering J, γ and ξ as the variables, we have

ρ(S) = inf ∥γ_{J}∥
sign(γ_{i}) = sign(ξ_{i}), i ∈ J̄,
∥γ∥ = 1,
γ ∈ S,  ξ ∈ S^{⊥}.

It is not hard to see that the above infimum is attained; after taking limits down a subsequence of a minimizing sequence, we can put into J any components that are zero in γ, and replace the limiting ξ if necessary (if it has a zero component in J̄ corresponding to a nonzero component of γ) by a suitable member of the subsequence. Alternatively, in the argument below we can take a near-optimal solution and then take limits.

Let K ⊆ {1, 2, …, n}. If we multiply by (−1) the columns of A indexed by K, then the resulting matrix (we call it the signing of A by K and denote it A_{−K}) has the same χ̄ value as A (this is apparent from Proposition 2). For a subspace U we similarly denote by U_{−K} the subspace consisting of points of U with their components indexed by K multiplied by (−1); note that (S^{⊥})_{−K} = (S_{−K})^{⊥}, so we can write S_{−K}^{⊥} unambiguously. We let σ_{K}(A) denote the σ value of A_{−K}, and similarly σ_{K}(S) and σ_{K}(S^{⊥}). We write \underline{σ}(A) for min_{K⊆{1,2,...,n}} σ_{K}(A). We have the following fact. For similar results using different norms, see [12].

Lemma 3

ρ(S) ≤ \underline{σ}(A).

Proof. Vavasis and Ye [13] proved ρ(S) ≤ σ(S), ρ(S^{⊥}) ≤ σ(S^{⊥}) (and ρ(S) ≤ \frac{σ(A)}{1−σ(A)}). Gonzaga and Lara [5] showed ρ(S) = ρ(S^{⊥}). Therefore, we have

ρ(S) ≤ σ(A).  (4)

Since we established that every signing of A gives the same χ̄_{A} value, applying inequality (4) to each signing K concludes the proof.

Theorem 2

\frac{1}{\sqrt{n}}\underline{σ}(A) ≤ ρ(S) ≤ \underline{σ}(A).

Proof. The right-hand inequality is Lemma 3. It remains to prove the left-hand inequality.

First we treat some special cases. If the unit vector e_{j} lies in S, and S is not spanned by e_{j}, then it is easy to check that

ρ(S\\{j\}) = ρ(S) and \underline{σ}(A\\{j\}) = \underline{σ}(A),

where S\{j} denotes the subspace of IR^{n−1} obtained by eliminating the jth component of every member of S and A\{j} denotes the matrix obtained from A by deleting its jth column. If S is spanned by a unit vector, then it is easy to see that both ρ(S) and \underline{σ}(A) are one, and the inequality holds. It also holds whenever ρ(S) is one. So from now on we assume that ρ(S) < 1 and that neither S nor S^{⊥} contains a unit vector.

We consider the optimization problem in Proposition 2 and let γ^{∗}, ξ^{∗}, and J give an optimal solution. Since ∥γ_{J}^{∗}∥ < 1 = ∥γ^{∗}∥, we have γ_{J}^{∗} and γ∗ ; J̄ nonzero. (If γ_{J}^{∗} were zero, γ^{∗} could not be orthogonal to ξ^{∗}.) We can also assume that J contains all indices of zero components of γ^{∗}, so that γ^{∗} and hence ξ^{∗} are nonzero on J̄. We use this solution to produce a feasible solution to the dual characterization in Proposition 1 of σ_{K}(S^{⊥}) (for some signing of A) with a close objective value.

Let γ_{j}^{∗} be the largest (in absolute value) of the components indexed by J, and let γ_{k}^{∗} be the largest (in absolute value) of the components indexed by J̄. Then at least one of |γ_{j}^{∗}| and |γ_{k}^{∗}| is at least 1/\sqrt{n}. Now scale γ^{∗} to get γ with |γ_{j}| + |γ_{k}| = 1; the scale factor is no more than \sqrt{n}, so we have |γ_{j}| = ∥γ_{J}∥_{∞} ≤ ∥γ_{J}∥ at most \sqrt{n}ρ(S).

By assumption, e_{j} does not lie in S, so there is some ξ̂ in S^{⊥} with ξ̂_{j} ≠ 0. If we had ξ_{j}^{∗} zero, we could add a small multiple of ξ̂ to ξ^{∗} so that its jth component would have the same sign as γ_{j} and then move j from J to J̄, contradicting the optimality of γ^{∗}. In fact, let Ĵ ⊆ J be the set of indices where γ_{J} is nonzero. The same argument shows that ξ^{∗} is nonzero on Ĵ. So ξ^{∗} is nonzero on Ĵ, where it has the opposite sign to γ (or we could again move components to J̄, decreasing the objective function), and on J̄, where it has the same sign as γ.

Now we choose a signing A_{−K} of A so that ξ^{∗} is nonpositive. It is then negative on Ĵ and J̄, so γ is positive on Ĵ and negative on J̄. Moreover, −ξ^{∗} is nonnegative, so for this signing, B contains Ĵ and J̄. Now since γ is negative on J̄ and j ∈ B, we have γ_{B}^{+} = γ_{j}. Similarly, γ_{B}^{−} = γ_{k}. Hence γ is feasible in the dual characterization of σ_{K}(S^{⊥}) with objective function value at most \sqrt{n}ρ(S) and the proof is complete.

Corollary 2 For any distribution on A, we have

E(| ln \underline{σ}(A)|) ≤ E(ln χ̄_{A}) ≤ E(| ln \underline{σ}(A)|) + \frac{1}{2} ln n.

4 Analysis of Random A

In the preceding two sections, we have presented a characterization of χ̄_{A} in terms of bases of A and we have related χ̄_{A} to \underline{σ}(A). Some probabilistic analyses of these related entities have been carried out for A with a Gaussian distribution (see, for examples, Anstreicher et al. [1], Girko [6], Todd [11], and Ye [15]), and they can both be used in our probabilistic analysis presented in this section. For simplicity, we shall use the characterization of χ̄_{A} to prove our next main theorem.

We have the following lemma due to Girko [6] (see also Todd [11]).

Lemma 4 Let B ∈ IR^{m×m} be a standard Gaussian matrix. Furthermore, let a ∈ IR^{m} be a standard Gaussian vector, independent of B. Then, B^{−1}a is a random vector

B^{−1}a = \frac{1}{η_{0}} ( \begin{matrix}η_{1} \\ η_{2} \\ ... \\ η_{m} \end{matrix} ) ,

where the η_{i}, i = 0, 1, ..., m, are i.i.d. from N(0, 1).

The next lemma is similar to results of Anstreicher et al. [1].

Lemma 5 Let B ∈ IR^{m×m} be a standard Gaussian matrix. Furthermore, let a ∈ IR^{m} be a standard Gaussian vector independent of B. Then,

E(∥B^{−1}a∥^{1/2}) ≤ m^{1/4} · (1 + \frac{2}{\sqrt{2π}} ) .

Proof. From the preceding lemma

E (∥B^{−1}a∥^{1/2}) = E (\frac{(∑_{i=1}^{m} η_{i}^{2})^{1/4}}{|η_{0}|^{1/2}} )
= E ((∑_{i=1}^{m} η_{i}^{2})^{1/4}) · E (|η_{0}|^{−1/2})
≤ (E (∑_{i=1}^{m} η_{i}^{2}))^{1/4} · E (|η_{0}|^{−1/2})
= m^{1/4}E (|η_{0}|^{−1/2}) ,

since the η_{i}, i = 0, 1, ..., m, are i.i.d. from N(0, 1). Now consider E (|η_{0}|^{−1/2}). Let f(x) = \frac{1}{\sqrt{2π}} exp(−x^{2}/2), the density function of N(0, 1). Then

E (|η_{0}|^{−1/2}) = 2 ∫_{0}^{∞} x^{−1/2}f(x)dx
= 2 (∫_{1}^{∞} x^{−1/2}f(x)dx + ∫_{0}^{1} x^{−1/2}f(x)dx)
≤ 2 (∫_{1}^{∞} f(x)dx + ∫_{0}^{1} x^{−1/2}f(x)dx)
= 2 (∫_{0}^{∞} f(x)dx + ∫_{0}^{1}(x^{−1/2} − 1)f(x)dx)
= 1 + 2 ∫_{0}^{1}(x^{−1/2} − 1)f(x)dx
≤ 1 + 2 ∫_{0}^{1}(x^{−1/2} − 1)\frac{1}{\sqrt{2π}} dx
= 1 + \frac{2}{\sqrt{2π}} .

Thus, we have the desired result.

Finally,

Theorem 3 Let A ∈ IR^{m×n} be a standard Gaussian matrix with m ≥ 3. Then, with probability one A has full row rank, and

E(ln χ̄_{A}) ≤ (2m + 2) ln n.

Proof. From Corollary 1 and the last lemma,

E(ln χ̄_{A})

≤ E (ln ∑_{B∈B} (m^{1/2} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥))
≤ E (ln ( ∑_{B∈B} (m^{1/4} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{1/2}))^{2})
= E (2 ln ∑_{B∈B} (m^{1/4} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{1/2}))
= 2E (ln ∑_{B∈B} (m^{1/4} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{1/2}))
≤ 2 ln E ( ∑_{B∈B} (m^{1/4} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{1/2}))
= 2 ln ( ∑_{B∈B} (m^{1/4} + ∑_{j=1}^{n−m} E (∥B^{−1}a_{Bj}∥^{1/2})))
≤ 2 ln ( ∑_{B∈B} (m^{1/4} + ∑_{j=1}^{n−m} m^{1/4} (1 + \frac{2}{\sqrt{2π}} )))
≤ 2 ln ( ∑_{B∈B} ((n − m + 1)m^{1/4} (1 + \frac{2}{\sqrt{2π}} )))
≤ 2 ln (( \begin{matrix}n \\ m \end{matrix} ) ((n − m + 1)m^{1/4} (1 + \frac{2}{\sqrt{2π}} )))
= 2 ln ( \begin{matrix}n \\ m \end{matrix} ) + 2 ln ((n − m + 1)m^{1/4} (1 + \frac{2}{\sqrt{2π}} ))
≤ 2(m ln n − ln m) + 2 ln(n − m + 1) + ln m/2 + 2 ln 2
≤ (2m + 2) ln n.

The expectation bound can be further sharpened if we consider the power 1/(1 + ϵ) for any fixed ϵ > 0, rather than (1/2), in Lemma 5. We can show

E(∥B^{−1}a∥^{1/(1+ϵ)}) ≤ m^{1/2(1+ϵ)} · (1 + \frac{2}{ϵ\sqrt{2π}} ) .

Then, we can modify the proof in Theorem 3 to

E(ln χ̄_{A})

≤ E (ln ∑_{B∈B} (m^{1/2} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥))

≤ E (ln ( ∑_{B∈B} (m^{1/2(1+ϵ)} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{1/(1+ϵ)}))^{1+ϵ})

= (1 + ϵ)E (ln ∑_{B∈B} (m^{1/2(1+ϵ)} + ∑_{j=1}^{n−m} ∥B^{−1}a_{Bj}∥^{1/(1+ϵ)}))

≤ (1 + ϵ) ln ( ∑_{B∈B} (m^{1/2(1+ϵ)} + ∑_{j=1}^{n−m} m^{1/2(1+ϵ)} (1 + \frac{2}{ϵ\sqrt{2π}} )))

≤ (1 + ϵ) ln (( \begin{matrix}n \\ m \end{matrix} ) ((n − m + 1)m^{1/2(1+ϵ)} (1 + \frac{2}{ϵ\sqrt{2π}} )))
= (1 + ϵ) ln ( \begin{matrix}n \\ m \end{matrix} ) + (1 + ϵ) ln ((n − m + 1)m^{1/2(1+ϵ)} (1 + \frac{2}{ϵ\sqrt{2π}} )) .

Suppose n > m ≥ 3. If we choose ϵ = 1/m, then the bound is

E(ln χ̄_{A}) ≤ (m + 3) ln n

(we use ln(1 + 2/(\sqrt{2π}m)) ≤ ln m + ln(2/\sqrt{2π} + 1/3) ≈ ln m + ln 1.1312); if we let ϵ = 1/n and note that

( \begin{matrix}n \\ m \end{matrix} ) ≤ 2^{n},

then

E(ln χ̄_{A}) ≤ n ln 2 + 3 ln n + 1

(using ln(1+2/(\sqrt{2π}n)) ≤ ln n+ln(2/\sqrt{2π}+1/4) and ln 2+(5/4) ln(2/\sqrt{2π}+ 1/4) < 1).

To summarize, we have Corollary 3 Let A ∈ IR^{m×n} be a standard Gaussian matrix with n > m ≥ 3. Then, with probability one A has full row rank, and

E(ln χ̄_{A}) ≤ min{(m + 3) ln n, n ln 2 + 3 ln n + 1}.

From Corollary 2 we deduce

Corollary 4 Let A ∈ IR^{m×n} be a standard Gaussian matrix with n > m ≥ 3. Then, with probability one A has full row rank, and

E(| ln \underline{σ}(A)|) ≤ min\{(m + 3) ln n, n ln 2 + 3 ln n + 1\}.

We also have a corollary for other distributions of A.

Corollary 5 Let the linear programming constraint matrix A ∈ IR^{m×n} be randomly generated. If for any basis B and any column vector a of A not in B, we have

E (∥B^{−1}a∥^{\frac{1}{m^{α}}} ) ≤ O(m^{β})

for some constants α, β ≥ 0, then the expected running time of the LIP algorithm is bounded by a polynomial in m and n for any right-hand side and objective function vectors.

References

[1] K. M. Anstreicher, J. Ji, F. Potra, and Y. Ye, Probabilistic analysis of an infeasible primal-dual algorithm for linear programming. Working paper, Dept. of Management Sciences, University of Iowa (Iowa City, IA, 1992), to appear in Mathematics of Operations Research.

[2] A. Ben-Tal and M. Teboulle, A geometric property of the least squares solution of linear equations. Linear Algebra and Its Applications 139 (1990) 165–170.

[3] I. I. Dikin, On the speed of an iterative process. Upravlaemye Sistemy 12 (1974) 54–60.

[4] A. Forsgren, On linear least-squares problems with diagonally dominant weight matrices. SIAM Journal on Matrix Analysis and Applications 17 (1996) 763–788.

[5] C. C. Gonzaga and H. Lara, A note on properties of condition numbers. Linear Algebra and Its Applications 261 (1997) 269–273.

[6] V. L. Girko, On the distribution of solution of systems of linear equations with random coefficients. Theory of Probability and Mathematical Statistics 2 (1974) 41–44.

[7] N. Megiddo, S. Mizuno and T. Tsuchiya, A modified layered-step interior-point algorithm for linear programming. IBM Technical Report, IBM Research Lab, San Jose, CA, 1996.

[8] D. P. O’Leary, On bounds for scaled projections and pseudoinverses. Linear Algebra and Its Applications 132 (1990) 115–117.

[9] G. W. Stewart, On scaled projections and pseudoinverses. Linear Algebra and Its Applications 112 (1989) 189–193.

[10] M. J. Todd, A Dantzig-Wolfe-like variant of Karmarkar’s interior-point linear programming algorithm. Operations Research 38 (1990) 1006– 1018.

[11] M. J. Todd, Probabilistic models for linear programming. Mathematics of Operations Research 16 (1991) 671–693.

[12] L. Tunçel, On the condition numbers for polyhedra in Karmarkar’s form. Operations Research Letters, to appear.

[13] S. A. Vavasis and Y. Ye, Condition numbers for polyhedra with real number data. Operations Research Letters 17 (1995) 209–214.

[14] S. A. Vavasis and Y. Ye, A primal-dual interior-point method whose running time depends only on the constraint matrix. Mathematical Programming 74 (1996) 79–120.

[15] Y. Ye, Toward probabilistic analysis of interior-point algorithms for linear programming. Mathematics of Operations Research 19 (1994) 38–52.