On the Role of the Objective Function in Barrier Methods^{∗}

Florian Jarre^{†}and Stephen Wright^{‡}

December 7, 1994

PREPRINT MCS-P485-1294, MCS DIVISION, ARGONNE NATIONAL LABORATORY

Abstract

To simplify the analysis of interior-point methods, one commonly formulates the problem so that the objective function is linear, by introducing a single extra variable if necessary. Here we show that a linear objective function makes the Newton direction for a barrier function a useful search direction if the current iterate is sufficiently close to the central path. Hence, there are two advantages to using a linear objective and staying close to the central path. First, the Newton direction (which coincides with the affine scaling direction on the central path) gives a very accurate approximation to the direction to the minimum. Second, a long step along the Newton direction is possible without violating the inequality constraints.

1 Introduction

We consider logarithmic barrier methods applied to the nonlinear programming problem

min f(x)  subject to  c(x) ≥ 0,  (1)

where f : IR^{n} → IR and c : IR^{n} → IR^{m} are smooth (three times continuously differentiable) functions. We are particularly interested in the case of linear f, that is,

f(x) = g^{T} x.  (2)

∗This research was supported by Obermann Fellowships in the Center for Advanced Studies at the University of Iowa and by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.

†Institute of Statistical Mathematics, Tokyo, Japan (Oct. 1994 – March 1995) and Institut für Angewandte Mathematik und Statistik, Universität Würzburg, am Hubland, 97074 Würzburg, Germany jarre@vax.rz.uni-wuerzburg.d400.de

‡Mathematics and Computer Science Division, Argonne National Laboratory, 9700 South Cass Avenue, Argonne, Illinois 60439. wright@mcs.anl.gov

The logarithmic barrier function for (1) is

P (x; μ) = f(x) − μ ∑_{i=1}^{m} ln c_{i}(x).  (3)

We denote by x(μ) a minimizer of P (.; μ) for μ > 0 and assume that x(μ) exists for all sufficiently small μ. Methods based on (3) approximate x(μ) for a sequence of small, decreasing values of μ > 0. Under certain conditions (see Fiacco and McCormick [1]), we have lim_{μ↓0} x(μ) = x^{∗}. After x(μ) has been approximated for a particular value of μ > 0, an obvious way to proceed is to decrease μ to some new value μ_{+} and then take a Newton step for minimizing the barrier function P (x; μ_{+}). It has recently been observed (see, for example, Wright [3]) that the resulting direction is generally a poor one, and some specialized direction generation and line search strategies have been proposed to remedy the situation. Below, we illustrate the bad behavior of these steps by means of a simple example. Then, in the main part of this article, we show that these difficulties do not arise when the objective function f is linear and the current iterate is close to the central path defined by {x(μ) | μ > 0}.

• Example: Consider the problem

min x_{1} + \frac{1}{2}(x_{2} − 1)^{2}, subject to (x_{1}, x_{2}) ≥ 0,  (4)

for which the solution is obviously x^{∗} = (0, 1)^{T}. Let us assume that the barrier parameter μ is small, and write

P (x; μ) = x_{1} + \frac{1}{2}(x_{2} − 1)^{2} − μ ln x_{1} − μ ln x_{2}.

The derivatives of P (·; μ) are

∇_{x}P (x; μ) = [ \begin{matrix}1 − μ/x_{1} \\ (x_{2} − 1) − μ/x_{2} \end{matrix} ] , ∇_{xx}P (x; μ) = [ \begin{matrix}μ/x_{1}^{2} & 0 \\ 0 & 1 + μ/x_{2}^{2} \end{matrix} ] .

By equating ∇_{x}P (x; μ) to zero, we find that x(μ) ≈ (μ, 1 + μ). Suppose the barrier parameter is decreased to μ_{+} ∈ (0, μ). Then

∇_{x}P (x(μ); μ_{+}) ≈ [ \begin{matrix}(μ − μ_{+})/μ \\ (μ − μ_{+}) \end{matrix} ] , ∇_{xx}P (x; μ_{+}) ≈ [ \begin{matrix}μ_{+}/μ^{2} & 0 \\ 0 & 1 \end{matrix} ] .

The Newton step starting at x(μ) for finding x(μ_{+}) is therefore

p = − [∇_{xx}P (x(μ); μ_{+})]^{−1} ∇_{x}P (x(μ); μ_{+}) ≈ − [ \begin{matrix}(μ/μ_{+})(μ − μ_{+}) \\ (μ − μ_{+}) \end{matrix} ] ,

while the actual difference between the two points is

x(μ_{+}) − x(μ) ≈ − [ \begin{matrix}μ − μ_{+} \\ μ − μ_{+} \end{matrix} ] .

The Newton step provides an excellent estimate of the second component of this difference, but it overestimates the first component by a factor of μ/μ_{+}. If, as is usual, we conduct a line search along the Newton direction p, the line search parameter α can be at most μ_{+}/μ because of the requirement x ≥ 0. This small value of α slows convergence in the second component; the error in this component is decreased only by a factor of about (1 − μ_{+}/μ).

We use the following notation in the rest of the paper. For related positive quantities α and β, we say β = O(α) if there is a constant M such that β ≤ Mα for all α sufficiently small. We say β = o(α) if β/α → 0 as α → 0, and β = Θ(α) if β = O(α) and α = O(β).

2 Assumptions and Basic Facts

Suppose that for some value of μ we have found an approximation to the minimizer x(μ) of P (x; μ). We quantify the inexactness in this approximation by defining a vector w by

w = \frac{1}{μ}∇_{x}P (x; μ),

so that

μw = ∇f(x) − ∑_{i=1}^{m} \frac{μ}{c_{i}(x)}∇c_{i}(x).  (5)

We use the notation x_{w}(μ) to denote the approximate minimizer, to emphasize its relationship to w. We note in passing that x_{w}(μ) is the exact minimizer of the modified log barrier function

P_{w}(x; μ) = f(x) − μ ∑_{i=1}^{m} ln c_{i}(x) − μw^{T} x  (6)

and that x(μ) = x_{0}(μ).

As the next section indicates, our results depend on an assumption that μ∥w∥ is sufficiently small. This implies that x_{w}(μ) is not too far from the central path traced by the exact minimizers of P (x; μ) for μ > 0.

Before proceeding, we define terminology and optimality conditions and specify some additional assumptions. The Lagrangian function for (1) is

L(x, λ) = f(x) − λ^{T} c(x),  (7)

where λ is the vector of Lagrange multipliers. A point x^{∗} satisfies the first-order conditions for optimality if c(x^{∗}) ≥ 0 and there is a vector λ^{∗} ≥ 0 such that (λ^{∗})^{T} c(x^{∗}) = 0 and ∇_{x}L(x^{∗}, λ^{∗}) = 0, that is,

∇f(x^{∗}) = A(x^{∗})λ^{∗},  (8)

where

A(x) = [∇c_{1}(x), ∇c_{2}(x), …, ∇c_{m}(x)]

is the transpose of the Jacobian of c. The active constraints are the components of c for which c_{i}(x^{∗}) = 0. Without loss of generality we assume these to be the first p components of c, and define

Ā(x) = [∇c_{1}(x), ∇c_{2}(x), …, ∇c_{p}(x)],  λ̄ = [λ_{1}, λ_{2}, …, λ_{p}].  (9)

We assume nondegeneracy, that is, Ā(x^{∗}) has full column rank p, and strict complementarity, that is, λ^{∗} + c(x^{∗}) > 0. A consequence of nondegeneracy is that p ≤ n. We assume further that x^{∗} satisfies the second-order sufficient conditions for optimality, namely,

y^{T} ∇_{xx}L(x^{∗}, λ^{∗})y > 0 for all y with Ā(x^{∗})^{T} y = 0, y ≠ 0.  (10)

The derivatives of the barrier function (3) are

∇_{x}P (x; μ) = ∇f(x) − ∑_{i=1}^{m} \frac{μ}{c_{i}(x)}∇c_{i}(x),  (11a)
∇_{xx}P (x; μ) = ∇^{2}f(x) + μ ∑_{i=1}^{m} [\frac{1}{c_{i}^{2}(x)}∇c_{i}(x)∇c_{i}(x)^{T} − \frac{1}{c_{i}(x)}∇^{2}c_{i}(x)] .  (11b)

Given any strictly feasible approximate solution x_{w}(μ), we can define Lagrange multiplier estimates λ_{w}(μ) by

λ_{w}(μ) = μC(x_{w}(μ))^{−1}e = [\frac{μ}{c_{1}(x_{w}(μ))}, …, \frac{μ}{c_{m}(x_{w}(μ))}]^{T} ,  (12)

where C(x) = diag(c(x)). Combining (12) with (5), we have

∇f(x_{w}(μ)) = A(x_{w}(μ))λ_{w}(μ) + μw.  (13)

Naturally, we use the notation λ(μ) for the Lagrange multipliers associated with the exact minimizer x(μ).

Let us return to the case of linear f. Setting (x, λ) = (x_{w}(μ), λ_{w}(μ)) and choosing a new value μ_{+} ∈ (0, μ), we have from (2), (11), and (12) that

∇_{x}P (x; μ_{+}) = g − (μ_{+}/μ)A(x)λ = (1 − μ_{+}/μ)g + μ_{+}w,
∇_{xx}P (x; μ_{+}) = (μ_{+}/μ^{2}) [A(x)Λ^{2}A(x)^{T} − μ ∑_{i=1}^{m} λ_{i}∇^{2}c_{i}(x)] ,

where Λ = diag(λ). For the Newton direction p, we have

p = −∇_{xx}P (x; μ_{+})^{−1}∇_{x}P (x; μ_{+})
= −μ [A(x)Λ^{2}A(x)^{T} − μ ∑_{i=1}^{m} λ_{i}∇^{2}c_{i}(x)]^{−1} [(μ/μ_{+} − 1)g + μw].  (14)

3 Limiting Behavior of the Newton Directions

We now compare the Newton direction (14) with an estimate of the differences between x_{w}(μ), x(μ_{+}), and the solution x^{∗}. Consider the vector function

F (x, λ) = [ \begin{matrix}∇_{x}L(x, λ) \\ Λc(x) \end{matrix} ] = [ \begin{matrix}g − A(x)λ \\ Λc(x) \end{matrix} ] ,  (15)

which maps IR^{n} × IR^{m} to itself, and note that F (x^{∗}, λ^{∗}) = 0. The Jacobian of F is

∇F (x, λ) = [ \begin{matrix}∇_{xx}L(x, λ) & −A(x) \\ ΛA(x)^{T} & C(x) \end{matrix} ] = [ \begin{matrix}− ∑_{i=1}^{m} λ_{i}∇^{2}c_{i}(x) & −A(x) \\ ΛA(x)^{T} & C(x) \end{matrix} ] .  (16)

Nonsingularity of ∇F (x^{∗}, λ^{∗}) follows from a standard argument, which we now sketch. Let y and z be such that

∇F (x^{∗}, λ^{∗}) [ \begin{matrix}y \\ z \end{matrix} ] = 0.  (17)

Because c_{i}(x^{∗}) > 0 and λ_{i}^{∗} = 0 for i = p + 1, p + 2, …, m, we have by considering the last m − p rows of (17) that z_{i} = 0, for i = p + 1, p + 2, …, m. Because c_{i}(x^{∗}) = 0 and λ_{i}^{∗} > 0 for i = 1, 2, …, p, we have again from (17) and (9) that Ā(x^{∗})^{T} y = 0. Hence,

y^{T} ∇_{xx}L(x^{∗}, λ^{∗})y = y^{T} A(x^{∗})z = y^{T} Ā(x^{∗}) [ z_{1} ; ⋮ ; z_{p} ] = 0.  (18)

Because of second-order sufficiency, (10) and (18) are consistent only if y = 0. Full rank of Ā(x^{∗}) then implies that z_{i} = 0, i = 1, …, p. Hence z = 0, and our claim is proved.

The following result is a consequence of the implicit function theorem (see, for example, Lang [2, p. 131]).

Theorem 3.1 Let the vector pair (x(z, σ), λ(z, σ)) be defined implicitly as the solution of the nonlinear system

F (x, λ) = [ \begin{matrix}z \\ σe \end{matrix} ] ,  (19)

for given (z, σ). Then there are positive constants ϵ > 0 and M > 0 such that the following statements hold.

(i) (x(z, σ), λ(z, σ)) is a C^{2} function of (z, σ) in the neighborhood defined by

N_{ϵ} = {(z, σ) | ∥z∥ + |σ| ≤ ϵ}.

(ii) For σ > 0 and (z, σ) ∈ N_{ϵ}, we have λ_{i}(z, σ) > 0 and c_{i}(z, σ) > 0 for i = 1, 2, …, m.

(iii) For (z_{1}, σ_{1}) and (z_{2}, σ_{2}) in N_{ϵ}, we have

[ \begin{matrix}x_{1} \\ λ_{1} \end{matrix} ] − [ \begin{matrix}x_{2} \\ λ_{2} \end{matrix} ] = ∇F (x_{1}, λ_{1})^{−1} [ \begin{matrix}z_{1} − z_{2} \\ (σ_{1} − σ_{2})e \end{matrix} ] + r_{1},  (20a)
= ∇F (x_{2}, λ_{2})^{−1} [ \begin{matrix}z_{1} − z_{2} \\ (σ_{1} − σ_{2})e \end{matrix} ] + r_{2},  (20b)

where (x_{1}, λ_{1}) = (x(z_{1}, σ_{1}), λ(z_{1}, σ_{1})) and (x_{2}, λ_{2}) = (x(z_{2}, σ_{2}), λ(z_{2}, σ_{2})), and

∥r_{1}∥ ≤ M(∥z_{1} − z_{2}∥ + |σ_{1} − σ_{2}|)^{2},  (21a)
∥r_{2}∥ ≤ M(∥z_{1} − z_{2}∥ + |σ_{1} − σ_{2}|)^{2}.  (21b)

Proof. Since ∇F (x^{∗}, λ^{∗}) is nonsingular and F (·, ·) is C^{2} in a neighborhood of (x^{∗}, λ^{∗}), we have from the implicit function theorem that there is ϵ_{1} > 0 such that (x(z, σ), λ(z, σ)) is a C^{2} function of (z, σ) with (x(0, 0), λ(0, 0)) = (x^{∗}, λ^{∗}) whenever (z, σ) ∈ N_{ϵ_{1}}.

For (ii), we can use the strict complementarity condition to choose ϵ_{2} ∈ (0, ϵ_{1}] such that for (z, σ) ∈ N_{ϵ_{2}} we have

λ_{i}(z, σ) > 0, i = 1, …, p, c_{i}(x(z, σ)) > 0, i = p + 1, …, m.

The condition λ_{i}c_{i}(x) = σ > 0 ensures that the complementary components are also strictly positive; that is,

c_{i}(x(z, σ)) > 0, i = 1, …, p, λ_{i}(z, σ) > 0, i = p + 1, …, m.

For (iii), we use the result of (i) to choose ϵ_{3} ∈ (0, ϵ_{2}] such that the condition number of ∇F (x(z, σ), λ(z, σ)) is uniformly bounded in the neighborhood N_{ϵ_{3}}. By a Taylor series argument and Lipschitz continuity of ∇F in this neighborhood, we have

F (x_{1}, λ_{1}) − F (x_{2}, λ_{2}) = ∇F (x_{1}, λ_{1}) [ \begin{matrix}x_{1} − x_{2} \\ λ_{1} − λ_{2} \end{matrix} ] + O (∥[ \begin{matrix}x_{1} − x_{2} \\ λ_{1} − λ_{2} \end{matrix} ]∥^{2}) .

Therefore, substituting for F (x_{1}, λ_{1}) and F (x_{2}, λ_{2}) from (19) and multiplying through by the inverse of ∇F (x_{1}, λ_{1}), we have

[ \begin{matrix}x_{1} − x_{2} \\ λ_{1} − λ_{2} \end{matrix} ] = ∇F (x_{1}, λ_{1})^{−1} [ \begin{matrix}z_{1} − z_{2} \\ (σ_{1} − σ_{2})e \end{matrix} ] + O (∥∇F (x_{1}, λ_{1})^{−1}∥ ∥[ \begin{matrix}x_{1} − x_{2} \\ λ_{1} − λ_{2} \end{matrix} ]∥^{2}) . (22)

Since (x, λ) is a C^{2} function of (z, λ) on N_{ϵ_{3}}, it is certainly Lipschitz C^{1}. Hence we have

[ \begin{matrix}x_{1} − x_{2} \\ λ_{1} − λ_{2} \end{matrix} ] = [ \begin{matrix}\frac{dx}{dz}(z_{1}, σ_{1}) & \frac{dx}{dσ}(z_{1}, σ_{1}) \\ \frac{dλ}{dz}(z_{1}, σ_{1}) & \frac{dλ}{dσ}(z_{1}, σ_{1}) \end{matrix} ] [ \begin{matrix}z_{1} − z_{2} \\ σ_{1} − σ_{2} \end{matrix} ] + O (∥[ \begin{matrix}z_{1} − z_{2} \\ σ_{1} − σ_{2} \end{matrix} ]∥^{2}) .  (23)

The Jacobian term in (23) is bounded, so we can combine (22) and (23) to obtain the result (20a) for r_{1} satisfying (21a), for some M > 0. The remaining result (20b), (21b) follows identically.

The choice ϵ = ϵ_{3} > 0 is sufficient for all of (i), (ii), and (iii).

It is not difficult to show that x(0, μ) defined from (19) is an isolated local minimizer of P (·; μ) for sufficiently small μ. In fact, x(μw, μ) is an isolated local minimizer of the modified log barrier function P_{w}(·; μ) provided that w is not too large. (The claim certainly holds when ∥w∥ = o(μ^{−1/2}), as we assume below in (29).)

Uniform nonsingularity of ∇F in a neighborhood of (x^{∗}, λ^{∗}) implies that the first terms in the right-hand side of (20a) and (20b) dominate the second terms for ϵ sufficiently small; that is,

∥[ \begin{matrix}x_{1} \\ λ_{1} \end{matrix} ] − [ \begin{matrix}x_{2} \\ λ_{2} \end{matrix} ]∥ = Θ (∥[ \begin{matrix}z_{1} − z_{2} \\ (σ_{1} − σ_{2})e \end{matrix} ]∥) = Θ(∥z_{1} − z_{2}∥ + |σ_{1} − σ_{2}|).  (24)

Let ϵ be the quantity in Theorem 3.1, and suppose that μ and w are such that

μ(∥w∥ + 1) ≤ ϵ.

Then for any μ_{+} ∈ [0, μ], the vector pairs (z, σ) = (−μw, μ) and (z, σ) = (0, μ_{+}) both lie in the neighborhood N_{ϵ}. It is easy to verify that

(z, σ) = (μw, μ) ⇒ (x, λ) = (x_{w}(μ), λ_{w}(μ)),
(z, σ) = (0, μ_{+}) ⇒ (x, λ) = (x(μ_{+}), λ(μ_{+})).

Hence, Theorem 3.1 (iii) implies that

[ \begin{matrix}x(μ_{+}) \\ λ(μ_{+}) \end{matrix} ] − [ \begin{matrix}x_{w}(μ) \\ λ_{w}(μ) \end{matrix} ] = ∇F (x_{w}(μ), λ_{w}(μ))^{−1} [ \begin{matrix}−μw \\ −(μ − μ_{+})e \end{matrix} ] + r,  (25)

where

∥r∥ ≤ M ((μ∥w∥ + |μ − μ_{+}|)^{2}) ≤ M(μ^{2}(∥w∥ + 1)^{2}).

Returning to (14), using (x, λ) = (x_{w}(μ), λ_{w}(μ)), and noting that c(x) > 0, we can define a vector δλ ∈ IR^{m} implicitly by the equation

ΛA(x)^{T} (μ_{+}/μ)p + C(x)δλ = −(μ − μ_{+})e.  (26)

We now show that (14) and (26) together imply that ((μ_{+}/μ)p, δλ) satisfies

∇F (x, λ) [ \begin{matrix}(μ_{+}/μ)p \\ δλ \end{matrix} ] = [ \begin{matrix}∇_{xx}L(x, λ) & −A(x) \\ ΛA(x)^{T} & C(x) \end{matrix} ] [ \begin{matrix}(μ_{+}/μ)p \\ δλ \end{matrix} ] = [ \begin{matrix}−μw \\ −(μ − μ_{+})e \end{matrix} ] . (27)

The second block row of (27) follows immediately from (26). To recover the Newton equations (14), multiply the second block row from the left by A(x)C(x)^{−1}, add it to the first block row, and use the identities

C(x)^{−1} = \frac{1}{μ}Λ, A(x)Λe = g − μw.

This manipulation yields

[\frac{1}{μ}A(x)Λ^{2}A(x)^{T} − ∑_{i=1}^{m} λ_{i}∇^{2}c_{i}(x)] \frac{μ_{+}}{μ} p = −μw + \frac{μ_{+} − μ}{μ}A(x)λ = (\frac{μ_{+}}{μ} − 1) g − μ_{+}w,

which is identical to (14).

It follows from (25) and (27) that

[ \begin{matrix}x(μ_{+}) − x_{w}(μ) \\ λ(μ_{+}) − λ_{w}(μ) \end{matrix} ] = [ \begin{matrix}(μ_{+}/μ)p \\ δλ \end{matrix} ] + O(μ^{2}(∥w∥ + 1)^{2}),

and consequently

(μ_{+}/μ)p = x(μ_{+}) − x_{w}(μ) + O(μ^{2}(∥w∥ + 1)^{2}).  (28)

The result we are most interested in — that (μ_{+}/μ)p and x(μ_{+}) − x_{w}(μ) are asymptotically the same direction — will follow from (28) if we can show that the O(μ^{2}(∥w∥+1)^{2}) remainder term is eventually dominated by either (hence both) of these two vectors. To show this, we need additional conditions on w and μ_{+}, namely,

∥w∥ = o(μ^{−1/2})  and  μ_{+} ≤ ρμ, for some ρ ∈ (0, 1).  (29)

The first condition controls the inexactness that we allow in the calculation of the minimizer of P (x; μ) as μ ↓ 0. Because of (5), the ratio

∇_{x}P (x_{w}(μ); μ)/μ^{1/2}

should approach zero as μ ↓ 0, where x_{w}(μ) is, as usual, the approximate minimizer for this value of μ. The condition on μ_{+} in (29) simply means that there is a significant decrease in μ at each step. If this condition fails to hold, so that μ_{+} ≈ μ, we expect the distance even between two successive exact minimizers x(μ) and x(μ_{+}) to be short; indeed, it might be swallowed up in the remainder term in (28).

Next, we show that (29) implies μ^{2}(∥w∥+1)^{2} = o(||(μ_{+}/μ)p||). Given (29) and sufficiently small μ, we have from (28) that

(μ_{+}/μ)p = x(μ_{+}) − x_{w}(μ) + o(μ).  (30)

Hence, our desired result will hold if we can show that (μ_{+}/μ)p = Θ(μ). From (27) and uniform nonsingularity of ∇F (x, λ) near (x^{∗}, λ^{∗}), we have

[ \begin{matrix}(μ_{+}/μ)p \\ δλ \end{matrix} ] = O(μ(∥w∥ + 1)) = o(μ^{1/2}).  (31)

Applying Theorem 3.1(iii) or, alternatively, Equation (24), with

(z_{1}, σ_{1}) = (μw, μ), that is, (x_{1}, λ_{1}) = (x_{w}(μ), λ_{w}(μ)),
(z_{2}, σ_{2}) = (0, 0), that is, (x_{2}, λ_{2}) = (x^{∗}, λ^{∗}),

we have

∥[ \begin{matrix}x_{w}(μ) − x^{∗} \\ λ_{w}(μ) − λ^{∗} \end{matrix} ]∥ = O(μ(∥w∥ + 1)) = o(μ^{1/2}).

Hence, for any active constraint (i = 1, 2, …, p), we have

c_{i}(x_{w}(μ)) = c_{i}(x_{w}(μ)) − c_{i}(x^{∗}) = o(μ^{1/2}).  (32)

Further, by our strict complementarity assumptions, we can define a constant γ > 0 such that

[λ_{w}(μ)]_{i} ≤ λ_{i}^{∗} + o(μ^{1/2}) ≤ 2λ_{i}^{∗} ≤ γ,  i = 1, 2, …, p,  (33)

for μ sufficiently small.

Consider now the first p components of the equation (26). Defining Ā(x) and λ̄ as in (9), and c̄(x), Λ̄, δλ̄ accordingly, we have for (x, λ) = (x_{w}(μ), λ_{w}(μ)) that

Λ̄Ā(x)(μ_{+}/μ)p + C̄(x)δλ̄ = −(μ − μ_{+})e
⇒ Ā(x)^{T} (μ_{+}/μ)p = −Λ̄^{−1} [(μ − μ_{+})e + C̄(x)δλ̄] .  (34)

Since C̄(x)δλ̄ = o(μ) from (32) and (31), we have

Λ̄^{−1} [(μ − μ_{+})e + C̄(x)δλ̄] ≥ γ^{−1}[(1 − ρ)μ + o(μ)]e ≥ γ^{−1} \frac{1 − ρ}{2}μe,  (35)

for sufficiently small μ, so the right-hand side of (34) is Θ(μ).

If we had (μ_{+}/μ)p = o(μ), then the right-hand side of (34) would be o(μ), which would contradict (35). Hence (μ_{+}/μ)p = Θ(μ), and so, from (30), the two directions x(μ_{+})−x_{w}(μ) and (μ_{+}/μ)p are asymptotically identical.

We state our main result as a theorem.

Theorem 3.2 Assume that the objective function f(x) of problem (1) is linear and x is a point near the minimizer x(μ) of P ( . , μ) in the sense that w defined from (5) satisfies (29). If μ_{+} satisfies the second part of (29), then the Newton direction p in (14) for the logarithmic barrier function P is asymptotically the exact direction to the minimum x(μ_{+}) of P ( . , μ_{+}) in the sense that

x + \frac{μ_{+}}{μ} p − x(μ_{+}) = o(x − x(μ_{+})).

Even if μ_{+} is chosen very small (μ_{+} ≪ μ), Theorem 3.2 by itself is not sufficient to guarantee that the Newton direction will bring us close to the optimal solution x^{∗} of (1). We need to check that the line segment defined by

x + α(μ_{+}/μ)p,  α ∈ [0, 1],  (36)

lies within the feasible region, except perhaps for values of α close to 1. It suffices to check that the constraints that are active at x^{∗} are satisfied. For any i = 1, …, p, we have from (34), the definition λ_{i} = μ/c_{i}(x), and the estimate |c_{i}(x)δλ_{i}| = o(μ) that

c_{i}(x) + α∇c_{i}(x)^{T} (μ_{+}/μ)p = \frac{μ}{λ_{i}} − \frac{α}{λ_{i}} [(μ − μ_{+}) + c_{i}(x)δλ_{i}]
= \frac{1}{λ_{i}} [(1 − α)μ + αμ_{+} + o(μ)].

Now, using the bound (33), the estimate ∥(μ_{+}/μ)p∥ = Θ(μ), and the smoothness of c_{i}, we have

c_{i}(x + α(μ_{+}/μ)p) = c_{i}(x) + α∇c_{i}(x)^{T} (μ_{+}/μ)p + O(μ^{2})
= \frac{1}{λ_{i}} [(1 − α)μ + αμ_{+} + o(μ)] + O(μ^{2})
≥ \frac{1}{γ} [(1 − α)μ + o(μ)].  (37)

Hence, if the segment (36) crosses the i-th constraint, we have c_{i}(x + α(μ_{+}/μ)p) = 0 for some α ∈ [0, 1]. Because of (37), this is possible only when 1 − α = o(μ)/μ. (In the case of w = 0, that is, x = x(μ) exactly on the central path, this estimate can be strengthened to 1 − α = O(μ).) Hence, near-unit steps can eventually be taken without violating the constraints.

4 Discussion

In this paper we have analyzed the first Newton step that a logarithmic barrier method takes after decrementing the barrier parameter. Assuming linearity of the objective (without which the direction may be no good at all), we have quantified the accuracy of the direction in terms of the Euclidean norm of the gradient ∥w∥ and the barrier parameter μ. We conjecture that condition ∥w∥ = o(μ^{−1/2}) can be weakened slightly if we use a more appropriate norm, such as ||w||_{∇^{2}P (x,μ)^{−1}} = (w^{T} ∇^{2}P (x, μ)^{−1}w)^{1/2}. However, our final example (below) illustrates that a rather strong condition on w is necessary indeed to maintain the validity of Theorem 3.2.

Finally, we point out that the second part of condition (29) can be dropped if we work with the modified barrier function (6). Having obtained a sufficiently accurate approximation to the minimizer x(μ) of P (·; μ), we may set w as in (5). Then, updating μ to μ_{+}, we can take a Newton step for the modified barrier function P_{w}(·; μ_{+}) toward x_{w}(μ_{+}). Theorem 3.2 holds for this Newton step, even if the second part of condition (29) does not hold. (The Newton direction for the modified barrier function generated in the above way coincides with the primal affine scaling direction.) The analysis of the Newton step for the modified barrier function is similar to the analysis above. Since the barrier function (3) is more commonly used, however, we confined our main result to this function.

• Example: Finally, we formulate our introductory example to demonstrate the asymptotic equivalence (28). By introducing an artificial variable, we transform (4) to

min x_{3} subject to (x_{1}, x_{2}) ≥ 0, x_{3} ≥ x_{1} + \frac{1}{2}(x_{2} − 1)^{2}.

Then the barrier function P (x; μ) is

P (x; μ) = x_{3} − μ ln(x_{3} − x_{1} − \frac{1}{2}(x_{2} − 1)^{2}) − μ ln x_{1} − μ ln x_{2},

and we find from ∇P (x(μ); μ) = 0 that

x(μ) = ( \begin{matrix}μ \\ \frac{1}{2}(1 + \sqrt{1 + 4μ}) \\ 1 + 4μ − \sqrt{1 + 4μ} \end{matrix} ) ≈ ( \begin{matrix}μ \\ 1 + μ \\ 2μ \end{matrix} ) ,

so

x(μ) − x^{∗} ≈ μ(1, 1, 2)^{T} .  (38)

A little manipulation shows that for μ_{+} ∈ (0, μ) and x = x(μ), we have

∇P (x; μ_{+}) = ( \begin{matrix}0 \\ 0 \\ 1 − μ_{+}/μ \end{matrix} ) , ∇^{2}P (x; μ_{+}) ≈ \frac{μ_{+}}{μ^{2}} [ \begin{matrix}2 & μ & −1 \\ μ & μ & −μ \\ −1 & −μ & 1 \end{matrix} ] ,

so the Newton step p is approximately

p ≈ −\frac{μ}{μ_{+}} (μ − μ_{+}) ( \begin{matrix}1 \\ 1 \\ 2 \end{matrix} ) .  (39)

As claimed, (38) and (39) are consistent with (28).

We conclude this example by illustrating the inaccuracy in the direction p for centered and noncentered points for this particular example. We calculate the direction accuracy

∥\frac{p}{∥p∥} − \frac{x − x^{∗}}{∥x − x^{∗}∥}∥

for various values of μ. For each μ, we choose x to be the exactly centered point x = x(μ) and also the noncentered point

x̂(μ) = ( \begin{matrix}μ/2 \\ 1 + 2μ \\ 4μ \end{matrix} ) .

Results are shown in Tables 1 and 2. Note that the directions line up as μ ↓ 0 in Table 1, while Table 2 shows that the noncentrality of x̂(μ) introduces a systematic error into the Newton direction p that does not vanish even when x̂(μ) is extremely close to x^{∗}.

Table 1: Direction accuracy from centered points x = x(μ)

μ  μ_{+} Relative Accuracy
1  10^{−1}  .60 × 10^{−1}
1  10^{−2}  .73 × 10^{−1}
10^{−2} 10^{−3}  .39 × 10^{−2}
10^{−2} 10^{−4}  .43 × 10^{−2}
10^{−4} 10^{−5}  .41 × 10^{−4}
10^{−4} 10^{−6}  .45 × 10^{−4}

Table 2: Direction accuracy from non-centered points x = x̂(μ)

μ  μ_{+} Relative Accuracy
10^{−2} 10^{−3}  .83 × 10^{−1}
10^{−2} 10^{−4}  .97 × 10^{−1}
10^{−4} 10^{−5}  .88 × 10^{−1}
10^{−4} 10^{−6}  .10
10^{−6} 10^{−7}  .88 × 10^{−1}
10^{−6} 10^{−8}  .10

Acknowledgments

Part of this work was done while the first author was visiting the Institute of Statistical Mathematics in Tokyo, Japan; thanks are due to Shinji Mizuno for his warm hospitality. He is also grateful to Takashi Tsuchiya for helpful discussions about the affine scaling direction and to Professor Kojima for his help with office and computing facilities at the Tokyo Institute of Technology.

References

[1] A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968.

[2] S. Lang, Real Analysis (2nd ed.), Addison-Wesley, Reading, Massachusetts, 1983.

[3] M. H. Wright, Why a pure primal Newton barrier step may be infeasible, Numerical Analysis Manuscript 93–02, AT&T Bell Laboratories, March 1993. To appear in SIAM Journal on Optimization.