IDENTIFIABLE SURFACES IN CONSTRAINED OPTIMIZATION^{∗}

STEPHEN J. WRIGHT^{†}

PREPRINT MCS–P261–0891, MCS DIVISION, ARGONNE NATIONAL LABORATORY

Abstract. The concept of a “class-C^{p} identifiable surface” of a convex set in Euclidean space in introduced. We show how the smoothness of these surfaces is related to the smoothness of the projection operator, and present finite identification results for certain algorithms for minimization of a function over this set. The work uses a partially geometric view of constrained optimization to generalize previous finite identification results.

Key words. Constrained optimization, active set identification

AMS(MOS) subject classifications. 90C25, 53A07, 26B10

1. Introduction. Here, we investigate the problem

min_{x∈Ω} F (x), (1)

where F is continuously differentiable, and Ω ⊂ R l ^{n} is closed and convex. In particular, we are interested in finding subsets of Ω that can be identified by an optimization algorithm after a finite number of iterations. That is, if the solution x^{∗} lies in one such subset, the iterates generated by the algorithm should eventually enter and remain within that subset. In the case in which Ω is defined by a set of algebraic inequalities, this property of the iterates corresponds to identifying the active constraints, and when Ω is a polyhedron, it means identifying the edge, or corner, upon which the solution x^{∗} lies.

The first-order conditions for x^{∗} to be a solution of (1) are

−∇F (x^{∗}) ∈ N(x^{∗}),

where N(x^{∗}) is the normal cone to Ω at x^{∗}. To prove the finite identification (“capture”) results, we assume a nondegeneracy condition due to Dunn [3]. This is stated simply as

− ∇F (x^{∗}) ∈ ri(N(x^{∗})), (2)

where ri(Λ) is the relative interior of Λ ⊂ R l ^{n}, that is, the interior of Λ relative to aff(Λ), the affine hull of Λ. This condition, which is a geometric generalization of the strict complementarity condition of nonlinear programming, has been used in the convergence analysis of Dunn [3] and Burke and Moré [1]. Both these papers specify similar classes of subsets of Ω that are finitely identifiable by gradient projection and Newton-like algorithms. We define these “open facets” as in [3]:

Definition 1.

a) For any closed convex cone K ⊂ R l ^{n}, we use K^{∘} to denote the polar of K, and define the lineality lin(K) to be (K^{∘})^{⊥};

b) Let T (x) and N(x) denote the tangent and normal cones, respectively, to Ω at x, as defined in Clarke [2]. A nonempty subset S ⊂ Ω is an open facet if the set V = x + lin(T (x)) is independent of x ∈ S, and S = int_{V} (Ω ∩ V), where int_{V} (.) denotes interior with respect to V.

∗ This research was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U. S. Department of Energy, under Contract W-31-109-Eng-38.

† Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL 60439.

It is easy to show that open facets are convex. When Ω is polyhedral, it can be partitioned into open facets, but when Ω has some curved boundaries, this is not the case. As an example, consider the set defined in [1, equation (2.2)]:

Ω_{1} = \{(ξ_{1}, ξ_{2}) | ξ_{2} ≤ \sqrt{1 − ξ_{1}^{2}}, 0 ≤ ξ_{1} ≤ 1\}.

The open facets in this set are its interior, the point (0, 1) and the edges {(0, ξ_{2}) | ξ_{2} < 1} and {(1, ξ_{2}) | ξ_{2} < 0}. No subset of the curved face {(ξ_{1}, ξ_{2}) | ξ_{1}^{2} + ξ_{2}^{2} = 1, 0 < ξ_{1} ≤ 1} satisfies Definition 1.

When Ω is defined by algebraic inequalities, that is,

Ω = {ξ | g_{i}(ξ) ≤ 0, i = 1, ⋯, m}, (3)

it is often assumed that the g_{i} are C^{2} and that the set

{∇g_{i}(x) | i ∈ A(x)},  where  A(x) = {i | 1 ≤ i ≤ m, g_{i}(x) = 0} (4)

is linearly independent. In this case, the nondegeneracy condition (2) (which reduces to the standard strict complementarity condition) ensures that surfaces defined by a particular active index set A ⊂ {1, 2, ⋯, m} are finitely identifiable by a number of standard algorithms. Note that Ω_{1} is not definable in the form (3),(4) for g_{i} ∈ C^{2}, since there is a curvature discontinuity in the boundary at (1, 0). If we allow g_{i} to be only C^{1}, then Ω_{1} is definable as (3),(4), but then the curved surface is indistinguishable from the face {(1, ξ_{2}) | ξ_{2} ≤ 0}.

In the next section, we define the concept of a “class-C^{p} identifiable surface.” Loosely speaking, such a surface S is usually a connected “patch” on ∂Ω which is locally parametrizable by a collection of C^{p} functions, for some integer p ≥ 1. (The interior of Ω is defined to be a class-C^{∞} surface.) Moreover, these functions can be defined so that their gradients can “enclose” any given ray in the relative interior of N(x), where x is a given point in S. We prove that open facets, and subsets of (3) that are defined by particular choices of A, are identifiable surfaces. (For the set Ω_{1}, the curved boundary, with its two endpoints excluded, is also an identifiable surface.) We show that class-C^{p} identifiable surfaces generate connected open regions in the exterior of Ω, within which the operation of projection onto Ω is p − 1 times continuously differentiable. In Section 3, we prove finite identification results for gradient projection and Newton-like algorithms.

In the remainder of the paper, ∥.∥ denotes the Euclidean norm. P denotes the projection operator; that is, ȳ = P (y) solves

min_{ȳ∈Ω} \frac{1}{2}∥ȳ − y∥^{2}.

(The notation ȳ = P (y) is used frequently.) B denotes the unit ball {ξ ∈ R l ^{n} | ∥ξ∥ ≤ 1}, and co(.) denotes the convex hull of a set of vectors.

2. Identifiable Surfaces and Smoothness of the Projection Operator. Throughout the remainder of the paper, we make the following assumption:

Assumption 1. Ω is closed and convex and has an interior in R l ^{n}. The last part of this assumption is made for convenience. If it does not hold, the results of this section can be recovered by restricting attention to aff(Ω).

Definition 2. A connected set S ⊂ Ω is a class-C^{p} identifiable surface, p a positive integer, if either a) S is an open subset of int(Ω), or

b) S ⊂ ∂Ω, and for any y ∈ R l ^{n}\Ω such that ȳ = P (y) ∈ S and y − ȳ ∈ ri(N(ȳ)), there exist functions g_{i}, i = 1, ⋯, r = r(y), and a constant ϵ = ϵ(y) > 0, such that

(i) g_{i} ∈ C^{p}(ȳ + ϵB); (ii) {∇g_{i}(ȳ), i = 1, ⋯, r} is linearly independent;

(iii) co{∇g_{i}(z̄), i = 1, ⋯, r} ⊂ N(z̄) for all z̄ ∈ S(ȳ; ϵ), and =^{△} (ȳ + ϵB) ∩ S;

(iv) y − ȳ ∈ ri [co{∇g_{i}(ȳ), i = 1, ⋯, r}]; and

(v) S(ȳ; ϵ) = {z̄ | ∥z̄ − ȳ∥ ≤ ϵ, g_{i}(z̄) = 0, i = 1, ⋯, r}. Obviously, if S is a class-C^{p} identifiable surface, then it is also a class-Cp̄ identi-

fiable surface, for any p̄ with 1 ≤ p̄ < p.

In what follows, we frequently use the notation

∇g(x) = [∇g_{1}(x)| ⋯ |∇g_{r}(x)] .

Before proceeding, to give a “feel” for how this definition differs from that of open facets and from (3), we review the example Ω_{1} from section 1, and give two more examples. The interior of Ω_{1}, the point (0, 1) and the edge {(0, ξ_{2}) | ξ_{2} < 1} are class-C^{∞} identifiable surfaces. The remaining surface defined by

\{(ξ_{1}, ξ_{2}) | ξ_{2} = \sqrt{1 − ξ_{1}^{2}}, 0 ≤ ξ_{1} < 1\} ∩ \{(1, ξ_{2}) | ξ_{2} < 0\} ∩ \{(1, 0)\}

is class-C^{1} identifiable. Each of the first two component subsets is class-C^{∞} identifiable.

Another example is an inverted cone in R l ^{3}, whose apex is at the origin:

Ω_{2} = \{(ξ_{1}, ξ_{2}, ξ_{3}) | ξ_{3} ≥ \sqrt{ξ_{1}^{2} + ξ_{2}^{2}}, 0 ≤ ξ_{3} ≤ 1\}.

Ω_{2} has just three maximal open facets: the point (0, 0, 0), the circular face {(ξ_{1}, ξ_{2}, 1) | ξ_{1}^{2}+ ξ_{2}^{2} < 1}, and the interior. A finite algebraic parametrization (3),(4) is apparently not possible, even if we allow g_{i} ∈ C^{1} (the difficulty is, of course, at the apex). However, the whole set can be partitioned into five maximal class-C^{∞} identifiable surfaces. They are the three open facets just mentioned, the circle {(ξ_{1}, ξ_{2}, 1) | ξ_{1}^{2} + ξ_{2}^{2} = 1}, and the curved face \{(ξ_{1}, ξ_{2}, ξ_{3}) | ξ_{3} = \sqrt{ξ_{1}^{2} + ξ_{2}^{2}}, 0 < ξ_{3} < 1\}. To show how the definition is satisfied in the case of (0, 0, 0), take some y ∈ int(N(0, 0, 0)). Then y = (y_{1}, y_{2}, y_{3}), with y_{3} < −\sqrt{y_{1}^{2} + y_{2}^{2}}. Clearly, we can choose γ > 0 such that y + γB ⊂ int(N(0, 0, 0)). Define three vectors as follows:

y^{(1)} = (y_{1} + γ, y_{2}, y_{3})
y^{(2)} = (y_{1} − (1/2)γ, y_{2} + (\sqrt{3}/2)γ, y_{3})
y^{(3)} = (y_{1} − (1/2)γ, y_{2} − (\sqrt{3}/2)γ, y_{3}).

Elementary manipulation shows that these are linearly independent and that y = (1/3)(y^{(1)} + y^{(2)} + y^{(3)}). If we define g_{i}(z) = z^{T} y^{(i)}, the five conditions in Definition 2 are easily verified.

A final example is the set

Ω_{3} = {(ξ_{1}, ξ_{2}, ξ_{3}) | ξ_{3} ≥ ξ_{1}^{2} + |ξ_{2}| + ξ_{2}^{4/3}}.

This set is representable in the form (3),(4) by splitting the inequality into two (for the two possibilities |ξ_{2}| = ±ξ_{2}), but the g_{i} are only C^{1}. There are no open facets, except the interior. However, the set can be partitioned into four class-C^{∞} identifiable surfaces. These are the interior, the face defined by

{(ξ_{1}, ξ_{2}, ξ_{3}) | ξ_{2} > 0, ξ_{3} = ξ_{1}^{2} + ξ_{2} + ξ_{2}^{4/3}}

and its counterpart

{(ξ_{1}, ξ_{2}, ξ_{3}) | ξ_{2} < 0, ξ_{3} = ξ_{1}^{2} − ξ_{2} + ξ_{2}^{4/3}},

and the ridge

{(ξ_{1}, 0, ξ_{3}) | ξ_{3} = ξ_{1}^{2}}.

The ridge can be made to fit the definition by taking

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

independently of the choice of y ∈ ri(N(ξ)).

The concept of a class-C^{p} identifiable surface is, in a certain sense, a generalization of the concept of a class-C^{p,α} boundary of a bounded domain Ω ⊂ R l ^{n}, as used extensively in the theory of partial differential equations (see, for example, the definition on page 94 of Gilbarg and Trudinger [6]). In fact, if Ω is convex, closed and bounded, and its boundary ∂Ω is of class-C^{p,0} according to the latter definition, then it can be partitioned into a class-C^{∞} identifiable surface (int(Ω)) and a class-C^{p} identifiable surface (∂Ω). Such sets have no “edges” or “corners” — the value of r corresponding to each y ∈ R l ^{n}\Ω is 1 — and hence they are not very interesting from the viewpoint of this paper.

We now derive some elementary properties of identifiable surfaces, and the functions g_{i} that are used to describe them. We focus on the case S ⊂ ∂Ω, since the corresponding results for S ⊂ int(Ω) are trivial.

Lemma 2.1. Let S be a class-C^{p} identifiable surface with S ⊂ ∂Ω and p ≥ 1, and let y ∈ R l ^{n}\Ω be such that ȳ = P (y) ∈ S and y − ȳ ∈ ri(N(ȳ)). Suppose that r = r(y) and that the g_{i}, i = 1, ⋯, r are chosen as in Definition 2. Then

(i) T_{S}(ȳ) = {s | s^{T} ∇g_{i}(ȳ) = 0, i = 1, ⋯, r}, where T_{S}(.) is the tangent cone with respect to S, as defined in [2];

(ii) lin(T (ȳ))^{⊥} = aff(N(ȳ)) = span{∇g_{i}(ȳ) | i = 1, ⋯, r} = T_{S}(ȳ)^{⊥}; and (iii) if p ≥ 2, the projection of ∇^{2}g_{i}(ȳ) onto T_{S}(ȳ) is positive semidefinite. Proof.

(i) This is a standard result which follows easily from Definition 2.

(ii) We prove the second equality. By Definition 2(iii), span{∇g_{i}(ȳ) | i = 1, ⋯, r} ⊂ aff(N(ȳ)). Since both sets are subspaces, the containment can be strict only if there is some v ∈ aff(N(ȳ)) with v ≠ 0 such that v^{T} ∇g_{i}(ȳ) = 0, i = 1, ⋯, r, that is, v ∈ T_{S}(ȳ). Clearly, also, −v ∈ T_{S}(ȳ). Since T_{S}(ȳ) ⊂ T (ȳ), it follows that v and −v are in T (ȳ), and hence v ∈ lin(T (ȳ)) = N(ȳ)^{⊥}. Hence 0 ≠ v ∈ aff(N(ȳ)) ∩ N(ȳ)^{⊥}, giving a contradiction. The remaining equalities follow from part (i) of the Theorem and

lin(T (ȳ)) = N(ȳ)^{⊥} = aff(N(ȳ))^{⊥} = T_{S}(ȳ).

(iii) Let v ∈ T_{S}(ȳ), and suppose for contradiction that v^{T} ∇^{2}g_{i}(ȳ)v < 0. There are sequences v_{j} → v and {t_{j}} with 0 < t_{j} ∈ R l , t_{j} → 0, such that ȳ + t_{j}v_{j} ∈ S ⊂ Ω, so g_{i}(ȳ + t_{j}v_{j}) = 0, i = 1, ⋯, r. Since ∇g_{i}(ȳ) ∈ N(ȳ), we have

∇g_{i}(ȳ)^{T} t_{j}v_{j} ≤ 0, and so
0 = g_{i}(ȳ + t_{j}v_{j})
= g_{i}(ȳ) + ∇g_{i}(ȳ)^{T} (t_{j}v_{j}) + \frac{1}{2}t_{j}^{2}v_{j}∇^{2}g_{i}(v̂_{j})v_{j},
where v̂_{j} ∈ [ȳ, ȳ + t_{j}v_{j}]. Hence

v_{j}^{T} ∇^{2}g_{i}(v̂_{j})v_{j} = −\frac{2}{t_{j}} v_{j}^{T} ∇g_{i}(ȳ) ≥ 0.

For j sufficiently large,

0 > \frac{1}{2}v^{T} ∇^{2}g_{i}(ȳ)v ≥ v_{j}^{T} ∇^{2}g_{i}(v̂_{j})v_{j} ≥ 0,

giving a contradiction.

The next result, which will be useful when we come to prove finite identification properties for constrained optimization algorithms, shows that the direct sum of an identifiable surface S and the relative interior of the normal cones along S, is a set that is open in R l ^{n}. This property is analogous to that described for open facets in Theorem 2.8 of Burke and Moré [1].

Lemma 2.2. Suppose that S is as in Lemma 2.1 with p ≥ 2. Define the set

K = {x + w | x ∈ S, w ∈ ri(N(x))}.

For each y ∈ K, there is a δ ∈ (0, ϵ(y)] such that y + δB ⊂ K, that is, K is open in R l ^{n}.

Proof. Given y, let r = r(y), ϵ = ϵ(y), and g_{i}, i = 1, ⋯, r be chosen as in Definition 2. Initially, choose δ_{1} > 0 such that δ_{1} ≤ ϵ and y + δ_{1}B ∩ Ω = ∅. Choose some u ∈ y + δ_{1}B. Then ū = P (u) solves

min_{ū∈Ω} \frac{1}{2}∥u − ū∥_{2}^{2} ≡ min_{ū∈∂Ω} \frac{1}{2}∥u − ū∥_{2}^{2}.

Since P (.) is nonexpansive, ∥ū − ȳ∥ ≤ δ_{1} ≤ ϵ. Suppose for the moment that ū ∈ S. By Definition 2(v), ū solves

min_{ū} \frac{1}{2}∥u − ū∥_{2}^{2}, g_{i}(ū) = 0, i = 1, ⋯, r, ∥ū − ȳ∥ ≤ ϵ.

First-order conditions for a solution of this subproblem are that there is λ^{u} ∈ R l ^{r} such that

u − ū − ∇g(ū)λ^{u} = 0, λ^{u} ≥ 0,
g_{i}(ū) = 0, i = 1, ⋯, r.

By Definition 2 (ii),(iv),(v), we know that there is λ > 0 such that

y − ȳ − ∇g(ȳ)λ = 0,
(5)  g_{i}(ȳ) = 0, i = 1, ⋯, r.

The implicit function theorem requires that

[ \begin{matrix}I + ∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(ȳ) & ∇g(ȳ) \\ ∇g(ȳ)^{T} & 0 \end{matrix} ]

be nonsingular and continuous with respect to ȳ and λ. This follows from Definition 2(i) and Lemma 2.1(iii). Hence there is δ ∈ (0, δ_{1}] such that

∥u − y∥ ≤ δ ⇒ λ^{u} > 0, ∥ū − ȳ∥ ≤ ϵ.

By Definition 2(iii), we have found a ū ∈ S ⊂ Ω with u − ū ∈ N(ū), and so, by uniqueness of the operation of projection onto a convex set, ū = P (u). In fact, since λ^{u} > 0, we have

u − ū ∈ ri (co{∇g_{i}(ū), i = 1, ⋯, r}) ⊂ ri(N(ū)),

and so u ∈ K, as required.

In the following two results, we show that the notion of an open facet and, for Ω defined by (3),(4), the notion of a set of active indices, can both be expressed in terms of the notion of an identifiable surface.

Theorem 2.3. Let S be an open facet in Ω. Then S is a class-C^{∞} identifiable surface.

Proof. The case S = int(Ω) is trivially true. Consider S ⊂ ∂Ω. Burke and Moré [1] show that any open facet S is the relative interior of a quasipolyhedral face. Hence N(ȳ) and T (ȳ) are the same for all ȳ ∈ S, and

aff(S) = ȳ + lin(T (ȳ)) (6)

for all ȳ ∈ S.

Suppose, as in Definition 2, that we are given some y such that ȳ = P (y) ∈ S and y − ȳ ∈ ri(N(ȳ)). Then there is a constant γ > 0 such that (y − ȳ) + γv ∈ ri(N(ȳ)) for all v ∈ aff(N(ȳ)) with ∥v∥ = 1. Supposing that aff(N(ȳ)) has dimension r, we can choose unit vectors v_{1}, ⋯, v_{r−1}, such that {v_{1}, ⋯, v_{r−1}, y−ȳ} is linearly independent in aff(N(ȳ)), and hence a spanning set. Now set

v_{r} = −\frac{1}{r − 1}(v_{1} + ⋯ + v_{r−1})

and

v̂_{i} = y − ȳ + γv_{i}, i = 1, ⋯, r.

Clearly, v̂_{i} ∈ aff(N(ȳ)) and ∥v̂_{i} − (y − ȳ)∥ ≤ γ∥v_{i}∥ ≤ γ, so v̂_{i} ∈ ri(N(ȳ)), i = 1, ⋯, r. Moreover, we can show that {v̂_{1}, ⋯, v̂_{r}} is linearly independent by the following argument: Suppose there are real coefficients μ_{1}, ⋯, μ_{r} such that ∑ μ_{i}v̂_{i} = 0. Then

0 = ∑_{i=1}^{r} μ_{i}v̂_{i} = (∑_{i=1}^{r} μ_{i})(y − ȳ) + γ ∑_{i=1}^{r} μ_{i}v_{i}

= (∑_{i=1}^{r} μ_{i})(y − ȳ) + γ ∑_{i=1}^{r−1}[μ_{i} − μ_{r}/(r − 1)]v_{i}.

By the original choice of v_{1}, ⋯, v_{r−1}, we must have

∑_{i=1}^{r} μ_{i} = 0, μ_{i} = μ_{r}/(r − 1), i = 1, ⋯, r − 1,

and it follows that μ_{1} = ⋯ = μ_{r} = 0, as desired. Now define g_{i}(z) = (z − ȳ)^{T} v̂_{i}, i = 1, ⋯, r. Conditions (i) and (ii) of Definition 2 are readily verified. Condition (iii) follows since N(z̄) is constant for z̄ ∈ S, and v̂_{i} ∈ ri(N(z̄)), i = 1, ⋯, r. Condition (iv) is verified by noting that

y − ȳ = ∑_{i=1}^{r−1} \frac{v̂_{i}}{2(r − 1)} + \frac{v̂_{r}}{2} ∈ co\{v̂_{i}, i = 1, ⋯, r\}.

To prove Condition (v), we first take V = aff(S) in Definition 1, and note that if ȳ ∈ S, there is ϵ > 0 such that z̄ ∈ aff(S) ∩ (ȳ + ϵB) ⇒ z̄ ∈ S. That is,

S(ȳ; ϵ) = {z̄ | ∥z̄ − ȳ∥ ≤ ϵ, z̄ ∈ aff(S)} = aff(S) ∩ (ȳ + ϵB).

However, by (6),

aff(S) = ȳ + lin(T (ȳ)) = ȳ + N(ȳ)^{⊥},

and so,

z̄ ∈ aff(S) ⇔ (z̄ − ȳ)^{T} v̂_{i} = 0, i = 1, ⋯, r.

Hence

S(ȳ, ϵ) = {z̄ | ∥z̄ − ȳ∥ ≤ ϵ, g_{i}(z̄) = 0, i = 1, ⋯, r},

as required.

Theorem 2.4. Suppose that Ω is defined by (3),(4), where g_{i}, i = 1, ⋯, m are C^{1} functions. Suppose that for some set A ⊂ {1, ⋯, m}, the surface S defined by

S = {z | g_{i}(z) = 0, i ∈ A, g_{i}(z) > 0, i ∉ A}

is a connected subset of Ω. Then S is a class-C^{1} identifiable surface. Moreover, if g_{i} ∈ C^{p} for i ∈ A and p ≥ 2, then S is a class-C^{p} identifiable surface.

Proof. This follows trivially, by identifying g_{i}, i ∈ A with g_{i}, i = 1, ⋯, r, in Definition 2.

We now consider smoothness of the projection operator P (.). The motivation for this comes from the work of Holmes [7] and Fitzpatrick and Phelps [5], who consider closed convex sets with smooth boundaries. In these papers, smoothness of the boundary is defined in terms of smoothness of the gauge function

ρ_{Ω}(x) = inf{t > 0 | x ∈ t(Ω − x_{0}) + x_{0}}, for some x_{0} ∈ int(Ω),

and the boundary of Ω is said to be C^{p} if ρ_{Ω} is C^{p} in some neighborhood of ∂Ω. By showing that this definition is equivalent to a local C^{p} parametrization of the boundary, Holmes [7] essentially shows that a C^{p} boundary (by the definition above) is the same as a class-C^{p,0} boundary, as defined in [6]. Hence, as discussed earlier, ∂Ω is a class-C^{p} identifiable surface.

Holmes proves the following result:

Theorem 2.5. [7, Theorem 2]. If Ω has a C^{p} boundary, for p ≥ 2, then the projection operator P (.) is C^{p−1} in R l ^{n}\Ω, and P′(y) is invertible in lin(T (P (y))). Fitzpatrick and Phelps [5, Theorem 3.10] prove the converse.

The case of p = 2 is most interesting. It is a classical result [4, p. 216] that, since P is Lipschitz continuous, it is differentiable almost everywhere. Below, we extend Theorem 2.5 to sets with piecewise smooth boundaries, by showing that class-C^{p} identifiable surfaces generate open regions in R l ^{n}\Ω in which P is C^{p−1}.

Theorem 2.6. Let S and K be as defined in Lemma 2.2, with p ≥ 2. Then P (.) is C^{p−1} on K. Also, P′(y) is invertible in lin(T (P (y))).

Proof. For any y ∈ K, we can choose ϵ > 0 and δ > 0 as in Lemma 2.2 such that, when u ∈ y + ϵB, P (u) is also the projection of u onto the set {z̄ | g_{i}(z̄) = 0, i = 1, ⋯, r, ∥z̄ − ȳ∥ ≤ ϵ}. Hence we can differentiate the system (5) with respect to y to obtain

[ \begin{matrix}I + ∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(ȳ) & ∇g(ȳ) \\ ∇g(ȳ)^{T} & 0 \end{matrix} ] [ \frac{dȳ}{dy} ; \frac{dλ}{dy} ] = [ \begin{matrix}I \\ 0 \end{matrix} ] , (7)

where P′(y) = \frac{dȳ}{dy}. The first result follows immediately from (5) and the implicit function theorem (see, for example, Lang [8, page 125]) by noting that the coefficient matrix in (7) is nonsingular.

For the second result, let Z ∈ R l ^{n×(n−r)} be a matrix of full rank such that ∇g(ȳ)^{T} Z = 0. By Lemma 2.1(ii), the columns of Z span lin(T (P (y))). The second equation in (7) implies that

P′(y) = \frac{dȳ}{dy} = ZW^{T}

for some W ∈ R l ^{n×(n−r)}. Multiplying the first equation in (7) by Z^{T}, we find that

Z^{T} (I + ∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(ȳ))ZW^{T} = Z^{T}

and so

P′(y) = Z[Z^{T} (I + ∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(ȳ))Z]^{−1}Z^{T} . (8)

It follows from (8) and Lemma 2.1(iii) that P′(y) has nonsingular projection onto lin(T (P (y))).

We conjecture that the converse of this theorem is also true; that is, if there is an open connected region K ⊂ R l ^{n}\Ω such that P (.) is C^{p−1} on K, and P′(y) is invertible in lin(T (P (y))) for each y ∈ K, then P (K) is a class-C^{p} identifiable surface. The continuity condition alone is not sufficient, as an example from Fitzpatrick and Phelps [5, p. 496] illustrates. Define

Ω_{4} = {(ξ_{1}, ξ_{2}) | ξ_{2} ≥ |ξ_{1}| + ξ_{1}^{4/3}}.

There is a corner in Ω_{4} at (0, 0), and the set has four maximal class-C^{∞} identifiable surfaces: the corner, the interior, and the two edges. Tedious calculation shows that P is C^{1} on R l ^{n}\Ω, although ∂Ω is obviously not a class-C^{2} surface. It can be shown that P′(y) = 0 along the lines {(ξ_{1}, ξ_{2}) | ξ_{2} = −ξ_{1}, ξ_{1} > 0} and {(ξ_{1}, ξ_{2}) | ξ_{2} = ξ_{1}, ξ_{1} < 0}, and so the invertibility condition is not satisfied.

It is clear from (8) that the invertibility condition is related to the boundedness of the quantities λ_{i}∇^{2}g_{i}(ȳ) on lin(T (ȳ)). Note that these quantities are invariant under scaling of the g_{i}s, that is, if g_{i} is replaced by αg_{i}, then λ_{i} becomes λ_{i}/α.

3. Finite Identification in Constrained Optimization Algorithms. We turn now to algorithms for solving the optimization problem (1).

In analyzing the gradient projection algorithm, we use the work of Dunn [3, §2], who gave a framework for proving “capture” results. Dunn states this algorithm as follows: Choosing constants γ_{1} and γ_{2} with 0 < γ_{1} < γ_{2} < 1, and an initial iterate x_{0} ∈ Ω, set

x_{k+1} = P (x_{k} − σ_{k}∇F (x_{k})), (9)

where σ_{k} is chosen to satisfy

(10)  F (x_{k}) − F (P (x_{k} − ∇F (x_{k}))) ≥ γ_{1} ⇒ σ_{k} = 1,
(11)  F (x_{k}) − F (P (x_{k} − ∇F (x_{k}))) < γ_{1} ⇒ σ_{k} ∈ (0, 1)

and

γ_{1} ≤ \frac{F (x_{k}) − F (P (x_{k} − σ_{k}∇F (x_{k})))}{∇F (x_{k})^{T} [x_{k} − P (x_{k} − σ_{k}∇F (x_{k}))]} ≤ γ_{2}. (12)

We start with a simple result: Theorem 3.1. Suppose that

(i) Assumption 1 and (2) hold at some point x^{∗}; (ii) ∇F is continuous at x^{∗}; (iii) x^{∗} ∈ S, where S is a class-C^{p} identifiable surface of Ω with p ≥ 1; (iv) there is σ̄ > 0 such that σ_{k} ∈ [σ̄, 1] for all k; and

(v) the sequence {x_{k}} generated by (9)–(12) converges to x^{∗}. Then x_{k} ∈ S for all k sufficiently large.

Proof. Define the set K as in Lemma 2.2 Setting y = x^{∗} − ∇F (x^{∗}), we can apply Definition 2 to find δ > 0 such that

x^{∗} − ∇F (x^{∗}) + δB ⊂ K.

By construction of K, this implies that

x^{∗} − σ∇F (x^{∗}) + σδB ⊂ K  for all  σ ∈ [σ̄, 1].

Now, choose k̄ such that, for all k ≥ k̄,

∥x_{k} − x^{∗}∥ + ∥∇F (x_{k}) − ∇F (x^{∗})∥ ≤ σ̄δ.

Then

∥[x_{k} − σ_{k}∇F (x_{k})] − [x^{∗} − σ_{k}∇F (x^{∗})]∥ ≤ σ̄δ,

and so

x_{k} − σ_{k}∇F (x_{k}) ∈ x^{∗} − σ_{k}∇F (x^{∗}) + σ̄δB ⊂ x^{∗} − σ_{k}∇F (x^{∗}) + σ_{k}δB ⊂ K.

Hence x_{k+1} ∈ P (K) = S, for k ≥ k̄.

Before proving the next result, we state some second-order conditions and define some terms:

Assumption 2. Suppose that Ω satisfies Assumption 1 and that there is x^{∗} that satisfies (2), such that x^{∗} ∈ S, where S is a class-C^{p} identifiable surface of Ω with p ≥ 2. Suppose that F is twice continuously differentiable in a neighborhood of x^{∗}, and let g_{i}, i = 1, ⋯ r be as defined in Definition 2, for y = x^{∗} − ∇F (x^{∗}). Choose λ^{∗} ∈ R l ^{r} such that λ^{∗} > 0 and

− ∇F (x^{∗}) = ∇g(x^{∗})λ^{∗}, (13)

and suppose that for all h ∈ T_{S}(x^{∗}),

h^{T} [∇^{2}F (x^{∗}) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{∗})] h ≥ α∥h∥^{2}, for some α > 0.

Definition 3.

(i) x^{∗} is a proper local minimizer of F in Ω if there is ρ_{1} > 0 such that

x ∈ Ω, 0 < ∥x − x^{∗}∥ ≤ ρ_{1} ⇒ F (x) > F (x^{∗}).

(ii) x^{∗} is a stable fixed point for (9)–(12) if −∇F (x^{∗}) ∈ N(x^{∗}), and there are d_{1} > 0, d_{2} > 0 such that

∥x_{0} − x^{∗}∥ ≤ d_{1} ⇒ ∥x_{k} − x^{∗}∥ ≤ d_{2},  for all  k ≥ 0.

(iii) x^{∗} is a stable local attractor for (9)–(12) if it is a stable fixed point, and d_{1} > 0 can be chosen so that

∥x_{0} − x^{∗}∥ ≤ d_{1} ⇒ lim_{k→∞} x_{k} = x^{∗}.

Theorem 3.2. Suppose that Assumption 2 holds. Then

(i) there are positive scalars ρ_{1} and α_{1} such that

x ∈ Ω, ∥x − x^{∗}∥ ≤ ρ_{1} ⇒ F (x) − F (x^{∗}) ≥ α_{1}∥x − x^{∗}∥^{2};

(ii) there are positive scalars ρ_{2} and α_{2} such that

x ∈ S, ∥x − x^{∗}∥ ≤ ρ_{2} ⇒ ∥x − P (x − ∇F (x))∥ ≥ α_{2}∥x − x^{∗}∥,

that is, the defect E(x) = x − P (x − ∇F (x)), restricted to S, has an isolated zero at x^{∗};

(iii) given any σ̄ > 0, there is ρ_{3} = ρ_{3}(σ̄) > 0 such that

∥x − x^{∗}∥ ≤ ρ_{3}, σ ∈ [σ̄, 1] ⇒ P (x − σ∇F (x)) ∈ S;

(iv) x^{∗} is a stable local attractor for the gradient projection algorithm, and the

sequences {x_{k}} that approach x^{∗} eventually enter and remain in S. Proof. Throughout the proof, let ϵ denote ϵ(x^{∗} − ∇F (x^{∗})).

(i) We show first that if w = ∇g(x^{∗})μ with ∇g_{i}(x^{∗})^{T} w ≤ c_{1} for c_{1} ≥ 0 and i = 1, ⋯, r, then there is some τ_{1} > 0 such that

∇F (x^{∗})^{T} w ≥ τ_{1}∥w∥ + O(c_{1}). (14)

Using the definition of λ^{∗} from Assumption 2, we have

∇F (x^{∗})^{T} w = −λ^{∗T} ∇g(x^{∗})^{T} ∇g(x^{∗})μ
≥ (min_{i} λ_{i}^{∗})∥∇g(x^{∗})^{T} ∇g(x^{∗})μ∥ + O(c_{1}).

Since ∇g(x^{∗}) has full rank, and ∥μ∥ ≥ ∥w∥/∥∇g(x^{∗})∥, there is τ_{2} such that

∥∇g(x^{∗})^{T} ∇g(x^{∗})μ∥ ≥ τ_{2}∥μ∥ ≥ \frac{τ_{2}}{∥∇g(x^{∗})∥}∥w∥.

By setting

τ_{1} = (min_{i} λ_{i}^{∗})\frac{τ_{2}}{∥∇g(x^{∗})∥},

we obtain (14).

Now, given x in the vicinity of x^{∗}, we seek vectors v ∈ R l ^{n} and μ ∈ R l ^{r} such that

v + ∇g(x^{∗})μ = x − x^{∗}
(15)  g(x^{∗} + v) = 0.

We can again apply the implicit function theorem to (15) to find ρ̄_{1} > 0 such that a solution v, μ exists for ∥x − x^{∗}∥ ≤ ρ̄_{1}. Moreover, ρ̄_{1} can be chosen small enough that ∥v∥ ≤ ϵ, and hence x^{∗} + v ∈ S ⊂ Ω. In follows that, since ∇g_{i}(x^{∗} + v) ∈ N(x^{∗} + v) for i = 1, ⋯, r, and since x ∈ Ω,

∇g_{i}(x^{∗} + v)^{T} [x − (x^{∗} + v)] ≤ 0, i = 1, ⋯, r.

Writing w = ∇g(x^{∗})μ = x − (x^{∗} + v), we have

∇g_{i}(x^{∗})^{T} w = ∇g_{i}(x^{∗} + v)^{T} w + O(∥v∥∥w∥) ≤ O(∥v∥∥w∥), i = 1, ⋯, r.

Application of (14) shows that

∇F (x^{∗})^{T} w ≥ τ_{1}∥w∥ + O(∥v∥∥w∥). (16)

Now consider the v component. Since x^{∗} + v ∈ S, and since (13) holds,

F (x^{∗} + v) − F (x^{∗}) = [F (x^{∗} + v) + λ^{∗T} g(x^{∗} + v)] − [F (x^{∗}) + λ^{∗T} g(x^{∗})]
(17)  = \frac{1}{2}v^{T} [∇^{2}F (x^{∗} + β_{1}v) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{∗} + β_{1}v)] v

for some β_{1} ∈ (0, 1). Since ∇g_{i}(x^{∗})^{T} v = O(∥v∥^{2}), we can choose ρ̄_{2} ∈ (0, ρ̄_{1}] such that when ∥x − x^{∗}∥ ≤ ρ̄_{2}, v is close enough to T_{S}(x^{∗}) and ∥v∥ is small enough that

v^{T} [∇^{2}F (x^{∗} + β_{1}v) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{∗} + β_{1}v)] v ≥ \frac{α}{2}∥v∥^{2},

for all β_{1} ∈ [0, 1]. Hence, from (17),

F (x^{∗} + v) − F (x^{∗}) ≥ \frac{α}{4}∥v∥^{2}. (18)

12 STEPHEN J. WRIGHT

By using (16) and (18), we can now write that, for x ∈ Ω ∩ (x^{∗} + ρ̄_{2}B),

F (x) − F (x^{∗}) = F (x^{∗} + v + w) − F (x^{∗} + v) + F (x^{∗} + v) − F (x^{∗})
= ∇F (x^{∗})^{T} w + O(∥v∥∥w∥ + ∥w∥^{2}) + F (x^{∗} + v) − F (x^{∗})
≥ τ_{1}∥w∥ + \frac{α}{4}∥v∥^{2} + O(∥v∥∥w∥ + ∥w∥^{2})
(19)  ≥ τ_{1}∥w∥ + \frac{α}{4}∥v∥^{2} − c_{2}(∥v∥∥w∥ + ∥w∥^{2}),

where c_{2} > 0 is some constant. Now, choose a constant δ_{1} > 0 such that

c_{2}(δ_{1}^{2} + δ_{1}) ≤ \frac{α}{8}, (20)

and define ρ_{1} ∈ (0, ρ̄_{2}] such that both of the following conditions are satisfied:

x ∈ Ω ∩ (x^{∗} + ρ_{1}B) ⇒ ∥w∥ ≤ \frac{τ_{1}δ_{1}}{2c_{2}(1 + δ_{1})}, (21)

ρ_{1} ≤ \frac{4τ_{1}δ_{1}(1 + δ_{1})}{α}. (22)

In the case ∥w∥ ≥ δ_{1}∥v∥, we have

∥x − x^{∗}∥ ≤ ∥w∥ + ∥v∥ ≤ (1 + \frac{1}{δ_{1}} )∥w∥. (23)

Also, from (19),

F (x) − F (x^{∗}) ≥ τ_{1}∥w∥ − c_{2}(1 + \frac{1}{δ_{1}} )∥w∥^{2}. (24)

Now, from (21), (23) and (24), we have that

F (x) − F (x^{∗}) ≥ \frac{τ_{1}}{2} ∥w∥ ≥ \frac{τ_{1}δ_{1}}{2(1 + δ_{1})}∥x − x^{∗}∥ ≥ \frac{τ_{1}δ_{1}}{2(1 + δ_{1})ρ_{1}} ∥x − x^{∗}∥^{2},

for x ∈ Ω ∩ (x^{∗} + ρ_{1}B). Application of (22) yields that

F (x) − F (x^{∗}) ≥ \frac{α}{8(1 + δ_{1})^{2}} ∥x − x^{∗}∥^{2}. (25)

In the remaining case ∥w∥ < δ_{1}∥v∥, we find from (19),(20) that

F (x) − F (x^{∗}) ≥ \frac{α}{4}∥v∥^{2} − c_{2}(δ_{1}^{2} + δ_{1})∥v∥^{2} ≥ \frac{α}{8}∥v∥^{2}.

Also,

∥x − x^{∗}∥ ≤ ∥v∥ + ∥w∥ < (1 + δ_{1})∥v∥,

and hence (25) still applies. The result follows by setting

α_{1} = \frac{α}{8(1 + δ_{1})^{2}} .

(ii) By setting y = x^{∗} − ∇F (x^{∗}) in Lemma 2.2, we can choose δ ∈ (0, ϵ] such that P (x^{∗} − ∇F (x^{∗}) + δB) ⊂ S. Now, there is a ρ̄_{1} ∈ (0, ϵ] such that

∥x − x^{∗}∥ ≤ ρ̄_{1} ⇒ ∥[x − ∇F (x)] − [x^{∗} − ∇F (x^{∗})]∥ ≤ δ,

and hence x̂ = P (x − ∇F (x)) ∈ S. By contractivity of P (.), ∥x̂ − x^{∗}∥ = ∥P (x − ∇F (x)) − P (x^{∗} − ∇F (x^{∗}))∥ ≤ δ ≤ ϵ. It therefore follows from Definition 2 (v) that x̂ solves the projection subproblem

min_{x̂} \frac{1}{2}∥x̂ − (x − ∇F (x))∥_{2}^{2}, g_{i}(x̂) = 0, i = 1, ⋯, r. (26)

When x = x^{∗}, then x̂ = x^{∗}, and (13) holds. By the implicit function theorem, ρ̄_{2} ∈ (0, ρ̄_{1}] can be chosen small enough that there is λ such that in fact

∥x − x^{∗}∥ ≤ ρ̄_{2} ⇒ [x − ∇F (x)] − x̂ = ∇g(x̂)λ, (27)

with

∥x̂ − x^{∗}∥ = O(∥x − x^{∗}∥), ∥λ − λ^{∗}∥ = O(∥x − x^{∗}∥), λ > 0.

Since ∥x − x^{∗}∥ ≤ ρ̄_{1} ≤ ϵ, we also have by Definition 2(v) that g_{i}(x) = 0, i = 1, ⋯, r.

Let Z ∈ R l ^{n×(n−r)} be an orthonormal matrix whose columns span the subspace T_{S}(x^{∗}). By using a Taylor series expansion of g about x^{∗}, it is easy to show that there are vectors η, η̂ ∈ R l ^{n−r} and ζ, ζ̂ ∈ R l ^{r} such that

(28)  x − x^{∗} = Zη + ∇g(x^{∗})ζ,
(29)  x − x̂ = Zη̂ + ∇g(x^{∗})ζ̂,

where ∥ζ∥ = O(∥x − x^{∗}∥^{2}) and ∥ζ̂∥ = O(∥x − x^{∗}∥^{2}) + O(∥x̂ − x^{∗}∥^{2}) = O(∥x − x^{∗}∥^{2}). From the second-order conditions, and boundedness of ∇^{2}g_{i} in a neighborhood of x^{∗}, there exists a constant c_{2} > 0 such that

(30)  η^{T} Z^{T} [∇^{2}F (x^{∗}) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{∗})] Zη ≥ α∥η∥^{2},

(31)  ∥Z^{T} [I + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{∗})] Zη∥ ≤ c_{2}∥η∥,

for all η ∈ R l ^{n−r}. It follows trivially from (30) that

∥Z^{T} [∇^{2}F (x^{∗}) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{∗})] Zη∥ ≥ α∥η∥. (32)

Now, from (27),

x − x̂ = ∇F (x) + ∇g(x̂)λ
⇒ x − x̂ = ∇F (x) + ∇g(x)λ^{∗} + [∇g(x̂) − ∇g(x)]λ + ∇g(x)[λ − λ^{∗}]
⇒ x − x̂ = [∇^{2}F (x^{(1)}) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{(1)})] (x − x^{∗}) +

∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(x^{(2)})(x̂ − x) + ∇g(x^{∗})[λ − λ^{∗}] + O(∥x − x^{∗}∥^{2}),

for x^{(1)} ∈ [x, x^{∗}] and x^{(2)} ∈ [x̂, x]. Premultiplying this equation by Z^{T}, and using (28) and (29), we obtain

Z^{T} [I + ∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(x^{(2)})] [Zη̂ + ∇g(x^{∗})ζ̂]

= Z^{T} [∇^{2}F (x^{(1)}) + ∑_{i=1}^{r} λ_{i}^{∗}∇^{2}g_{i}(x^{(1)})] [Zη + ∇g(x^{∗})ζ] + O(∥x − x^{∗}∥^{2}).

Now, from (31) and (32), we can choose ρ̄_{3} ∈ (0, ρ̄_{2}] small enough that, for ∥x−x^{∗}∥ ≤ ρ̄_{3},

2c_{2}∥η̂∥ ≥ ∥Z^{T} [I + ∑_{i=1}^{r} λ_{i}∇^{2}g_{i}(x^{(2)})] Zη̂∥
≥ O(∥ζ̂∥) + O(∥ζ∥) + O(∥x − x^{∗}∥^{2}) + \frac{α}{2}∥η∥.

Since

∥η̂∥ = ∥x − x̂∥ + O(∥x − x^{∗}∥^{2}),
∥η∥ = ∥x − x^{∗}∥ + O(∥x − x^{∗}∥^{2}),

there is a constant c_{3} > 0 such that

2c_{2}∥x − x̂∥ ≥ \frac{α}{2}∥x − x^{∗}∥ − c_{3}∥x − x^{∗}∥^{2}
⇒ ∥x − x̂∥ ≥ \frac{α}{4c_{2}} ∥x − x^{∗}∥ [1 − \frac{2c_{3}}{α} ∥x − x^{∗}∥] .

Now, choosing ρ_{2} = min(ρ̄_{3}, α/(4c_{3})), the desired result follows, with α_{2} = α/(8c_{2}).

(iii) The proof of this part is identical to that of Theorem 3.1, and hence is omitted.

(iv) This follows from Theorem 2.1 of Dunn [3], after we make the following observations. Part (i) of this theorem implies that x^{∗} is a uniformly proper local minimizer of F in Ω. The fact that F ∈ C^{2} in a neighborhood of x^{∗} means that it is possible to choose a σ̄ ∈ (0, 1) such that, for x_{k} is in this neighborhood, any σ_{k} satisfying (10)–(12) lies in [σ̄, 1].

We turn now to Newton-like methods for (1). Here, an initial iterate x_{0} ∈ Ω is chosen, and for each k ≥ 0, the following subproblem is solved to find a search direction p_{k}:

min_{p_{k}} ∇F (x_{k})^{T} p_{k} + \frac{1}{2}p_{k}^{T} B_{k}p_{k}, x_{k} + p_{k} ∈ Ω. (33)

A steplength σ_{k} ∈ [0, 1] is chosen, usually with the help of some “sufficient decrease” criterion, and the next iterate is obtained by setting

x_{k+1} = x_{k} + σ_{k}p_{k}. (34)

A simple result, similar to Theorem 3.1, follows:

Theorem 3.3. Suppose that

(i) Assumption 1 and (2) hold at some point x^{∗}; (ii) ∇F (x) is continuous at x^{∗}; (iii) x^{∗} ∈ S, where S is some class-C^{p} identifiable surface of Ω with p ≥ 1; and

(iv) x_{k} → x^{∗} and p_{k} → 0 as k → ∞, and {∥B_{k}∥} is bounded. Then x_{k} + p_{k} ∈ S for all k sufficiently large.

Proof. As in Lemma 2.2, we can find a set K ⊂ R l ^{n}\Ω with P (K) ⊂ S, and a scalar δ > 0, such that

x^{∗} − ∇F (x^{∗}) + δB ⊂ int(K).

First-order conditions for (33) are that

−∇F (x_{k}) − B_{k}p_{k} ∈ N(x_{k} + p_{k}) ⇔ x_{k} + p_{k} = P (x_{k} + p_{k} − ∇F (x_{k}) − B_{k}p_{k}).

Now,

∥(x_{k} + p_{k} − ∇F (x_{k}) − B_{k}p_{k}) − (x^{∗} − ∇F (x^{∗}))∥
≤ ∥x_{k} − x^{∗}∥ + ∥∇F (x_{k}) − ∇F (x^{∗})∥ + (1 + ∥B_{k}∥)∥p_{k}∥.

We can choose k̄ large enough that, for k ≥ k̄, the right-hand side of the above inequality does not exceed δ. Then x_{k} + p_{k} ∈ S, as required.

Finally, we prove a capture and convergence result for Newton’s method, which makes use of the second-order conditions in Assumption 2.

Theorem 3.4. Suppose that Assumption 2 holds and that, in addition, ∇^{2}F (x) is Lipschitz continuous in a neighborhood of x^{∗}. Let B_{k} = ∇^{2}F (x_{k}) in (33). Then there are positive constants ρ_{4} and α_{4} such that, if x_{0} ∈ Ω ∩ (x^{∗} + ρ_{4}B) and σ_{k} ≡ 1 for all k ≥ 0, then the algorithm (33),(34) generates a sequence {x_{k}} such that

∥x_{k+1} − x^{∗}∥ ≤ α_{4}∥x_{k} − x^{∗}∥^{2}  for all  k ≥ 0.

In addition, x_{k} ∈ S for all k sufficiently large.

Proof. The proof rests on a result of Sachs [9, Theorem 2.1]. To apply this result, we need only show that, for some positive constants ρ̄_{1} and ᾱ_{1},

inf ; \begin{matrix}∥x − x^{∗}∥ ≥ τ, \\ x ∈ Ω ∩ (x^{∗} + ρ̄_{1}B) \end{matrix} ∇F (x^{∗})^{T} (x − x^{∗}) + \frac{1}{2}(x − x^{∗})^{T} ∇^{2}F (x^{∗})(x − x^{∗}) ≥ ᾱ_{1}τ^{2}, (35)

for all τ ∈ [0, ρ̄_{1}).

Choose ρ̄_{1} small enough that

• F is twice Lipschitz continuously differentiable on the open ball {x | ∥x − x^{∗}∥ < 2ρ̄_{1}}, and ∇^{2}F has Lipschitz constant L; and

• if α_{1}, ρ_{1} are the constants from Theorem 3.2(i), then ρ̄_{1} ≤ min(ρ_{1}, α_{1}/L). Now, for τ ∈ [0, ρ̄_{1}) and x such that

x ∈ Ω, ρ̄_{1} ≥ ∥x − x^{∗}∥ ≥ τ,

we obtain

∇F (x^{∗})^{T} (x − x^{∗}) + \frac{1}{2}(x − x^{∗})^{T} ∇^{2}F (x^{∗})(x − x^{∗})

≥ F (x) − F (x^{∗}) − \frac{1}{2}L∥x − x^{∗}∥^{3}
≥ [α_{1} − \frac{L}{2} ∥x − x^{∗}∥] ∥x − x^{∗}∥^{2}
≥ \frac{α_{1}}{2} ∥x − x^{∗}∥^{2},

where the second inequality follows from Theorem 3.2(i). Hence (35) follows by setting ᾱ_{1} = α_{1}/2. Applying [9, Theorem 2.1] with

a = ᾱ_{1},
κ = L,
ρ = ρ̄_{1},
σ̄ = 0,
V = {x | ∥x − x^{∗}∥ < 2ρ̄_{1}},
U = Ω ∩ (x^{∗} + ρ̄_{1}B),

we obtain the desired result, with

ρ_{4} = min (ρ̄_{1}, \frac{2ᾱ_{1}}{3L} ) , α_{4} = \frac{3L}{2ᾱ_{1}} .

(Note that [9, Theorem 2.1] continues to hold when σ̄ = 0.) The final statement in the theorem follows from Theorem 3.3.

REFERENCES

[1] J. V. Burke and J. J. Moré, On the identification of active constraints, SIAM Journal on Numerical Analysis, 25 (1988), pp. 1197–1211.

[2] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York, 1983.

[3] J. C. Dunn, On the convergence of projected gradient processes to singular critical points, Journal of Optimization Theory and Applications, 55 (1987), pp. 203–216.

[4] H. Federer, Geometric Measure Theory, Springer-Verlag, New York, 1969.

[5] S. Fitzpatrick and R. R. Phelps, Differentiability of the metric projection in Hilbert space, Transactions of the American Mathematical Society, 270 (1982), pp. 483–501.

[6] D. Gilbarg and N. S. Trudinger, Elliptic Partial Differential Equations of Second Order, Springer-Verlag, Berlin, 1983.

[7] R. B. Holmes, Smoothness of certain metric projections on Hilbert space, Transactions of the American Mathematical Society, 183 (1973), pp. 87–100.

[8] S. Lang, Analysis II, Addison-Wesley, Reading, MA, 1969.

[9] E. W. Sachs, Newton’s method for singular constrained optimization problems, Applied Mathematics and Optimization, 11 (1984), pp. 247–276.