ARGONNE NATIONAL LABORATORY 9700 South Cass Avenue Argonne, Illinois 60439

EXPOSING CONSTRAINTS

James V. Burke^{∗} and Jorge J. Moré

Mathematics and Computer Science Division

Preprint MCS-P308-0592

June 1992

Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.

∗ Permanent address: Department of Mathematics, University of Washington, Seattle, Washington 98195. Work supported in part by the National Science Foundation grant DMS-9102059.

ABSTRACT

The development of algorithms and software for the solution of large-scale optimization problems has been the main motivation behind the research on the identification properties of optimization algorithms. The aim of an identification result for a linearly constrained problem is to show that if the sequence generated by an optimization algorithm converges to a stationary point, then there is a nontrivial face F of the feasible set such that after a finite number of iterations, the iterates enter and remain in the face F. This paper develops the identification properties of linearly constrained optimization algorithms without any nondegeneracy or linear independence assumptions. The main result shows that the projected gradient converges to zero if and only if the iterates enter and remain in the face exposed by the negative gradient. This result generalizes results of Burke and Moré obtained for nondegenerate cases.

EXPOSING CONSTRAINTS

James V. Burke^{∗} and Jorge J. Moré

1 Introduction

The development of algorithms and software for the solution of large-scale constrained optimization problems,

min{f(x) : x ∈ Ω},  (1.1)

has been the main motivation behind the research on the identification properties of optimization algorithms. Much of this research has been done under the assumption that the set Ω is a general convex set and that the stationary points of the optimization problem (1.1) are nondegenerate. In this work we show that it is possible to develop the identification properties of linearly constrained optimization algorithms without any nondegeneracy or linear independence assumptions.

The aim of an identification result is to show that if {x_{k}} is a sequence in Ω that converges to a stationary point x^{∗}, then there is an index k_{0} > 0 and a nontrivial face F (x^{∗}) of Ω with x_{k} ∈ F (x^{∗}) for all k ≥ k_{0}. These results are of importance because they show that eventually the behavior of the algorithm is determined by the properties of f on the face F (x^{∗}). For recent work on the identification properties of optimization algorithms see, for example, Conn, Gould, and Toint [7]. Dunn [11], Wright [24], Burke [3], Burke, Moré, and Toraldo [5], Lescrenier [17], Wright [25], and Kelley and Sachs [16].

In linearly constrained problems an identification result can also be expressed in terms of the indices of the active constraints. For example, if Ω has the specific representation

Ω = {x ∈ IR^{n} : ⟨c_{j}, x⟩ ≥ δ_{j}, 1 ≤ j ≤ m} ,  (1.2)

for some vectors c_{j} ∈ IR^{n} and scalars δ_{j}, then all faces F of Ω are of the form

F = {x ∈ Ω : ⟨c_{j}, x⟩ = δ_{j}, j ∈ A(F)}

for some index set A(F). Thus, identification results can be given in terms of an index set that defines the face F (x^{∗}). In this paper we obtain results in terms of the face structure of Ω; results in terms of index sets of active constraints are direct consequences of these results.

An important consequence of the assumption that the stationary point x^{∗} is nondegenerate is that F (x^{∗}) is the unique face of Ω that contains x^{∗} in the relative interior. Thus, it follows that x_{k} ∈ ri {F (x^{∗})} for all k ≥ k_{0}, where ri {·} denotes the relative interior. One of the main difficulties in extending identification results to the degenerate case is that there may be no face F (x^{∗}) such that x_{k} ∈ ri {F (x^{∗})} for all k sufficiently large. However, we show that there is a face F (x^{∗}) such that x_{k} ∈ F (x^{∗}) for all k sufficiently large.

Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.

∗Permanent address: Department of Mathematics, University of Washington, Seattle, Washington 98195.

Work supported in part by the National Science Foundation grant DMS-9102059.

The approach in this paper is reminiscent of the approach of Burke and Moré [4]. In particular, the approach depends on the concept of an exposed face, and on the facial geometry of a convex set Ω. These results are developed in Sections 2 and 3. The definition of an exposed face and several important properties of exposed faces are presented in Section 2, while Section 3 contains a key result on the existence of a partition of IR^{n} based on the face structure of Ω.

The main result of this paper appears in Section 4. This result is a characterization of the identification properties of a sequence {x_{k}} in terms of the projected gradient and the face E[−∇f(x^{∗})] of Ω exposed by −∇f(x^{∗}). If f : IR^{n} → IR is continuously differentiable on the polyhedral set Ω, and {x_{k}} is a sequence in Ω that converges to a stationary point x^{∗} of (1.1), then we show that

lim_{k→∞} P_{T (x_{k})} [−∇f(x_{k})] = 0  (1.3)

if and only if there is a k_{0} > 0 such that

x_{k} ∈ E[−∇f(x^{∗})],  k ≥ k_{0}.  (1.4)

This result has important ramifications because optimization algorithms for linearly constrained problems tend to satisfy (1.3). This can be seen by noting that if the polyhedral set Ω has the representation (1.2), then the projected gradient is

P_{T (x)} [−∇f(x)] = −∇f(x) + ∑_{j∈A(x)} λ_{j}c_{j},

where A(x) is the set of active constraints at x ∈ Ω, and λ_{j} is a nonnegative estimate (a precise definition is given in Section 6) of the Lagrange multiplier for the i-th constraint.

The identification property (1.4) can be expressed in terms of Lagrange multipliers at the solution because we show that E[−∇f(x^{∗})] is defined in terms of the active set by

x ∈ E[−∇f(x^{∗})] ⟺ {i ∈ A(x^{∗}) : λ_{i}^{∗} > 0} ⊂ A(x), x ∈ Ω,

where λ_{i}^{∗} is the Lagrange multiplier for the i-th constraint. This result depends on the choice of Lagrange multipliers.

The identification property (1.4) has an equivalent formulation that is clearly independent of the choice of Lagrange multipliers. Section 5 shows that it is possible to define a set of strictly binding constraints B_{s}^{∗} at a stationary point x^{∗} independent of the choice of Lagrange multipliers, and that

x ∈ E[−∇f(x^{∗})] ⟺ B_{s}^{∗} ⊂ A(x), x ∈ Ω.

This leads, in particular, to a version of the results of Section 4 in terms of B_{s}^{∗}.

Section 4 also contains a discussion of the connection of these result to the identification results of Burke and Moré [4], and to the convergence results for the class of trust region methods for bound constrained optimization problems proposed by Conn, Gould, and Toint [7, 8]. The connection between these results and the class of trust region methods for general linearly constrained methods analyzed by Moré [18] and Burke, Moré, and Toraldo [5] will be reported in a later paper.

We end the paper with two applications of these identification results. Section 6 examines the influence of degeneracy on the standard second-order sufficiency conditions. In particular, we show that if x^{∗} is degenerate, a satisfactory convergence analysis can be obtained if we assume that ∇^{2}f(x^{∗}) is positive definite on the affine hull of E[−∇f(x^{∗})] − x^{∗}. Section 7 examines the implication of the identification results to the GPCG algorithm of Moré and Toraldo [19]. In particular, we show that the convergence condition of the GPCG algorithm is satisfied in a finite number of iterations even when the solution is degenerate.

2 Exposed Faces

The geometric approach to the identification properties of optimization algorithms requires an understanding of the face structure of a convex set Ω. In this section we provide some of the necessary results and background from convex analysis.

Recall that the affine hull aff {Ω} of a convex set Ω in IR^{n} is the smallest affine set that contains Ω, and the relative interior ri (Ω) of Ω is the interior of Ω relative to aff {Ω}. In all cases we assume that Ω is not empty.

A nonempty subset F of a convex set Ω is a face of Ω if every convex subset of Ω whose relative interior meets F is contained in F. Thus, if x and y are in Ω and λx + (1 − λ)y lies in F for some λ in (0, 1), then both x and y must belong to F. A basic result on the face structure of a convex set is that the relative interiors of the faces of Ω form a partition of Ω. For future reference, we state this result formally.

Theorem 2.1 If F is the collection of all faces of the convex set Ω, then the collection

{ri (F) : F ∈ F}

is a partition of Ω.

This result can be found, for example, in Rockafellar [22, Theorem 18.2]. Note that this result shows that every point x ∈ Ω can be associated with a unique face F (x) of Ω such that x ∈ ri (F).

We are concerned with faces of Ω that are exposed by a given vector d in IR^{n}. A nonempty subset F of a convex set Ω is exposed by a vector d ∈ IR^{n} if F = E(d), where

E(d) = arg max{⟨d, x⟩ : x ∈ Ω}

Figure 2.1: Convex set defined by (2.1)

for some inner product ⟨·, ·⟩ of IR^{n}. A computation shows that E(d) is a face whenever E(d) is not empty.

Every face of a polyhedron is exposed (see, for example, Theorem 2.4.12 of Stoer and Witzgall [23]), but this is not the case for general convex sets. For example, in the convex set Ω defined by

Ω = \{(ξ_{1}, ξ_{2}) : −1 ≤ ξ_{2} ≤ (1 − ξ_{1}^{2})^{\frac{1}{2}} , 0 ≤ ξ_{1} ≤ 1\} ,  (2.1)

the point (1, 0) is a face of Ω that is not exposed by any vector. This can be seen clearly in Figure 2.1.

The concept of an exposed face is closely related to the concept of a normal cone. For a convex set Ω, the normal cone at x in Ω is defined by

N(x) = {u ∈ IR^{n} : ⟨u, y − x⟩ ≤ 0, y ∈ Ω} .

The tangent cone T (x) is the dual of the normal cone. Thus v ∈ T (x) if and only if ⟨v, u⟩ ≤ 0 for all u ∈ N(x). The tangent cone T (x) can also be defined as the closure of all vectors v ∈ IR^{n} such that x + αv ∈ Ω for all α > 0 sufficiently small.

Exposed faces and normal cones are related by the observation that x ∈ E(d) if and only if d ∈ N(x). We make use of this observation throughout this section.

The concept of an exposed face is also related to the standard first-order optimality conditions for problem (1.1). Recall that the standard first order conditions for a stationary point x^{∗} of problem (1.1) are that

⟨∇f(x^{∗}), x − x^{∗}⟩ ≥ 0, x ∈ Ω.

In terms of normal cones, this is equivalent to requiring that

−∇f(x^{∗}) ∈ N(x^{∗}).

The following result shows the connection between stationary points and exposed faces.

Lemma 2.2 If Ω in IR^{n} is a closed convex set, then x^{∗} is a stationary point for problem (1.1) if and only if x^{∗} ∈ E[−∇f(x^{∗})].

The proof of this result is a direct consequence of the observation that x ∈ E(d) if and only if d ∈ N(x).

Lemma 2.2 shows that any stationary point x^{∗} belongs to the exposed face E[−∇f(x^{∗})]. The stationary point x^{∗} may belong to other faces of Ω, but in Section 4 we show that optimization algorithms tend to generate sequences {x_{k}} with x_{k} ∈ E[−∇f(x^{∗})] for all k sufficiently large. In this section we develop part of the necessary machinery for this result.

We extend the concept of normal and tangent cones at a point x ∈ Ω by defining a normal cone N(F) and a tangent cone T (F) for each F ∈ F by

N(F) ≡ N(x), T (F) ≡ T (x), x ∈ ri (F) .

This definition relies on the result of Burke and Moré [4] that normal and tangent cones are independent of x ∈ ri (F) for any F ∈ F.

The intersection of an arbitrary collection of faces is easily shown to be a face, but the union of faces is not necessarily a face. On the other hand, the following result shows that the union of all faces F ∈ F such that d ∈ N(F) is the face exposed by d.

Lemma 2.3 If Ω in IR^{n} is a closed convex set, then

E(d) = ⋃_{F ∈F (d)} F

for any d ∈ IR^{n}, where F(d) is the collection of faces F ∈ F such that d ∈ N(F).

Proof. Assume first that x ∈ E(d). Then d ∈ N(x), and since Theorem 2.1 guarantees that x ∈ ri (F) for some F ∈ F, we have d ∈ N(x) = N(F). This shows that

E(d) ⊂ ⋃_{F ∈F (d)} F.

We complete the proof by showing that if F ∈ F(d) then F ⊂ E(d). Assume that x ∈ F for some F ∈ F(d). We can choose a sequence {x_{k}} with x_{k} ∈ ri (F) such that {x_{k}} converges to x. Since x_{k} ∈ ri (F) and d ∈ N(F), we have d ∈ N(x_{k}), and hence, x_{k} ∈ E(d). Since the exposed face E(d) is closed and {x_{k}} converges to x, we obtain that x ∈ E(d) as desired.

The proof of Lemma 2.3 yields the stronger result that {ri (F) : F ∈ F(d)} is a partition of E(d). This result, however, is not needed in this paper.

Lemma 2.3 also shows that if d ∈ N(F) for some F ∈ F, then F ⊂ E(d). For a general convex set Ω, it is difficult to characterize the vectors d ∈ N(F) that expose a face F. On the other hand, the following result of Burke [3, Theorem 4.1] provides a complete characterization for polyhedral Ω.

Theorem 2.4 Let Ω be a polyhedral set in IR^{n}.

If x ∈ Ω, then x ∈ ri {E(d)} if and only if d ∈ ri {N(x)}.
If F ∈ F, then F = E(d) if and only if d ∈ ri {N(F)}.

Burke [3] proved only the first claim in Theorem 2.4, but it is not difficult to show that both claims are equivalent.

Theorem 2.4 fails if Ω is a general convex set. For example, if Ω is the set in Figure 2.1, and F = {(1, 0)}, then F is not exposed by d = (1, 0), but d ∈ ri {N(F)}. Moreover, if F = E(d) for d = (0, 1), then d exposes F, but d ∉ ri {N(F)}. This example shows that the assumption of polyhedrality is required in Theorem A.1 of Burke [3].

The above example also shows that a face may not be exposed by a vector d ∈ ri {N(F)}. In the remainder of this section we show that F is exposed by a vector d ∈ ri {N(F)} if F is a quasi-polyhedral face. This result is of interest because it leads to a connection with the identification results of Burke and Moré [4] for general convex sets. However, note that the remainder of this section is not needed for the main results in this paper.

Burke and Moré [4] defined quasi-polyhedral faces in terms of the lineality of the tangent cone T (x). Recall that for a cone K in IR^{n}, the lineality lin {K} of the cone K is the largest subspace contained in K. Hence, lin {K} = K ∩ (−K).

Definition. A face F of a convex set Ω is quasi-polyhedral if

aff {F } = x + lin {T (x)} , x ∈ ri (F) .

The convex set Ω in Figure (2.1) can be used to illustrate the difference between exposed faces and quasi-polyhedral faces. This set has an infinite number of faces, but the only face that is not exposed by a vector d ∈ ri {N(F)} is F = {(0, 1)}. Also note that Ω has six quasi-polyhedral faces and that these faces are exposed by any vector d ∈ ri {N(F)}.

Burke and Moré [4] show that the lineality of the tangent cone is the orthogonal complement of the normal cone, that is,

lin {T (x)} = N(x)^{⊥},

where the orthogonal complement S^{⊥} of a set S is the subspace of vectors v such that ⟨v, w⟩ = 0 for all w ∈ S. This implies that

lin {T (x)}^{⊥} = aff {N(x)} .

These results lead to the decomposition

T (x) = lin {T (x)} ⊕ lin {T (x)}^{⊥} ∩ T (x)  (2.2)

of the tangent cone. This result is valid if T (x) is replaced by a general convex cone K. See, for example, Stoer and Witzgall [23, Theorem 2.10.5].

Theorem 2.5 A quasi-polyhedral face F of a convex set Ω is exposed by any d ∈ ri {N(F)}.

Proof. The bulk of the proof consists of proving that if x ∈ Ω, then

E(d) = Ω ∩ [x + lin {T (x)}],  d ∈ ri {N(x)} .  (2.3)

Given this result, we complete the proof by noting that F = Ω ∩ aff {F } for any face of Ω, and thus

F = Ω ∩ [x + lin {T (x)}], x ∈ ri {F } ,

for a quasi-polyhedral face. Hence (2.3) yields that F = E(d) if d ∈ ri {N(x)} = ri {N(F)}.

We now prove that (2.3) holds; we first show that Ω ∩ [x + lin {T (x)}] is a subset of E(d). Choose any y in Ω ∩ [x + lin {T (x)}]. Then y − x ∈ lin {T (x)} = N(x)^{⊥}, and since d ∈ N(x), we obtain that ⟨d, y − x⟩ = 0. Since y ∈ Ω, this implies that y ∈ E(d).

We now show that E(d) is a subset of Ω ∩ [x + lin {T (x)}]. Choose any y in E(d). Then y ∈ Ω, and thus y − x ∈ T (x). The decomposition (2.2) of the tangent cone T (x) shows that we can write

y − x = v_{1} + v_{2}, v_{1} ∈ lin {T (x)} , v_{2} ∈ lin {T (x)}^{⊥} ∩ T (x).

If we show that v_{2} = 0, then y − x = v_{1} ∈ lin {T (x)} as desired. We first show that ⟨d, v_{2}⟩ = 0. Note that ⟨d, y − x⟩ = 0 because both y and x belong to E(d), and that ⟨d, v_{1}⟩ = 0 because d ∈ N(x) and v_{1} ∈ lin {T (x)} = N(x)^{⊥}. Hence, ⟨d, v_{2}⟩ = 0.

We claim that v_{2} = 0 since d ∈ ri {N(x)}, v_{2} ∈ lin {T (x)}^{⊥} = aff {N(x)}, and ⟨d, v_{2}⟩ = 0. The proof of this claim is not difficult. Since d ∈ ri {N(x)} and v_{2} ∈ aff {N(x)}, we obtain that d + ϵv_{2} ∈ N(x) for ϵ > 0 sufficiently small. We now use that v_{2} ∈ T (x) to obtain that ⟨d + ϵv_{2}, v_{2}⟩ ≤ 0. Since ⟨d, v_{2}⟩ = 0, this implies that v_{2} = 0, as desired.

3 Face Geometry

The main result of this section is a partition of IR^{n} in terms of the face structure of a convex set. We then use this result to extend Lemma 3.3 of Burke and Moré [4]. As we shall see, this extension is crucial to the results on exposing constraints.

Our development requires a few basic properties of projection operators. The projection P : IR^{n} → Ω into a closed convex set Ω is defined by

P (x) = argmin {∥y − x∥ : y ∈ Ω} ,

where ∥ · ∥ is an inner-product norm. This definition implies that the projection operator P can be characterized in terms of the inner product ⟨·, ·⟩ by requiring that

⟨x − P (x), y − P (x)⟩ ≤ 0, y ∈ Ω.

In terms of normal cones, this characterization requires that

x − P (x) ∈ N[P (x)]  (3.1)

In particular, note that this characterization implies that

P (x + z) = x,  x ∈ Ω, z ∈ N(x).  (3.2)

We extend this result by proving that

P (x + z) = x,  x ∈ F, z ∈ N(F)  (3.3)

for any face F ∈ F. We prove (3.3) by noting that if {x_{k}} is a sequence in ri (F) that converges to x, then z ∈ N(F) = N(x_{k}), and thus (3.2) implies that P (x_{k} + z) = x_{k}. The result now follows from the continuity of the projection operator.

We now present two decompositions of IR^{n} in terms of the face structure of a convex set. The first decomposition extends a result of Goffin [15] for polyhedral Ω.

Theorem 3.1 If Ω is a closed convex set in IR^{n}, then the collection

{ri (F) + N{F } : F ∈ F}

forms a partition of IR^{n}.

Proof. Let x ∈ IR^{n}, and note that x = P (x) + [x − P (x)]. Certainly P (x) ∈ ri (F) for some F ∈ F, and thus the characterization (3.1) of the projection operator implies that

x − P (x) ∈ N[P (x)] = N(F).

Hence, x = P (x) + [x − P (x)] belongs to ri (F) + N(F), and thus

IR^{n} = ⋃_{F ∈F} [ri (F) + N(F)] .

We now show that this decomposition of IR^{n} is a partition. Assume that x_{i} ∈ ri (F_{i}) and z_{i} ∈ N(F_{i}) satisfy x_{1} + z_{1} = x_{2} + z_{2} for some F_{1} and F_{2} in F. Then (3.2) implies that

x_{1} = P (x_{1} + z_{1}) = P (x_{2} + z_{2}) = x_{2}.

Thus, ri (F_{1}) ∩ ri (F_{2}) ≠ ∅. Since the relative interiors of the faces of Ω form a partition of Ω, we must have F_{1} = F_{2} as desired.

Theorem 3.1 suggests that it may be possible to decompose IR^{n} in terms of sets of the form F +ri {N(F)}. We now show that this is possible provided Ω is polyhedral. The proof is similar to that of Theorem 3.1, but depends heavily on Theorem 2.4.

Theorem 3.2 If Ω is a polyhedral set in IR^{n}, then the collection

{F + ri {N(F)} : F ∈ F}

forms a partition of IR^{n}.

Proof. If we define F = E[x − P (x)], then Theorem 2.4 shows that x − P (x) ∈ ri {N(F)}. Moreover, since x − P (x) ∈ N[P (x)], we obtain that P (x) ∈ E[x − P (x)] = F. Hence,

x = P (x) + [x − P (x)] ∈ F + ri {N(F)} .

This proves that

IR^{n} = ⋃_{F ∈F} [F + ri {N(F)}] .

We now prove that this decomposition of IR^{n} is a partition. Assume that x_{i} ∈ F_{i} and z_{i} ∈ ri {N(F_{i})} satisfy x_{1} + z_{1} = x_{2} + z_{2} for some F_{1} and F_{2} in F. Then (3.2) implies that

x_{1} = P (x_{1} + z_{1}) = P (x_{2} + z_{2}) = x_{2}.

Thus, z_{1} = z_{2}. Since z_{i} ∈ ri {N(F_{i})}, Theorem 2.4 shows that F_{i} = E(z_{i}), and thus z_{1} = z_{2} implies that F_{1} = F_{2} as desired.

Theorem 3.2 does not hold for general convex sets Ω. For example, if Ω is the convex set shown in Figure 2.1, then any point of the form (0, ξ) with ξ > 1 does not belong to a set of the form F + ri {N(F)} for F ∈ F. On the other hand, Theorem 3.1 shows that (0, ξ) with ξ > 1 must belong to a set of the form ri (F) + N{F }; a computation shows that F = {(0, 1)}.

We proved Theorems 3.1 and 3.2 because of the interest in partitions of IR^{n} in terms of the faces of a convex set. In the remainder of this section, however, we only need to know that if Ω is polyhedral then the collection {F + N(F) : F ∈ F} covers IR^{n}. Clearly, both Theorems 3.1 and 3.2 yield this result.

In the proof of the lemma below we make use of the result that if Ω is polyhedral then Ω has a finite number of faces. This result can be found, for example, in Rockafellar [22, Theorem 19.1]. We also need to know that if Ω is closed and convex, then any face of Ω is closed. For this result, see Stoer and Witzgall [23, Theorem 3.6.6].

Lemma 3.3 Assume that Ω is a polyhedral set in IR^{n}. If x ∈ Ω and d ∈ N(x), then

x + d ∈ int{K(d)},

where

K(d) = ⋃_{F ∈F (d)}[F + N(F)],

and F(d) is defined in Lemma 2.3.

Proof. The first step in the proof is to show that if F ∈ F, then F + N(F) is closed. The definition of a normal cone shows that N(F) is closed, and since Ω is closed, each face F is closed. Now let {y_{k}} be a sequence in F + N(F) that converges, and let y_{k} = x_{k} + z_{k}, where x_{k} ∈ F and z_{k} ∈ N(F). Since (3.3) implies that

x_{k} = P (x_{k} + z_{k}) = P (y_{k}),

and {y_{k}} converges, it follows that {x_{k}} converges. Moreover, since y_{k} = x_{k} + z_{k}, the sequence {z_{k}} also converges. We now use that x_{k} ∈ F and z_{k} ∈ N(F), to conclude that {x_{k}} converges to some x ∈ F and {z_{k}} converges to some z ∈ N(F). Hence, {y_{k}} converges to x + z in F + N(F). This shows that F + N(F) is closed.

The next step in the proof is technical; we need to show that x + d does not belong to the set

L(d) = ⋃_{F ∉F (d)}[F + N(F)].

Theorem 3.1 shows that x + d ∈ F + N(F) for some F ∈ F. Let y ∈ F and z ∈ N(F) be such that x + d = y + z. Then (3.3) implies that

x = P (x + d) = P (y + z) = y,

and thus d = z ∈ N(F). Hence, F ∈ F(d). This shows that x + d ∉ L(d) as desired.

We have shown that F + N(F) is closed for each F ∈ F. Since Ω is polyhedral, there is a finite number of faces, and thus L(d) is closed. Moreover, since x + d ∉ L(d), there is an open set U such that x + d ∈ U and U ∩ L(d) = ∅. Now note that Theorem 3.1 implies that K(d) ∪ L(d) = IR^{n}, and thus U ⊂ K(d). Hence,

x + d ∈ U ⊂ int{K(d)},

as desired.

Lemmas 2.1 and 3.3 are the ingredients needed to prove the main result of this section.

Theorem 3.4 Let Ω be a polyhedral set in IR^{n}. Assume that {x_{k}} and {d_{k}} are sequences in IR^{n} with x_{k} ∈ Ω and d_{k} ∈ N(x_{k}). If {x_{k}} converges to x^{∗} and {d_{k}} converges to d^{∗}, then x_{k} ∈ E(d^{∗}) for all k sufficiently large.

Proof. Lemma 3.3 implies that x^{∗} + d^{∗} ∈ int{K(d^{∗})} so that x_{k} + d_{k} ∈ K(d^{∗}) for all k sufficiently large. Since d_{k} ∈ N(x_{k}),

x_{k} = P (x_{k} + d_{k}) ∈ P [K(d^{∗})]

by virtue of (3.2). Now note that (3.3) and Lemma 2.1 imply that

P [K(d^{∗})] ⊂ { ⋃_{F ∈F (d^{∗})} P [F + N(F)]} = { ⋃_{F ∈F (d^{∗})} F } = E(d^{∗}),

and thus x_{k} ∈ E(d^{∗}) for all k sufficiently large.

Burke and Moré [4] proved a similar result for general Ω by assuming that x^{∗} ∈ ri {F } for a quasi-polyhedral face F and d^{∗} ∈ ri {N(F)}. The assumption that d^{∗} ∈ ri {N(F)} is a nondegeneracy assumption that is avoided in Theorem 3.4 by assuming that Ω is polyhedral.

Theorem 3.4 fails if Ω is a general closed convex set even if we assume that x^{∗} ∈ ri {F } for a quasi-polyhedral face F. For example, consider the set Ω shown in Figure 2.1. The sequence {x_{k}} defined by

x_{k} = (sin(\frac{π}{k}), cos(\frac{π}{k}))

belongs to Ω for k > 1, and d_{k} = x_{k} ∈ N(x_{k}). However, {d_{k}} converges to d^{∗} = (0, 1), and E(d^{∗}) = {(0, 1)}. Thus, x_{k} ∉ E(d^{∗}) for any k > 1.

4 Exposing Constraints

Previous results on the identification properties of algorithms in the neighborhood of a stationary point either assumed linear independence of the active constraint normals or nondegeneracy of the stationary point. In this section we avoid these restrictions.

Definition. Given a convex set Ω, a stationary point x^{∗} is nondegenerate if

− ∇f(x^{∗}) ∈ ri {N(x^{∗})} .  (4.1)

This nondegeneracy condition is due to Dunn [10]. An advantage of this definition is that it does not make any linear independence assumptions on the constraints. Also note that Burke and Moré [4] proved that if Ω is polyhedral, then x^{∗} is nondegenerate if and only if there is a set of positive Lagrange multipliers. This result implies that this definition of nondegeneracy can be viewed as a generalization of the standard strict complementarity condition.

The main result of this section is an extension of the following identification result of Burke and Moré [4]. For this result recall that F (x) is the unique face of Ω that contains x in the relative interior.

Theorem 4.1 Let f : IR^{n} → IR be continuously differentiable on the closed, convex set Ω. If {x_{k}} is a sequence in Ω that converges to a nondegenerate stationary point x^{∗} of (1.1), then

lim_{k→∞} P_{T (x_{k})} [−∇f(x_{k})] = 0  (4.2)

if and only if there is a k_{0} > 0 such that

x_{k} ∈ ri {F (x^{∗})} , k ≥ k_{0}.

An advantage of Theorem 4.1 is that it is independent of the representation of Ω. For applications, however, it is necessary to express Theorem 4.1 in terms of a specific representation of Ω. Note, in particular, that if Ω is the polyhedral set defined by the set of linear constraints

Ω = {x ∈ IR^{n} : ⟨c_{j}, x⟩ ≥ δ_{j}, 1 ≤ j ≤ m} ,  (4.3)

for some vectors c_{j} ∈ IR^{n} and scalars δ_{j}, then Calamai and Moré [6] proved that the projected gradient that appears in (4.2) can be expressed in the familiar form

P_{T (x)} [−∇f(x)] = −∇f(x) + ∑_{j∈A(x)} λ_{j}c_{j},  (4.4)

where the set of active constraints is defined by

A(x) ≡ {j : ⟨c_{j}, x⟩ = δ_{j}},

and λ_{j} for j ∈ A(x) solves the bound constrained linear least squares problem

min {∥∇f(x) − ∑_{j∈A(x)} λ_{j}c_{j}∥ : λ_{j} ≥ 0} .

Also note that representation (4.4) of the projected gradient is unique even if the active constraints c_{j} with j ∈ A(x) are linearly dependent.

Theorem 4.1 characterizes the limiting behavior of many algorithms with respect to the face structure of Ω. For example, Burke and Moré [4] prove that the sequential quadratic programming algorithm and the gradient projection algorithm generate sequences that satisfy (4.2). Consequently, if the stationary point x^{∗} is nondegenerate, the sequences generated by these algorithms eventually enter and remain in the relative interior of the face F (x^{∗}). This can be extremely useful knowledge in the design of algorithms for the solution of (1.1).

Note that Theorem 4.1 gives information on the identification of the active constraints. This is based on the observation of Burke and Moré [4] that

ri {F (x^{∗})} = {x ∈ Ω : ⟨c_{j}, x⟩ = δ_{j}, j ∈ A(x^{∗}), ⟨c_{j}, x⟩ > δ_{j}, j ∉ A(x^{∗})} .

Thus, Theorem 4.1 shows that if {x_{k}} is a sequence in Ω that converges to a nondegenerate stationary point x^{∗} of (1.1), then the sequence {P_{T (x_{k})} [−∇f(x_{k})]} converges to zero if and only if there is a k_{0} > 0 such that

A(x_{k}) = A(x^{∗}), k ≥ k_{0}.

The following example of Stephen Wright shows that this result fails in degenerate cases.

Example. Define f : IR^{2} → IR by

f(ξ_{1}, ξ_{2}) = \frac{1}{2} (ξ_{1}^{2} + μξ_{2}^{2})

for some μ > 1, and define Ω ⊂ IR^{2} by

Ω = {(ξ_{1}, ξ_{2}) ∈ IR^{2} : ξ_{1} ≥ μ^{2}ξ_{2}, ξ_{1} ≥ −ξ_{2}} .

Note that f is a strictly convex quadratic and that x^{∗} = 0 is the global minimizer in Ω. A computation shows that the steepest descent iterates are generated by

( \begin{matrix}ξ_{1} \\ ξ_{2} \end{matrix} )_{+} = \frac{μ − 1}{ξ_{1}^{2} + μ^{3}ξ_{2}^{2}} ( \begin{matrix}μ^{2}ξ_{1}ξ_{2}^{2} \\ −ξ_{1}^{2}ξ_{2} \end{matrix} ) .

This implies, in particular, that all the iterates are feasible and that

\frac{ξ_{1}^{(k+2)}}{ξ_{2}^{(k+2)}} = \frac{ξ_{1}^{(k)}}{ξ_{2}^{(k)}} .

Hence, every other iterate of the steepest descent method lies in the same ray from the origin. Thus, if the initial iterate satisfies either the constraint ξ_{1} = μ^{2}ξ_{2} or the constraint ξ_{1} = −ξ_{2}, the iterates of the steepest descent method oscillate between the two constraints that define Ω. Since these iterates are feasible, the steepest descent iterates coincide with the gradient projection iterates. This implies that in this example,

A(x_{k+1}) ≠ A(x_{k}), A(x_{k}) ≠ A(x^{∗}), k ≥ k_{0}.

Of course, in this case x^{∗} is degenerate because ∇f(x^{∗}) = 0.

We now consider the case when x^{∗} is degenerate and show that the nondegeneracy assumption in Theorem 4.1 can be dropped if we replace ri {F (x^{∗})} by E[−∇f(x^{∗})].

Theorem 4.2 Let f : IR^{n} → IR be continuously differentiable on the polyhedral set Ω, and assume that {x_{k}} is a sequence in Ω that converges to a stationary point x^{∗} of (1.1). Then

lim_{k→∞} P_{T (x_{k})} [−∇f(x_{k})] = 0

if and only if there is a k_{0} > 0 such that

x_{k} ∈ E[−∇f(x^{∗})], k ≥ k_{0}.

Proof. The proof depends on the Moreau decomposition (see, for example, Lemma 2.2 of Zarantonello [26]) and Theorem 3.4. The Moreau decomposition of −∇f shows that

−∇f(x_{k}) = −P_{T (x_{k})} [−∇f(x_{k})] + P_{N(x_{k})}[−∇f(x_{k})].

In particular,

−∇f(x_{k}) = −P_{T (x_{k})} [−∇f(x_{k})] + d_{k},

where d_{k} ∈ N(x_{k}). Hence, if the sequence {P_{T (x_{k})} [−∇f(x_{k})]} converges to zero, then {d_{k}} converges to −∇f(x^{∗}), and thus Theorem 3.4 shows that x_{k} ∈ E[−∇f(x^{∗})] for all k sufficiently large.

Conversely, assume that x_{k} ∈ E[−∇f(x^{∗})] for all k sufficiently large. Since x ∈ E(d) if and only if d ∈ N(x), we have that there is a k_{0} > 0 such that −∇f(x^{∗}) ∈ N(x_{k}) for all k ≥ k_{0}. Since the Moreau decomposition implies that

∥P_{T (x_{k})} [−∇f(x_{k})]∥ = min {∥∇f(x_{k}) + d∥ : d ∈ N(x_{k})} ,

we obtain that

∥P_{T (x_{k})} [−∇f(x_{k})]∥ ≤ ∥∇f(x_{k}) − ∇f(x^{∗})∥.

This yields the desired result.

In the remainder of this section we examine various consequences of Theorem 4.2. We first use Burke’s result (Theorem 2.4) to show that Theorem 4.2 is an extension of Theorem 4.1 for polyhedral Ω.

Theorem 4.3 If Ω is a polyhedral set, then x^{∗} is a nondegenerate stationary point for problem (1.1) if and only if x^{∗} ∈ ri {E[−∇f(x^{∗})]}.

Proof. This result is a direct consequence of Theorem 2.4.

We can show that Theorem 4.2 is an extension of Theorem 4.1 by noting that if x^{∗} is a nondegenerate stationary point for problem (1.1), then Theorem 4.3 shows that x^{∗} is in ri {E[−∇f(x^{∗})]}, and thus any x ∈ E[−∇f(x^{∗})] sufficiently close to x^{∗} also belongs to ri {E[−∇f(x^{∗})]}.

We now show that if the polyhedral set Ω has the specific representation (4.3), then the face E[−∇f(x^{∗})] can be expressed in terms of the positive Lagrange multipliers at x^{∗}.

Theorem 4.4 If Ω is the polyhedral set in IR^{n} defined by (4.3) and

∇f(x^{∗}) = ∑_{j∈A(x^{∗})} λ_{j}^{∗}c_{j},  λ_{j}^{∗} ≥ 0,  (4.5)

for some stationary point x^{∗} of problem (1.1), then

E[−∇f(x^{∗})] = {x ∈ Ω : ⟨c_{j}, x⟩ = δ_{j}, λ_{j}^{∗} > 0} .

Proof. Note that

⟨∇f(x^{∗}), x⟩ = ∑_{j∈A(x^{∗})} λ_{j}^{∗}⟨c_{j}, x⟩ ≥ ∑_{j∈A(x^{∗})} λ_{j}^{∗}δ_{j}

for any x ∈ Ω. Thus, ⟨∇f(x^{∗}), x⟩ is minimized only when ⟨c_{j}, x⟩ = δ_{j} for λ_{j}^{∗} > 0.

If the active constraint normals are linearly dependent then there is an infinite set of Lagrange multipliers that satisfy (4.5). Nevertheless, Theorem 4.4 shows that the set

{x ∈ Ω : ⟨c_{j}, x⟩ = δ_{j}, λ_{j}^{∗} > 0}

is independent of the choice of Lagrange multipliers.

Theorem 4.5 Let f : IR^{n} → IR be continuously differentiable on the polyhedral set Ω defined by (4.3). Assume that x^{∗} is a stationary point of (1.1) and that the Lagrange multipliers λ_{i}^{∗} satisfy (4.5). If {x_{k}} is a sequence in Ω that converges to x^{∗}, then

lim_{k→∞} P_{T (x_{k})} [−∇f(x_{k})] = 0  (4.6)

if and only if there is a k_{0} > 0 such that

{i ∈ A(x^{∗}) : λ_{i}^{∗} > 0} ⊂ A(x_{k}),  k ≥ k_{0}.  (4.7)

Proof. Theorem 4.4 shows that

x ∈ E[−∇f(x^{∗})] ⟺ {i ∈ A(x^{∗}) : λ_{i}^{∗} > 0} ⊂ A(x), x ∈ Ω.

Thus, the result is a direct consequence of Theorem 4.2.

This result has immediate applications to several algorithms. For example, Calamai and Moré [6] show that the gradient projection method generates sequences that satisfy (4.6). Hence, Theorem 4.5 implies that if the sequence {x_{k}} generated by the gradient projection method converges to x^{∗}, then (4.7) holds.

Closely related convergence results for the gradient projection method are due to Bertsekas [1, 2], Gafni and Bertsekas [12, 13], and Dunn [9]. However, in these papers it is not shown that (4.6) holds; instead, it is shown that any limit point of the sequence {x_{k}} is stationary.

Theorem 4.5 also has application to the class of trust region methods for bound constrained optimization problems proposed by Conn, Gould, and Toint [7, 8]. For this algorithm Lescrenier [17] proved that (4.7) holds. Hence, Theorem 4.5 implies that (4.6) holds. This result is of interest because the measure

ν(x; f) = ∥P_{T (x)} [−∇f(x)]∥  (4.8)

is a natural criterion for terminating the algorithm. This is clear from expression (4.4) for the projected gradient. Moreover, note that ν(x; ·) is scale invariant in the sense that ν(x; αf) = αν(x, f) for any α > 0. Other criteria, for example,

ν(x; f) = ∥P [x − ∇f(x)] − x∥

do not have this important property.

Finally, Theorem 4.5 has implications to the class of trust region methods for general linearly constrained methods analyzed by Burke, Moré, and Toraldo [5]. These results will be reported in a later paper.

5 Strictly Binding Constraints

We have stressed the geometric viewpoint of Theorem 4.2 because this viewpoint leads to results that are independent of the representation of Ω. On the other hand, the viewpoint of Theorem 4.5 is needed because it is closely related to computational issues. In this section we show that it is possible to define a set of strictly binding constraints B_{s}^{∗} at x^{∗}, independent of the choice of Lagrange multipliers. This leads, in particular, to a version of Theorem 4.5 in terms of B_{s}^{∗}.

We will show that the set of strictly binding constraints B_{s}^{∗} can be defined in terms of the active set of the exposed face E[−∇f(x^{∗})].

Definition. If Ω is a polyhedral set and F is a face of Ω, then

A (F) = A(x), x ∈ ri {F }

is the active set of F.

We justify this definition by showing that the active set A(x) is independent of x ∈ ri {F }. Assume that Ω is defined by (4.3), and choose any x ∈ ri {F }. If y ∈ F, then

x_{λ} = x + λ(y − x) ∈ F

for some λ < 0. Hence, if i ∈ A(x), then

δ_{i} ≤ ⟨c_{i}, x_{λ}⟩ = (1 − λ)⟨c_{i}, x⟩ + λ⟨c_{i}, y⟩ = (1 − λ)δ_{i} + λ⟨c_{i}, y⟩.

Since λ < 0, this implies that ⟨c_{i}, y⟩ ≤ δ_{i}. Thus, i ∈ A(y). We have shown that A(x) ⊂ A(y) if x ∈ ri {F } and y ∈ F. Hence, A(x) = A(y) if x and y belong to ri {F }.

This definition of A(F) is direct and intuitive. We now establish an alternative characterization of A(F). For the proof of this result we need to know that

− d ∈ ri {N(x)} ⟺ d = ∑_{i∈A(x)} λ_{i}c_{i}, λ_{i} > 0.  (5.1)

This characterization of ri {N(x)} is due to Burke and Moré [4, Lemma 3.2].

Lemma 5.1 If Ω is a polyhedral set, then

F = {x ∈ Ω : ⟨c_{i}, x⟩ = δ_{i}, i ∈ A(F)}

for any face F of Ω.

Proof. Every face of a polyhedron is exposed (see, for example, Theorem 2.4.12 of Stoer and Witzgall [23]), and thus F = E(−d) for some d ∈ IR^{n}. Hence, Theorem 2.4 implies that −d ∈ ri {N(F)}, and thus d ∈ ri {N(x)} for any x ∈ ri {F }. We now appeal to the characterization (5.1), and conclude that there are λ_{i} > 0 such that

d = ∑_{i∈A(x)} λ_{i}c_{i}, λ_{i} > 0.

A computation now shows that

E[−d] = {x ∈ Ω : ⟨c_{i}, x⟩ = δ_{i}, i ∈ A(x)} .

Since A(x) = A(F) and F = E[−d], this establishes the result.

This result characterizes A(F) as the set of active constraints that are essential for F. In view of this result, it is natural to investigate the properties of the active set of the exposed face E[−∇f(x^{∗})].

Definition. If Ω is a polyhedral set and x^{∗} is a stationary point of (1.1), then

B_{s}^{∗} = A(E[−∇f(x^{∗})])

is the set of strictly binding constraints at x^{∗}.

This definition requires justification because strictly binding constraints are usually associated with positive Lagrange multipliers; the following result provides this justification.

Theorem 5.2 Let f : IR^{n} → IR be continuously differentiable on the polyhedral set Ω defined by (4.3). If x^{∗} is a stationary point of (1.1) then

∇f(x^{∗}) = ∑_{j∈B∗ s} λ_{j}^{∗}c_{j},  λ_{j}^{∗} > 0,  (5.2)

for some set of positive Lagrange multipliers λ_{i}^{∗}.

Proof. Theorem 2.4 implies that −∇f(x^{∗}) ∈ ri {N(F)} for F = E[−∇f(x^{∗})]. Hence, −∇f(x^{∗}) ∈ ri {N(x)} for any x ∈ ri {F }. Since A(x) = B_{s}^{∗} for x ∈ ri {F }, the characterization (5.1) yields the result.

Theorem 5.2 justifies the definition of B_{s}^{∗} as the set of strictly binding constraints. This result is of interest because it does not make any nondegeneracy or linear independence assumptions. Note that if x^{∗} is nondegenerate then Theorem 4.3 shows that x^{∗} ∈ ri {E[−∇f(x^{∗})]}, and thus B_{s}^{∗} = A(x^{∗}). Hence, for nondegenerate x^{∗}, Theorem 5.2 is a direct consequence of (5.1) and the definition of nondegeneracy.

Theorem 5.3 Let f : IR^{n} → IR be continuously differentiable on the polyhedral set Ω defined by (4.3). If x^{∗} is a stationary point of (1.1) and {λ_{i}^{∗}} is any set of Lagrange multipliers, then the following three statements are equivalent.

1. x ∈ E[−∇f(x^{∗})].

2. {i ∈ A(x^{∗}) : λ_{i}^{∗} > 0} ⊂ A(x) for x ∈ Ω.

3. B_{s}^{∗} ⊂ A(x) for x ∈ Ω.

Proof. Theorem 4.4 shows that the first two statements are equivalent. The equivalence of the first and third statements is obtained by noting that Lemma 5.1 implies that

E[−∇f(x^{∗})] = {x ∈ Ω : ⟨c_{i}, x⟩ = δ_{i}, i ∈ B_{s}^{∗}} .

This result shows that Theorem 4.5 can be phrased in terms of B_{s}^{∗}. Another interesting consequence of Theorem 5.3 is obtained by choosing any x ∈ ri {E[−∇f(x^{∗})]} in the second statement in Theorem 5.3. This shows that

{i ∈ A(x^{∗}) : λ_{i}^{∗} > 0} ⊂ B_{s}^{∗}

for any set of Lagrange multipliers {λ_{i}^{∗}}. Hence, the indices in B_{s}^{∗} identify a maximal set of positive Lagrange multipliers.

6 Second-Order Sufficiency Conditions

We have shown that optimization algorithms tend to generate iterates such that

x_{k} ∈ E[−∇f(x^{∗})]

for all k sufficiently large. Another important component in the analysis of an optimization algorithm is to show that the iterates converge under suitable conditions. This type of result usually requires the assumption that the iterates {x_{k}} have an isolated limit point x^{∗}. This assumption is satisfied, for example, if x^{∗} is an isolated stationary point, that is, there is a neighborhood S(x^{∗}) such that x^{∗} is the only stationary point in S(x^{∗}) ∩ Ω. In this section we show that if the Hessian is positive definite in the cone generated by E[−∇f(x^{∗})] − x^{∗}, then the stationary point x^{∗} is isolated.

The assumption that x^{∗} is an isolated stationary point can be guaranteed by imposing second-order conditions on f. The following result uses a version of the second-order sufficiency conditions that is appropriate for problem (1.1) with a general convex set Ω.

Theorem 6.1 Let f : IR^{n} → IR be continuously differentiable on a closed convex set Ω and twice differentiable at a point x^{∗} in Ω. If x^{∗} is a stationary point of problem (1.1) and

⟨∇f(x^{∗}), w⟩ = 0, w ∈ T (x^{∗}), w ≠ 0 ⟹ ⟨w, ∇^{2}f(x^{∗})w⟩ > 0,  (6.1)

then x^{∗} is an isolated stationary point of f.

Theorem 6.1 is a special case of a result of Robinson [21, Theorem 2.4]. The proof of Theorem 6.1 is not difficult in our setting. Note that if x^{∗} is not an isolated stationary point, then there is a sequence {x_{k}} of stationary points converging to x^{∗}. In particular,

⟨∇f(x^{∗}), x_{k} − x^{∗}⟩ ≥ 0,  ⟨∇f(x_{k}), x^{∗} − x_{k}⟩ ≥ 0.  (6.2)

This implies that

⟨∇f(x_{k}) − ∇f(x^{∗}), x_{k} − x^{∗}⟩ ≤ 0.  (6.3)

Hence, if w is a limit point of the sequence {w_{k}} defined by

w_{k} = \frac{x_{k} − x^{∗}}{∥x_{k} − x^{∗}∥},

then (6.2) shows that ⟨∇f(x^{∗}), w⟩ = 0, while (6.3) shows that ⟨w, ∇^{2}f(x^{∗})w⟩ ≤ 0. Moreover, since w_{k} ∈ T (x^{∗}) and ∥w_{k}∥ = 1, we also have that w ∈ T (x^{∗}) and that ∥w∥ = 1. This contradicts (6.1).

For a polyhedral Ω, condition (6.1) coincides with the standard second-order sufficiency conditions. This observation follows by noting that if Ω is the set defined by (4.3) and

∇f(x^{∗}) = ∑_{j∈A(x^{∗})} λ_{j}^{∗}c_{j}, λ_{j}^{∗} ≥ 0,

then

{w ∈ IR^{n} : ⟨∇f(x^{∗}), w⟩ = 0, w ∈ T (x^{∗})} =
{w ∈ IR^{n} : ⟨c_{j}, w⟩ ≥ 0, j ∈ A(x^{∗}), ⟨c_{j}, w⟩ = 0, λ_{j}^{∗} > 0} .

For a general convex Ω, condition (6.1) has an advantage over the standard second-order sufficiency conditions because it is independent of the representation of Ω. On the other hand, an example of Burke, Moré, and Toraldo [5] shows that condition (6.1) does not take into account the curvature of Ω, and thus differs from the standard second-order sufficiency conditions.

If x^{∗} is a nondegenerate stationary point, then (6.1) can be expressed in terms of N(x^{∗})^{⊥} where for any set S the orthogonal complement S^{⊥} of S is the subspace of vectors v such that ⟨v, w⟩ = 0 for all w ∈ S. Indeed, Burke, Moré,, and Toraldo [5] prove that if x^{∗} is a nondegenerate stationary point, then

N(x^{∗})^{⊥} = { w ∈ T (x^{∗}) : ⟨∇f(x^{∗}), w⟩ = 0} .  (6.4)

These results are familiar when Ω is the polyhedral set defined by (4.3) because

N(x^{∗})^{⊥} = {v ∈ IR^{n} : ⟨c_{j}, v⟩ = 0, j ∈ A(x^{∗})}.

We now show that the second-order sufficiency condition can be expressed in terms of the exposed face E[−∇f(x^{∗})]. In this result, cone {S} is the cone spanned by the set S, that is, the set of vectors αw for some α ≥ 0 and w ∈ S.

Theorem 6.2 Let f : IR^{n} → IR be continuously differentiable on a polyhedral Ω and twice differentiable at a point x^{∗} in Ω. If x^{∗} is a stationary point of problem (1.1), then

{w ∈ T (x^{∗}) : ⟨∇f(x^{∗}), w⟩ = 0} = cone {E[−∇f(x^{∗})] − x^{∗}} .  (6.5)

Moreover, if

w ∈ cone {E[−∇f(x^{∗})] − x^{∗}} , w ≠ 0 ⟹ ⟨w, ∇^{2}f(x^{∗})w⟩ > 0,  (6.6)

then x^{∗} is an isolated stationary point of f.

Proof. The result follows from Theorem 6.1 if we establish (6.5). We first show that

cone {E[−∇f(x^{∗})] − x^{∗}} ⊂ {w ∈ T (x^{∗}) : ⟨∇f(x^{∗}), w⟩ = 0} .

If w ∈ cone {E[−∇f(x^{∗})] − x^{∗}}, then w = α(x − x^{∗}) for some x ∈ E[−∇f(x^{∗})]. Thus, since ⟨∇f(x^{∗}), ·⟩ is constant on E[−∇f(x^{∗})], we obtain that ⟨∇f(x^{∗}), w⟩ = 0. Moreover, since x ∈ Ω, it is clear that w ∈ T (x^{∗}). For the reverse inclusion assume that ⟨∇f(x^{∗}), w⟩ = 0 for some w ∈ T (x^{∗}). Since w ∈ T (x^{∗}) and Ω is polyhedral, x^{∗} + αw ∈ Ω for all α > 0 sufficiently small. Moreover, since ⟨∇f(x^{∗}), w⟩ = 0, it follows that x^{∗} + αw ∈ E[−∇f(x^{∗})]. Thus, w ∈ cone {E[−∇f(x^{∗})] − x^{∗}} as desired.

We have already noted that if x^{∗} is nondegenerate, then (6.4) holds. This implies, in particular, that

{w ∈ T (x^{∗}) : ⟨∇f(x^{∗}), w⟩ = 0}

is a subspace. In view of (6.5), we have shown that if x^{∗} is nondegenerate then the secondorder condition (6.1) reduces to the assumption that ∇^{2}f(x^{∗}) is positive definite on the subspace aff {E[−∇f(x^{∗})] − x^{∗}}. In the context of algorithms, the fact that (6.5) is a subspace is extremely helpful. However, the same effect can be obtained without assuming nondegeneracy if one is willing to strengthen the second-order sufficiency condition.

Definition. Let f : IR^{n} → IR be twice differentiable at x^{∗} ∈ Ω. The strong second-order sufficiency condition for problem (1.1) is satisfied at a stationary point x^{∗} if ∇^{2}f(x^{∗}) is positive definite on the subspace aff {E[−∇f(x^{∗})] − x^{∗}}, that is,

w ∈ aff {E[−∇f(x^{∗})] − x^{∗}} , w ≠ 0 ⟹ ⟨w, ∇^{2}f(x^{∗})w⟩ > 0.  (6.7)

If the strong second-order sufficiency condition (6.7) holds, then the standard second-order sufficiency condition (6.1) must also hold because

cone {E[−∇f(x^{∗})] − x^{∗}} ⊂ aff {E[−∇f(x^{∗})] − x^{∗}} .

The following example shows that the converse can fail even if f is quadratic.

Example. Let f : IR^{2} → IR be given by

f(ξ_{1}, ξ_{2}) = ξ_{1}^{2} + 4ξ_{1}ξ_{2} + ξ_{2}^{2},

and let Ω ⊂ IR^{2} be given by

Ω = {(ξ_{1}, ξ_{2}) ∈ IR^{2} : ξ_{1} ≥ 0, ξ_{2} ≥ 0} .

For this problem x^{∗} = (0, 0) is the global minimum of f over Ω. Note that ∇f(x^{∗}) = 0, and thus E[−∇f(x^{∗})] = Ω. Hence,

cone {E[−∇f(x^{∗})] − x^{∗}} = IR_{+}^{2}, aff {E[−∇f(x^{∗})] − x^{∗}} = IR^{2}.

A computation shows that the standard second-order sufficiency condition (6.1) holds at x^{∗}. However, it is clear that the strong second-order sufficiency condition (6.7) is not satisfied at x^{∗} because ∇^{2}f(x^{∗}) is not positive definite.

Other authors have used the term strong second-order sufficiency condition to mean that

⟨c_{j}, w⟩ = 0, λ_{j}^{∗} > 0, w ≠ 0 ⟹ ⟨w, ∇^{2}f(x^{∗})w⟩ > 0.  (6.8)

For example, Gay [14], Lescrenier [17], and Robinson [20] use this condition in their analysis of the convergence behavior of algorithms. A disadvantage of condition (6.8) is that it depends on the representation of Ω and the choice of multipliers. The following example shows that condition (6.8) is stronger than (6.7) even if f is a quadratic.

Example. Let f : IR^{3} → IR be given by

f(ξ_{1}, ξ_{2}, ξ_{3}) = ξ_{3}^{2} − ξ_{2}^{2} + ξ_{3},

and let Ω = {x ∈ IR^{3} : ⟨c_{i}, x⟩ ≥ 0, 1 ≤ i ≤ 4} be the cone with vertex at the origin, where

c_{1} = e_{1}, c_{2} = e_{2}, c_{3} = e_{3} − e_{1}, c_{4} = e_{3} − e_{2}.

For this problem x^{∗} = (0, 0, 0) is the global minimum of f over Ω. A computation shows that E[−∇f(x^{∗})] = {x^{∗}}, and thus the strong second-order condition (6.7) holds. However, condition (6.8) does not hold if we choose λ_{2}^{∗} = λ_{4}^{∗} = 0.

This example shows that condition (6.8) is stronger than (6.7) for some set of multipliers. On the other hand, the following result shows that there is a set of multipliers such that condition (6.8) is equivalent to (6.7).

Theorem 6.3 Let f : IR^{n} → IR be continuously differentiable on the polyhedral set Ω defined by (4.3). If x^{∗} is a stationary point of (1.1), then

aff {E[−∇f(x^{∗})] − x^{∗}} = {v ∈ IR^{n} : ⟨c_{j}, v⟩ = 0, j ∈ B_{s}^{∗}} ,

where B_{s}^{∗} is the set of strictly binding constraints defined in Section 5.

Proof. If v ∈ E[−∇f(x^{∗})] − x^{∗}, then ⟨∇f(x^{∗}), v⟩ = 0, because ⟨∇f(x^{∗}), ·⟩ is constant on E[−∇f(x^{∗})]. Moreover, since v is a feasible direction, ⟨c_{j}, v⟩ ≥ 0 for j ∈ A(x^{∗}). Now recall that Theorem 5.2 guarantees that (5.2) holds. Hence,

0 = ⟨∇f(x^{∗}), v⟩ = ∑_{j∈B∗ s} λ_{j}^{∗}⟨c_{j}, v⟩ ≥ 0.

This implies that ⟨c_{j}, v⟩ = 0 when j ∈ B_{s}^{∗}. Thus, we have shown that

E[−∇f(x^{∗})] − x^{∗} ⊂ {v ∈ IR^{n} : ⟨c_{j}, v⟩ = 0, j ∈ B_{s}^{∗}} .

Hence,

aff {E[−∇f(x^{∗})] − x^{∗}} ⊂ {v ∈ IR^{n} : ⟨c_{j}, v⟩ = 0, j ∈ B_{s}^{∗}} .  (6.9)

For the reverse inclusion choose any x_{0} ∈ ri {E[−∇f(x^{∗})]}. If ⟨c_{j}, v⟩ = 0 for j ∈ B_{s}^{∗}, then v is a feasible direction because B_{s}^{∗} = A(x_{0}). Hence x_{0} + αv ∈ Ω for all α > 0 sufficiently small. Moreover, (5.2) implies that

⟨∇f(x^{∗}), x + αv⟩ = ⟨∇f(x^{∗}), x⟩.

This shows that x_{0} + αv ∈ E[−∇f(x^{∗})]. We have established that

{v ∈ IR^{n} : ⟨c_{j}, v⟩ = 0, j ∈ B_{s}^{∗}} ⊂ E[−∇f(x^{∗})] − x_{0}.

Hence,

dim {v ∈ IR^{n} : ⟨c_{j}, v⟩ = 0, j ∈ B_{s}^{∗}} ≤ dim {E[−∇f(x^{∗})]} .

Since we have already established (6.9), this completes the proof.

7 Algorithms

Theorem 4.5 is an important tool for the convergence analysis of optimization algorithms. In this section we examine the use of Theorem 4.5 in the GPCG algorithm of Moré and Toraldo [19]. In particular, we show that the convergence condition of the GPCG algorithm is satisfied in a finite number of iterations even when the solution is degenerate.

The GPCG algorithm uses a combination of the gradient projection algorithm and the conjugate gradient algorithm to solve large-scale problems of the form

min{q(x) : l ≤ x ≤ u}.  (7.1)

The GPCG algorithm uses the conjugate gradient method to explore the active set

A(x) = {i : x_{i} ∈ {l_{i}, u_{i}}}  (7.2)

defined by the current iterate. Once this exploration is completed, the gradient projection method is used to choose a new active set. The convergence properties of algorithm GPCG are summarized in the following result of Moré and Toraldo [19].

Theorem 7.1 Let q : IR^{n} → IR be a strictly convex quadratic. If {x_{k}} is the sequence generated by algorithm GPCG for problem (7.1), then either {x_{k}} terminates at the solution x^{∗} in a finite number of iterations, or {x_{k}} converges to the solution x^{∗} of problem (7.1). If the solution x^{∗} of problem (7.1) satisfies the nondegeneracy condition

∂_{i}q(x^{∗}) ≠ 0, i ∈ A(x^{∗}),

then algorithm GPCG terminates at the solution x^{∗} in a finite number of iterations.

This convergence result is not entirely satisfactory when the solution x^{∗} is degenerate, because it does not show that the convergence test is satisfied in a finite number of iterations. Given a starting point x_{0} in the feasible region Ω = {x ∈ IR^{n} : l ≤ x ≤ u} and a tolerance τ > 0, the convergence test of the GPCG algorithm requires that

∥∇_{Ω}q(x_{k})∥ ≤ τ∥∇q(x_{0})∥,  (7.3)

where ∇_{Ω}q is defined by

[∇_{Ω}q(x)]_{i} = \{ \begin{matrix}∂_{i}q(x) & if x_{i} ∈ (l_{i}, u_{i}) \\ min\{∂_{i}q(x), 0\} & if x_{i} = l_{i} \\ max\{∂_{i}q(x), 0\} & if x_{i} = u_{i} \end{matrix} .

This convergence test is closely related to (4.6) because

∇_{Ω}q(x) = −P_{T (x)} [−∇f(x)].

In particular, if (4.6) holds, then the convergence test (7.3) is satisfied after a finite number of iterations. In the remainder of this section we show that (4.6) holds.

Given the current iterate x_{k}, algorithm GPCG explores the active set defined by the current iterate by computing an approximate minimizer of the subproblem

min{q(x_{k} + d) : d_{i} = 0, i ∈ A(x_{k})}.  (7.4)

Given an approximate minimizer d_{k} of subproblem (7.4), algorithm GPCG uses a projected search to choose a search parameter α_{k} such that q(x_{k+1}) < q(x_{k}), where

x_{k+1} = P (x_{k} + α_{k}d_{k})

and P is the projection into the feasible region Ω. Details on the projected search can be found in the paper of Moré and Toraldo [19]. For this paper it is necessary to note only that since the i-th coordinate is zero when i ∈ A(x_{k}), we obtain that

A(x_{k}) ⊂ A(x_{k+1})  (7.5)

holds whenever algorithm GPCG explores the active set defined by the current iterate.

The approximate minimizer d_{k} of subproblem (7.4) is obtained by first noting that if i_{1}, …, i_{m_{k}} are the indices of the free variables, that is, those variables with indices outside of A(x_{k}), then subproblem (7.4) is equivalent to the unconstrained subproblem

min{q_{k}(w) : w ∈ IR^{m_{k}}},  (7.6)

where q_{k} : IR^{m_{k}} → IR is defined by q_{k}(w) ≡ q(x_{k} + Z_{k}w), and Z_{k} is the matrix in IR^{n×m_{k}} whose j-th column is the i_{j}-th column of the identity matrix in IR^{n×n}. Given the starting point w_{0} = 0 in IR^{m_{k}}, the conjugate gradient algorithm generates a sequence of iterates {w_{j_{k}}}. The approximate solution of subproblem (7.4) is then d_{k} = Z_{k}w_{j_{k}} for some j_{k} ≥ 0.

If the iterate x_{k+1} generated by the conjugate gradient method appears to have identified the active set defined by the solution, then algorithm GPCG explores this active set further. The decision to continue the conjugate gradient method is based on the observation that if A(x) = A(x^{∗}), then the binding set

B(x) = {i : x_{i} = l_{i} and ∂_{i}q(x) ≥ 0, or x_{i} = u_{i} and ∂_{i}q(x) ≤ 0}

agrees with the active set A(x). Thus, if the conjugate gradient method produces an iterate x_{k+1} such that B(x_{k+1}) = A(x_{k+1}), then algorithm GPCG continues to use the conjugate gradient method to explore this active set. The finite termination properties of the conjugate gradient algorithm show that at most m_{k} iterations are needed before the conjugate gradient algorithm finds a solution of subproblem (7.4); at this point there would be no need to explore this active set further.

Once the conjugate gradient algorithm has explored an active set, algorithm GPCG uses the gradient projection method

y_{k+1} = P [y_{k} − α_{k}∇q(y_{k})]

with y_{0} = x_{k} to select a new active set. The GPCG algorithm sets x_{k+1} = y_{j_{k}} for some j_{k} ≥ 0. Additional details on the implementation of the gradient projection method can be found in the paper of Moré and Toraldo [19].

We now use Theorem 4.5 to prove that (4.6) holds for the iterates generated by algorithm GPCG. The proof consists of showing that condition (4.7) holds. For the bound constrained problem (7.1), condition (4.7) is just that

B_{s}^{∗} ≡ {i ∈ A(x^{∗}) : ∂_{i}q(x^{∗}) ≠ 0} ⊂ A(x_{k}), k ≥ k_{0},

where B_{s}^{∗} is the set of strictly binding constraints at x^{∗} defined in Section 5.

Theorem 7.2 Let q : IR^{n} → IR be a strictly convex quadratic. If {x_{k}} is the sequence generated by algorithm GPCG for problem (7.1), then either {x_{k}} terminates at the solution x^{∗} in a finite number of iterations, or there is an index k_{0} such that the convergence test (7.3) is satisfied for all k ≥ k_{0}.

Proof. Theorem 7.1 shows that either {x_{k}} terminates at the solution x^{∗} in a finite number of iterations, or {x_{k}} converges to x^{∗}. The result follows if {x_{k}} terminates at the solution x^{∗}, so we assume that {x_{k}} converges to x^{∗}. Let K_{GP} be the set of indices k such that x_{k+1} is generated by the gradient projection method. Theorem 5.2 of Calamai and Moré [6] shows that

lim_{k∈K_{GP} ,k→∞} P_{T (x_{k+1})} [−∇q(x_{k+1})] = 0.

Hence, Theorem 4.6 shows that

B_{s}^{∗} ⊂ A(x_{k+1})

if k ∈ K_{GP} if k is sufficiently large. Moreover, since (7.5) holds whenever the conjugate gradient method is used to explore the current active set, we immediately obtain that

B_{s}^{∗} ⊂ A(x_{k})

holds for all sufficiently large indices k. Hence, (4.7) holds, and thus Theorem 4.5 shows that (4.6) holds as desired.

Acknowledgments. We thank Stephen Wright for his interesting example in Section 4 of a degenerate optimization problem where the active set does not settle down. We are also grateful to Gail Pieper for her gentle comments on the manuscript.

References

[1] D. P. Bertsekas, On the Goldstein–Levitin–Polyak gradient projection method, IEEE Trans. Automat. Control, 21 (1976), pp. 174–184.

[2] , Projected Newton methods for optimization problems with simple constraints, SIAM J. Control Optim., 20 (1982), pp. 221–246.

[3] J. V. Burke, On the identification of active constraints II: The nonconvex case, SIAM J. Numer. Anal., 27 (1990), pp. 1081–1102.

[4] J. V. Burke and J. J. Moré, On the identification of active constraints, SIAM J. Numer. Anal., 25 (1988), pp. 1197–1211.

[5] J. V. Burke, J. J. Moré, and G. Toraldo, Convergence properties of trust region methods for linear and convex constraints, Math. Programming, 47 (1990), pp. 305–336.

[6] P. H. Calamai and J. J. Moré, Projected gradient methods for linearly constrained problems, Math. Programming, 39 (1987), pp. 93–116.

[7] A. R. Conn, N. I. M. Gould, and P. L. Toint, Global convergence of a class of trust region algorithms for optimization problems with simple bounds, SIAM J. Numer. Anal., 25 (1988), pp. 433–460.

[8] , Testing a class of methods for solving minimization problems with simple bounds on the variables, Math. Comp., 50 (1988), pp. 399–430.

[9] J. C. Dunn, Global and asymptotic convergence rate estimates for a class of projected gradient processes, SIAM J. Control Optim., 19 (1981), pp. 368–400.

[10] , On the convergence of projected gradient processes to singular critical points, J. Optim. Theory Appl., 55 (1987), pp. 203–216.

[11] , A projected Newton method for minimization problems with nonlinear inequality constraints, Numer. Math., 53 (1988), pp. 377–410.

[12] E. M. Gafni and D. P. Bertsekas, Convergence of a gradient projection method, Report LIDS-P-1201, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, Cambridge, Massachusetts, 1982.

[13] , Two-metric projection methods for constrained optimization, SIAM J. Control Optim., 22 (1984), pp. 936–964.

[14] D. M. Gay, A trust region approach to linearly constrained optimization, in Numerical Analysis, D. F. Griffiths, ed., Lecture Notes in Mathematics 1066, Springer-Verlag, 1984, pp. 72–105.

[15] J. L. Goffin, The relaxation method for solving systems of linear inequalities, Math. Oper. Res., 5 (1980), pp. 388–414.

[16] C. T. Kelley and E. W. Sachs, Mesh independence of the gradient projection method for optimal control problems, SIAM J. Control Optim., 30 (1992), pp. 477–493.

[17] M. Lescrenier, Convergence of trust region algorithms for optimization with bounds when strict complementarity does not hold, SIAM J. Numer. Anal., 28 (1991), pp. 476– 495.

[18] J. J. Moré, Trust regions and projected gradients, in Systems Modelling and Optimization, M. Iri and K. Yajima, eds., Lecture Notes in Control and Information Sciences 113, Springer-Verlag, 1988, pp. 1–13.

[19] J. J. Moré and G. Toraldo, Algorithms for bound constrained quadratic programming problems, Numer. Math., 55 (1989), pp. 377–400.

[20] S. M. Robinson, Strongly regular generalized equations, Math. Oper. Res., 5 (1980), pp. 43–62.

[21] , Generalized equations and their solutions, part II: Applications to nonlinear programming, Math. Programming Stud., 19 (1982), pp. 200–221.

[22] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970.

[23] J. Stoer and C. Witzgall, Convexity and Optimization in Finite Dimensions I, Springer-Verlag, 1970.

[24] S. J. Wright, Implementing proximal point methods for linear programming, J. Optim. Theory Appl., 65 (1990), pp. 531–554.

[25] , Identifiable surfaces in constrained optimization, SIAM J. Control Optim., (1992). to appear.

[26] E. H. Zarantonello, Projections on convex sets in Hilbert space and spectral theory, in Contributions to Nonlinear Functional Analysis, E. H. Zarantonello, ed., Academic Press, 1971, pp. 237–424.