Global Convergence of the Affine Scaling Algorithm for Convex Quadratic Programming

Renato D.C. Monteiro^{∗}  T. Tsuchiya^{†}

March 24, 1995

Abstract

In this paper we give a global convergence proof of the second order affine scaling algorithm for convex quadratic programming problems, where the next iterate is the point which minimizes the objective function over the intersection of the feasible region with the ellipsoid centered at the current point and whose radius is a fixed fraction β ∈ (0, 1] of the radius of the largest “scaled” ellipsoid inscribed in the nonnegative orthant. The analysis is based on the local Karmarkar potential function introduced by Tsuchiya. For any β ∈ (0, 2/3] and without assuming any nondegeneracy assumption on the problem, it is shown that the sequences of primal iterates and dual estimates converge to optimal solutions of the quadratic program and its dual, respectively.

1 Introduction

The affine scaling (AS) algorithm for linear programming (LP) was introduced by Dikin [6] in 1967 but remained unknown to the west community until the late 80’s. It was later rediscovered by Barnes [2] and Vanderbei et al. [26] as a natural simplification of Karmarkar’s algorithm [12]. Because of the theoretical and practical importance of the AS algorithm, there are a number of papers which study its global and local convergence [2, 6, 7, 8, 10, 18, 20, 21, 23, 24, 26, 25] and the behavior of its associated continuous trajectories [1, 3, 13, 14, 27]. Like in the simplex algorithm, the analysis of the affine scaling algorithm for primal degenerate LP problems is much harder than for primal nondegenerate LP problems. By introducing a local Karmarkar potential function, Tsuchiya [20, 21] shows the global convergence of the short-step version of the AS algorithm where the next iterate minimizes the (linear) objective function over the intersection of the feasible region with the ellipsoid centered at the current point and whose radius is a fixed fraction β, β ≤ 1/8, of the radius of the largest “scaled” ellipsoid inscribed in the nonnegative orthant. The global convergence of the long step version of the affine scaling algorithm for degenerate LP problems, that is the version where the next iterate is determined by taking a fixed fraction λ ∈ (0, 1) of the whole step to the boundary of the feasible region, was established by Dikin [8] for any λ ∈ (0, 1/2] and by Tsuchiya and Muramatsu [24] for any λ ∈ (0, 2/3]. We refer the reader to Monteiro et al.

∗School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, 30332. The work of this author was based on research supported by the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.

†The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, Tokyo, 106, Japan.

[15] and Saigal [16] for a simplified and self-contained analysis of the AS algorithm in the context of LP problems.

In this paper, we focus our attention on the second order affine scaling algorithm for convex quadratic programming (QP), and prove its global convergence without any nondegeneracy assumption by using a local potential function similar to the one used in the LP context. This version of the AS algorithm was originally proposed by Dikin (see the references in his book [9]), and was later rediscovered by Ye [28] and Ye and Tse [30] after the introduction of Karmarkar’s algorithm [12]. The algorithm analyzed in this paper is similar to the short-step version of the AS algorithm for LP problems in that the next iterate is the point which minimizes the (quadratic) objective function over the intersection of the feasible region with the ellipsoid centered at the current point and whose radius is a fixed fraction β of the radius of the largest “scaled” ellipsoid inscribed in the nonnegative orthant. The papers [28, 30] assume that the QP problem is primal nondegenerate and also impose an extra dual nondegeneracy assumption involving the objective function. These assumptions considerably simplify the convergence analysis of the AS algorithm.

Global convergence of the second order AS algorithm which drops the assumption of primal nondegeneracy but still keeps some sort of dual nondegeneracy is given in Tsuchiya [22] for strictly convex QP problems and any β ∈ (0, 1/8]. Sun [17] proves global convergence for this algorithm without imposing any nondegeneracy assumption. His analysis, which generalizes the one given in Tseng and Luo [18] for LP problems, is still restrictive in the sense that it allows only very small radius β, i.e. β = 2^{−O(L)}, where L is the input size of the problem. In an unpublished manuscript, reported in the presentation [19], Tsuchiya proves global convergence of the second order AS algorithm for strictly convex QP with β ∈ (0, 1/8]. Part of this paper is based on the ideas developed in that manuscript.

Convergence of the first order AS algorithm for linearly constrained convex programming problems is proved in Gonzaga and Carlos [11] under the assumption of primal nondegeneracy. In this algorithm, the search direction is obtained by minimizing a first order linear approximation of the objective function at the current point over the same ellipsoid mentioned above and the next point is determined by performing a line search along this direction.

Convergence analysis of the second order AS algorithm for non-convex QP problems under the assumption of primal and dual nondegeneracy can be found in the papers Ye [29] and Bonnans and Bouhtou [4].

This paper is organized as follows. In Section 2 we describe the second order AS algorithm for QP problems and review some basic results about this method. After introducing a local assumption which requires that a partition of the variables satisfy certain conditions, we prove in Section 3 that the sequence of primal iterates and the sequence of dual estimates generated by the second order AS algorithm with β ∈ (0, 2/3] converge to optimal solutions of the given QP problem and its dual, respectively. Two important tools play a crucial role in the convergence analysis: the local potential function and an asymptotic decomposition formula of the scaled projection matrix near the boundary of the feasible region. Finally, we show in Section 4 that the local assumption of Section 3 is satisfied by some (in fact, unique) partition of variables. Appendix A presents a general framework for analyzing the asymptotic reduction of the local potential function. The asymptotic decomposition formula for the scaled projection matrix is presented in Tsuchiya [21] but its derivation is quite involved. For this reason we give a simplified proof of this formula in Appendix B.

The following notation is used throughout our paper. We denote the vector of all ones by e. Its dimension is always clear from the context. IR^{p}, IR_{+}^{p} and IR_{++}^{p} denote the p-dimensional Euclidean space, the nonnegative orthant of IR^{p} and the positive orthant of IR^{p}, respectively. The set of all p × q matrices with real entries is denoted by IR^{p×q}. Given a vector x ∈ IR^{p} and an index set α ⊆ {1, …, p}, we denote the subvector [x_{i}]_{i∈α} by x_{α}. Given x and y in IR^{p}, x ≤ y means x_{i} ≤ y_{i} for every i = 1, …, n. If α ⊆ {1, …, p}, β ⊆ {1, …, q} and Q ∈ IR^{p×q}, we let Q_{αβ} denote the submatrix [Q_{ij}]_{i∈α, j∈β}. If α = {1, …, p} we denote Q_{αβ} simply by Q_{β}. For a vector w, we let χ[w] denote the largest component of w. The Euclidean norm, the 1-norm and the ∞-norm are denoted by ∥ · ∥, ∥ · ∥_{1} and ∥ · ∥_{∞}, respectively. The diagonal matrix corresponding to a vector w is denoted by diag(w) and the vector whose i-th component is 1/w_{i} is denoted by w^{−1}. If J is a finite index set then |J| denotes its cardinality, that is the number of elements of J. We say that (B, N) is a partition of {1, …, p} if B ∪ N = {1, …, p} and B ∩ N = ∅. The superscript ^{T} denotes transpose.

2 Notation and preliminary results

In this section we describe the second order AS algorithm for QP problems and review some basic results about this method.

We consider the following convex quadratic program (QP)

minimize f(x) = \frac{1}{2}x^{T} Qx + c^{T} x
subject to Ax = b
x ≥ 0

(1)

and its associated dual QP

maximize b^{T} y − \frac{1}{2}x^{T} Qx
subject to A^{T} y + s = ∇f(x)
s ≥ 0,

(2)

where c, x, s ∈ IR^{n}, A ∈ IR^{m×n}, b ∈ IR^{m}, and Q ∈ R^{n×n} is a symmetric positive semidefinite matrix.

The following notation is used throughout the paper. The quantity (x^{T} Qx)^{1/2} is simply denoted by ∥x∥_{Q}. Clearly, ∥ · ∥_{Q} is a norm only when Q is positive definite; in general, it fails to be a norm due to the fact that ∥x∥_{Q} = 0 does not imply x = 0. If {τ_{k}} and {β_{k}} are two sequences of real numbers and K is an infinite index set of nonnegative integers then the notation τ_{k} = O(β_{k}) for k ∈ K means that there exists a scalar r ≥ 0 such that |τ_{k}| ≤ rβ_{k} for every k ∈ K sufficiently large; clearly, if β_{k} > 0 for all k ∈ K then |τ_{k}| ≤ rβ_{k} holds for all k ∈ K by taking a larger scalar r if necessary. When K is equal to the set of all nonnegative integers, we simply write τ_{k} = O(β_{k}). The notation τ_{k} ∼ β_{k} for k ∈ K means that τ_{k} = O(β_{k}) for k ∈ K and β_{k} = O(τ_{k}) for k ∈ K.

Given a partition (B, N) of {1, …, n}, we let

P_{N} ≡ {x ∈ IR^{n} | A_{B}x_{B} = b, x_{N} = 0};
P_{N}^{+} ≡ {x ∈ P_{N} | x_{B} ≥ 0};
P_{N}^{++} ≡ {x ∈ P_{N} | x_{B} > 0};
D_{B}(x) ≡ {(y, s) ∈ IR^{m} × IR^{n} | A^{T} y + s = ∇f(x), s_{B} = 0};  (3)
D_{B}^{+}(x) ≡ {(y, s) ∈ D_{B} | s_{N} ≥ 0};
D_{B}^{++}(x) ≡ {(y, s) ∈ D_{B} | s_{N} > 0}.

When N = ∅, we denote the sets P_{N}, P_{N}^{+} and P_{N}^{++} by P, P^{+} and P^{++}, respectively. The sets P^{+} and P^{++} are the sets of feasible solutions and strictly feasible solutions of problem (1). Similarly, when B = ∅, we denote the sets D_{B}(x), D_{B}^{+}(x) and D_{B}^{++}(x) by D(x), D^{+}(x) and D^{++}(x), respectively.

Throughout this paper, we make the following assumption.

Assumption 2.1 The following assumptions are made with respect to problem (1):

(A) rank (A) = m;

(B) P^{++} ≠ ∅;

(C) the set of optimal solutions of problem (1) is nonempty and bounded.

We next describe the second order affine scaling algorithm which is analyzed in this paper.

Algorithm AS: Let x^{0} ∈ P^{++} and β ∈ (0, 2/3] be given. Set k = 0.

step 1: compute the solution x^{k+1} of the problem

min{f(x) | Ax = b, ∥(X^{k})^{−1}(x − x^{k})∥^{2} ≤ β^{2}};  (4)

step 2: if ∥(X^{k})^{−1}(x^{k+1} − x^{k})∥ < β then stop; otherwise, increment k by 1 and go to step 1.

end of Algorithm AS.

Using the fact that ∥(X^{k})^{−1}(x^{k+1} − x^{k})∥ ≤ β, it follows that

(1 − β)x^{k} ≤ x^{k+1} ≤ (1 + β)x^{k},  ∀k ≥ 0.  (5)

As a consequence, it follows that all iterates generated by Algorithm AS lie in P^{++}.

Proposition 2.2 The following implications hold:

(a) if ∥(X^{k})^{−1}(x^{k+1} − x^{k})∥ < β for some k then x^{k+1} is an optimal solution of problem (1);

(b) if ∥(X^{k})^{−1}(x^{k+1} − x^{k})∥ = β for all k then every accumulation point of the sequence {x^{k}} lies on the relative boundary of P^{+}, that is, the set P^{+}\P^{++}.

When case (a) of Proposition 2.2 occurs, Algorithm AS finds an optimal solution of problem (1) in a finite number of iterations. Throughout the paper we assume that case (b) of Proposition 2.2 holds. One of our goals will be to show that the sequence of iterates {x^{k}} generated by Algorithm AS converges to an optimal solution of (1).

Throughout this paper, we let X^{k} ≡ diag(x^{k}) and g^{k} = ∇f(x^{k}) for every k. The following quantities associated with the sequence {x^{k}} generated by Algorithm AS play a fundamental role in the sequel:

y^{k} ≡ [A(X^{k})^{2}A^{T} ]^{−1} A(X^{k})^{2}g^{k+1},  (6)
s^{k} ≡ g^{k+1} − A^{T} y^{k} = g^{k+1} − A^{T} [A(X^{k})^{2}A^{T} ]^{−1} A(X^{k})^{2}g^{k+1},  (7)
P (x^{k}) ≡ I − X^{k}A^{T} [A(X^{k})^{2}A^{T} ]^{−1} AX^{k},  (8)
d^{k} ≡ (X^{k})^{2}s^{k} = X^{k}P (x^{k})X^{k}g^{k+1}.  (9)

Using the fact that ∥(X^{k})^{−1}(x^{k+1} − x^{k})∥ = β and x^{k+1} satisfies the optimality condition associated with (1), we can easily prove the following result.

Lemma 2.3 The following relations hold for every integer k ≥ 0:

x^{k+1} = x^{k} − β \frac{d^{k}}{∥(X^{k})^{−1}d^{k}∥} = x^{k} − β \frac{(X^{k})^{2}s^{k}}{∥X^{k}s^{k}∥};  (10)
(g^{k+1})^{T} d^{k} = (s^{k})^{T} d^{k} = ∥(X^{k})^{−1}d^{k}∥^{2} = ∥X^{k}s^{k}∥^{2};  (11)
β∥X^{k}s^{k}∥ = (g^{k+1})^{T} (x^{k} − x^{k+1}) ≤ f(x^{k}) − f(x^{k+1}).  (12)

The following result is well-known (see for example Ye [28] (or Ye and Tse [30]) and Sun [17]).

Lemma 2.4 The following statements hold:

(a) the sequence {x^{k}} converges to some point x^{∗} ∈ P^{+};

(b) f(x^{k+1}) − f(x^{∗}) ≤ (1 − β/\sqrt{n})(f(x^{k}) − f(x^{∗})) for every k sufficiently large;

(c) there exists a constant C_{0} > 0 such that ∥x^{k} − x^{∗}∥^{2} ≤ C_{0}[f(x^{k}) − f^{∗}] for every k ≥ 0;

(d) the sequence {(y^{k}, s^{k})} is bounded;

(e) ∑_{k=0}^{∞} ∥x^{k}s^{k}∥ < ∞ (in particular, every accumulation point (y^{∗}, s^{∗}) of {(y^{k}, s^{k})} satisfies x^{∗}s^{∗} = 0).

Proof. The proof of (a), (b) and (c) are given in Theorem 1 and Theorem 2 of Sun [17] under the conditions stated in Assumption 2.1. It has been proved in Vanderbei and Lagarias [25] that the matrix valued mapping U(x) ≡ (AX^{2}A^{T})^{−1}AX^{2} is bounded on P^{++} whenever Assumption 2.1(A) holds. Since y^{k} = U(x^{k})∇f(x^{k+1}), s^{k} = ∇f(x^{k+1}) − A^{T} y^{k} and {∇f(x^{k+1})} is bounded, it follows that {(y^{k}, s^{k})} is bounded. Statement (e) is an immediate consequence of (12).

The following trivial result is frequently used in our presentation.

Lemma 2.5 If (y^{∗}, s^{∗}) is an accumulation point {(y^{k}, s^{k})} and (B, N) is a partition of {1, …, n} such that {i | s_{i}^{∗} ≠ 0} ⊆ N then ∇f(x^{∗})^{T} (x − x^{∗}) = (s_{N}^{∗})^{T} x_{N} for any x ∈ P.

Proof. First note that A^{T} y^{k} + s^{k} = ∇f(x^{k+1}) implies A^{T} y^{∗} + s^{∗} = ∇f(x^{∗}). This relation together with the fact that A(x − x^{∗}) = 0, x^{∗}s^{∗} = 0 and s_{B}^{∗} = 0 imply that

∇f(x^{∗})^{T} (x − x^{∗}) = (s^{∗})^{T} (x − x^{∗}) = (s_{N}^{∗})^{T} x_{N}.

3 Convergence to an optimal solution

In this section we review an important asymptotic decomposition result for the projection matrix P (x^{k}). This result is used in several places of our presentation and it is important in its own right. We also introduce a potential function that generalizes the one used in the context of linear programs and plays an important role in the convergence analysis of this section. After introducing a local assumption which guarantees the existence of a partition (B, N) of {1, …, n} satisfying certain properties, we prove that the sequence of primal iterates and the sequence of dual estimates generated by the second order AS algorithm with β ∈ (0, 2/3] converge to optimal solutions of the given QP problem and its dual, respectively. The main goal of the next section is to show the existence of the partition (B, N) required for the analysis of this section.

We start this section by stating the following result on a decomposition of the projection matrix P (x^{k}) whose proof can be found in Tsuchiya [21]. For completeness, a simpler proof of this result is given in the appendix. It is convenient to introduce the following notation. Let P (x) denote the projection matrix onto the null space of the matrix AX, P̃_{B}(x_{B}) denote the projection matrix onto the null space of the matrix A_{B}X_{B} and P̃_{N}(x_{N}) denote the projection matrix onto the subspace {p_{N} | AXp = 0} = {p_{N} | A_{N}X_{N}p_{N} ∈ Range(A_{B})}. Hence, for every h ∈ IR^{n},

P (x)h = argmin_{p}{∥p − h∥^{2} | AXp = 0},  (13)
P̃_{N}(x_{N})h_{N} = argmin_{p_{N}} {∥p_{N} − h_{N}∥^{2} | AXp = 0}.  (14)
P̃_{B}(x_{B})h_{B} = argmin_{p_{B}}{∥p_{B} − h_{B}∥^{2} | A_{B}X_{B}p_{B} = 0},  (15)

Lemma 3.1 For every x ∈ P^{++}, let

R(x) ≡ P (x) − ( \begin{matrix}P̃_{N}(x_{N}) & 0 \\ 0 & P̃_{B}(x_{B}) \end{matrix} ) .  (16)

Then the following statements hold:

(a) for every x ∈ P^{++}, R(x) is a symmetric matrix such that

R_{NN}(x) = P̃_{N}(x_{N})R_{NN}(x)P̃_{N}(x_{N}), R_{NB}(x) = P̃_{N}(x_{N})R_{NB}(x);  (17)

(b) there exists a constant C_{1} > 0 such that for every x ∈ P^{++} with Δ_{N}(x) ≡ ∥x_{N}∥ ∥x_{B}^{−1}∥ sufficiently small, there hold

∥R_{NN}(x)∥ ≤ C_{1}Δ_{N}(x)^{2},
∥R_{BB}(x)∥ ≤ C_{1}Δ_{N}(x)^{2},
∥R_{BN}(x)∥ = ∥R_{NB}^{T}(x)∥ ≤ C_{1}Δ_{N}(x).

Throughout this section, we make a local assumption that will be used to show that Algorithm AS converges to an optimal solution of problem (1) (see Theorem 3.6). This assumption imposes conditions on the way the sequences {x^{k}} and {y^{k}, s^{k}} generated by Algorithm AS behave. In Section 4, we show that it also holds without assuming any nondegeneracy assumption on problem (1).

Before stating the local assumption, we introduce the following notation that will be used throughout our presentation.

g^{∗} = ∇f(x^{∗}),
s̃^{k} = g^{∗} − A^{T} [A(X^{k})^{2}A^{T}]^{−1}A(X^{k})^{2}g^{∗},  (18)
d̃^{k} = X^{k}P (x^{k})X^{k}g^{∗} = (X^{k})^{2}s̃^{k}.
N_{∗} = {i | x_{i}^{∗} = 0},  B_{∗} = {i | x_{i}^{∗} > 0},

Note that d̃^{k} and s̃^{k} are the search direction and the dual estimate corresponding to the affine scaling algorithm applied to the LP problem whose objective function is (g^{∗})^{T} x = (lim_{k→∞} ∇f(x^{k}))^{T} x.

Local Assumption 3.2 There exists a partition (B, N) of {1, …, n} such that N ⊆ N_{∗} and the following properties are satisfied:

(A) the sequence {Δ_{N}^{k}} defined as Δ_{N}^{k} ≡ ∥x_{N}^{k}∥ ∥(x_{B}^{k})^{−1}∥ for all k ≥ 0 satisfies ∑_{k=0}^{∞} Δ_{N}^{k} < ∞;

(B) there exists τ_{0} > 0 such that (g^{∗})^{T} (x^{k} − x^{∗}) ≥ τ_{0}∥x_{N}^{k}∥ for every k sufficiently large;

(C) the sequences {u^{k}} and {ũ^{k}} defined as

u^{k} ≡ \frac{(X^{k})^{−1}d^{k}}{(g^{∗})^{T} (x^{k} − x^{∗})},  ũ^{k} ≡ \frac{(X^{k})^{−1}d̃^{k}}{(g^{∗})^{T} (x^{k} − x^{∗})},  ∀k ≥ 0,  (19)

satisfy the following properties: {u^{k} − ũ^{k}} is bounded and u_{N}^{k} − ũ_{N}^{k} = O(Δ_{N}^{k});

(D) lim_{k→∞} s_{i}^{k} = 0 for every i ∈ N_{∗}\N.

Our goal in the remaining of this section is to show that Local Assumption 3.2 is a sufficient condition for {x^{k}}, {(y^{k}, s^{k})} to converge to optimal solutions of (1) and (2). We start with the following lemma.

Lemma 3.3 The following properties hold:

(a) {ũ^{k}} is bounded;

(b) |e^{T} ũ_{N}^{k} − 1| = O((Δ_{N}^{k})^{2}) (and hence ∥ũ_{N}^{k}∥ ≥ 1/|N| − O((Δ_{N}^{k})^{2});

(c) ∥ũ_{B}^{k}∥ = O(Δ_{N}^{k}).

Proof. First note that

(X^{k})^{−1}d̃^{k} = P (x^{k})X^{k}g^{∗} = P (x^{k})X^{k}s̄,  (20)

for any (ȳ, s̄) ∈ D(x^{∗}). Let (ȳ, s̄) be an accumulation point of the sequence {(y^{k}, s^{k})}. Clearly, (ȳ, s̄) ∈ D(x^{∗}) and, by Local Assumption 3.2(D) and Lemma 2.4(e), we have s̄_{B} = 0. Then, by (19), (20) and Local Assumption 3.2(B), we obtain

∥ũ^{k}∥ = \frac{∥P (x^{k})X^{k}s̄∥}{(g^{∗})^{T} (x^{k} − x^{∗})} ≤ \frac{∥X^{k}s̄∥}{(g^{∗})^{T} (x^{k} − x^{∗})} ≤ \frac{∥s̄_{N}∥∥x_{N}^{k}∥}{(g^{∗})^{T} (x^{k} − x^{∗})} ≤ O(1),

and hence (a) follows. By (20), Lemma 3.1 and the fact that s̄_{B} = 0, we obtain

(X^{k})^{−1}d̃^{k} = P (x^{k})X^{k}s̄ = ( \begin{matrix}\{P̃_{N}(x_{N}^{k}) + R_{NN}(x^{k})\} X_{N}^{k} s̄_{N} \\ R_{BN}(x^{k})X_{N}^{k} s̄_{N} \end{matrix} ) ,  (21)

where ∥R_{BN}(x^{k})∥ = O(Δ_{N}^{k}) and ∥R_{NN}(x^{k})∥ = O((Δ_{N}^{k})^{2}). Hence,

∥ũ_{B}^{k}∥ = \frac{∥R_{BN}(x^{k})X_{N}^{k} s̄_{N}∥}{(g^{∗})^{T} (x^{k} − x^{∗})} ≤ \frac{O(∥x_{N}^{k}∥Δ_{N}^{k})}{(g^{∗})^{T} (x^{k} − x^{∗})} ≤ O(Δ_{N}^{k}),

where the last inequality follows from Local Assumption 3.2(B). This shows (c). To show (b), we claim that

e^{T} P̃_{N}(x_{N}^{k})X_{N}^{k} s̄_{N} = (g^{∗})^{T} (x^{k} − x^{∗}),  ∀k ≥ 0.  (22)

Before showing (22), we show how (22) implies (b). Indeed, by (19), (21) and (22), we obtain

|e^{T} ũ_{N}^{k} − 1| = |\frac{e^{T} [(X_{N}^{k})^{−1}d̃_{N}^{k} − P̃_{N}(x_{N}^{k})X_{N}^{k} s̄_{N} ]}{(g^{∗})^{T} (x^{k} − x^{∗})}| = |\frac{e^{T} R_{NN}(x^{k})X_{N}^{k} s̄_{N}}{(g^{∗})^{T} (x^{k} − x^{∗})} | ≤ O((Δ_{N}^{k})^{2}),

where the last inequality follows from Local Assumption 3.2(B) and the fact that ∥R_{NN}(x^{k})∥ = O((Δ_{N}^{k})^{2}). We have thus shown (b). It remains to verify (22). Let p_{N}^{k} ≡ P_{N}(x_{N}^{k})X_{N}^{k} s̄_{N}. Since p_{N}^{k} solves problem (14) with x_{N} = x_{N}^{k} and h_{N} = X_{N}^{k} s̄_{N}, the optimality condition for this problem yields

(A_{B})^{T} ŷ^{k} = 0, X_{N}^{k}(A_{N})^{T} ŷ^{k} = p_{N}^{k} − X_{N}^{k} s̄_{N},  (23)

for some vector ŷ^{k} ∈ IR^{m}. Since b = A_{B_{∗}}x_{B_{∗}}^{∗} ∈ Range(A_{B}), it follows that A_{N}x_{N}^{k} = b − A_{B}x_{B}^{k} ∈ Range(A_{B}). Using this observation and the first equality in (23), we obtain e^{T} [X_{N}^{k}(A_{N})^{T} ŷ^{k}] = (A_{N}x_{N}^{k})^{T} ŷ^{k} = 0. Hence, the second equality in (23) yields

e^{T} p_{N}^{k} = s̄_{N}^{T}x_{N}^{k} = (g^{∗})^{T} (x^{k} − x^{∗}),

where the last equality follows from Lemma 2.5. This shows the claim.

The following potential function, usually referred to as th local Karmarkar potential function, plays an important role in our analysis. It was introduced by Tsuchiya to analyze the affine scaling algorithms for LP in [19] and for QP in [22]. For every x ∈ P_{++} satisfying (g^{∗})^{T} (x − x^{∗}) > 0, let

ψ_{N}(x) = |N| log[(g^{∗})^{T} (x − x^{∗})] − ∑_{i∈N} log x_{i}.  (24)

The following result provides an upper bound for the difference ψ_{N}(x^{k+1}) − ψ_{N}(x^{k}).

Lemma 3.4 Suppose that Local Assumption 3.2 hold and that |N| ≥ 2. Then, there exists τ > 0 such that for every k sufficiently large,

ψ_{N}(x^{k+1}) − ψ_{N}(x^{k}) ≤ −τλ_{k}η_{k}^{2} [1 − \frac{λ_{k}}{2(1 − λ_{k})}(1 + η_{k})^{−1}] + O(Δ_{N}^{k}) ≤ O(Δ_{N}^{k}),  (25)

where

λ_{k} ≡ \frac{β χ(ũ^{k})}{∥u^{k}∥}, and  η_{k} ≡ ∥\frac{ũ_{N}^{k}}{e^{T} ũ_{N}^{k}} − \frac{1}{|N|}e∥ .  (26)

Proof. Let (y^{∗}, s^{∗}) be an accumulation point of {(y^{k}, s^{k})}. Observe that Local Assumption 3.2(D) implies that {i | s_{i}^{∗} ≠ 0} ⊆ N. Hence, it follows from Lemma 2.5 that (g^{∗})^{T} (x^{k} − x^{∗}) = (s_{N}^{∗})^{T} x_{N}^{k} for every k ≥ 0. Using Local Assumption 3.2(B), the above observation and relation (5), we obtain

\frac{(g^{∗})^{T} (x^{k+1} − x^{∗})}{(g^{∗})^{T} (x^{k} − x^{∗})} ≥ \frac{τ_{0} ∥x_{N}^{k+1}∥}{(s_{N}^{∗})^{T} x_{N}^{k}} ≥ \frac{τ_{0}}{∥s_{N}^{∗}∥} \frac{∥x_{N}^{k+1}∥}{∥x_{N}^{k}∥} ≥ \frac{τ_{0} (1 − β)}{∥s_{N}^{∗}∥}.  (27)

Using relation (10), the fact that (g^{∗})^{T} d̃^{k} = ∥(X^{k})^{−1}d̃^{k}∥^{2} for all k, the definition of λ_{k}, u^{k} and ũ^{k}, Lemma 3.3(b) and conditions (B) and (C) of Local Assumption 3.2, we obtain

\frac{(g^{∗})^{T} (x^{k+1} − x^{∗})}{(g^{∗})^{T} (x^{k} − x^{∗})} = 1 − \frac{β}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{(g^{∗})^{T} d^{k}}{∥(X^{k})^{−1}d^{k}∥}
= 1 − \frac{β}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{(g^{∗})^{T} d̃^{k}}{∥(X^{k})^{−1}d^{k}∥} + \frac{β}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{(g^{∗})^{T} (d̃^{k} − d^{k})}{∥(X^{k})^{−1}d^{k}∥}
= 1 − \frac{β}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{∥(X^{k})^{−1}d̃^{k}∥^{2}}{∥(X^{k})^{−1}d^{k}∥} + \frac{β}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{(s_{N}^{∗})^{T} (d̃_{N}^{k} − d_{N}^{k})}{∥(X^{k})^{−1}d^{k}∥}
= 1 − β \frac{∥ũ^{k}∥^{2}}{∥u^{k}∥} + \frac{β}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{(X_{N}^{k}s_{N}^{∗})^{T} (ũ_{N}^{k} − u_{N}^{k})}{∥u^{k}∥}
= 1 − λ_{k} \frac{∥ũ^{k}∥^{2}}{χ(ũ^{k})} + O (\frac{∥x_{N}^{k}∥}{(g^{∗})^{T} (x^{k} − x^{∗})} \frac{∥ũ_{N}^{k} − u_{N}^{k}∥}{∥u_{N}^{k}∥})
= 1 − λ_{k} \frac{∥ũ^{k}∥^{2}}{χ(ũ^{k})} + O(Δ_{N}^{k}).  (28)

Using relations (5) and (10), the definition of λ_{k}, u^{k} and ũ^{k} and Local Assumption 3.2(C), we obtain for every i ∈ N that

1 − β ≤ \frac{x_{i}^{k+1}}{x_{i}^{k}} = 1 − β \frac{(x_{i}^{k})^{−1}d_{i}^{k}}{∥(X^{k})^{−1}d^{k}∥}
= 1 − β \frac{(x_{i}^{k})^{−1}d̃_{i}^{k}}{∥(X^{k})^{−1}d^{k}∥} + β \frac{(x_{i}^{k})^{−1}(d̃_{i}^{k} − d_{i}^{k})}{∥(X^{k})^{−1}d^{k}∥}
= 1 − β \frac{ũ_{i}^{k}}{∥u^{k}∥} + β \frac{ũ_{i}^{k} − u_{i}^{k}}{∥u^{k}∥}
= 1 − λ_{k} \frac{ũ_{i}^{k}}{χ(ũ^{k})} + O (\frac{∥ũ_{N}^{k} − u_{N}^{k}∥}{∥u^{k}∥})
= 1 − λ_{k} \frac{ũ_{i}^{k}}{χ(ũ^{k})} + O(Δ_{N}^{k}).  (29)

Relations (27), (28) and (29) and the expression

ψ_{N}(x^{k+1}) − ψ_{N}(x^{k}) = |N| log (\frac{(g^{∗})^{T} (x^{k+1} − x^{∗})}{(g^{∗})^{T} (x^{k} − x^{∗})}) − ∑_{i∈N} log \frac{x_{i}^{k+1}}{x_{i}^{k}}

then imply that

ψ_{N}(x^{k+1}) − ψ_{N}(x^{k}) ≤ |N| log (1 − λ_{k} \frac{∥ũ^{k}∥^{2}}{χ(ũ^{k})} ) − ∑_{i∈N} log (1 − λ_{k} \frac{ũ_{i}^{k}}{χ(ũ^{k})}) + O(Δ_{N}^{k}).  (30)

We will now show that {ũ^{k}} and {λ_{k}} satisfy all the conditions (a)-(e) of Proposition A.4. Indeed, conditions (b), (c) and (d) follows immediately from Lemma 3.3. Condition (a) follows from (27),

(28) and the fact that lim_{k→∞} Δ_{N}^{k} = 0, in view of Local Assumption 3.2(A). It remains to verify that (e) holds. Assume for contradiction that (e) does not hold. Then there exists an infinite index set K such that

\frac{λ_{k}}{2(1 − λ_{k})} > 1 + η_{k},  ∀k ∈ K.  (31)

Clearly, this implies that lim inf_{k∈K} λ_{k} ≥ 2/3. Noting that Lemma 3.3 and conditions (A) and (C) of Local Assumption 3.2 imply that lim_{k→∞} ∥ũ_{B}^{k}∥ = 0, lim_{k→∞} e^{T} u_{N}^{k} = 1, and lim_{k→∞} ∥u_{N}^{k} −ũ_{N}^{k}∥ = 0, it is easy to see that lim sup_{k→∞} ∥ũ^{k}∥/∥u^{k}∥ ≤ 1. This fact and the inequalities β ≤ 2/3 and χ(u) ≤ ∥u∥, for any vector u, yield

lim sup_{k→∞} λ_{k} = β lim sup_{k→∞} \frac{χ(ũ^{k})}{∥u^{k}∥} ≤ \frac{2}{3} lim sup_{k→∞} \frac{χ(ũ^{k})}{∥ũ^{k}∥} ≤ \frac{2}{3}.  (32)

This expression together with lim inf_{k∈K} λ_{k} ≥ 2/3 imply

lim_{k∈K} λ_{k} = 2/3, and lim_{k∈K} \frac{χ(ũ^{k})}{∥ũ^{k}∥} = 1.

The first relation in the last expression together with (31) then imply that lim_{k∈K} η_{k} = 0, that is,

lim_{k∈K} \frac{ũ_{N}^{k}}{e^{T} ũ_{N}^{k}} = \frac{1}{|N|}e.

It is now easy to see that this relation and the fact that lim_{k→∞} ∥ũ_{B}^{k}∥ = 0 and lim_{k→∞} e^{T} ũ_{N}^{k} = 1 contradicts the fact that lim_{k∈K} χ(ũ^{k})/∥ũ^{k}∥ = 1 when |N| ≥ 2. Hence, we conclude that {ũ^{k}} and {λ_{k}} satisfy all the conditions (a)-(e) of Proposition A.4. It follows from Proposition A.4, relation (30), Lemma 3.3 and Local Assumption 3.2(A) that for all k sufficiently large,

ψ_{N}(x^{k+1}) − ψ_{N}(x^{k})
≤ −τλ_{k}η_{k}^{2} [1 − \frac{λ_{k}}{2(1 − λ_{k})}(1 + η_{k})^{−1}] + O(Δ_{N}^{k}) + O (|e^{T} ũ_{N}^{k} − 1| + ∥ũ_{B}^{k}∥^{2})
= −τλ_{k}η_{k}^{2} [1 − \frac{λ_{k}}{2(1 − λ_{k})}(1 + η_{k})^{−1}] + O(Δ_{N}^{k}),

This shows the first inequality in (25). The second inequality in (25) follows from the fact that λ_{k}/[2(1 − λ_{k})] ≤ 1 + η_{k} for every k sufficiently large.

The next result shows that lim_{k→∞} u_{N}^{k} = e/|N|.

Lemma 3.5 Suppose that Local Assumption 3.2 hold. Then,

lim_{k→∞} u_{N}^{k} = \frac{1}{|N|}e.  (33)

Proof. If |N| = 1 then (33) follows immediately from Lemma 3.3(b) and the fact that, by Local Assumption 3.2(C), lim_{k→∞} u_{N}^{k} − ũ_{N}^{k} = 0. We now consider the case in which |N| ≥ 2. First observe that the sequence {ψ_{N}(x^{k})} is bounded below since

ψ_{N}(x^{k}) = |N| log (\frac{(g^{∗})^{T} (x^{k} − x^{∗})}{∑_{i∈N} x_{i}^{k}}) + |N| log(∑_{i∈N} x_{i}^{k}) − ∑_{i∈N} log x_{i}^{k}
≥ |N| log (\frac{τ_{0}}{|N|^{1/2}} ) + |N| log |N|,  (34)

where the last inequality is due to the inequalities ∥x_{N}^{k}∥ ≥ (∑_{i∈N} x_{i}^{k})/\sqrt{|N|} and (∑_{i∈N} x_{i}^{k})/|N| ≥ (∏_{i∈N} x_{i}^{k})^{1/|N|} and Local Assumption 3.2(B). We next show that the sequence {η_{k}} defined in (26) converges to 0. Assume for contradiction that, for some ϵ > 0 and some infinite index set K, we have η_{k} ≥ ϵ for all k ∈ K. We claim that lim sup_{k∈K} ψ_{N}(x^{k+1})−ψ(x_{N}^{k}) < 0. Indeed, due to relation (32), we have lim sup_{k→∞} λ_{k} ≤ 2/3, and hence

lim inf_{k∈K} (1 − \frac{λ_{k}}{2(1 − λ_{k})}(1 + η_{k})^{−1}) ≥ 1 − (1 + ϵ)^{−1} > 0.

Moreover, using (a) and (b) of Lemma 3.3 and (26), it is easy to see that lim inf_{k→∞} λ_{k} > 0. These two last observations, the fact that lim_{k→∞} Δ_{N}^{k} = 0 and Lemma 3.4 imply that the claim holds. By reducing K if necessary, we may assume that, for some constant γ > 0, ψ_{N}(x^{k+1}) − ψ(x_{N}^{k}) ≤ −γ for all k ∈ K. Hence, it follows that

∑_{k∈K} ψ_{N}(x^{k+1}) − ψ(x_{N}^{k}) = −∞.  (35)

Moreover, Lemma 3.4 implies that, for some constant L_{0} > 0, ψ_{N}(x^{k+1}) − ψ(x_{N}^{k}) ≤ L_{0}Δ_{N}^{k} for all k ≥ 0. This implies that

∑_{k∉K} ψ_{N}(x^{k+1}) − ψ_{N}(x_{N}^{k}) ≤ L_{0} ∑_{k∉K} Δ_{N}^{k} < ∞,

where the last inequality is due to Local Assumption 3.2(A). Combining this last relation with (35), we conclude that

∑_{k=0}^{∞} ψ_{N}(x^{k+1}) − ψ_{N}(x_{N}^{k}) = −∞,

and hence, lim_{k→∞} ψ_{N}(x_{N}^{k}) = −∞. But this contradicts (34) and hence we conclude that {η_{k}} converges to 0. Using (26), the fact that, by Lemma 3.3(b), lim_{k→∞} e^{T} ũ_{N}^{k} = 1 and, by Local Assumption 3.2(C), lim_{k→∞} u_{N}^{k} − ũ_{N}^{k} = 0, we can now easily see that (33) holds.

The next result establishes that the sequence {x^{k}} generated by Algorithm AS converges to an optimal solution of problem (1) and that the sequence of dual estimates {(y^{k}, s^{k})} converges to an optimal solution of (2).

Theorem 3.6 Suppose that the partition (B, N) satisfies Local Assumption 3.2. Then the limit point x^{∗} of the sequence {x^{k}} generated by Algorithm AS is an optimal solution of problem (1) and the associated sequence of dual estimates {(y^{k}, s^{k})} converges to an optimal solution (y^{∗}, s^{∗}) of the dual problem (2) having the following property: (y^{∗}, s^{∗}) is the unique optimal solution of the problem

maximize ∑_{i∈N} log s_{i}
subject to A^{T} y + s = g^{∗},
s_{B} = 0, s_{N} > 0.

(36)

Proof. Let (y^{∗}, s^{∗}) denote the optimal solution (y^{∗}, s^{∗}) of (36). Since A has full row rank, it follows that if lim_{k→∞} s^{k} = s^{∗} then lim_{k→∞} y^{k} = y^{∗}. Hence, it is sufficient to show that lim_{k→∞} s^{k} = s^{∗}. It can be easily verified that s^{∗} is the unique point satisfying the following relations:

s_{N} > 0, s_{B} = 0;  (37)
s ∈ g^{∗} + Range(A^{T});  (38)
A_{N}(s_{N})^{−1} ∈ Range(A_{B}),  (39)

where (s_{N})^{−1} denotes the subvector [(s_{i})^{−1}]_{i∈N}. We will show that every accumulation point of the (bounded) sequence {s^{k}} satisfies relations (37), (38) and (39), thereby showing that lim_{k→∞} s^{k} = s^{∗}. Indeed, let s^{∞} denote an accumulation point of {s^{k}}, that is, s^{∞} = lim_{k∈K} s^{k} for some infinite index set K. By Lemma 2.4(e) and Local Assumption 3.2(D), we know that s_{B}^{∞} = 0. Letting k tend to ∞ in the relation s^{k} ∈ g^{k+1} + Range(A^{T}), we conclude that s^{∞} ∈ g^{∗} + Range(A^{T}). By Lemma 3.5, we have

lim_{k→∞} u_{N}^{k} = lim_{k→∞} \frac{X_{N}^{k}s_{N}^{k}}{(g^{∗})^{T} (x^{k} − x^{∗})} = \frac{1}{|N|}e,

where X_{N}^{k} = diag(x_{N}^{k}), and by Local Assumption 3.2(B), we know that ∥x_{N}^{k}∥/[(g^{∗})^{T} (x^{k} − x^{∗})] is bounded. From these two observations, we can easily see that s_{N}^{∞} > 0 and that

lim_{k∈K} \frac{|N|}{(g^{∗})^{T} (x^{k} − x^{∗})}x_{N}^{k} = (s_{N}^{∞})^{−1}.  (40)

Since b ∈ Range(A_{B_{∗}}) ⊆ Range(A_{B}) and Ax^{k} = b, we conclude that

A_{N} (\frac{|N|}{(g^{∗})^{T} (x^{k} − x^{∗})}x_{N}^{k} ) ∈ Range(A_{B}), ∀k ≥ 0.

Letting k ∈ K tend to ∞ in this relation and using (40), we obtain that

A_{N}(s_{N}^{∞})^{−1} ∈ Range(A_{B}).

We have thus shown that s^{∞} satisfies (37), (38) and (39), and hence it follows that s^{∞} = s^{∗}.

4 Global convergence proof

The main goal of this section is to show the existence of the partition (B, N) satisfying the conditions (A)-(D) of Assumption 3.2.

The following technical lemma is easy to verify and is frequently used in our presentation.

Lemma 4.1 Let F ∈ IR^{p×q} be given. Then, there exists a constant C_{2} = C_{2}(F) with the following property: for any f ∈ IR^{p} such that the system F w = f is feasible and any z ∈ IR^{q}, there exists a solution w̄ of F w = f such that

∥w̄ − z∥ ≤ C_{2}∥f − F z∥.

Our next goal is to show that for index set N such that N ⊆ N_{∗}, we have f(x^{k}) − f(x^{∗}) = O(∥x_{N}^{k}∥) (see Theorem 4.4). This result plays a fundamental role in the analysis of this section.

We use the following notation. Given a point x ∈ P^{++}, let

E(x) = E(x; β) ≡ {w ∈ P | ∥X^{−1}(w − x)∥ ≤ β}.  (41)

Lemma 4.2 f(x^{k+1}) − f(x^{∗}) = O(∥X^{k}s^{k}∥).

Proof. Consider the point x̃^{k+1} defined as

x̃^{k+1} ≡ x^{k} + \frac{β(x^{∗} − x^{k})}{∥(X^{k})^{−1}(x^{∗} − x^{k})∥}.

Clearly, x̃^{k+1} ∈ E(x^{k}) (see (41)). Since x^{k+1} is the optimal solution of (4), we know that (g^{k+1})^{T} (x− x^{k+1}) ≥ 0 for all x ∈ E(x^{k}). In particular, x = x̃^{k+1} yields

(g^{k+1})^{T} (x^{k} − x^{k+1} + \frac{β (x^{∗} − x^{k})}{∥(X^{k})^{−1}(x^{∗} − x^{k})∥}) ≥ 0,

or equivalently,

∥(X^{k})^{−1}(x^{∗} − x^{k})∥ − β ≥ \frac{β (g^{k+1})^{T} (x^{k+1} − x^{∗})}{(g^{k+1})^{T} (x^{k} − x^{k+1})}.  (42)

It is easy to see that lim_{k→∞} ∥(X^{k})^{−1}(x^{∗} − x^{k})∥ = |N_{∗}|^{1/2}. This relation together with (12), (42) and the inequality f(x^{k+1}) − f(x^{∗}) ≤ (g^{k+1})^{T} (x^{k+1} − x^{∗}) imply

lim sup_{k→∞} \frac{f(x^{k+1}) − f(x^{∗})}{∥X^{k}s^{k}∥} ≤ β lim sup_{k→∞} \frac{(g^{k+1})^{T} (x^{k+1} − x^{∗})}{(g^{k+1})^{T} (x^{k} − x^{k+1})}
≤ lim sup_{k→∞} (∥(X^{k})^{−1}(x^{∗} − x^{k})∥ − β) = |N_{∗}|^{1/2} − β,

and the result follows.

Lemma 4.3 Assume that {a_{k}} is an unbounded sequence of positive scalars such that a_{k+1} = O(a_{k}). Then there exists a subsequence {a_{k}}_{k∈K} such that lim_{k∈K} a_{k} = ∞ and a_{k} ≤ a_{k+1} for all k ∈ K.

Proof. Let K_{0} ≡ {k | a_{k−1} ≤ a_{k}}. We first show that the subsequence {a_{k}}_{k∈K_{0}} is unbounded. Indeed, assume for contradiction that, for some L_{0} > 0, a_{k} ≤ L_{0} for every k ∈ K_{0}. Let k_{0} denote the smallest index in K_{0}. We claim that a_{k} ≤ L_{0} for every k ≥ k_{0}, a fact that contradicts the assumption that {a_{k}} is unbounded. To prove the claim, let k ≥ k_{0} be given. Clearly, if k ∈ K_{0} then a_{k} ≤ L_{0}. If k ∉ K_{0} then let j(k) denote the largest index j ∈ K_{0} such that j < k. Since j(k) ∈ K_{0} and j(k) + 1, …, k ∉ K_{0}, we have L_{0} ≥ a_{j(k)} > a_{j(k)+1} > … > a_{k}. This shows that a_{k} ≤ L_{0} for every k ≥ k_{0} and, hence, that {a_{k}}_{k∈K_{0}} is unbounded. Hence, there exists an infinite index set K such that a_{k} ≤ a_{k+1} for every k ∈ K and lim_{k∈K} a_{k+1} = ∞. Since a_{k+1} = O(a_{k}), it also follows that lim_{k∈K} a_{k} = ∞. Hence, the result follows.

Now we are ready to see the theorem.

Theorem 4.4 Let N ⊆ N_{∗} be given. Then the following statements hold:

(a) f(x^{k}) − f(x^{∗}) = O(∥x_{N}^{k}∥);

(b) ∥x^{k} − x^{∗}∥^{2} = O(∥x_{N}^{k}∥).

Proof. Observe that (b) follows as a consequence of (a) and Lemma 2.4(c). We next show (a). Assume for contradiction that a_{k} ≡ [f(x^{k}) − f(x^{∗})]/∥x_{N}^{k}∥ is unbounded. Clearly, we have a_{k+1} ≤ (1 − β)^{−1}a_{k} = O(a_{k}). Hence, it follows from Lemma 4.3 that there exists an infinite index set K such that lim_{k∈K}a_{k} = ∞ and a_{k} ≤ a_{k+1} for all k ∈ K. Using the definition of a_{k}, the last inequality and Lemma 2.4(b), we obtain

\frac{∥x_{N}^{k+1}∥}{∥x_{N}^{k}∥} ≤ \frac{f(x^{k+1}) − f(x^{∗})}{f(x^{k}) − f(x^{∗})} ≤ γ_{0} < 1,  ∀k ∈ K,  (43)

where γ_{0} = 1 − β/\sqrt{n} < 1. It is easy to see that this relation implies that

lim inf_{k∈K}∥(X_{N}^{k})^{−1}(x_{N}^{k+1} − x_{N}^{k}) ∥ > 0.  (44)

We can easily verify the existence of an index set N̂ ⊆ {1, …, n} and an infinite index set K_{0} ⊆ K such that

∥xk ; N̂∥ = O(∥x_{N}^{k}∥),  ∀k ∈ K_{0},  (45)
lim_{k∈K_{0}} \frac{x_{i}^{k}}{∥x_{N}^{k}∥} = ∞,  ∀i ∉ N̂.  (46)

These relations imply that lim_{k∈K} Δk ; N̂ = 0. Clearly, N ⊆ N̂ ⊆ N_{∗}. In view of (45) and the fact that lim_{k∈K}a_{k} = ∞, we obtain

lim_{k∈K_{0}} \frac{f(x^{k}) − f(x^{∗})}{∥xk ; N̂∥} = ∞.  (47)

Using Lemma 4.1 with z = x^{k+1}, it follows that for every k ≥ 0 the feasible system (e.g., x = x^{k} is a feasible solution)

Ax = b,  xN̂ = xk ; N̂  (48)

has a solution x̂^{k+1} such that

∥x̂^{k+1} − x^{k+1}∥ = O (∥xk ; N̂ − xk+1 ; N̂∥) = O (∥xk ; N̂∥) .  (49)

We will now show that the half line starting at x^{k} and passing through the point x̂^{k+1} contains a point in E(x^{k}) whose f–function value is smaller than f(x^{k+1}) whenever k ∈ K_{0} is sufficiently large, a fact that that contradicts the definition of x^{k+1}. We first show that

lim sup_{k∈K_{0}} ∥(X^{k})^{−1}(x̂^{k+1} − x^{k})∥ < β.  (50)

Indeed, the fact that x̂k+1 ; N̂ = xk ; N̂ implies

∥(X^{k})^{−1}(x̂^{k+1} − x^{k})∥^{2} = ∥(Xk ; B̂)^{−1}(x̂k+1 ; B̂ − xk ; B̂)∥^{2}
≤ ∥(Xk ; B̂)^{−1}(xk+1 ; B̂ − xk ; B̂)∥^{2} + ∥(Xk ; B̂)^{−1}(x̂k+1 ; B̂ − xk+1 ; B̂)∥^{2}

+ 2 ∥(Xk ; B̂)^{−1}(x̂k+1 ; B̂ − xk+1 ; B̂)∥ ∥(Xk ; B̂)^{−1}(xk+1 ; B̂ − xk ; B̂)∥

≤ β^{2} − ∥(Xk ; N̂)^{−1}(xk+1 ; N̂ − xk ; N̂)∥^{2} + ∥(Xk ; B̂)^{−1}(x̂k+1 ; B̂ − xk+1 ; B̂)∥^{2}
+ 2β ∥(Xk ; B̂)^{−1}(x̂k+1 ; B̂ − xk+1 ; B̂)∥.  (51)

By (49) and the fact that lim_{k∈K} Δk ; N̂ = 0, we have

lim_{k∈K_{0}} ∥(Xk ; B̂)^{−1}(x̂k+1 ; B̂ −xk+1 ; B̂)∥ ≤ lim_{k∈K_{0}} ∥(Xk ; B̂)^{−1}∥ ∥x̂k+1 ; B̂ −xk+1 ; B̂∥ = lim_{k∈K_{0}} O(∥(Xk ; B̂)^{−1}∥∥xk ; N̂∥) = 0, (52)

where the last equality follows from (45) and (46). Combining (44), (51) and (52), we obtain (50).

For λ ≥ 0, consider the point x^{k+1}(λ) ≡ x^{k} + λ(x̂^{k+1} − x^{k}). It follows from (50) that there exists ϵ > 0 such that x^{k+1}(λ) ∈ E(x^{k}) for every λ ∈ [0, 1 + ϵ] and k ∈ K_{0} sufficiently large. We now estimate the difference f(x^{k+1}) − f(x^{k+1}(λ)). It is easy to see that

f(x^{k+1}) − f(x^{k+1}(λ)) = f(x^{k+1}) − f(x^{k}) + f(x^{k}) − f(x^{k+1}(λ))
= ∇f(x^{k})^{T} (x^{k+1} − x^{k+1}(λ)) + \frac{1}{2}∥x^{k+1} − x^{k}∥_{Q}^{2} − \frac{1}{2}∥x^{k+1}(λ) − x^{k}∥_{Q}^{2}

(53)

Using (49) and the definition of x^{k+1}(λ), we obtain

∇f(x^{k})^{T} (x^{k+1} − x^{k+1}(λ)) = (1 − λ)∇f(x^{k})^{T} (x^{k+1} − x^{k}) + λ∇f(x^{k})^{T} (x^{k+1} − x̂^{k+1})
≥ (λ − 1)∇f(x^{k})^{T} (x^{k} − x^{k+1}) − O(∥xk ; N̂∥)
= (λ − 1) [∥x^{k} − x^{k+1}∥_{Q}^{2} + β∥X^{k}s^{k}∥] − O(∥xk ; N̂∥),  (54)

where the last equality follows from (12). Moreover,

∥x^{k+1}(λ) − x^{k}∥_{Q}^{2} = λ^{2}∥x̂^{k+1} − x^{k}∥_{Q}^{2}
≤ λ^{2} [∥x̂^{k+1} − x^{k+1}∥_{Q}^{2} + ∥x^{k+1} − x^{k}∥_{Q}^{2} + 2∥x̂^{k+1} − x^{k+1}∥_{Q} ∥x^{k+1} − x^{k}∥_{Q}]
≤ λ^{2}∥x^{k+1} − x^{k}∥_{Q}^{2} + O(∥xk ; N̂∥),  ∀λ ∈ [0, 1 + ϵ].

Combining (53), (54) and (55) and rearranging, we obtain that for every λ ∈ (1, 1 + ϵ],

\frac{f(x^{k+1}) − f(x^{k+1}(λ))}{(λ − 1) ∥X^{k}s^{k}∥} ≥ \{β − \frac{1}{2}(λ − 1)\frac{∥x^{k+1} − x^{k}∥_{Q}^{2}}{∥X^{k}s^{k}∥} − O (\frac{∥xk ; N̂∥}{(λ − 1)∥X^{k}s^{k}∥})\} .  (55)

Now, by (5), (43) and Lemma 4.2, it follows that

f(x^{k}) − f(x^{∗}) ≤ (1 − β)^{−1} [f(x^{k+1}) − f(x^{∗})] = O(∥X^{k}s^{k}∥),  ∀k ∈ K ⊇ K_{0}.  (56)

This relation, relation (47) and the identity f(x^{k}) − f(x^{k+1}) = β∥X^{k}s^{k}∥ + ∥x^{k+1} − x^{k}∥_{Q}^{2}/2 imply that

lim_{k∈K_{0}} \frac{∥xk ; N̂∥}{∥X^{k}s^{k}∥} = 0,  \frac{∥x^{k+1} − x^{k}∥_{Q}^{2}}{∥X^{k}s^{k}∥} ≤ L_{0},  ∀k ∈ K_{0},  (57)

where L_{0} is some positive constant. Let λ̄ ≡ 1 + min{ϵ, β/L_{0}}. Then, it follows from (55) with λ = λ̄ that

\frac{f(x^{k+1}) − f(x^{k+1}(λ̄))}{(λ̄ − 1) ∥X^{k}s^{k}∥} ≥ \frac{β}{2} − O (\frac{∥xk ; N̂∥}{∥X^{k}s^{k}∥}) > 0, ∀k ∈ K_{0} sufficiently large.

Hence, f(x^{k+1}(λ̄)) < f(x^{k+1}) for every k ∈ K_{0} sufficiently large. This conclusion together with the fact that x^{k+1}(λ̄) ∈ E(x^{k}) contradicts the definition of x^{k+1}.

The following set is frequently used in our presentation. Let

Γ ≡ {N | N ⊆ N_{∗} ⊆ {1, …, n}, lim inf_{k→∞} Δ_{N}^{k} = 0}.  (58)

We now give an outline for the remaining part of this section. The main result of this section is Theorem 4.15 which establishes global convergence of Algorithm AS. Its statement is very similar to the one of Theorem 3.6 except that it guarantees the existence of a unique partition (B̄, N̄) satisfying Local Assumption 3.2. Let N̄ denote a minimal element of the set Γ with respect to inclusion and let B̄ ≡ {1, …, n}\N̄. The main goal from now on is to show that (B̄, N̄) satisfies all the conditions of Local Assumption 3.2. In Theorem 4.15 we show that there can be only one partition satisfying Local Assumption 3.2 from which it also follows that the set Γ has only one minimal element, in other words, Γ has a smallest element with respect to inclusion. Theorem 4.13 shows that (B̄, N̄) satisfies condition (A) of Local Assumption 3.2. In fact, once this condition is verified, it is not difficult to obtain the other ones. We separate the proof of Theorem 4.13 into several lemmas. The major part of the proof are given in Lemma 4.10, Lemma 4.11 and Lemma 4.12. All the results between (and including) Lemma 4.5 and 4.9 are mainly technical ones.

Lemma 4.5 Assume that an infinite index set K and an index set N ⊆ {1, …, n} are such that N ⊆ N_{∗} and lim_{k∈K} Δ_{N}^{k} = 0. Then, lim_{k∈K} s_{B}^{k} = 0, where B ≡ {1, …, n}\N.

Proof. By Theorem 4.4(a), it follows that there exists L_{0} > 0 such that f(x^{k})−f(x^{∗}) ≤ L_{0}∥x_{N}^{k}∥ for every integer k ≥ 0. Using this fact and inequality (12), we obtain

∥s_{B}^{k}∥ ≤ ∥(x_{B}^{k})^{−1}∥ ∥x_{B}^{k}s_{B}^{k}∥ ≤ ∥(x_{B}^{k})^{−1}∥ ∥x^{k}s^{k}∥
≤ ∥(x_{B}^{k})^{−1}∥\frac{f(x^{k}) − f(x^{k+1})}{β} ≤ ∥(x_{B}^{k})^{−1}∥\frac{f(x^{k}) − f(x^{∗})}{β}
≤ \frac{L_{0}}{β} ∥(x_{B}^{k})^{−1}∥ ∥x_{N}^{k}∥ = O(Δ_{N}^{k}).

Since by assumption lim_{k∈K} Δ_{N}^{k} = 0, the result immediately follows.

Lemma 4.6 Suppose that N ∈ Γ and B ≡ {1, …, n}\N. Then the following statements hold:

(a) g_{B}^{∗} ∈ Range(A_{B}^{T});

(b) x^{∗} ∈ P_{N}^{+} and x ↦ (g^{∗})^{T} x is constant over the face P_{N}^{+};

(c) P_{N}^{++} ≠ ∅.

Proof. Since N ∈ Γ, we have lim inf_{k→∞} Δ_{N}^{k} = 0. By Lemma 4.5, the sequence {(y^{k}, s^{k})} has an accumulation point (ȳ, s̄) such that s̄_{B} = 0. Since A^{T} ȳ + s̄ = g^{∗} and s̄_{B} = 0, (a) follows. Statement (b) follows from (a) and the fact that N ⊆ N_{∗}. We next show (c). Let K be an infinite index set such that lim_{k∈K} Δ_{N}^{k} = 0. Consider the feasible system (e.g., x = x^{∗} is a feasible solution)

Ax = b,  x_{N} = 0.  (59)

Using Lemma 4.1 with z = x^{k}, there exist a constant L_{0} > 0 and a sequence {w^{k}} of solutions of (59) such that

∥x^{k} − w^{k}∥ ≤ L_{0}∥x_{N}^{k}∥, ∀k ≥ 0.

Hence, we obtain

∥(X_{B}^{k})^{−1}(w_{B}^{k} − x_{B}^{k})∥ ≤ ∥(x_{B}^{k})^{−1}∥ ∥w_{B}^{k} − x_{B}^{k}∥ ≤ L_{0}∥(x_{B}^{k})^{−1}∥ ∥x_{N}^{k}∥ = L_{0}Δ_{B}^{k},

from which we conclude that lim_{k∈K} ∥(X_{B}^{k})^{−1}(w_{B}^{k} − x_{B}^{k})∥ = 0. Clearly, this implies that w_{B}^{k} > 0 for sufficiently large k ∈ K, and hence that w^{k} ∈ P_{N}^{++}, for all k ∈ K sufficiently large.

Lemma 4.7 Assume that N̄ is a minimal element of Γ with respect to inclusion and let B̄ = {1, …, n}\N̄. Then there exist scalars δ_{0} > 0 and η_{0} > 0 such the following implication holds for every k sufficiently large:

Δk ; N̄ ≤ δ_{0} ⟹ \frac{∥Xk ; N̄sk ; N̄∥}{∥xk ; N̄∥} ≥ η_{0}  (60)

Proof. Assume for contradiction that the conclusion of the lemma does not hold. Then there exists an infinite index set K such that

lim_{k∈K} Δk ; N̄ = 0,  lim_{k∈K} \frac{∥Xk ; N̄sk ; N̄∥}{∥xk ; N̄∥} = 0.  (61)

Since {sk ; N̄} and {xk ; N̄/∥xk ; N̄∥} are bounded sequences, by passing to a subsequence if necessary we may assume that

lim_{k∈K} sk ; N̄ = s∞ ; N̄, and lim_{k∈K} \frac{xk ; N̄}{∥xk ; N̄∥} = d∞ ; N̄  (62)

for some |N̄|-dimensional vectors s∞ ; N̄ and d∞ ; N̄. Clearly, d∞ ; N̄ ≥ 0, ∥d∞ ; N̄∥ = 1 and, by the second relation in (61), s∞ ; N̄d∞ ; N̄ = 0. Let N ≡ {j ∈ N̄ | d_{j}^{∞} = 0} and B ≡ {1, …, n}\N. Since ∥d∞ ; N̄∥ = 1 and s_{N}^{∞} ≠ 0, it follows that N ⊆ N̄ properly, and hence that B ⊇ B̄ properly. Using the first relation in (61), the second relation in (62) and the fact that d_{N}^{∞} = 0 and d_{N̄\N}^{∞} > 0, we can easily see that lim_{k∈K} Δ_{N}^{k} = 0. Hence, it follows that lim inf_{k→∞} Δ_{N}^{k} = 0, and since N ⊆ N̄ ⊆ N_{∗}, we conclude that N ∈ Γ. But this together with the fact that N is contained N̄ properly contradict the assumption that N̄ is a minimal element of Γ.

The next result plays an important role in several of the results that will be stated later. It is useful to recall the definition of the set D_{B}(x) given in (3).

Lemma 4.8 The following statements hold:

(a) s_{B_{∗}}^{k} = O(∥X^{k}s^{k}∥ ∥x^{k+1} − x^{k}∥);

(b) there exists a sequence {(y_{∗}^{k}, s_{∗}^{k})} ⊆ D_{B_{∗}}(x^{∗}) such that

∥s_{N_{∗}}^{k} − (s_{∗}^{k})_{N_{∗}}∥ = O(∥x^{k+1} − x^{∗}∥),  (63)
∥X^{k}(s^{k} − s_{∗}^{k})∥ = O(∥X^{k}s^{k}∥).  (64)

Proof. Statement (a) follows from the fact that (x_{i}^{k})^{−1} is bounded above for every i ∈ B_{∗} and from the relation

s_{i}^{k} = (x_{i}^{k})^{−2}(x_{i}^{k} − x_{i}^{k+1})\frac{∥X^{k}s^{k}∥}{β}.

We next show (b). Consider the feasible system (e.g., if (y^{∗}, s^{∗}) is an accumulation point of {(y^{k}, s^{k})} then (y, s) = (y^{∗}, s^{∗}) is a feasible solution of this system)

A^{T} y + s = g^{∗},  s_{B_{∗}} = 0  (65)

(e.g., if (y^{∗}, s^{∗}) is an accumulation point of {(y^{k}, s^{k})} then (y, s) = (y^{∗}, s^{∗}) is a feasible solution of this system). Using Lemma 4.1 with z = (y^{k}, s^{k}) and the fact that A^{T} y^{k} + s^{k} = g^{k+1}, we conclude that for every k ≥ 0, (65) has a solution (y_{∗}^{k}, s_{∗}^{k}) such that

∥y^{k} − y_{∗}^{k}∥ + ∥s^{k} − s_{∗}^{k}∥ = O(∥g^{k+1} − g^{∗}∥ + ∥s_{B_{∗}}^{k}∥).

Clearly, {(y_{∗}^{k}, s_{∗}^{k})} ⊆ D_{B_{∗}}(x^{∗}), and (63) now follows from the above expression, statement (a) and the fact that ∥g^{k+1} − g^{∗}∥ = ∥Q(x^{k+1} − x^{∗})∥ = O(∥x^{k+1} − x^{∗}∥). We next show (64). First observe that (a) and the fact that (s_{∗}^{k})_{B_{∗}} = 0 imply that

∥X_{B_{∗}}^{k}(s^{k} − s_{∗}^{k})_{B_{∗}}∥ = ∥X_{B_{∗}}^{k}s_{B_{∗}}^{k}∥ = O(∥x^{k+1} − x^{k}∥ ∥X^{k}s^{k}∥) ≤ O(∥X^{k}s^{k}∥).

By Lemma 4.2 and Lemma 2.4(c), it follows that

∥x^{k+1} − x^{∗}∥^{2} = O(∥X^{k}s^{k}∥).

Using this relation, (5) and (63), we obtain

∥X_{N_{∗}}^{k}(s^{k} − s_{∗}^{k})_{N_{∗}}∥ ≤ (1 − β)^{−1}∥x_{N_{∗}}^{k+1}∥ ∥(s^{k} − s_{∗}^{k})_{N_{∗}}∥
≤ O (∥x^{k+1} − x^{∗}∥^{2}) = O(∥X^{k}s^{k}∥).

Lemma 4.9 Let (B, N) be a partition such that D_{B}(x^{∗}) ≠ ∅. Then there exists a constant C_{3} > 0 such that ∥(P (x)Xg^{∗})_{B}∥ ≤ C_{3} (∥x_{N}∥Δ_{N}(x)) for every x ∈ P_{++} with Δ_{N}(x) sufficiently small.

Proof. Since D_{B}(x^{∗}) ≠ ∅, let (ȳ, s̄) ∈ D_{B}(x^{∗}) be given. We have s̄_{B} = 0 and P (x)Xg^{∗} = P (x)Xs̄. From Lemma 3.1, it follows that

P (x)Xs̄ = ( \begin{matrix}P̃_{N}(x_{N})X_{N} s̄_{N} \\ P̃_{B}(x_{B})X_{B}s̄_{B} \end{matrix} ) + R(x)Xs̄,

where ∥R(x)∥ ≤ C_{1}Δ_{N}(x) for every x ∈ P_{++} with Δ_{N}(x) sufficiently small. Since s̄_{B} = 0, we obtain

∥(P (x)Xg^{∗})_{B}∥ = ∥(P (x)Xs̄)_{B}∥ ≤ ∥R(x)∥∥X_{N} s̄_{N}∥ ≤ C_{1}∥s̄_{N}∥ ∥x_{N}∥Δ_{N}(x),

for every x ∈ P_{++} with Δ_{N}(x) sufficiently small. Letting C_{3} ≡ C_{1}∥s̄_{N}∥, the result follows.

The main goal of the next three results is to prepare the reader for the proof that ∑_{k=0}^{∞} Δk ; N̄ < ∞. This fact will be more easily proved by working with a related sequence of scalars, namely the sequence {Ψk ; B̄} defined as

Ψk ; B̄ ≡ \frac{f(x^{k}) − f(x^{∗})}{min(xk ; B̄)},  ∀k ≥ 0.  (66)

We will show that ∑_{k=0}^{∞} Ψk ; B̄ < ∞ and this in turn will allow us to show that ∑_{k=0}^{∞} Δk ; N̄ < ∞. For Δk ; N̄ sufficiently small, the next three lemmas deals with three cases (not necessarily disjoint) that arise by considering the size of the two quantities:

\frac{∥x_{N_{∗}\N̄}^{k}∥^{2}}{∥xk ; N̄∥} , \frac{min (x_{N_{∗}\N̄}^{k})}{max (x_{N_{∗}\N̄}^{k})}.

Lemma 4.10 deals with the case where the first quantity is sufficiently small; Lemma 4.11 deals with the case where the second quantity is sufficiently small; finally, Lemma 4.12 deals with the case where the first and second quantities are bounded away from 0. In the proof of Theorem 4.13, we combine these three cases together to prove that ∑_{k=0}^{∞} Δk ; N̄ < ∞.

Lemma 4.10 Assume that N̄ is a minimal element of Γ with respect to inclusion and let B̄ = {1, …, n}\N̄. There exist constants δ_{1} > 0, τ_{1} > 0 and γ_{1} ∈ (0, 1) such that the following implication holds for every k sufficiently large:

∥x_{N_{∗}\N̄}^{k}∥^{2} ≤ τ_{1}∥xk ; N̄∥, Δk ; N̄ ≤ δ_{1} ⟹ Ψk+1 ; B̄ ≤ γ_{1}Ψk ; B̄.

Proof. Assume for contradiction that for some infinite index set K, there holds

lim_{k∈K} \frac{∥x_{N_{∗}\N̄}^{k}∥^{2}}{∥xk ; N̄∥} = 0,  (67)
lim_{k∈K} Δk ; N̄ = 0,  (68)
lim sup_{k∈K} \frac{Ψk+1 ; B̄}{Ψk ; B̄} ≥ 1.  (69)

Observe that (68) and Lemma 4.7 imply that

∥xk ; N̄∥ = O(∥X^{k}s^{k}∥),  ∀k ∈ K.  (70)

Below we concentrate our effort in showing the following claim:

lim_{k∈K}(Xk ; B̄)^{−1}(xk+1 ; B̄ − xk ; B̄) = 0.  (71)

This relation clearly implies that

lim_{k∈K} \frac{min(xk+1 ; B̄)}{min(xk ; B̄)} = 1,

which together with Lemma 2.4(b) in turn imply that lim sup_{k∈K} Ψk+1 ; B̄/Ψk ; B̄ < 1, a fact that contradicts (69) and hence establishes the validity of the lemma.

To prove the claim, first observe that

(X^{k})^{−1}(x^{k+1} − x^{k}) = β(p_{1}^{k} + p_{2}^{k}),  (72)

where

p_{1}^{k} ≡ P (x^{k})\frac{X^{k}g^{∗}}{∥X^{k}s^{k}∥},  p_{2}^{k} ≡ P (x^{k})\frac{X^{k}(g^{k+1} − g^{∗})}{∥X^{k}s^{k}∥}.  (73)

The claim follows once we show that lim_{k∈K} (p_{1}^{k})B̄ = 0 and lim_{k∈K} p_{2}^{k} = 0. We first show that lim_{k∈K} (p_{1}^{k})B̄ = 0. Since N̄ ∈ Γ, it follows from Lemma 4.6(a) that g∗ ; B̄ ∈ Range(AT ; B̄), or equivalently, that DB̄(x^{∗}) ≠ ∅. Hence, by (68), (70) and Lemma 4.9, we obtain

(p_{1}^{k})B̄ = O (\frac{∥xk ; N̄∥ Δk ; N̄}{∥X^{k}s^{k}∥} ) ≤ O(Δk ; N̄),  ∀k ∈ K,  (74)

from which we conclude that lim_{k∈K} (p_{1}^{k})B̄ = 0. We next show that lim_{k∈K} p_{2}^{k} = 0. Indeed, recalling the definition of (y_{∗}^{k}, s_{∗}^{k}) in Lemma 4.8(b) and using the fact that (y^{k}, s^{k}) ∈ D(x^{k+1}) and (y_{∗}^{k}, s_{∗}^{k}) ∈ D(x^{∗}), we obtain

p_{2}^{k} = P (x^{k})\frac{X^{k}(s^{k} − s_{∗}^{k})}{∥X^{k}s^{k}∥}

and hence,

∥p_{2}^{k}∥ ≤ \frac{∥X^{k}(s^{k} − s_{∗}^{k})∥}{∥X^{k}s^{k}∥}.  (75)

Now, Lemma 4.8(a) and the fact that (s_{∗}^{k})_{B_{∗}} = 0 imply

\frac{∥X_{B_{∗}}^{k}(s_{B_{∗}}^{k} − (s_{∗}^{k})_{B_{∗}})∥}{∥X^{k}s^{k}∥} ≤ ∥x_{B_{∗}}^{k}∥\frac{∥s_{B_{∗}}^{k}∥}{∥X^{k}s^{k}∥} = O(∥x^{k+1} − x^{k}∥),  ∀k ∈ K,  (76)

and, from Lemma 4.8(b), Theorem 4.4(b) and (70), we obtain

\frac{∥X_{N_{∗}}^{k}(s_{N_{∗}}^{k} − (s_{∗}^{k})_{N_{∗}})∥}{∥X^{k}s^{k}∥} ≤ \frac{(∥xk ; N̄∥ + ∥x_{N_{∗}\N̄}^{k}∥) ∥s_{N_{∗}}^{k} − (s_{∗}^{k})_{N_{∗}}∥}{∥X^{k}s^{k}∥}

≤ O (\frac{(∥xk ; N̄∥ + ∥x_{N_{∗}\N̄}^{k}∥)}{∥xk ; N̄∥^{1/2}} \frac{∥x^{k+1} − x^{∗}∥}{∥xk ; N̄∥^{1/2}} )

≤ O (\frac{∥xk ; N̄∥ + ∥x_{N_{∗}\N̄}^{k}∥}{∥xk ; N̄∥^{1/2}} ) ,  ∀k ∈ K,  (77)

which converges to 0 in view of (67). It follows from (75), (76) and (77) that lim_{k∈K} p_{2}^{k} = 0. We have thus shown that lim_{k∈K}(Xk ; B̄)^{−1}(xk+1 ; B̄ − xk ; B̄) = 0.

Lemma 4.11 Assume that N̄ is a minimal element of Γ with respect to inclusion and let B̄ = {1, …, n}\N̄. There exist constants δ_{2} > 0, M_{0} > 0 and γ_{2} ∈ (0, 1) such that the following implication holds for every k sufficiently large:

\frac{max(x_{N_{∗}\N̄}^{k})}{min(x_{N_{∗}\N̄}^{k})} ≥ M_{0}, Δk ; N̄ ≤ δ_{2} ⟹ Ψk+1 ; B̄ ≤ γ_{2}Ψk ; B̄.

Proof. Assume for contradiction that for some infinite index set K, there holds

lim_{k∈K} \frac{max(x_{N_{∗}\N̄}^{k})}{min(x_{N_{∗}\N̄}^{k})} = ∞,  (78)
lim_{k∈K} Δk ; N̄ = 0,  (79)
lim sup_{k∈K} \frac{Ψk+1 ; B̄}{Ψk ; B̄} ≥ 1.  (80)

It is easy to see that there exist some infinite subset K_{0} of K and some set N ⊆ {1, …, n} such that

lim sup_{k∈K_{0}} \frac{x_{i}^{k}}{min(x_{N_{∗}\N̄}^{k})} < ∞,  ∀i ∈ N,  (81)

lim_{k∈K_{0}} \frac{x_{i}^{k}}{min(x_{N_{∗}\N̄}^{k})} = ∞,  ∀i ∉ N.  (82)

Using (79) and the fact that lim_{k→∞} x_{B_{∗}}^{k} > 0, it is easy to see that N̄ ⊆ N ⊆ N_{∗}. Moreover, the definition of N, (78) and (79) imply that these two inclusions are proper. We claim that

lim_{k∈K_{0}}(X_{N\N̄}^{k})^{−1}(x_{N\N̄}^{k+1} − x_{N\N̄}^{k}) = 0.  (83)

As we will see, showing this relation is the major effort of the proof. As in (72), we know that (X^{k})^{−1}(x^{k+1} − x^{k}) = β(p_{1}^{k} + p_{2}^{k}), where p_{1}^{k} and p_{2}^{k} are defined in (73). The claim follows if we show that lim_{k∈K} (p_{1}^{k})B̄ = 0 and lim_{k∈K_{0}}(p_{2}^{k})_{N} = 0. The proof that lim_{k∈K} (p_{1}^{k})B̄ = 0 is exactly the same as in (74) of Lemma 4.10. We next show that lim_{k∈K_{0}}(p_{2}^{k})_{N} = 0. First observe (81) and (82) imply that lim_{k∈K_{0}} Δ_{N}^{k} = 0, where N ≡ {1, ⋯, n}\B. Using Lemma 3.1, we obtain

p_{2}^{k} = \frac{1}{∥X^{k}s^{k}∥}P (x^{k})X^{k}(s^{k} − s_{∗}^{k})
= \frac{1}{∥X^{k}s^{k}∥} ( \begin{matrix}P̃_{N}(x_{N}^{k})X_{N}^{k}(s^{k} − s_{∗}^{k})_{N} \\ P̃_{B}(x_{B}^{k})X_{B}^{k}(s^{k} − s_{∗}^{k})_{B} \end{matrix} ) + R(x^{k})\frac{X^{k}(s^{k} − s_{∗}^{k})}{∥X^{k}s^{k}∥},

where ∥R(x^{k})∥ = O(Δ_{N}^{k}). Using this relation, (63), (64) and (5), we obtain

∥(p_{2}^{k})_{N}∥ ≤ \frac{∥P̃_{N}(x_{N}^{k})X_{N}^{k}(s^{k} − s_{∗}^{k})_{N}∥}{∥X^{k}s^{k}∥} + ∥R(x^{k})∥\frac{∥X^{k}(s^{k} − s_{∗}^{k})∥}{∥X^{k}s^{k}∥}

≤ \frac{∥x_{N}^{k}∥ ∥(s^{k} − s_{∗}^{k})_{N}∥}{∥X^{k}s^{k}∥} + O(Δ_{N}^{k})
≤ O (\frac{∥x_{N}^{k}∥}{∥x^{k+1} − x^{∗}∥} \frac{∥x^{k+1} − x^{∗}∥^{2}}{∥X^{k}s^{k}∥} ) + O(Δ_{N}^{k})

≤ O (\frac{∥x_{N}^{k}∥}{∥x_{N_{∗}\N}^{k+1}∥}) + O(Δ_{N}^{k})

≤ O (\frac{∥x_{N}^{k}∥}{∥x_{N_{∗}\N}^{k}∥}) + O(Δ_{N}^{k})
≤ O(Δ_{N}^{k}),

where in the third inequality we used the fact that ∥x^{k+1}−x^{∗}∥^{2} = O(∥X^{k}s^{k}∥), due to Lemma 2.4(c) and Lemma 4.2. Since {Δ_{N}^{k}}_{k∈K_{0}} converges to 0, the last expression shows that lim_{k∈K_{0}}(p_{2}^{k})_{N} = 0. Using (5), (81) and (82), it easy to see that for every k ∈ K_{0} sufficiently large,

min(xk ; B̄) = min(x_{N\N̄}^{k}),  min(xk+1 ; B̄) = min(x_{N\N̄}^{k+1}).  (84)

It then follows from (83) and (84) that

lim_{k∈K_{0}} (\frac{min(xk+1 ; B̄)}{min(xk ; B̄)}) = lim_{k∈K_{0}} (\frac{min(x_{N\N̄}^{k+1})}{min(x_{N\N̄}^{k})}) = 1.

This relation and Lemma 2.4(b) then imply that lim sup_{k∈K_{0}} Ψk+1 ; B̄/Ψk ; B̄ < 1, a fact that contradicts (80).

Lemma 4.12 Assume that N̄ is a minimal element of Γ and let B̄ = {1, …, n}\N̄. Let δ_{0}, τ_{1} and M_{0} be the constants introduced in Lemma 4.7, 4.10 and 4.11. Then there exist constants α_{1} > 0, α_{2} > 0 and M_{1} > 0 such that the following two implications hold for every k sufficiently large:

Δk ; N̄ ≤ δ_{0} ⟹ α_{1}Ψk ; B̄ ≤ Δk ; N̄ ≤ α_{2}Ψk ; B̄,  (85)

\begin{matrix}Δk ; N̄ ≤ δ_{0}, \\ ∥x_{N_{∗}\N̄}^{k}∥^{2} ≥ τ_{1}∥xk ; N̄∥, \\ max (x_{N_{∗}\N̄}^{k}) ≤ M_{0} min (x_{N_{∗}\N̄}^{k}) \end{matrix} \} ⟹ Δk ; N̄ ≤ M_{1}(f(x^{k}) − f(x^{∗}))^{1/2}.  (86)

Proof. We first show implication (85). Assume that k_{0} is such that implication (60) holds for every k ≥ k_{0}. Using (60), (12) and Theorem 4.4(a), we conclude that if k ≥ k_{0} and Δk ; N̄ ≤ δ_{0} then

∥xk ; N̄∥ ≤ \frac{∥Xk ; N̄sk ; N̄∥}{η_{0}} ≤ \frac{∥X^{k}s^{k}∥}{η_{0}} ≤ \frac{f(x^{k}) − f(x^{k+1})}{βη_{0}}
≤ \frac{f(x^{k}) − f(x^{∗})}{βη_{0}} = O(∥xk ; N̄∥),

or equivalently, that ∥xk ; N̄∥ ∼ f(x^{k})−f(x^{∗}), for every k such that Δk ; N̄ ≤ δ_{0}. Using this fact, it is now straightforward to verify that there exist α_{1} > 0 and α_{2} > 0 such that (85) holds for every k ≥ k_{0}.

We now show that (86) holds. Assume that k ≥ k_{0} is such that Δk ; N̄ ≤ δ_{0}, ∥x_{N_{∗}\N̄}^{k}∥^{2} ≥ τ_{1}∥xk ; N̄∥ and max (x_{N_{∗}\N̄}^{k}) ≤ M_{0} min (x_{N_{∗}\N̄}^{k}). Then,

∥(xk ; B̄)^{−1}∥ ∥xk ; N̄∥ ≤ \frac{max((xk ; B̄)^{−1})∥xk ; N̄∥}{\sqrt{n}} = \frac{∥xk ; N̄∥}{\sqrt{n} min(xk ; B̄)}

≤ \frac{∥xk ; N̄∥}{\sqrt{n} min(x_{N_{∗}\N̄}^{k})} ≤ \frac{M_{0}∥xk ; N̄∥}{\sqrt{n} max(x_{N_{∗}\N̄}^{k})}

≤ \frac{M_{0}∥xk ; N̄∥}{∥x_{N_{∗}\N̄}^{k}∥} ≤ \frac{M_{0} ∥xk ; N̄∥}{\sqrt{τ_{1}∥xk ; N̄∥}}

= \frac{M_{0}}{\sqrt{τ_{1}}} ∥xk ; N̄∥^{1/2} = O(f(x^{k}) − f(x^{∗}))^{1/2}.

This shows that there exists M_{1} > 0 such that (86) holds for every k ≥ k_{0}.

The following result shows that the partition (B̄, N̄), where N̄ is a minimal element of Γ, satisfies condition (A) of Assumption 3.2.

Theorem 4.13 Assume that N̄ is a minimal element of Γ and let B̄ = {1, …, n}\N̄. Then,

∑_{k=0}^{∞} Δk ; N̄ < ∞.

Proof. First of all, it is useful to recall the content of Lemmas 4.10, 4.11 and 4.12 here. Namely, there exist positive constants δ_{0}, δ_{1}, δ_{2}, M_{0}, M_{1}, τ_{1}, α_{1}, α_{2}, γ_{1} < 1 and γ_{2} < 1 such that the following implications hold:

∥x_{N_{∗}\N̄}^{k}∥^{2} ≤ τ_{1}∥xk ; N̄∥, Δk ; N̄ ≤ δ_{1} ⟹ Ψk+1 ; B̄ ≤ γ_{1}Ψk ; B̄;  (87)

\frac{max(x_{N_{∗}\N̄}^{k})}{min(x_{N_{∗}\N̄}^{k})} ≥ M_{0}, Δk ; N̄ ≤ δ_{2} ⟹ Ψk+1 ; B̄ ≤ γ_{2}Ψk ; B̄;  (88)

Δk ; N̄ ≤ δ_{0} ⟹ α_{1}Ψk ; B̄ ≤ Δk ; N̄ ≤ α_{2}Ψk ; B̄;  (89)

\begin{matrix}Δk ; N̄ ≤ δ_{0}, \\ ∥x_{N_{∗}\N̄}^{k}∥^{2} ≥ τ_{1}∥xk ; N̄∥, \\ max (x_{N_{∗}\N̄}^{k}) ≤ M_{0} min (x_{N_{∗}\N̄}^{k}) \end{matrix} \} ⟹ Δk ; N̄ ≤ M_{1}(f(x^{k}) − f(x^{∗}))^{1/2}.  (90)

Observe that implications (87), (88) and (90) covers all possible situations for Δk ; N̄ sufficiently small. Define

ϵ_{1} ≡ \frac{1 − β}{1 + β} min\{δ_{0}, δ_{1}, δ_{2}\}.  (91)

First, we claim that there exists an integer k_{0} ≥ 0 such that

Δk ; N̄ ≤ ϵ_{1},  ∀k ≥ k_{0}.  (92)

Indeed, let

ϵ_{2} ≡ \frac{(1 − β)ϵ_{1}}{(1 + β)α_{2}} ,  ϵ_{3} ≡ (\frac{α_{1}(1 − β)ϵ_{2}}{M_{1}} )^{2} .  (93)

Due to Lemmas 4.7, 4.10, 4.11 and 4.12 and the fact that lim inf_{k→∞} Δk ; N̄ = 0 and lim_{k→∞} f(x^{k}) = f(x^{∗}), it is easy to show the existence of an integer k_{0} ≥ 0 such that the implications (87), (88),

(89) and (90) hold for every k ≥ k_{0} and

Δk_{0} ; N̄ ≤ ϵ_{1}, Ψk_{0} ; B̄ ≤ ϵ_{2}, f(x^{k_{0}}) − f(x^{∗}) ≤ ϵ_{3},  (94)

where we use (90) to obtain the second relation. We will prove by induction on k that

Δk ; N̄ ≤ ϵ_{1}, Ψk ; B̄ ≤ ϵ_{2},  (95)

for all k ≥ k_{0}, thereby proving our claim (92). In view of the first two inequalities in (94), k_{0} satisfies (95). Assume that the index k satisfies (95). Since Δk ; N̄ ≤ ϵ_{1} ≤ min{δ_{0}, δ_{1}, δ_{2}} and the implications (87), (88), (89) and (90) hold, we conclude that

α_{1}Ψk ; B̄ ≤ Δk ; N̄ ≤ α_{2}Ψk ; B̄,  (96)

and that either

Δk ; N̄ ≤ M_{1}(f(x^{k}) − f(x^{∗}))^{1/2}  (97)

holds, or the inequality

Ψk+1 ; B̄ ≤ γ̄Ψk ; B̄  (98)

holds, where γ̄ ≡ max{γ_{1}, γ_{2}} < 1. Using (5), (96), the second inequality in (95) and (93), we obtain

Δk+1 ; N̄ ≤ \frac{1 + β}{1 − β} Δk ; N̄ ≤ \frac{1 + β}{1 − β} α_{2}Ψk ; B̄ ≤ \frac{1 + β}{1 − β} α_{2}ϵ_{2} = ϵ_{1}.

If inequality (97) holds then, using (5), (96), the last inequality in (94), (93), and the fact that {f(x^{k}) − f(x^{∗})} decreases monotonically, we obtain

Ψk+1 ; B̄ ≤ \frac{1}{1 − β} Ψk ; B̄ ≤ \frac{1}{α_{1}(1 − β)}Δk ; N̄ ≤ \frac{M_{1}}{α_{1}(1 − β)}(f(x^{k}) − f(x^{∗}))^{1/2} ≤ \frac{M_{1}}{α_{1}(1 − β)}ϵ_{3}^{1/2} = ϵ_{2}.

If instead (98) holds then, by the last inequality of (95) and the fact that γ̄ < 1, we obtain Ψk+1 ; B̄ ≤ γ̄Ψk ; B̄ ≤ Ψk ; B̄ ≤ ϵ_{2}. We have thus shown that Δk+1 ; N̄ ≤ ϵ_{1} and Ψk+1 ; B̄ ≤ ϵ_{2}, and hence that (95) holds for every k ≥ k_{0}.

We now show that ∑_{k=0}^{∞} Δk ; N̄ < ∞. Indeed, since, for every k ≥ k_{0}, Δk ; N̄ ≤ min{δ_{0}, δ_{1}, δ_{2}} and the implications (87), (88), (89) and (90) hold, it follows that (96) holds and that either (97) or (98) holds, for every k ≥ k_{0}. Since (96) holds for every k ≥ k_{0}, it is sufficient to show that ∑_{k=0}^{∞} Ψk ; B̄ < ∞. Let K denote those indices k ≥ k_{0} for which (97) holds. If K is finite then we have ∑_{k=0}^{∞} Ψk ; B̄ < ∞ since (98) holds for every k sufficiently large. So assume that K is infinite and, without loss of generality, that k_{0} ∈ K. Note that if k′ < k′′ are two consecutive indices in K then

∑_{k=k′+1}^{k′′} Ψk ; B̄ ≤ \frac{1}{1 − γ̄} Ψk′+1 ; B̄,

since (98) holds for every k = k′ + 1, …, k′′ − 1. Using this observation, (5), (96), the fact that (97) holds for every k ∈ K and Lemma 2.4(b), we obtain

∑_{k=k_{0}+1}^{∞} Ψk ; B̄ ≤ \frac{1}{1 − γ̄} ∑_{k∈K} Ψk+1 ; B̄ ≤ \frac{1}{(1 − β)(1 − γ̄)} ∑_{k∈K} Ψk ; B̄
≤ \frac{1}{α_{1}(1 − β)(1 − γ̄)} ∑_{k∈K} Δk ; N̄ ≤ \frac{M_{1}}{α_{1}(1 − β)(1 − γ̄)} ∑_{k∈K}(f(x^{k}) − f(x^{∗}))^{1/2}

≤ \frac{M_{1}}{α_{1}(1 − β)(1 − γ̄)} ∑_{k=0}^{∞}(f(x^{k}) − f(x^{∗}))^{1/2} < ∞.

We have thus proved that ∑_{k=0}^{∞} Ψk ; B̄ < ∞, and hence that ∑_{k=0}^{∞} Δk ; N̄ < ∞.

The following lemma is the last step towards the main result of this paper.

Lemma 4.14 Assume that N̄ is a minimal element of Γ and let B̄ = {1, …, n}\N̄. Then the following statements hold:

(a) For every i ∈ N̄, there holds

x_{i}^{k} ∼ ∥xk ; N̄∥ ∼ ∥X^{k}s^{k}∥ ∼ ∥Xk ; N̄sk ; N̄∥ ∼ f(x^{k}) − f(x^{∗}) ∼ f(x^{k}) − f(x^{k+1});

(b) lim_{k→∞} ∥Xk ; N̄(s^{k} − s̃^{k})N̄∥/∥xk ; N̄∥ = 0;

(c) lim inf_{k→∞}(g^{∗})^{T} (x^{k} − x^{k+1})/∥xk ; N̄∥ > 0.

Proof. Due to relation (12), Lemma 4.7, Theorem 4.13 and Theorem 4.4(a), we conclude that for every i ∈ N̄ and k sufficiently large,

x_{i}^{k} ≤ ∥xk ; N̄∥ ≤ \frac{∥Xk ; N̄sk ; N̄∥}{η_{0}} ≤ \frac{∥X^{k}s^{k}∥}{η_{0}} ≤ \frac{f(x^{k}) − f(x^{k+1})}{βη_{0}}
≤ \frac{f(x^{k}) − f(x^{∗})}{βη_{0}} = O(x_{i}^{k}),

which clearly implies statement (a). To prove (b), note that by (7) and (18), we have

X^{k}(s^{k} − s̃^{k}) = P (x^{k})X^{k}(g^{k+1} − g^{∗}) = P (x^{k})X^{k}(s^{k} − s_{∗}^{k}),

where {s_{∗}^{k}} is the sequence introduced in Lemma 4.8. Using Lemma 3.1, we obtain

X^{k}(s^{k} − s̃^{k}) = ( \begin{matrix}P̃B̄(xk ; B̄)Xk ; B̄(s^{k} − s_{∗}^{k})B̄ \\ P̃N̄(xk ; N̄)Xk ; N̄(s^{k} − s_{∗}^{k})N̄ \end{matrix} ) + R(x^{k})[X^{k}(s^{k} − s_{∗}^{k})]

where ∥R(x^{k})∥ = O(Δk ; N̄). This relation together with (63), (64) and statement (a) imply

\frac{∥Xk ; N̄(s^{k} − s̃^{k})N̄∥}{∥xk ; N̄∥} ≤ \frac{∥P̃N̄(xk ; N̄)Xk ; N̄(s^{k} − s_{∗}^{k})N̄∥}{∥xk ; N̄∥} + ∥R(x^{k})∥\frac{∥X^{k}(s^{k} − s_{∗}^{k})∥}{∥xk ; N̄∥}
≤ ∥(s^{k} − s_{∗}^{k})N̄∥ + O(Δk ; N̄) = O(∥x^{k+1} − x^{k}∥ + Δk ; N̄),

from which (b) follows. We next prove (c). By (a), we have that lim inf_{k→∞} ∥Xk ; N̄sk ; N̄∥/∥xk ; N̄∥ > 0. Hence, by (b), we conclude that

lim inf_{k→∞} ∥Xk ; N̄s̃k ; N̄∥/∥xk ; N̄∥ > 0  (99)

By Lemma 4.6, we have that g∗ ; B̄ ∈ Range(AT ; B̄), or equivalently, that DB̄ ≠ ∅. Let (ȳ, s̄) be an arbitrary element of DB̄. We have,

(g^{∗})^{T} (x^{k} − x^{k+1}) = \frac{β}{∥X^{k}s^{k}∥}(g^{∗})^{T} (X^{k})^{2}s^{k}
= \frac{β}{∥X^{k}s^{k}∥} \{(g^{∗})^{T} (X^{k})^{2}s̃^{k} + (g^{∗})^{T} (X^{k})^{2}(s^{k} − s̃^{k})\}
= \frac{β}{∥X^{k}s^{k}∥} \{∥X^{k}s̃^{k}∥^{2} + s̄^{T} (X^{k})^{2}(s^{k} − s̃^{k})\}
≥ \frac{β}{∥X^{k}s^{k}∥} \{∥Xk ; N̄s̃k ; N̄∥^{2} − ∥Xk ; N̄ s̄N̄∥ ∥Xk ; N̄(s^{k} − s̃^{k})N̄∥\} .

This inequality together with statements (a) and (b) imply that

lim inf_{k→∞} \frac{(g^{∗})^{T} (x^{k} − x^{k+1})}{∥xk ; N̄∥} ≥ β lim inf_{k→∞} \frac{∥Xk ; N̄s̃k ; N̄∥^{2}}{∥X^{k}s^{k}∥ ∥xk ; N̄∥},

which in view of (a) and (99) imply (c).

We are now in a position to state the main result of this paper. Its content is very similar to the one in Theorem 3.6. The main difference lies in the fact that Theorem 4.15 establishes the existence of a (unique) partition (B̄, N̄) satisfying the Local Assumption 3.2 while Theorem 3.6 assumes its existence.

Theorem 4.15 Assume that N̄ is a minimal element of Γ and let B̄ = {1, …, n}\N̄. Then the limit point x^{∗} of the sequence {x^{k}} generated by Algorithm AS is an optimal solution of problem (1) and the associated sequence of dual estimates {(y^{k}, s^{k})} converges to the optimal solution (y^{∗}, s^{∗}) of the dual problem (2) that solves the problem

maximize ∑_{i∈N̄} log s_{i}
subject to A^{T} y + s = g^{∗},
sB̄ = 0, sN̄ > 0.

(100)

In particular, it follows that Γ has a unique minimal element, or equivalently, N̄ is the smallest element of Γ (with respect to inclusion).

Proof. The result follows as an immediate consequence of Theorem 3.6 once we verify that the partition (B̄, N̄) satisfies Local Assumption 3.2. That (B̄, N̄) satisfies conditions (A) and (D) of Local Assumption 3.2 follows as a consequence of Theorem 4.13 and Lemma 4.5. We now show that (B̄, N̄) satisfies condition (B). Indeed, by Lemma 4.14(c), there exists k_{0} ≥ 0 such that (g^{∗})^{T} (x^{k} − x^{k+1}) > 0 for all k ≥ k_{0}. This observation and the fact that (g^{∗})^{T} (x^{k} − x^{∗}) = ∑_{l=k}^{∞}(g^{∗})^{T} (x^{l} − x^{l+1}) imply that (g^{∗})^{T} (x^{k} − x^{∗}) ≥ (g^{∗})^{T} (x^{k} − x^{k+1}) for every k ≥ k_{0}. In view of Lemma 4.14(c), we then conclude that

lim inf_{k→∞} \frac{(g^{∗})^{T} (x^{k} − x^{∗})}{∥xk ; N̄∥} ≥ lim inf_{k→∞} \frac{(g^{∗})^{T} (x^{k} − x^{k+1})}{∥xk ; N̄∥} > 0,  (101)

which shows that (B̄, N̄) satisfies condition (B). We now show that (B̄, N̄) satisfies condition (C). First observe that

u^{k} − ũ^{k} = \frac{X^{k}(s^{k} − s̃^{k})}{(g^{∗})^{T} (x^{k} − x^{∗})} = \frac{P (x^{k})X^{k}(g^{k+1} − g^{∗})}{(g^{∗})^{T} (x^{k} − x^{∗})} = \frac{P (x^{k})X^{k}(s^{k} − s_{∗}^{k})}{(g^{∗})^{T} (x^{k} − x^{∗})},  (102)

where {s_{∗}^{k}} is the sequence introduced in Lemma 4.8. Hence, by (64) and (101), we obtain

lim sup_{k→∞} ∥u^{k} − ũ^{k}∥ ≤ lim sup_{k→∞} \frac{∥X^{k}(s^{k} − s_{∗}^{k})∥}{(g^{∗})^{T} (x^{k} − x^{∗})} ≤ lim sup_{k→∞} \frac{O(∥X^{k}s^{k}∥)}{(g^{∗})^{T} (x^{k} − x^{∗})}
≤ lim sup_{k→∞} \frac{O(∥xk ; N̄∥)}{(g^{∗})^{T} (x^{k} − x^{∗})} < ∞.  (103)

This shows that {u^{k} − ũ^{k}} is bounded. That the condition lim_{k→∞} ∥uk ; N̄ − ũk ; N̄∥ = 0 is satisfied follows as an immediate consequence of the first equality in (102), Lemma 4.14(b), (101).

Consider the following set associated with problem (1) and its dual (2):

S ≡ {(x, y, s) | x ∈ P^{+}, (y, s) ∈ D^{+}(x), x^{T} s = 0}.  (104)

It is well known that (x, y, s) ∈ S if and only if x is an optimal solution of (1) and (x, y, s) is an optimal solution of (2). Define

B_{S} ≡ {j | x_{j} > 0 for some (x, y, s) ∈ S};
N_{S} ≡ {j | s_{j} > 0 for some (x, y, s) ∈ S};
J_{S} ≡ {j | x_{j} = s_{j} = 0 for all (x, y, s) ∈ S} = {1, …, n}\(B_{S} ∪ N_{S}).

It is well known that (B_{S}, N_{S}, J_{S}) forms a partition of {1, …, n} and that there exists (x̄, ȳ, s̄) ∈ S such that x̄_{B_{S}} > 0 and s̄_{N_{S}} > 0.

Theorem 4.16 Let N̄ denote the smallest element of Γ. Then N̄ = N_{S}.

Proof. Observe that the limit point (x^{∗}, y^{∗}, s^{∗}) is an element of S such that s∗ ; N̄ > 0. It follows from the definition of N_{S} that N̄ ⊆ N_{S}. To prove the reverse inclusion, let (x̄, ȳ, s̄) be an element of S such that x̄_{B_{S}} > 0 and s̄_{N_{S}} > 0. Then, we have

f(x^{k}) − f(x^{∗}) = f(x^{k}) − f(x̄) ≥ ∇f(x̄)^{T} (x^{k} − x̄) = s̄^{T} (x^{k} − x̄) = s̄_{N_{S}}^{T}x_{N_{S}}^{k} ≥ s̄_{j}x_{j}^{k},

and hence, x_{j}^{k} = O(f(x^{k})−f(x^{∗})) for every j ∈ N_{S}. It follows from Lemma 4.14(a) that x_{i}^{k} ∼ x_{j}^{k} for every i, j ∈ N_{S}. Since N̄ ∈ Γ, we have lim inf_{k→∞} Δk ; N̄ = 0 and, in view of the previous observation, this can only happens if N̄ = N_{S}.

Concluding Discussion

In this paper, we have established the global convergence of the affine scaling algorithm for convex QP without assuming any nondegeneracy assumption. We conclude the paper by pointing out a few problems which can be topics for future research.

The first problem is to remove the assumption that the set of optimal solutions of (1) is bounded. The only part we use this assumption in this paper is to show the convergence of the sequence {x^{k}}, where we use a result of Jie Sun [17]. The second problem is to establish that B_{S} = B̄. This fact would imply that when the QP problem (1) has a pair of primal and dual solutions satisfying strictly complementarity (that is, J_{S} = ∅) then the limit points x^{∗} and (y^{∗}, s^{∗}) of Theorem 4.15 would satisfy the strictly complementarity condition that x^{∗}+s^{∗} > 0. This would generalize a result obtained by Dikin [7] (see also Vanderbei and Lagarias [25]) for primal nondegenerate LP problems and by Tsuchiya and Muramatsu [24] for degenerate LP problems which establishes that the limit points x^{∗} and (y^{∗}, s^{∗}) of Theorem 4.15 always satisfy the strictly complementarity condition. The last problem would be to show convergence of Algorithm AS for any value of β ∈ (0, 1]. Towards this end, a result established by Dikin [5] could be useful. For a homogeneous LP problem having 0 as the unique optimal solution, Dikin shows that each step of the affine scaling algorithm with β = 1 reduces the value of the potential function by a fixed constant.

Appendix A

In this appendix we establish some technical results that are used in the paper.

Lemma A.1: If α_{1} and α_{2} are positive scalars then

| log α_{1} − log α_{2} | ≤ \frac{1}{min\{α_{1}, α_{2}\}}|α_{1} − α_{2}|

Lemma A.2: Let an integer q ≥ 2 be given. If v ∈ IR^{q} is such that e^{T} v = 0 then

χ(v) ≥ \frac{∥v∥}{\sqrt{q(q − 1)}} ≥ \frac{∥v∥}{q}.

Proof. If v = 0 then the result obviously hold. Assume then that v ≠ 0 and let I = {i | v_{i} > 0}. Since e^{T} v = 0 and v ≠ 0, it follows that 1 ≤ |I| ≤ q − 1. Using the fact that e^{T} v = 0, we obtain

χ(v)^{2} = \frac{1}{|I|} ∑_{i∈I} v_{i}^{2} = \frac{∥v∥^{2} − ∑_{i∉I} v_{i}^{2}}{|I|} ≥ \frac{∥v∥^{2} − (∑_{i∉I} |v_{i}|)^{2}}{|I|}

= \frac{∥v∥^{2} − (∑_{i∈I} v_{i})^{2}}{|I|} ≤ \frac{∥v∥^{2} − |I|^{2}χ(v)^{2}}{|I|}

Rearranging the above inequality, we obtain

χ(v) ≥ \frac{∥v∥}{\sqrt{|I|(|I| + 1)}} ≥ \frac{∥v∥}{\sqrt{q(q − 1)}}

where the last inequality is due to the fact that |I| ≤ q − 1.

The proof of the following result can be found in Tsuchiya and Muramatsu [24], Lemma 5.1 (Lemma 3.1 in the revised version). Lemma A.3: For every (w, ρ) ∈ Ω, where

Ω = {(w, ρ) ∈ IR^{q} × IR | e^{T} w = 1, ρ∥w∥^{2} < 1 and ρw_{i} < 1, ∀i = 1, …, q},

there holds

q log(1 − ρ∥w∥^{2}) − ∑_{i=1}^{q} log(1 − ρw_{i}) ≤ \frac{qρ}{q − ρ} ∥w − \frac{1}{q}e∥^{2} (−q + \frac{ρ}{2\{1 − ρχ[w]\}}) .

Proposition A.4: Assume that the sequences {ũ^{k}} ⊂ IR^{n} and {λ_{k}} ⊂ IR and the partition (B, N) of {1, …, n} satisfy:

(a) there exists δ ∈ (0, 1) such that 1 − λ_{k}∥ũ^{k}∥^{2}/χ(ũ^{k}) ≥ δ for all k ≥ 0;

(b) e^{T} ũ_{N}^{k} − 1 → 0 as k → ∞;

(c) ∥ũ_{B}^{k}∥ → 0 as k → ∞;

(d) {ũ^{k}} is bounded;

(e) for every integer k sufficiently large,

\frac{λ_{k}}{2(1 − λ_{k})} ≤ 1 + η_{k}, where η_{k} ≡ ∥\frac{ũ_{N}^{k}}{e^{T} ũ_{N}^{k}} − \frac{1}{|N|}e∥ .

Define

ϕ(ũ^{k}, λ_{k}) ≡ |N| log (1 − \frac{λ_{k}}{χ(ũ^{k})}∥ũ^{k}∥^{2}) − ∑_{i∈N} log (1 − \frac{λ_{k}}{χ(ũ^{k})}ũ_{i}^{k})

Then, there exists τ > 0 such that, for every k ≥ 0, ϕ(ũ^{k}, λ_{k}) is well-defined and

ϕ(ũ^{k}, λ_{k}) ≤ −τλ_{k}η_{k}^{2} [1 − \frac{λ_{k}}{2(1 − λ_{k})}(1 + η_{k})^{−1}] + O (|e^{T} ũ_{N}^{k} − 1| + ∥ũ_{B}^{k}∥^{2}) .  (105)

Proof. Using (b), (d) and the definition of {η_{k}}, it is easy to see that {η_{k}} is bounded. Due to (e), this implies that there exists δ′ ∈ (0, 1) such that

λ_{k} ≤ 1 − δ′, ∀k ≥ 0. (106)

Well-definedness of ϕ(ũ^{k}, λ_{k}) follows from (a) and the fact that

1 − \frac{λ_{k}}{χ(ũ^{k})}ũ_{i}^{k} ≥ 1 − λ_{k} ≥ δ′, ∀k ≥ 0.

Using conditions (b) and (c), it is easy to see that χ(ũ^{k}) = χ(ũ_{N}^{k}) for every k sufficiently large. Let w_{N}^{k} = ũ_{N}^{k}/e^{T} ũ_{N}^{k} for every k ≥ 0. Since e^{T} w_{N}^{k} = 1, we have χ(w_{N}^{k}) ≥ 1/|N| for every k. In view of (b) and the above observations, we obtain

lim inf χ(ũ^{k}) = lim inf χ(ũ_{N}^{k}) = lim inf χ(w_{N}^{k}) ≥ 1/|N|.  (107)

Using the fact that χ(ũ^{k}) = χ(ũ_{N}^{k}) and the definition of w_{N}^{k}, we obtain

\frac{λ_{k}}{χ(w_{N}^{k})}w_{j}^{k} = \frac{λ_{k}}{χ(ũ^{k})}ũ_{j}^{k},  ∀j ∈ N  (108)

and

\frac{λ_{k}}{χ(w_{N}^{k})}∥w_{N}^{k}∥^{2} − \frac{λ_{k}}{χ(ũ^{k})}∥ũ^{k}∥^{2} = \frac{λ_{k}∥ũ_{N}^{k}∥^{2}}{χ(ũ^{k})(e^{T} ũ_{N}^{k})} − \frac{λ_{k}}{χ(ũ^{k})}(∥ũ_{N}^{k}∥^{2} + ∥ũ_{B}^{k}∥^{2})
= \frac{1 − e^{T} ũ_{N}^{k}}{e^{T} ũ_{N}^{k}} \frac{λ_{k}∥ũ_{N}^{k}∥^{2}}{χ(ũ^{k})(e^{T} ũ_{N}^{k})} − \frac{λ_{k}}{χ(ũ^{k})}∥ũ_{B}^{k}∥^{2}
= O(|e^{T} ũ_{N}^{k} − 1| + ∥ũ_{B}^{k}∥^{2}).  (109)

where the last equality follows from (b), (d), (106) and (107). Now, using (108), (109), Lemma A.1, Lemma A.3 and (a), we obtain

ϕ(ũ^{k}, λ_{k}) = |N| log (1 − \frac{λ_{k}}{χ(w_{N}^{k})}∥w_{N}^{k}∥^{2}) − ∑_{i∈N} log (1 − \frac{λ_{k}}{χ(w_{N}^{k})}w_{i}^{k})

+ |N| [log (1 − \frac{λ_{k}}{χ(ũ^{k})}∥ũ^{k}∥^{2}) − log (1 − \frac{λ_{k}}{χ(w_{N}^{k})}∥w_{N}^{k}∥^{2})]

≤ −\frac{|N| (λ_{k}/χ(w_{N}^{k}))}{|N| − (λ_{k}/χ(w_{N}^{k}))} η_{k}^{2} (|N| − \frac{λ_{k}}{2(1 − λ_{k})}χ(w_{N}^{k})^{−1})
+ O (|e^{T} ũ_{N}^{k} − 1| + ∥ũ_{B}^{k}∥^{2}) .  (110)

We now estimate the first term in the right hand side of (110). Using Lemma A.2 with v = w_{N}^{k} − (1/|N|)e, it is easy to verify that χ(w_{N}^{k}) ≥ (1 + η_{k})/|N|. Hence,

|N| − \frac{λ_{k}}{2(1 − λ_{k})}χ(w_{N}^{k})^{−1} ≥ |N| (1 − \frac{λ_{k}}{2(1 − λ_{k})}(1 + η_{k})^{−1}) ≥ 0,  (111)

where the last inequality follows from (e). Also, since χ(w_{N}^{k}) ≤ ∥w_{N}^{k}∥ and {w_{N}^{k}} is bounded, it follows that χ(w_{N}^{k})^{−1} ≥ ϵ, for some constant ϵ > 0. Hence,

\frac{|N| (λ_{k}/χ(w_{N}^{k}))}{|N| − (λ_{k}/χ(w_{N}^{k}))} ≥ \frac{λ_{k}}{χ(w_{N}^{k})} ≥ λ_{k}ϵ > 0.  (112)

Combining (110), (111) and (112) and defining τ ≡ ϵ|N|, we obtain (105).

Appendix B

The objective of this section is to provide a proof of Lemma 3.1. Lemma B.1: Let h ∈ IR^{n} and a partition (B, N) of {1, …, n} be given and define p(x) = P (x)h, p̃_{B}(x_{B}) = P̃_{B}(x_{B})h_{B} and p̃_{N}(x_{N}) = P̃_{N}(x_{N})h_{N}. Then, the following statements hold:

(a) The vector δ_{B}(x) = p_{B}(x) − p̃_{B}(x_{B}) is the unique optimal solution of the problem

minimize_{δ_{B}}  \frac{1}{2}∥δ_{B}∥^{2}
subject to A_{B}X_{B}δ_{B} = −A_{N}X_{N}p_{N}(x);

(113)

(b) The pair (p_{B}(x), δ_{N}(x)), where δ_{N}(x) ≡ p_{N}(x) − p̃(x_{N}), is the unique optimal solution of the

problem

minimize_{(p_{B},δ_{N})} \frac{1}{2}∥p_{B}∥^{2} + \frac{1}{2}∥δ_{N}∥^{2} − h_{B}^{T}p_{B}
subject to  A_{B}X_{B}p_{B} + A_{N}X_{N}δ_{N} = −A_{N}X_{N} p̃_{N}(x_{N}); (114)

Proof. We first show (a). Since p(x) is the optimal solution of (13), we know that

p(x) − h ∈ Range(XA^{T}), AXp(x) = 0. (115)

Since p̃_{B}(x_{B}) is the optimal solution of (15), we have

p̃_{B}(x_{B}) − h_{B} ∈ Range(X_{B}A_{B}^{T}), A_{B}X_{B}p̃_{B}(x_{B}) = 0. (116)

From (115) and (116), it follows that

p_{B}(x) − p̃_{B}(x_{B}) ∈ Range(X_{B}A_{B}^{T}), A_{B}X_{B}[p_{B}(x) − p̃_{B}(x_{B})] = −A_{N}X_{N}p_{N}(x), and this shows that δ_{B}(x) = p_{B}(x) − p̃_{B}(x_{B}) satisfies the optimality conditions for (113). Hence,

(a) follows. We next show (b). Since p̃_{N}(x_{N}) is the optimal solution of (14), we conclude

( \begin{matrix}0 \\ p̃_{N}(x_{N}) − h_{N} \end{matrix} ) ∈ Range(XA^{T}),  A_{N}X_{N} p̃_{N}(x_{N}) ∈ Range(A_{B}).  (117)

Hence, it follows from (115) and (117) that

( \begin{matrix}p_{B}(x) − h_{B} \\ δ_{N}(x) \end{matrix} ) ∈ Range(XA^{T}),  A_{B}X_{B}p_{B}(x) + A_{N}X_{N}δ_{N}(x) = −A_{N}X_{N} p̃_{N}(x_{N}), (118)

which shows that (p_{B}(x), δ_{N}(x)) satisfies the optimality conditions for (114). Lemma B.2: There exists a constant K_{0} > 0 such that

∥δ_{B}(x)∥ ≤ K_{0}Δ_{N}(x)∥p_{N}(x)∥,  ∀x ∈ P^{++}.  (119)

Proof. By (115), we know that A_{N}X_{N}p_{N}(x) ∈ Range(A_{B}). Hence, Lemma 4.1 implies the existence of a constant K_{0} > 0 with the property that for every x ∈ P^{++} there exists a vector u_{B}(x) satisfying

A_{B}u_{B}(x) = −A_{N}X_{N}p_{N}(x), ∥u_{B}(x)∥ ≤ K_{0}∥X_{N}p_{N}(x)∥.

Thus, X_{B}^{−1}u_{B}(x) is a feasible solution for (113). In view of Lemma B.1(a), this implies that for every x ∈ P^{++},

∥δ_{B}(x)∥ ≤ ∥X_{B}^{−1}u_{B}(x)∥ ≤ ∥x_{B}^{−1}∥∥u_{B}(x)∥ ≤ K_{0}∥x_{B}^{−1}∥∥X_{N}p_{N}(x)∥ ≤ K_{0}Δ_{N}(x)∥p_{N}(x)∥.

Lemma B.3: There exist constants K_{1} > 0 and K_{2} > 0 with the property that, for every x ∈ P^{++} with Δ_{N}(x) ≡ ∥x_{B}^{−1}∥ ∥x_{N}∥ sufficiently small, there hold

∥δ_{N}(x)∥ ≤ K_{1} [Δ_{N}(x)^{2}∥h_{N}∥ + Δ_{N}(x)∥h_{B}∥]  (120)

and

∥δ_{B}(x)∥ ≤ K_{2} [Δ_{N}(x)^{2}∥h_{B}∥ + Δ_{N}(x)∥h_{N}∥] .  (121)

Proof. We first prove that (120) holds. From (117) and (118), we have that A_{N}X_{N}δ_{N}(x) ∈ Range(A_{B}). By Lemma 4.1, there exists a constant K_{0} > 0 (same as in Lemma B.2) such that, for every x ∈ P^{++}, there exists a vector v_{B}(x) satisfying

A_{B}v_{B}(x) = −A_{N}X_{N}δ_{N}(x),  ∥v_{B}(x)∥ ≤ K_{0}∥X_{N}δ_{N}(x)∥ ≤ K_{0}∥x_{N}∥ ∥δ_{N}(x)∥.  (122)

Relation (118) and (122) imply that A_{B}[X_{B}p_{B}(x) − v_{B}(x)] = −A_{N}X_{N} p̃_{N}(x_{N}), and hence that the pair (p_{B}(x) − X_{B}^{−1}v_{B}(x), 0) is feasible for (114). This together with Lemma B.1(b) imply that

\frac{1}{2}∥p_{B}(x)∥^{2} + \frac{1}{2}∥δ_{N}(x)∥^{2} − h_{B}^{T}p_{B}(x) ≤ \frac{1}{2}∥p_{B}(x) − X_{B}^{−1}v_{B}(x)∥^{2} − h_{B}^{T}[p_{B}(x) − X_{B}^{−1}v_{B}(x)].

Rearranging this last expression and using relation (122) and the fact that ∥u∥^{2} − ∥v∥^{2} ≤ ∥u − v∥ ∥u + v∥ for any two vectors u and v, we obtain

\frac{1}{2}∥δ_{N}(x)∥^{2} ≤ \frac{1}{2} \{∥p_{B}(x) − X_{B}^{−1}v_{B}(x)∥^{2} − ∥p_{B}(x)∥^{2}\} + h_{B}^{T}[X_{B}^{−1}v_{B}(x)]
≤ \frac{1}{2}∥2p_{B}(x) − X_{B}^{−1}v_{B}(x)∥ ∥X_{B}^{−1}v_{B}(x)∥ + ∥h_{B}∥ ∥X_{B}^{−1}v_{B}(x)∥
≤ ∥x_{B}^{−1}∥ ∥v_{B}(x)∥ \{\frac{1}{2}∥2p_{B}(x) − X_{B}^{−1}v_{B}(x)∥ + ∥h_{B}∥\}
≤ K_{0} Δ_{N}(x)∥δ_{N}(x)∥ \{∥p_{B}(x)∥ + \frac{1}{2}∥x_{B}^{−1}∥ ∥v_{B}(x)∥ + ∥h_{B}∥\} ,

from which it follows that

∥δ_{N}(x)∥ ≤ 2K_{0} Δ_{N}(x) \{∥p_{B}(x)∥ + \frac{1}{2}∥x_{B}^{−1}∥ ∥v_{B}(x)∥ + ∥h_{B}∥\} .

We now bound the term within the parentheses in the last expression. Using (122), Lemma B.2 and the fact that ∥p̃_{B}(x_{B})∥ ≤ ∥h_{B}∥ and ∥p̃_{N}(x_{N})∥ ≤ ∥h_{N}∥, we obtain

∥p_{B}(x)∥ + \frac{1}{2}∥x_{B}^{−1}∥ ∥v_{B}(x)∥ + ∥h_{B}∥

≤ ∥δ_{B}(x)∥ + ∥p̃_{B}(x_{B})∥ + \frac{1}{2}K_{0} ∥x_{B}^{−1}∥∥X_{N}∥∥δ_{N}(x)∥ + ∥h_{B}∥
≤ K_{0} Δ_{N}(x)∥p_{N}(x)∥ + \frac{1}{2}K_{0} Δ_{N}(x)∥δ_{N}(x)∥ + 2∥h_{B}∥
≤ K_{0} Δ_{N}(x) [∥p_{N}(x)∥ + \frac{1}{2}∥δ_{N}(x)∥] + 2∥h_{B}∥
≤ K_{0} Δ_{N}(x) [∥p̃_{N}(x)∥ + \frac{3}{2}∥δ_{N}(x)∥] + 2∥h_{B}∥
≤ K_{0} Δ_{N}(x) [∥h_{N}∥ + \frac{3}{2}∥δ_{N}(x)∥] + 2∥h_{B}∥

Combining the last two inequalities and rearranging, we have

∥δ_{N}(x)∥ ≤ \frac{1}{1 − 3K_{0}^{2}Δ_{N}(x)^{2}} [2K_{0}^{2}Δ_{N}(x)^{2}∥h_{N}∥ + 4K_{0} Δ_{N}(x)∥h_{B}∥]
≤ K_{1} [Δ_{N}(x)^{2}∥h_{N}∥ + Δ_{N}(x)∥h_{B}∥] ,

for every x ∈ P^{++} such that Δ_{N}(x) ≤ 1/\sqrt{6K_{0}}, where K_{1} ≡ 4 max\{K_{0}^{2}, 2K_{0}\}. We next show that (121) holds. Using Lemma B.2 and the fact that ∥p̃_{N}(x_{N})∥ ≤ ∥h_{N}∥, we obtain

∥δ_{B}(x)∥ ≤ K_{0}Δ_{N}(x)∥p_{N}(x)∥
≤ K_{0}Δ_{N}(x) [ ∥p̃_{N}(x_{N})∥ + ∥δ_{N}(x)∥]
≤ K_{0}Δ_{N}(x) [∥h_{N}∥ + K_{1}Δ_{N}(x)^{2}∥h_{N}∥ + K_{1}Δ_{N}(x)∥h_{B}∥]
≤ K_{2} [Δ_{N}(x)^{2}∥h_{B}∥ + Δ_{N}(x)∥h_{N}∥] ,

for every x ∈ P^{++} such that Δ_{N}(x) ≤ 1/\sqrt{K_{1}}, where K_{2} ≡ max\{2K_{0}, K_{0}K_{1}\}.

We are now ready to give the proof of Lemma 3.1.

Proof of Lemma 3.1: To show (a), let x ∈ P^{++} be given. The symmetry of the matrix R(x) follows trivially from the fact that P (x), P̃_{B}(x_{B}) and P̃_{N}(x_{N}) are symmetric matrices. From (117) and (118), we have that A_{N}X_{N}δ_{N}(x) ∈ Range(A_{B}). Hence, it follows from (14) that P̃_{N}(x_{N})δ_{N}(x) = δ_{N}(x), or equivalently,

P̃_{N}(x_{N})R_{NB}(x)h_{B} + P̃_{N}(x_{N})R_{NN}(x)h_{N} = R_{NB}(x)h_{B} + R_{NN}(x)h_{N}.

Since the last relation holds for every vector h = (h_{B}, h_{N}), we conclude that P̃_{N}(x_{N})R_{NB}(x) = R_{NB}(x) and P̃_{N}(x_{N})R_{NN}(x) = R_{NN}(x). This shows the first relation in (17). Using the fact that P̃_{N}(x_{N})R_{NN}(x) = R_{NN}(x) and the fact that R_{NN}(x) and P̃_{N}(x_{N}) are symmetric matrices, we obtain

P̃_{N}(x_{N})R_{NN}(x)P̃_{N}(x_{N}) = R_{NN}(x)P̃_{N}(x_{N}) = (P̃_{N}(x_{N})R_{NN}(x))^{T} = R_{NN}(x)^{T} = R_{NN}(x),

which shows the second relation in (17). We now show (b). Relation (120) implies that

∥δ_{B}(x)∥ = ∥R_{BB}(x)h_{B} + R_{BN}(x)h_{N}∥ ≤ K_{1}(Δ_{N}(x)^{2}∥h_{B}∥ + Δ_{N}(x)∥h_{N}∥),

for every x ∈ P^{++} with Δ_{N}(x) sufficiently small. Since this relation holds for every h = (h_{B}, h_{N}), we conclude that ∥R_{BB}(x)∥ ≤ K_{1}Δ_{N}(x)^{2} and ∥R_{BN}(x)∥ ≤ K_{1}Δ_{N}(x), for every x ∈ P^{++} with Δ_{N}(x) sufficiently small. Similarly, using (121), it is easy to see that ∥R_{NN}(x)∥ ≤ K_{2}Δ_{N}(x)^{2}, for every x ∈ P^{++} with Δ_{N}(x) sufficiently small. Hence (b) follows if we let K_{0} ≡ max{K_{1}, K_{2}}.

References

[1] I. Adler and R. D. C. Monteiro, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Mathematical Programming, 50 (1991), pp. 29–51.

[2] E. R. Barnes, A variation on Karmarkar’s algorithm for solving linear programming problems, Mathematical Programming, 36 (1986), pp. 174–182.

[3] D. A. Bayer and J. C. Lagarias, The nonlinear geometry of linear programming, Part I : Affine and projective scaling trajectories, Transactions of the American Mathematical Society, 314 (1989), pp. 499–526.

[4] J. F. Bonnans and M. Bouhtou, The trust region affine scaling interior point algorithm for convex and nonconvex quadratic programming, manuscript, INRIA, B.P. 105, 78153, Rocquencourt, France, July 1993.

[5] I. I. Dikin, Convergence of a sequence of dual variables at solution of a completely degenerate problem of linear programming. Talk given at the 15th International Symposium on Mathematical Programming, An Arbor, Michigan, USA, August 15–19, 1994.

[6] , Iterative solution of problems of linear and quadratic programming, Doklady Akademii Nauk SSSR, 174 (1967), pp. 747–748. Translated in : Soviet Mathematics Doklady, 8:674–675, 1967.

[7] , On the convergence of an iterative process, Upravlyaemye Sistemi, 12 (1974), pp. 54–60. (In Russian).

[8] , The convergence of dual variables, Technical Report, Siberian Energy Institute, Irkutsk, Russia, December 1991.

[9] I. I. Dikin and V. I. Zorkaltsev, Iterative solutions of mathematical programming problems, Nauka, Novosibirsk, 1980.

[10] C. C. Gonzaga, Convergence of the large step primal affine–scaling algorithm for primal nondegenerate linear programs, Technical Report ES–230/90, Dept. of Systems Engineering and Computer Science, COPPE Federal University of Rio de Janeiro, 21941 Rio de Janeiro, RJ, Brazil, September 1990.

[11] C. C. Gonzaga and L. A. Carlos, A primal affine–scaling algorithm for linearly constrained convex programs, Technical Report ES–238/90, Dept. of Systems Engineering and Computer Science, COPPE Federal University of Rio de Janeiro, 21941 Rio de Janeiro, RJ, Brazil, December 1990.

[12] N. K. Karmarkar, A new polynomial–time algorithm for linear programming, Combinatorica, 4 (1984), pp. 373–395.

[13] N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, Mathematics of Operations Research, 14 (1989), pp. 97–114.

[14] R. D. C. Monteiro, Convergence and boundary behavior of the projective scaling trajectories for linear programming, Mathematics of Operations Research, 16 (1991), pp. 842–858.

[15] R. D. C. Monteiro, T. Tsuchiya, and Y. Wang, A simplified global convergence proof of the affine scaling algorithm, Annals of Operations Research, 47 (1993), pp. 443–482.

[16] R. Saigal, A simple proof of primal affine scaling method, Technical Report, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan, USA, December 1992.

[17] J. Sun, A convergence proof for an affine-scaling algorithm for convex quadratic programming without nondegeneracy assumptions, Mathematical Programming, 60 (1993), pp. 69–79.

[18] P. Tseng and Z. Q. Luo, On the convergence of the affine–scaling algorithm, Mathematical Programming, 56 (1992), pp. 301–319.

[19] T. Tsuchiya, Global convergence of the affine scaling algorithm for degenerate strictly convex quadratic programming problems. Talk presented at TIMS/ORSA Joint Nationtal Meeting, Chicago, Illinois, May, 1993.

[20] , Global convergence of the affine–scaling methods for degenerate linear programming problems, Mathematical Programming, 52 (1991), pp. 377–404.

[21] , Global convergence property of the affine scaling method for primal degenerate linear programming problems, Mathematics of Operations Research, 17 (1992), pp. 527–557.

[22] , Global convergence of the affine scaling algorithm for primal degenerate strictly convex quadratic programming problems, Annals of Operations Research, 47 (1993), pp. 509–539.

[23] T. Tsuchiya and R. D. C. Monteiro, Superlinear convergence of the affine scaling algorithm, Technical Report, Dept. of Systems and Industrial Engineering, University of Arizona, Tucson, AZ 85721, USA, November 1992. Conditionally accepted for publication in Mathematical Programming.

[24] T. Tsuchiya and M. Muramatsu, Global convergence of a long–step affine scaling algorithm for degenerate linear programming problems, Research Memorandum 423, The Institute of Statistical Mathematics, 4–6–7 Minami–Azabu, Minato–ku, Tokyo 106, Japan, January 1992 (revised, September, 1992). (To appear in SIAM Journal on Optimization, Vol. 5, 1995).

[25] R. J. Vanderbei and J. C. Lagarias, I. I. Dikin’s convergence result for the affine–scaling algorithm, in Mathematical Developments Arising from Linear Programming: Proceedings of a Joint Summer Research Conference held at Bowdoin College, Brunswick, Maine, USA, June/July 1988, J. C. Lagarias and M. J. Todd, eds., vol. 114 of Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, USA, 1990, pp. 109–119.

[26] R. J. Vanderbei, M. S. Meketon, and B. A. Freedman, A modification of Karmarkar’s linear programming algorithm, Algorithmica, 1 (1986), pp. 395–407.

[27] C. Witzgall, P. T. Boggs, and P. D. Domich, On the convergence behavior of trajectories for linear programming, in Mathematical Developments Arising from Linear Programming: Proceedings of a Joint Summer Research Conference held at Bowdoin College, Brunswick, Maine, USA, June/July 1988, J. C. Lagarias and M. J. Todd, eds., vol. 114 of Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, USA, 1990, pp. 161– 187.

[28] Y. Ye, An extension of karmarkar’s projective algorithm and the trust region method for quadratic programming, in Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddo, ed., Springer, Berlin, 1989, pp. 49–63.

[29] , On an affine scaling algorithm for nonconvex quadratic programming, Mathematical Programming, 52 (1992), pp. 285–300.

[30] Y. Ye and E. Tse, An extension of karmarkar’s projective algorithm for convex quadratic programming, Mathematical Programming, 44 (1989), pp. 157–180.