A SUPERLINEAR INFEASIBLE-INTERIOR-POINT AFFINE SCALING ALGORITHM FOR LCP

R. D. C. MONTEIRO^{∗} AND S. J. WRIGHT^{†}

Abstract. We present an infeasible-interior-point algorithm for monotone linear complementarity problems in which the search directions are affine scaling directions and the step lengths are obtained from simple formulae that ensure both global and superlinear convergence. By choosing the value of a parameter in appropriate ways, polynomial complexity and convergence with Q-order up to (but not including) two can be achieved. The only assumption made to obtain the superlinear convergence is the existence of a solution satisfying strict complementarity.

Key words. infeasible-interior-point methods, monotone linear complementarity problems, superlinear convergence

1. Introduction. The monotone linear complementarity problem (LCP) is to find a vector pair (x, y) ∈ IR^{n} × IR^{n} that satisfies the following conditions:

y = Mx + q, (1.1a) x ≥ 0, y ≥ 0, (1.1b) x^{T} y = 0, (1.1c)

where M is a positive semidefinite matrix. We use S to denote the solution set of (1.1) and S_{c} to denote the set of solutions that satisfy strict complementarity, that is,

S_{c} = {(x^{∗}, y^{∗}) ∈ S | x^{∗} + y^{∗} > 0}.

We say that (1.1) is nondegenerate if S_{c} ≠ 0.

It is well known that problems in linear programming and convex quadratic programming can be posed in the form (1.1). This fact partly accounts for the extensive effort that has gone into designing interior-point algorithms for this class of problems.

In this paper, we develop a superlinearly convergent infeasible-interior-point algorithm that uses only affine scaling directions. Several infeasible-interior-point algorithms have been developed to solve problem (1.1), or the linear programming (LP) subclass. For LP problems, these include works by Kojima, Megiddo, and Mizuno [1], Kojima, Megiddo, and Todd [3], Mizuno [2], Potra [6], and Zhang and Zhang [12]. For LCP, we mention Wright [7, 8], while Zhang [11] considers a generalized form of the monotone LCP.

In a companion paper [4], we describe a method in which all iterates (x^{k}, y^{k}) are strictly feasible (that is, (x^{k}, y^{k}) > 0 and y^{k} = Mx^{k} + q) and search directions are generated by solving the linear system

[ \begin{matrix}M & −I \\ Y^{k} & X^{k} \end{matrix} ] [ \begin{matrix}Δx^{k} \\ Δy^{k} \end{matrix} ] = [ \begin{matrix}0 \\ −X^{k}Y^{k}e \end{matrix} ] , (1.2)

∗ School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332. The work of this author was based on research supported by the National Science Foundation under grant DDM-9109404 and the Office of Naval Research under grant N00014-93-1-0234. This work was done while the first author was a faculty member of the Systems and Industrial Engineering Department at the University of Arizona.

† Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, IL 60439. The work of this author was based on research supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.

where X^{k} = diag(x_{1}^{k}, x_{2}^{k}, …, x_{n}^{k}), Y^{k} = diag(y_{1}^{k}, y_{2}^{k}, …, y_{n}^{k}), and e = (1, 1, …, 1)^{T}. The direction (Δx^{k}, Δy^{k}) is known as the primal-dual affine scaling direction, and one can easily see that it is simply the Newton direction for the nonlinear mapping F (x, y) = (Mx + q − y, XY e) = (0, 0) at the point (x^{k}, y^{k}). In [4], we choose a parameter δ ∈ (0, 1/2) and define the scalars ϕ_{k} and χ_{k} by

(1.3)  ϕ_{k} =^{△} \frac{Δx^{k}^{T} Δy^{k}}{x^{k}^{T} y^{k}} ,  χ_{k} =^{△} max (0, max_{{i=1,2,...,n \atop Δx_{i}^{k}Δy_{i}^{k}<0}} (\frac{|Δx_{i}^{k}Δy_{i}^{k}|}{x_{i}^{k}y_{i}^{k}}))

and the step length α_{k} by

α_{k} =^{△} \frac{δ}{δ + χ_{k} + (1 + δ)ϕ_{k}} . (1.4)

The step from one iterate to the next is defined as

(x^{k+1}, y^{k+1}) = (x^{k}, y^{k}) + α_{k}(Δx^{k}, Δy^{k}).

The resulting simple algorithm is globally and superlinearly convergent. It even exhibits polynomial complexity for certain choices of the parameter δ and starting point (x^{0}, y^{0}).

In this paper, we generalize this algorithm by allowing the iterates to be infeasible. Given an initial point (x^{0}, y^{0}) > 0, the modified algorithm generates iterates (x^{k}, y^{k}) in such a way that x^{k}^{T} y^{k} ↓ 0 and ∥y^{k} − Mx^{k} − q∥ → 0 as k → ∞. Moreover, the convergence of {x^{k}^{T} y^{k}} to zero is superlinear. Much of the elegance of the analysis for the feasible algorithm [4] does not carry through to this infeasible case and the results are slightly weaker here, so we feel that a separate report is needed.

Our analysis makes use of the fact that all iterates generated by our algorithm lie in a set of the form

N (δ, η, ρ) = {(x, y) > 0 | ρx^{T} y ≥ ∥r∥^{1+δ}, x_{i}y_{i} ≥ η(x^{T} y)^{1+δ}, i = 1, 2, …, n},

where δ > 0, η > 0, and ρ ≥ 0, and r = y − Mx − q. Note that N (δ, η, 0) corresponds to the neighborhood N (δ, η) that was used in [4].

We formally specify our algorithm as follows.

Algorithm IAS initially: Choose δ ∈ (0, 1] and (x^{0}, y^{0}) > 0; for k = 0, 1, 2, …

Let (Δx^{k}, Δy^{k}) denote the solution of the linear system

(1.5a)  MΔx − Δy = r,
(1.5b)  Y Δx + XΔy = −Y Xe,

where r = r^{k} = y^{k} − Mx^{k} − q, X = X^{k}, and Y = Y^{k}; Calculate ϕ_{k} and χ_{k} as in (1.3) and set

α_{k} = \frac{δ}{δ + χ_{k} + (1 + δ)ϕ_{k}^{+}} , (1.6)

where ϕ_{k}^{+} = max(0, ϕ_{k});
Set (x^{k+1}, y^{k+1}) = (x^{k} + α_{k}Δx^{k}, y^{k} + α_{k}Δy^{k});

end for

Note that in the case of (x^{k}, y^{k}) feasible, we have

Δx^{k}^{T} Δy^{k} = Δx^{k}^{T} MΔx^{k} ≥ 0.

Therefore ϕ_{k} ≥ 0 for all k, so the definition of α_{k} in (1.6) reduces to (1.4). Hence, the algorithm in [4] is a special case of Algorithm IAS.

In the remainder of the paper, we prove that Algorithm IAS produces a sequence of iterates {(x^{k}, y^{k})} such that the complementarity gap x^{k}^{T} y^{k} and the residual ∥r^{k}∥ converge to zero. Moreover, we show that this convergence is Q-superlinear provided that S_{c} ≠ ∅ and δ < 1/7. An interesting feature of our superlinear convergence result is that we do not assume any condition that would imply the boundedness of the sequence {(x^{k}, y^{k})} such as (i) existence of a strictly feasible point or (ii) convergence of {x^{k}^{T} y^{k}} and {∥r^{k}∥} to 0 at a similar rate. Most superlinear convergence results for infeasible-interior-point algorithms require the first condition. Exceptions are the results of Potra [6] and Wright [8], which require only the second condition; specifically, for some γ > 0 we have x^{k}^{T} y^{k} ≥ γ∥r^{k}∥ for all k ≥ 0. In this paper, we show first that {x^{k}^{T} y^{k}} converges superlinearly to zero then, as a consequence, that the sequence of iterates {(x^{k}, y^{k})} converges and hence is bounded. Also, for certain values of δ and for initial points (x^{0}, y^{0}) satisfying (x^{0}, y^{0}) ≥ (x^{∗}, y^{∗}), for some (x^{∗}, y^{∗}) ∈ S, we show that the number of iterations required to reduce the gap x^{k}^{T} y^{k} below a certain ϵ > 0 is polynomially bounded.

The following notational conventions are used in the remainder of the paper. When S_{c} ≠ ∅, we can partition the index set {1, 2, …, n} into subsets B and N such that

i ∈ B ⇔ x_{i}^{∗} > 0, ∀(x^{∗}, y^{∗}) ∈ S_{c}, i ∈ N ⇔ y_{i}^{∗} > 0, ∀(x^{∗}, y^{∗}) ∈ S_{c}.

Unless otherwise specified, ∥.∥ denotes the the Euclidean norm. For a general vector z ∈ IR^{n} and index set L ⊆ {1, 2, …, n}, z_{L} denotes the vector made up of components z_{i} for i ∈ L. If M ∈ IR^{n×n} and I, L ⊆ {1, 2, …, n}, then M_{IL} refers to the submatrix of M consisting of the elements M_{ij} for i ∈ I and j ∈ L. If D ∈ IR^{n×n} is diagonal, then D_{B} denotes the diagonal matrix constructed from D_{ii} for i ∈ B.

2. Global Convergence. In this section, we prove the global convergence of Algorithm IAS. We show that for certain values of δ, Algorithm IAS has a polynomial bound on the number of iterations. We also obtain certain bounds on the directions generated by the algorithm, which will be used in the next section to prove superlinear convergence.

For much of the analysis, it is convenient to drop the iteration index k that appears on quantities such as (x^{k}, y^{k}), ϕ_{k}, and α_{k}. Accordingly, we define some index-free notation. For an arbitrary positive vector pair (x, y) > 0, let (Δx, Δy) be obtained from (1.5), and define

(x(α), y(α)) =^{△} (x, y) + α(Δx, Δy),
r(α) =^{△} y(α) − Mx(α) − q,
(2.1)  ϕ =^{△} \frac{Δx^{T} Δy}{x^{T} y} ,

χ =^{△} max (0, max_{{i=1,2,...,n \atop Δx_{i}Δy_{i}<0}} (\frac{|Δx_{i}Δy_{i}|}{x_{i}y_{i}})) ,

where α ∈ [0, 1].

We start by stating and proving some basic results for quantities in (2.1).

Lemma 2.1. ϕ ≥ −χ.

Proof. We have

ϕ = \frac{Δx^{T} Δy}{x^{T} y} ≥ ∑_{{i=1,2,...,n \atop Δx_{i}Δy_{i}<0}} \frac{Δx_{i}Δy_{i}}{x^{T} y} ≥ −\frac{χ}{x^{T} y} ∑_{{i=1,2,...,n \atop Δx_{i}Δy_{i}<0}} x_{i}y_{i} ≥ −χ.

Lemma 2.2. Let (x, y) > 0 be given, and let (Δx, Δy) be the direction determined by (1.5). Then, for all α ∈ [0, 1],

(a) x(α)^{T} y(α) = x^{T} y(1 − α + α^{2}ϕ);

(b) x_{i}(α)y_{i}(α) ≥ x_{i}y_{i}(1 − α − α^{2}χ);
(c) r(α) = (1 − α)r;

(d) Δx_{i}Δy_{i} = 0 for all i = 1, 2, …, n if and only if (x(1), y(1)) is a solution of (1.1) that satisfies strict complementarity.

Proof. Statements (a), (b), and (c) follow immediately from (1.5) and (2.1). The proof of (d) is essentially given by Monteiro and Wright [4, Lemma 3.1(d)], if we note in addition that r(1) = 0.

We now show that {x^{k}^{T} y^{k}} is a decreasing sequence and that the property of membership of N (δ, η, ρ) is inherited by successive iterates of the algorithm. In the proof of this result, we make use of the inequality

(1 − u)^{1+δ} ≤ 1 − (1 + δ)u + δu^{2},  ∀u ≤ 1,  ∀δ ∈ (0, 1], (2.2)

which is proved by Monteiro and Wright [4, Lemma 3.2].

Lemma 2.3. Suppose that (x, y) ∈ N (δ, η, ρ) for some δ ∈ (0, 1], η > 0, and ρ ≥ 0 and that (Δx, Δy) is determined by (1.5). Assume that Δx_{i}Δy_{i} ≠ 0 for some i ∈ {1, 2, …, n}. Then, for all

α ∈ J =^{△} [0, \frac{δ}{δ + χ + (1 + δ)ϕ^{+}} ] , (2.3)

where ϕ^{+} ≡ max(0, ϕ), we have (a) x(α)^{T} y(α) ≤ [1 − α/(1 + δ)]x^{T} y; and

(b) (x(α), y(α)) ∈ N (δ, η, ρ).

Proof. To show statement (a), note that for α ∈ J, we have

αϕ^{+} ≤ \frac{δϕ^{+}}{δ + χ + (1 + δ)ϕ^{+}} ≤ \frac{δ}{1 + δ} . (2.4)

Thus in view of Lemma 2.2(a), we obtain

x(α)^{T} y(α) ≤ x^{T} y(1 − α(1 − αϕ^{+})) ≤ x^{T} y (1 − \frac{α}{1 + δ} ) .

For statement (b), we start by showing that x(α)^{T} y(α) > 0 for all α ∈ J. Observe first that the condition that Δx_{i}Δy_{i} ≠ 0 for some i ∈ {1, 2, …, n} implies that either χ > 0 or ϕ > 0. Hence, χ + (1 + δ)ϕ^{+} > 0, and therefore

α ≤ \frac{δ}{δ + χ + (1 + δ)ϕ^{+}} ≤ \frac{1}{1 + χ + (1 + δ)ϕ^{+}} < 1, α ≤ \frac{1}{1 + χ}, (2.5)

for all α ∈ J. Observe that if ϕ ≥ 0, then, in view of Lemma 2.2(a) and (2.5), we have x(α)^{T} y(α) ≥ (1 − α)x^{T} y > 0, for all α ∈ J. Assume that ϕ < 0. In this case, we must have χ > 0. This together with (2.5), Lemma 2.1, and Lemma 2.2(a) then imply

x(α)^{T} y(α) = x^{T} y(1 − α + α^{2}ϕ)
≥ x^{T} y(1 − α − α^{2}χ)
> x^{T} y (1 − α(1 + χ)) ≥ 0

for all α ∈ J with α > 0. We have thus shown that x(α)^{T} y(α) > 0 for all α ∈ J. Now, using Lemma 2.2(a), (2.2), and (2.4), we obtain for all α ∈ J that

0 < η[x(α)^{T} y(α)]^{1+δ}
≤ η(x^{T} y)^{1+δ}[1 − α(1 − αϕ^{+})]^{1+δ}
≤ η(x^{T} y)^{1+δ}[1 − (1 + δ)α(1 − αϕ^{+}) + δα^{2}(1 − αϕ^{+})^{2}]
≤ η(x^{T} y)^{1+δ}[1 − (1 + δ)α(1 − αϕ^{+}) + δα^{2}]
(2.6)  ≤ η(x^{T} y)^{1+δ}[1 − α − α^{2}χ],

where in the last inequality we used the fact that the interval J is exactly the set of all α ≥ 0 for which

1 − α(1 + δ)(1 − αϕ^{+}) + δα^{2} ≤ 1 − α − α^{2}χ.

From (2.6), Lemma 2.2(b), and the fact that (x, y) ∈ N (δ, η, ρ), we have

x_{i}(α)y_{i}(α) ≥ x_{i}y_{i}(1 − α − α^{2}χ)
≥ η(x^{T} y)^{1+δ}(1 − α − α^{2}χ)
≥ η[x(α)^{T} y(α)]^{1+δ} > 0.

Thus, the second condition for membership of N (δ, η, ρ) is satisfied by (x(α), y(α)). To show the first condition, we observe that

ρx^{T} y ≥ ∥r∥^{1+δ}. (2.7)

From Lemma 2.2(c), we know that ∥r(α)∥ = (1 − α)∥r∥. By (2.2) and (2.7), it follows that

∥r(α)∥^{1+δ} = (1 − α)^{1+δ}∥r∥^{1+δ} ≤ [1 − (1 + δ)α + δα^{2}]ρx^{T} y. (2.8)

For α ≥ 0, the inequality

1 − (1 + δ)α + δα^{2} ≤ 1 − α + α^{2}ϕ (2.9)

is equivalent to δ ≥ α(δ − ϕ), which is satisfied by every α ∈ [0, δ/(δ + ϕ^{−})], where ϕ^{−} ≡ − min(0, ϕ). Now, using Lemma 2.1, we can easily see that J ⊆ [0, δ/(δ + ϕ^{−})]. We then conclude that (2.9) is satisfied by every α ∈ J. Hence, in view of (2.8) and Lemma 2.2(a), we have

∥r(α)∥^{1+δ} ≤ (1 − α + α^{2}ϕ)ρx^{T} y = ρx(α)^{T} y(α).

Therefore, the first condition for membership of (x(α), y(α)) in N (δ, η, ρ) is also satisfied, and we have the result.

From now on, given the initial point (x^{0}, y^{0}) and δ ∈ (0, 1], we let

π_{0} = \frac{min_{i=1,2,...,n}(x_{i}^{0}y_{i}^{0})}{x^{0}^{T} y^{0}/n}, ρ = \frac{∥r^{0}∥^{1+δ}}{x^{0}^{T} y^{0}} ,

η = \frac{min_{i=1,2,...,n}(x_{i}^{0}y_{i}^{0})}{(x^{0}^{T} y^{0})^{1+δ}} = \frac{π_{0}}{n(x^{0}^{T} y^{0})^{δ}} , (2.10)

Note that π_{0} (a measure of the centrality of the initial point) is at most 1 and (x^{0}, y^{0}) ∈ N (δ, η, ρ).

The following result is an immediate consequence of Lemma 2.2(c) and Lemma 2.3. Corollary 2.4. The sequence {(x^{k}, y^{k})} generated by Algorithm IAS satisfies

(a) x^{k+1}^{T} y^{k+1} ≤ [1 − α_{k}/(1 + δ)]x^{k}^{T} y^{k} for all k ≥ 0;

(b) r^{k} = ν_{k}r^{0} for all k ≥ 0, where ν_{k} ≡ Π_{l=0}^{k−1}(1 − α_{l});

(c) (x^{k}, y^{k}) ∈ N (δ, η, ρ) for all k ≥ 0, where η and ρ are as defined in (2.10).

Our main goal now is to derive estimates for the quantities χ and ϕ. These estimates will then be used to establish global convergence of Algorithm IAS, as well as polynomial complexity for certain values of δ. The following inequality is exploited in a number of proofs that follow.

Lemma 2.5. Let (x^{0}, y^{0}) and (x, y) be points such that y − Mx − q = ν(y^{0} − Mx^{0} − q) for some ν ∈ IR^{n}, and let (x̄, ȳ) be a point such that ȳ − Mx̄ − q = 0. Then,

0 ≤ ν^{2}x^{0}^{T} y^{0} + (1 − ν)^{2}x̄^{T} ȳ + x^{T} y + ν(1 − ν)(x^{0}^{T} ȳ + x̄^{T} y^{0})

−ν(x^{0}^{T} y + x^{T} y^{0}) − (1 − ν)(x̄^{T} y + x^{T} ȳ). (2.11)

Proof. See, for example, Wright [8, Lemma 3.2].

As an immediate consequence of this inequality, we obtain the following result.

Lemma 2.6. Let (x^{0}, y^{0}) > 0 be given. Then there exists a constant C_{0} ≥ 0 satisfying the following property: If (x, y) ≥ 0 is a point such that y − Mx − q = ν(y^{0} − Mx^{0} − q) for some ν ∈ [0, 1], then

max {ν∥x∥_{∞}, ν∥y∥_{∞}} ≤ C_{0} [x^{T} y + ν] . (2.12)

Proof. Assume that (x̄, ȳ) is a solution of (1.1). Using inequality (2.11) and the facts that ν ∈ [0, 1], (x^{0}, y^{0}) > 0, (x, y) ≥ 0, (x̄, ȳ) ≥ 0, and x̄^{T} ȳ = 0, we obtain

x^{0}^{T} (νy) + y^{0}^{T} (νx) ≤ νx^{0}^{T} y^{0} + x^{T} y + ν(x^{0}^{T} ȳ + y^{0}^{T} x̄)
≤ max {1 , x^{0}^{T} y^{0} + x^{0}^{T} ȳ + y^{0}^{T} x̄} (x^{T} y + ν).

Relation (2.12) now follows by letting

C_{0} =^{△} max {1, x^{0}^{T} y^{0} + x^{0}^{T} ȳ + y^{0}^{T} x̄} ; min_{i=1,2,...,n} {min(x_{i}^{0}, y_{i}^{0})}.

Lemma 2.7. Let the vectors u^{0} ∈ IR^{n} and v^{0} ∈ IR^{n} and the parameters η > 0 and δ ≥ 0 be given. Then, for every positive vector (x, y) ∈ IR^{2n} and scalar ν ≥ 0 such that

(2.13)  y − Mx − q = ν(v^{0} − Mu^{0}),
(2.14) min_{i=1,2,...,n} x_{i}y_{i} ≥ η(x^{T} y)^{1+δ},

the corresponding direction (Δx, Δy) determined by (1.5) satisfies

max (∥D^{−1}Δx∥, ∥DΔy∥) ≤ (x^{T} y)^{1/2} + \frac{2ν}{η^{1/2}(x^{T} y)^{(1+δ)/2}} [∥Y u^{0}∥ + ∥Xv^{0}∥] , (2.15)

where D ≡ X^{1/2}Y^{−1/2}.

Proof. We will first show that max (∥D^{−1}Δx∥, ∥DΔy∥) ≤ (x^{T} y)^{1/2} + 2ν [∥D^{−1}u^{0}∥ + ∥Dv^{0}∥] . (2.16) Indeed, it follows from (1.5a) and (2.13) that

MΔx − Δy = r = y − Mx − q = ν(v^{0} − Mu^{0}).

Therefore,

M(Δx + νu^{0}) = Δy + νv^{0},

which by monotonicity of (1.1) implies that

(Δx + νu^{0})^{T} (Δy + νv^{0}) ≥ 0.

Hence, we obtain Δx^{T} Δy ≥ −νu^{0}^{T} Δy − νv^{0}^{T} Δx − ν^{2}u^{0}^{T} v^{0}. (2.17) If we multiply (1.5b) by (XY)^{−1/2} and square both sides, we obtain

∥D^{−1}Δx∥^{2} + ∥DΔy∥^{2} + 2Δx^{T} Δy = x^{T} y,

which, in view of (2.17), implies

∥D^{−1}Δx − νDv^{0}∥^{2} + ∥DΔy − νD^{−1}u^{0}∥^{2} − ν^{2}∥Dv^{0} + D^{−1}u^{0}∥^{2} ≤ x^{T} y.

Therefore, using the inequality (β^{2} + γ^{2})^{1/2} ≤ |β| + |γ| and the triangle inequality, we have

∥D^{−1}Δx∥ ≤ [x^{T} y + ν^{2}∥Dv^{0} + D^{−1}u^{0}∥^{2}]^{1/2} + ν∥Dv^{0}∥
≤ (x^{T} y)^{1/2} + 2ν∥Dv^{0}∥ + ν∥D^{−1}u^{0}∥
(2.18)  ≤ (x^{T} y)^{1/2} + 2ν [∥Dv^{0}∥ + ∥D^{−1}u^{0}∥] .

A similar bound can be derived for ∥DΔy∥, and hence relation (2.16) follows. We now derive (2.15) from (2.16) and (2.14). From (2.14) we obtain

∥D^{−1}u^{0}∥^{2} = ∑_{i=1}^{n} \frac{y_{i}(u_{i}^{0})^{2}}{x_{i}} = ∑_{i=1}^{n} \frac{(y_{i}u_{i}^{0})^{2}}{x_{i}y_{i}} ≤ \frac{∥Y u^{0}∥^{2}}{η(x^{T} y)^{1+δ}} . (2.19)

Similarly, we also have

∥Dv^{0}∥^{2} ≤ \frac{∥Xv^{0}∥^{2}}{η(x^{T} y)^{1+δ}} . (2.20)

Relation (2.15) now follows by substituting (2.19) and (2.20) into (2.16).

We are now ready to show global convergence of Algorithm IAS without imposing any condition on the initial point (x^{0}, y^{0}).

Theorem 2.8. For any initial point (x^{0}, y^{0}) > 0, the sequence {(x^{k}, y^{k})} generated by Algorithm IAS satisfies

(a) x^{k}^{T} y^{k} → 0; and

(b) r^{k} → 0.

Proof. First note that (b) follows as a consequence of (a) from Corollary 2.4(c). To show (a), we assume for contradiction that x^{k}^{T} y^{k} does not converge to 0. Thus, in view of Corollary 2.4(a), it follows that there exists ϵ > 0 such that

x^{k}^{T} y^{k} ≥ ϵ, ∀k ≥ 0. (2.21)

Hence, in view of Corollary 2.4(c), we have

min_{i=1,2,...,n}{x_{i}^{k}y_{i}^{k}} ≥ η(x^{k}^{T} y^{k})^{1+δ} ≥ ηϵ^{1+δ}, ∀k ≥ 0. (2.22)

Since the point (x^{k}, y^{k}) satisfies the assumptions of Lemma 2.6 from Corollary 2.4(b), we obtain

max{ν^{k}∥x^{k}∥_{∞}, ν^{k}∥y^{k}∥_{∞}} ≤ C_{0} (x^{k}^{T} y^{k} + ν^{k}) ≤ C_{0} (x^{0}^{T} y^{0} + 1) , ∀k ≥ 0. (2.23)

Let (u^{0}, v^{0}) ∈ IR^{2n} be such that v^{0} − Mu^{0} = r^{0} (e.g., u^{0} = 0 and v^{0} = r^{0}). From Corollary 2.4, (x^{k}, y^{k}) and ν_{k} satisfy the assumptions of Lemma 2.7 with η given by (2.10). Hence, inequality (2.15) gives

max (∥(D^{k})^{−1}Δx^{k}∥, ∥D^{k}Δy^{k}∥)
≤ (x^{k}^{T} y^{k})^{1/2} + \frac{2ν^{k}}{η^{1/2}(x^{k}^{T} y^{k})^{(1+δ)/2}} [∥Y^{k}u^{0}∥ + ∥X^{k}v^{0}∥]

≤ (x^{k}^{T} y^{k})^{1/2} + \frac{2}{η^{1/2}ϵ^{(1+δ)/2}} max (∥ν^{k}y^{k}∥_{∞}, ∥ν^{k}x^{k}∥_{∞}) (∥u^{0}∥ + ∥v^{0}∥)

(2.24)  ≤ (x^{0}^{T} y^{0})^{1/2} + \frac{2C_{0} (x^{0}^{T} y^{0} + 1)}{η^{1/2}ϵ^{(1+δ)/2}} (∥u^{0}∥ + ∥v^{0}∥) =^{△} Ĉ_{0}.

Using (2.22) and (2.24), we obtain for all k ≥ 0 that

max\{ϕ_{k}^{+}, χ_{k}\} ≤ max_{i=1,2,...,n} \{\frac{|Δx_{i}^{k}Δy_{i}^{k}|}{x_{i}^{k}y_{i}^{k}}\}

≤ \frac{∥diag(Δx^{k})Δy^{k}∥}{min_{i=1,2,...,n}\{x_{i}^{k}y_{i}^{k}\}}

≤ \frac{∥(D^{k})^{−1}Δx^{k}∥∥D^{k}Δy^{k}∥}{ηϵ^{1+δ}}

≤ \frac{Ĉ_{0}^{2}}{ηϵ^{1+δ}} ,

where the first inequality follows by using a similar argument as in the proof of Lemma 2.1. Hence, from (1.6) we have inf_{k} α_{k} > 0, which implies x^{k}^{T} y^{k} → 0 from Corollary 2.4(a). We have thus obtained a contradiction, and statement (a) follows.

We note that Theorem 2.8 does not imply that the sequence {(x^{k}, y^{k})} is convergent or bounded. In Section 3, we will show that {(x^{k}, y^{k})} is convergent under the assumptions that there is a solution of (1.1) satisfying strict complementarity and that δ < 1/7.

Our next aim is to derive an upper bound on the number of iterations required by Algorithm IAS to reduce the duality gap below a given tolerance ϵ > 0. We will see that for certain values of δ, Algorithm IAS has a polynomial bound on this number of iterations. We restrict our analysis to certain choices of the initial point (x^{0}, y^{0}).

Given some conditions on the initial point (x^{0}, y^{0}), the next result gives bounds on the left-hand side of (2.15) in terms of the initial gap x^{0}^{T} y^{0}, the current gap x^{T} y, and the measure of initial centrality π_{0}.

Lemma 2.9. Suppose that the initial point (x^{0}, y^{0}) > 0 is chosen so that (x^{0}, y^{0}) ≥ (x^{∗}, y^{∗}) for some (x^{∗}, y^{∗}) ∈ S and that π_{0}, η, and ρ are defined by (2.10). Let (x, y) be any vector pair in N (δ, η, ρ) with x^{T} y ≤ x^{0}^{T} y^{0} and y − Mx − q = ν(y^{0} − Mx^{0} − q) for some ν ∈ (0, 1]. Let (Δx, Δy) be the direction determined by (1.5). Then, we have

max (∥D^{−1}Δx∥, ∥DΔy∥) ≤ 9 (\frac{n}{π_{0}} )^{1/2} (\frac{x^{0}^{T} y^{0}}{x^{T} y} )^{3δ/2} (x^{T} y)^{1/2}. (2.25)

Proof. We start by defining a vector pair (u^{0}, v^{0}) by

(u^{0}, v^{0}) = (x^{0}, y^{0}) − (x^{∗}, y^{∗}) ≥ 0, (2.26)

for (x^{∗}, y^{∗}) ∈ S. It is easy to check that

ν(v^{0} − Mu^{0}) = ν(y^{0} − Mx^{0} − q) = y − Mx − q.

Therefore Lemma 2.7 applies, and as a consequence the inequality (2.15) holds. Now, using (2.26), we obtain

∥Y u^{0}∥ + ∥Xv^{0}∥ ≤ y^{T} u^{0} + x^{T} v^{0} = y^{T} (x^{0} − x^{∗}) + x^{T} (y^{0} − y^{∗}) ≤ y^{T} x^{0} + x^{T} y^{0}. (2.27)

By substituting this last relation into (2.15), we obtain

max (∥D^{−1}Δx∥, ∥DΔy∥) ≤ (x^{T} y)^{1/2} + 2νη^{−1/2}(x^{T} y)^{−(1+δ)/2}[y^{T} x^{0} + x^{T} y^{0}]. (2.28)

We now invoke the inequality (2.11) with (x̄, ȳ) = (x^{∗}, y^{∗}), noting that ν ∈ (0, 1], (x^{∗}, y^{∗}) ≥ 0, x^{∗}^{T} y^{∗} = 0, and (x, y) > 0, to deduce that

ν(x^{0}^{T} y + x^{T} y^{0}) ≤ ν^{2}x^{0}^{T} y^{0} + x^{T} y + ν(x^{0}^{T} y^{∗} + x^{∗}^{T} y^{0}). (2.29)

Now, by (2.26), we have

\frac{x^{0}^{T} y^{∗} + x^{∗}^{T} y^{0}}{x^{0}^{T} y^{0}} = \frac{x^{0}^{T} (y^{0} − v^{0}) + (x^{0} − u^{0})^{T} y^{0}}{x^{0}^{T} y^{0}} = 2 − \frac{x^{0}^{T} v^{0} + u^{0}^{T} y^{0}}{x^{0}^{T} y^{0}} ≤ 2. (2.30)

In addition, by (2.10) and the definition of N (δ, η, ρ), we have

ν = \frac{∥r∥}{∥r^{0}∥} ≤ \frac{[ρx^{T} y]^{1/(1+δ)}}{∥r^{0}∥} = (\frac{x^{T} y}{x^{0}^{T} y^{0}} )^{1/(1+δ)} . (2.31)

Combining (2.29), (2.30), and (2.31), we get

ν(x^{0}^{T} y + x^{T} y^{0}) ≤ x^{0}^{T} y^{0} [ν^{2} + (\frac{x^{T} y}{x^{0}^{T} y^{0}} ) + 2ν]

≤ x^{0}^{T} y^{0} (\frac{x^{T} y}{x^{0}^{T} y^{0}} )^{1/(1+δ)} [ν + (\frac{x^{T} y}{x^{0}^{T} y^{0}} )^{δ/(1+δ)} + 2]

(2.32)  ≤ 4x^{0}^{T} y^{0} (\frac{x^{T} y}{x^{0}^{T} y^{0}} )^{1/(1+δ)} .

If we substitute (2.32) into (2.28) and replace η by its definition (2.10), we obtain

max (∥D^{−1}Δx∥, ∥DΔy∥) ≤ (x^{T} y)^{1/2} + 8η^{−1/2}(x^{T} y)^{−(1+δ)/2}(x^{0}^{T} y^{0})^{δ/(1+δ)}(x^{T} y)^{1/(1+δ)}

= (x^{T} y)^{1/2} [1 + 8 (\frac{n}{π_{0}} )^{1/2} (\frac{x^{0}^{T} y^{0}}{x^{T} y} )^{(δ/2)(3+δ)/(1+δ)}]

≤ 9 (\frac{n}{π_{0}} )^{1/2} (\frac{x^{0}^{T} y^{0}}{x^{T} y} )^{3δ/2} (x^{T} y)^{1/2},

where the last inequality follows from

\frac{x^{0}^{T} y^{0}}{x^{T} y} ≥ 1,  \frac{3 + δ}{1 + δ} < 3,  π_{0} ≤ 1.

We next derive uniform bounds for the quantities |ϕ_{k}| and χ_{k} defined by (1.3).

Lemma 2.10. Suppose that the initial point (x^{0}, y^{0}) > 0 satisfies (x^{0}, y^{0}) ≥ (x^{∗}, y^{∗}) for some (x^{∗}, y^{∗}) ∈ S and that η and ρ are defined by (2.10). Then for all iterates (x^{k}, y^{k}) generated by Algorithm IAS, we have

(2.33a)  |ϕ_{k}| ≤ 81 (\frac{n}{π_{0}} ) (\frac{x^{0}^{T} y^{0}}{x^{k}^{T} y^{k}} )^{3δ} ,

(2.33b)  0 ≤ χ_{k} ≤ 81 (\frac{n}{π_{0}} )^{2} (\frac{x^{0}^{T} y^{0}}{x^{k}^{T} y^{k}} )^{4δ} .

Proof. By Corollary 2.4, it follows that (x^{k}, y^{k}) satisfies the assumptions of Lemma 2.9 for all k ≥ 0. Hence, it follows from (2.25) that

|ϕ_{k}| = \frac{|Δx^{k}^{T} Δy^{k}|}{x^{k}^{T} y^{k}} ≤ \frac{∥D^{k}Δx^{k}∥∥(D^{k})^{−1}Δy^{k}∥}{x^{k}^{T} y^{k}} ≤ 81 (\frac{n}{π_{0}} ) (\frac{x^{0}^{T} y^{0}}{x^{k}^{T} y^{k}} )^{3δ} .

Similarly, by (2.10), (2.25), and the definition of N (δ, η, ρ), we have

χ_{k} ≤ max_{i=1,2,...,n} \frac{|Δx_{i}^{k}Δy_{i}^{k}|}{x_{i}^{k}y_{i}^{k}} ≤ \frac{∥D^{k}Δx^{k}∥∥(D^{k})^{−1}Δy^{k}∥}{η(x^{k}^{T} y^{k})^{1+δ}}

≤ 81 (\frac{n}{π_{0}} ) (\frac{x^{0}^{T} y^{0}}{x^{k}^{T} y^{k}} )^{3δ} (x^{k}^{T} y^{k})^{−δ}η^{−1}

= 81 (\frac{n}{π_{0}} )^{2} (\frac{x^{0}^{T} y^{0}}{x^{k}^{T} y^{k}} )^{4δ} ,

as required.

We can now state a global convergence result.

Theorem 2.11. Suppose that the initial point (x^{0}, y^{0}) > 0 satisfies (x^{0}, y^{0}) ≥ (x^{∗}, y^{∗}) for some (x^{∗}, y^{∗}) ∈ S. Let δ ∈ (0, 1] be given, and let η and ρ be defined by (2.10). Then, given ϵ ∈ (0, x^{0}^{T} y^{0}), Algorithm IAS will generate an iterate (x^{k}, y^{k}) with x^{k}^{T} y^{k} ≤ ϵ in at most

O (\frac{1}{δ} (\frac{n}{π_{0}} )^{2} (\frac{x^{0}^{T} y^{0}}{ϵ} )^{4δ} log(x^{0}^{T} y^{0}/ϵ)) (2.34)

iterations, and the sequence {x^{k}^{T} y^{k}} will be strictly monotonically decreasing.

Proof. To simplify notation, let τ = (x^{0}^{T} y^{0}/ϵ). If the iterate (x^{k}, y^{k}) satisfies x^{k}^{T} y^{k} ≥ ϵ then, in view of (2.33), we have

|ϕ_{k}| ≤ 81(n/π_{0})τ^{3δ}, χ_{k} ≤ 81(n/π_{0})^{2}τ^{4δ},

and hence

α_{k} = \frac{δ}{δ + χ_{k} + (1 + δ)ϕ_{k}^{+}}
≥ \frac{δ}{δ + 81(n/π_{0})^{2}τ^{4δ} + (1 + δ)81(n/π_{0})τ^{3δ}}
≥ \frac{δ}{δ + 243(n/π_{0})^{2}τ^{4δ}}
≥ \frac{δ}{244} (\frac{π_{0}}{n} )^{2} τ^{−4δ}
(2.35)  =^{△} ᾱ.

Strictly monotonic decrease of the sequence {x^{k}^{T} y^{k}} now follows from Corollary 2.4(a) and the fact that the inclusion (x^{k}, y^{k}) ∈ N (δ, η, ρ) implies that x^{k}^{T} y^{k} > 0. Now let K be the smallest nonnegative integer for which x^{K+1}^{T} y^{K+1} ≤ ϵ. Since (2.35) holds for every 0 ≤ k ≤ K, we obtain from Lemma 2.3(a) that

x^{K}^{T} y^{K} ≤ [1 − ᾱ/(1 + δ)]^{K}x^{0}^{T} y^{0}. (2.36)

Assume for contradiction that

K ≥ \frac{(1 + δ) log τ}{ᾱ} .

Using the inequality log(1 − β) ≤ −β for β < 1 and the previous relation, we can easily show that

[1 − ᾱ/(1 + δ)]^{K} ≤ τ^{−1},

which, in view of the definition of τ and relation (2.36), implies

x^{K}^{T} y^{K} ≤ τ^{−1}x^{0}^{T} y^{0} = ϵ.

This relation contradicts our definition of K. Therefore, using (2.35) and the definition of τ, we have

K < \frac{(1 + δ) log τ}{ᾱ} = O (\frac{1}{δ} (\frac{n}{π_{0}} )^{2} (\frac{x^{0}^{T} y^{0}}{ϵ} )^{4δ} log(x^{0}^{T} y^{0}/ϵ)) .

Note in particular that if

ϵ = e^{−O(L)},  x^{0}^{T} y^{0} = e^{O(L)},  π_{0} = O(1),  δ = 1/O(L),

then the bound in (2.34) is O(n^{2}L^{2}), that is, there is a polynomial bound on the number of iterations of Algorithm IAS.

3. Local Convergence. Under the conditions that problem (1.1) is nondegenerate and δ ∈ (0, 1/7), we prove in this section that Algorithm IAS started from any initial point (x^{0}, y^{0}) > 0 generates a sequence of iterates {(x^{k}, y^{k})} such that {x^{k}^{T} y^{k}} converges superlinearly to zero. Moreover, under the same conditions, we also show that the sequence {(x^{k}, y^{k})} converges to a solution of (1.1). We emphasize that the convergence of {(x^{k}, y^{k})} is obtained without assuming the existence of a strictly feasible point for (1.1). (This assumption was used by the local convergence analysis in Wright [7], for example.)

The following assumption is imposed throughout this section.

Assumption 1. (Nondegeneracy) S_{c} ≠ ∅. We show in [5] that Assumption 1 is in fact necessary for superlinear convergence of Newtonbased primal-dual algorithms.

An important feature of this section is that we are able to prove boundedness of the steps (Δx^{k}, Δy^{k}) in terms of x^{k}^{T} y^{k} without an intermediate result that the sequence (x^{k}, y^{k}) is bounded. The key result — that ∥Δx_{B}^{k}∥ and ∥Δy_{N}^{k}∥ are both O(x^{k}^{T} y^{k}) — is obtained by combining Lemmas 3.3 and 3.4 below. In [7], the same result was obtained by combining Lemma 3.4 with a more elementary result in which boundedness of (x^{k}, y^{k}) was an essential ingredient. In fact, we can use the techniques of this section to drop the strict feasibility assumption from the analysis of [7] without affecting the conclusions of the paper (see Wright [9]).

After finding the bounds on the steps (Δx^{k}, Δy^{k}) in terms of the complementarity gap x^{k}^{T} y^{k}, we bound the scalars |ϕ_{k}| and χ_{k}. Subsequently, we show that α_{k} → 1, from which Q-superlinear convergence follows. We also find a lower bound on the Q-order of convergence in terms of δ.

The following result yields bounds on the nonbasic components of x and y.

Lemma 3.1. Suppose that Assumption 1 holds. Assume that a point (x^{0}, y^{0}) > 0 and that scalars δ ≥ 0, η > 0, and ρ ≥ 0 are given. Then, there exists a constant C_{1} ≥ 0 with the following property: For every vector (x, y) ∈ N (δ, η, ρ) such that

(3.1)  x^{T} y ≤ x^{0}^{T} y^{0},
(3.2)  y − Mx − q = ν(y^{0} − Mx^{0} − q), for some ν ∈ [0, 1/2],

we have

(3.3a)  x_{i} ≤ C_{1}(x^{T} y)^{1/(1+δ)},  ∀i ∈ N,
(3.3b)  y_{i} ≤ C_{1}(x^{T} y)^{1/(1+δ)},  ∀i ∈ B.

Proof. Consider first the infeasible case in which r^{0} = y^{0} − Mx^{0} − q ≠ 0. Setting (x̄, ȳ) = (x^{∗}, y^{∗}) for some (x^{∗}, y^{∗}) ∈ S_{c} in inequality (2.11) and using the fact that ν ∈ [0, 1/2], (x, y) > 0, (x^{∗}, y^{∗}) ≥ 0 and x^{∗}^{T} y^{∗} = 0, we obtain

(3.4)  x^{∗}^{T} y + x^{T} y^{∗} ≤ \frac{ν}{1 − ν} x^{0}^{T} y^{0} + \frac{1}{1 − ν} x^{T} y + ν(x^{0}^{T} y^{∗} + x^{∗}^{T} y^{0}).

Using (3.2) and the fact that (x, y) ∈ N (δ, η, ρ), we get

ν = \frac{∥r∥}{∥r^{0}∥} ≤ \frac{(ρx^{T} y)^{1/(1+δ)}}{∥r^{0}∥} , (3.5)

where, as usual, r = y − Mx − q. From (3.1), (3.5), (3.4), and the fact that 1 − ν ≥ 1/2, we get

x^{∗}^{T} y + x^{T} y^{∗}

≤ \frac{2x^{0}^{T} y^{0}}{∥r^{0}∥} ρ^{1/(1+δ)}(x^{T} y)^{1/(1+δ)} + 2x^{T} y + \frac{1}{∥r^{0}∥}ρ^{1/(1+δ)}(x^{0}^{T} y^{∗} + x^{∗}^{T} y^{0})(x^{T} y)^{1/(1+δ)}

≤ (x^{T} y)^{1/(1+δ)} [\frac{2x^{0}^{T} y^{0}}{∥r^{0}∥} ρ^{1/(1+δ)} + 2(x^{0}^{T} y^{0})^{δ/(1+δ)} + \frac{1}{∥r^{0}∥}ρ^{1/(1+δ)}(x^{0}^{T} y^{∗} + x^{∗}^{T} y^{0})]

= C̄_{1}(x^{T} y)^{1/(1+δ)},

where C̄_{1} is defined in an obvious way. This last relation immediately implies (3.3) when we define

C_{1} =^{△} C̄_{1} max \{max_{i∈N} \frac{1}{y_{i}^{∗}} , max_{i∈B} \frac{1}{x_{i}^{∗}} \} .

For the feasible case r^{0} = 0, note from the condition y − Mx − q = ν(y^{0} − Mx^{0} − q) that r = y − Mx − q = 0 for all (x, y) satisfying the assumptions of the theorem. Hence we can take ν = 0 in (3.4) and obtain

x^{∗}^{T} y + x^{T} y^{∗} ≤ x^{T} y.

A simple argument produces the required bound with C_{1} defined by

C_{1} = (x^{0}^{T} y^{0})^{δ/(1+δ)} max \{max_{i∈N} \frac{1}{y_{i}^{∗}} , max_{i∈B} \frac{1}{x_{i}^{∗}} \} .

We now use this lemma to find bounds on the nonbasic components of (Δx, Δy).

Lemma 3.2. Suppose that Assumption 1 holds and that (x^{0}, y^{0}) > 0 is given. Assume that scalars δ ∈ [0, 1/3], η > 0, and ρ ≥ 0 are given. Then, there exists a constant C_{2} ≥ 0 with the following property: For any vector pair (x, y) ∈ N (δ, η, ρ) such that

(3.6)  x^{T} y ≤ min(1, x^{0}^{T} y^{0}),
(3.7)  y − Mx − q = ν(y^{0} − Mx^{0} − q), for some ν ∈ [0, 1/2],

we have

(3.8a)  |Δx_{i}| ≤ C_{2}(x^{T} y)^{1−3δ},  ∀i ∈ N,
(3.8b)  |Δy_{i}| ≤ C_{2}(x^{T} y)^{1−3δ},  ∀i ∈ B.

Proof. We first show that there exists a constant C̄_{2} such that

max {∥D^{−1}Δx∥, ∥DΔy∥} ≤ C̄_{2}(x^{T} y)^{(1−3δ)/2}. (3.9)

We give the proof only for the case in which r^{0} ≡ y^{0} − Mx^{0} − q ≠ 0, since the proof for r^{0} = 0 is trivial. The assumptions of the lemma imply that (2.12) and (3.5) hold. These two relations together with (3.6) then imply

max {ν∥x∥_{∞}, ν∥y∥_{∞}} ≤ C_{0} [x^{T} y + ν]
≤ C_{0} [1 + \frac{ρ^{1/(1+δ)}}{∥r^{0}∥} ] (x^{T} y)^{1/(1+δ)}
= Ĉ_{2}(x^{T} y)^{1/(1+δ)}
(3.10)  ≤ Ĉ_{2}(x^{T} y)^{1−δ},

where Ĉ_{2} is defined in an obvious way. Since the assumptions of Lemma 2.7 are satisfied, inequality (2.15) together with (3.10) and (3.6) then yield

max (∥D^{−1}Δx∥, ∥DΔy∥)
≤ (x^{T} y)^{1/2} + \frac{2ν}{η^{1/2}(x^{T} y)^{(1+δ)/2}} [∥Y u^{0}∥ + ∥Xv^{0}∥]

≤ (x^{T} y)^{1/2} + \frac{2}{η^{1/2}(x^{T} y)^{(1+δ)/2}} (∥u^{0}∥ + ∥v^{0}∥) max (∥νy∥_{∞}, ∥νx∥_{∞})

≤ (x^{T} y)^{1/2} + \frac{2Ĉ_{2}}{η^{1/2}(x^{T} y)^{(1+δ)/2}} (∥u^{0}∥ + ∥v^{0}∥) (x^{T} y)^{1−δ}

≤ [1 + \frac{2Ĉ_{2}}{η^{1/2}} (∥u^{0}∥ + ∥v^{0}∥)] (x^{T} y)^{(1−3δ)/2}

= C̄_{2}(x^{T} y)^{(1−3δ)/2},

where C̄_{2} is defined in an obvious way. We have thus shown that (3.9) holds.

Considering i ∈ N, we have from the definition D = X^{1/2}Y^{−1/2}, the formulae (3.9) and (3.3a), and the inclusion (x, y) ∈ N (δ, η, ρ) that

|Δx_{i}| ≤ (\frac{x_{i}}{y_{i}} )^{1/2} C̄_{2}(x^{T} y)^{(1−3δ)/2}

= \frac{x_{i}}{(x_{i}y_{i})^{1/2}} C̄_{2}(x^{T} y)^{(1−3δ)/2}

≤ C̄_{2} \frac{C_{1}(x^{T} y)^{1/(1+δ)}}{η^{1/2}(x^{T} y)^{(1+δ)/2}} (x^{T} y)^{(1−3δ)/2}
(3.11)  = (C̄_{2}C_{1}η^{−1/2})(x^{T} y)^{(1−2δ−2δ^{2})/(1+δ)}.

Since δ ∈ [0, 1/3], we have

\frac{1 − 2δ − 2δ^{2}}{1 + δ} ≥ (1 − 2δ − 2δ^{2})(1 − δ) = 1 − 3δ + 2δ^{3} ≥ 1 − 3δ ≥ 0,

and since x^{T} y ≤ 1, we conclude from (3.11) that

|Δx_{i}| ≤ (C̄_{2}C_{1}η^{−1/2})(x^{T} y)^{1−3δ} = C_{2}(x^{T} y)^{1−3δ},

for C_{2} defined in an obvious way. Hence, we have proved (3.8a). The proof of (3.8b) is identical.

To find bounds on the remaining components of (Δx, Δy), we cite the following two results, which have been proved in earlier reports.

Lemma 3.3. ([4, Lemma 2.2]) Let f ∈ IR^{q} and H ∈ IR^{p×q} be given. Then there exists a constant L = L(f, H) with the property that for any positive definite diagonal matrix D and any vector h ∈ Range(H), the (unique) optimal solution w̄ = w̄(D, h) of

(3.12)  min_{w} f^{T} w + \frac{1}{2} ∥Dw∥^{2} ,  subject to Hw = h,

satisfies

\left∥{ \atop w̄}\right∥_{∞} ≤ L \{|f^{T} w̄| + ∥h∥_{∞}\} .

Lemma 3.4. ([7, Lemma 5.2]) Let (x, y) > 0 be given, and consider the direction (Δx, Δy) determined by (1.5). Then (Δx_{B}, Δy_{N}) solves the convex quadratic programming problem

min_{(w,z)} \frac{1}{2}∥D_{B}w∥^{2} + \frac{1}{2}∥D_{N}^{−1}z∥^{2}

subject to

M_{BB}w = r_{B} − M_{BN}Δx_{N} + Δy_{B}
M_{NB}w − z = r_{N} − M_{NN}Δx_{N}.

Lemma 3.4 is an extension to the infeasible case of a result due to Ye and Anstreicher [10, Lemma 3.5].

As a consequence of Lemmas 3.3 and 3.4, we can find bounds on Δx_{B} and Δy_{N}.

Lemma 3.5. Suppose the assumptions of Lemma 3.2 hold. Then there exists a constant C_{3} ≥ 0 such that

(3.13a)  |Δx_{i}| ≤ C_{3}(x^{T} y)^{1−3δ},  ∀i ∈ B,
(3.13b)  |Δy_{i}| ≤ C_{3}(x^{T} y)^{1−3δ},  ∀i ∈ N.

Proof. From Lemmas 3.2, 3.3, and 3.4, we have

∥(Δx_{B}, Δy_{N})∥_{∞} ≤ L [∥r∥_{∞} + ∥M∥_{∞}∥Δx_{N}∥_{∞} + ∥Δy_{B}∥_{∞}]
≤ L [(ρx^{T} y)^{1/(1+δ)} + (∥M∥_{∞} + 1)C_{2}(x^{T} y)^{1−3δ}] .

Since 1/(1 + δ) ≥ 1 − 3δ when δ ∈ [0, 1/3], we obtain the desired result by setting

C_{3} = L [ρ^{1/(1+δ)} + (∥M∥_{∞} + 1)C_{2}] .

As a immediate consequence of Lemmas 3.2 and 3.5, we obtain the following result. Theorem 3.6. Suppose that Assumption 1 holds and that δ ∈ [0, 1/3] is given. Then,

there exists a constant C_{4} ≥ 0 such that for all k sufficiently large, we have

(3.14a)  |Δx_{i}^{k}| ≤ C_{4}(x^{k}^{T} y^{k})^{1−3δ},  ∀i = 1, 2, …, n,
(3.14b)  |Δy_{i}^{k}| ≤ C_{4}(x^{k}^{T} y^{k})^{1−3δ},  ∀i = 1, 2, …, n.

Proof. Since the assumptions of Theorem 2.8 are satisfied, we know that x^{k}^{T} y^{k} ↓ 0 and ∥r^{k}∥ → 0. Hence, in view of Corollary 2.4(b), we have that ν_{k} → 0. Thus, there exists an index K ≥ 0 such that ν_{k} ≤ 1/2 and x^{k}^{T} y^{k} ≤ 1 for all k ≥ K. The above observations together with Corollary 2.4 imply that the assumptions of Lemmas 3.2 and 3.5 are satisfied by all points (x^{k}, y^{k}) with k ≥ K. Thus, we obtain (3.14) by choosing C_{4} = max(C_{2}, C_{3}).

Corollary 3.7. Suppose the assumptions of Theorem 3.6 are satisfied. Then there is a constant C_{5} ≥ 0 such that for all k sufficiently large, we have

|ϕ_{k}| ≤ C_{5}(x^{k}^{T} y^{k})^{1−6δ}, 0 ≤ χ_{k} ≤ C_{5}(x^{k}^{T} y^{k})^{1−7δ}. (3.15)

Proof. For sufficiently large k, we have from (3.14) that

|ϕ_{k}| = \frac{|Δx^{k}^{T} Δy^{k}|}{x^{k}^{T} y^{k}} ≤ nC_{4}^{2}(x^{k}^{T} y^{k})^{1−6δ},

as required. Since (x^{k}, y^{k}) ∈ N (δ, η, ρ), we also have that

χ_{k} ≤ max_{i=1,2,...,n} \frac{|Δx_{i}^{k}Δy_{i}^{k}|}{x_{i}^{k}y_{i}^{k}} ≤ \frac{C_{4}^{2}(x^{k}^{T} y^{k})^{2−6δ}}{η(x^{k}^{T} y^{k})^{1+δ}} = (C_{4}^{2}/η)(x^{k}^{T} y^{k})^{1−7δ}.

The result follows if we set C_{5} = max(nC_{4}^{2}, C_{4}^{2}/η).

We are now ready to prove the main local convergence result.

Theorem 3.8. Suppose that Assumption 1 holds and that δ ∈ (0, 1/7) is given. Then the sequence {x^{k}^{T} y^{k}} converges Q-superlinearly to zero with Q-order at least 2 − 7δ.

Proof. Suppose the index K is chosen sufficiently large that the relation x^{k}^{T} y^{k} ≤ 1 and the bounds in (3.15) hold for all k ≥ K. Then we have

1 − α_{k} = \frac{χ_{k} + (1 + δ)ϕ_{k}^{+}}{δ + χ_{k} + (1 + δ)ϕ_{k}^{+}}

≤ \frac{χ_{k} + (1 + δ)ϕ_{k}^{+}}{δ}
≤ \frac{C_{5} [1 + (1 + δ)(x^{k}^{T} y^{k})^{δ}] (x^{k}^{T} y^{k})^{1−7δ}}{δ}
≤ \frac{3C_{5}}{δ} (x^{k}^{T} y^{k})^{1−7δ}.

Hence, from Lemma 2.2(a), we have for all k ≥ K that

x^{k+1}^{T} y^{k+1} ≤ x^{k}^{T} y^{k}(1 − α_{k} + α_{k}^{2}ϕ_{k})
≤ x^{k}^{T} y^{k}(1 − α_{k} + |ϕ_{k}|)
≤ x^{k}^{T} y^{k} (\frac{3C_{5}}{δ} (x^{k}^{T} y^{k})^{1−7δ} + C_{5}(x^{k}^{T} y^{k})^{1−6δ})
≤ \frac{4C_{5}}{δ} (x^{k}^{T} y^{k})^{2−7δ},

as required.

Convergence (and therefore boundedness) of the sequence {(x^{k}, y^{k})} follows as a corollary of Theorem 3.8.

Corollary 3.9. Suppose the assumptions of Theorem 3.8 hold. Then the sequence {(x^{k}, y^{k})} is convergent.

Proof. It suffices to show that the sequence is Cauchy. From Theorem 3.8, there exists an index K̄ such that x^{k+1}^{T} y^{k+1} ≤ (1/2)^{1/(1−3δ)}x^{k}^{T} y^{k} for all k ≥ K̄. Hence, from (3.14) we have for k_{1}, k_{2} with K̄ ≤ k_{1} < k_{2} that

∥(x^{k_{2}}, y^{k_{2}}) − (x^{k_{1}}, y^{k_{1}})∥_{∞} ≤ ∑_{k=k_{1}}^{k_{2}−1} ∥(Δx^{k}, Δy^{k})∥_{∞}

≤ C_{4} ∑_{k=k_{1}}^{k_{2}−1} (x^{k}^{T} y^{k})^{1−3δ}

≤ C_{4} (x^{k_{1}}^{T} y^{k_{1}})^{1−3δ} ∑_{k=k_{1}}^{k_{2}−1} \frac{1}{2^{k−k_{1}}}

≤ 2C_{4} (x^{k_{1}}^{T} y^{k_{1}})^{1−3δ} .

Since x^{k}^{T} y^{k} ↓ 0, the above relation shows that, given any ϵ > 0, we can choose K̂ ≥ K̄ such that

∥(x^{k_{2}}, y^{k_{2}}) − (x^{k_{1}}, y^{k_{1}})∥_{∞} ≤ ϵ ∀k_{2} > k_{1} ≥ K̂,

and so the sequence {(x^{k}, y^{k})} is Cauchy.

REFERENCES

[1] M. Kojima, N. Megiddo, and S. Mizuno, A primal-dual infeasible-interior-point point algorithm for linear programming, Mathematical Programming, Series A, 61 (1993), pp. 261–280.

[2] S. Mizuno, Polynomiality of Kojima-Meggido-Mizuno infeasible-interior-point algorithm for linear programming, Tech. Rep. 1006, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, N.Y., January 1993.

[3] S. Mizuno, M. Kojima, and M. Todd, Infeasible interior-point primal-dual potential-reduction algorithms for linear programming, Tech. Rep. 1023, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York, August 1992. To appear in SIAM Journal on Optimization.

[4] R. D. C. Monteiro and S. J. Wright, Superlinear primal-dual affine scaling algorithms for LCP, Preprint MCS–P360–0693, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill., June 1993. To appear in Mathematical Programming, Series A.

[5] , Local convergence of interior-point algorithms for degenerate monotone LCP, Computational Optimization and Applications, 3 (1994), pp. 131–155.

[6] F. A. Potra, A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points, Reports on Computational Mathematics 28 & 34, University of Iowa, Iowa City, December 1993. To appear in Mathematical Programming.

[7] S. J. Wright, An infeasible-interior-point algorithm for linear complementarity problems, Preprint MCS–P331–1092, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill., October 1992. To appear in Mathematical Programming, Series A.

[8] , A path-following infeasible-interior-point algorithm for linear complementarity problems, Optimization Methods and Software, 2 (1993), pp. 79–106.

[9] , A path-following interior-point algorithm for linear and quadratic optimization problems, Preprint MCS–P401–1293, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill., December 1993.

[10] Y. Ye and K. Anstreicher, On quadratic and O(\sqrt{n}L) convergence of a predictor-corrector algorithm for LCP, Mathematical Programming, Series A, 62 (1993), pp. 537–551.

[11] Y. Zhang, On the convergence of a class of infeasible-interior-point methods for the horizontal linear complementarity problem, SIAM Journal on Optimization, 4 (1994), pp. 208–227.

[12] Y. Zhang and D. Zhang, Superlinear convergence of infeasible interior-point methods for linear programming, Research Report 92–15, Department of Mathematics and Statistics, University of Maryland Baltimore County, September 1992. To appear in Mathematical Programming, Series A.