Copyright information to be inserted by the Publishers

ERGODIC CONVERGENCE IN SUBGRADIENT OPTIMIZATION

T. LARSSON^{1}, M. PATRIKSSON^{2} and A.-B. STRÖMBERG^{1}

1Department of Mathematics, Linköping University, Linköping, Sweden 2Department of Mathematics, Chalmers University of Technology, Göteborg,

Sweden

When nonsmooth, convex minimization problems are solved by subgradient optimization methods, the subgradients used will in general not accumulate to subgradients which verify the optimality of a solution obtained in the limit. It is therefore not a straightforward task to monitor the progress of a subgradient method in terms of the approximate fulfilment of optimality conditions. Further, certain supplementary information, such as convergent estimates of Lagrange multipliers and convergent lower bounds on the optimal objective value, is not directly available in subgradient schemes.

As a means of overcoming these weaknesses in subgradient methods, we introduce the computation of an ergodic (averaged) sequence of subgradients. Specifically, we consider a nonsmooth, convex program solved by a conditional subgradient optimization scheme with divergent series step lengths, and show that the elements of the ergodic sequence of subgradients in the limit fulfil the optimality conditions at the optimal solution, to which the sequence of iterates converges.

This result has three important implications. First, it enables the finite identification of active constraints at the solution obtained in the limit. Second, it is used to establish the ergodic convergence of sequences of Lagrange multipliers; this result enables us to carry out sensitivity analyses for solutions obtained by subgradient methods. The third implication is the convergence of a lower bounding procedure based on an ergodic sequence of affine underestimates of the objective function; this procedure provides a proper termination criterion for subgradient methods.

KEY WORDS: Nonsmooth minimization, conditional subgradient optimization, ergodic convergence, finite identification results, Lagrange multipliers, bounding procedure

1 INTRODUCTION

Subgradient optimization methods are popular practical tools for nonsmooth, convex minimization, especially in the context of Lagrangean relaxation; their simplicity has contributed to their success. This paper focuses on information which is lacking in the straightforward application of subgradient optimization methods and on how to access it through suitable modifications or extensions of the scheme. A technique which is both classical and modern for inducing properties which an original sequence lacks is the construction of an ergodic (averaged) sequence which smoothes out oscillations in the original sequence. We introduce the computation of ergodic sequences from sequences of subgradients, normal elements, and Lagrange multipliers, and establish that the ergodic sequences inherit important properties from analogous sequences associated with smooth functions. The ergodic sequences are then utilized in procedures generating the interesting information.

The basis for our construction of ergodic sequences is the conditional subgradient optimization method (Larsson et al., 1996a) — which includes traditional subgradient optimization as a special case — using divergent series step lengths. The work preceding the writing of this paper is basic theoretical research with the purpose of finding and analyzing inherent properties of subgradient optimization methods; it reveals new and interesting characteristics of these methods.

2 BACKGROUND and BASIC CONCEPTS

Let X ⊆ ℜ^{n} be a nonempty, closed and convex set, and the function f : ℜ^{n} ↦ ℜ be nonsmooth and convex and thus everywhere continuous and subdifferentiable. Further, assume that inf_{x∈X} f(x) is attained at some x ∈ X. These properties are assumed to hold throughout the paper. The program considered is

[P] f^{∗} = min_{x∈X} f(x),

with the nonempty, closed and convex solution set X^{∗} = {x ∈ X | f(x) ≤ f^{∗}}.

To enable the statement of optimality conditions for this program, we first give some basic definitions. The subdifferential of f at x ∈ ℜ^{n} is

∂f(x) = { γ ∈ ℜ^{n} | f(y) ≥ f(x) + γ^{T} (y − x), ∀y ∈ ℜ^{n} } ,  (1)

the elements of which are called subgradients. The normal cone to the set X at some x ∈ X is the set

N_{X}(x) = { ν ∈ ℜ^{n} | ν^{T} (y − x) ≤ 0, ∀y ∈ X } ,  (2)

and the tangent cone to the set X at x ∈ X is

T_{X}(x) = { τ ∈ ℜ^{n} | τ^{T} ν ≤ 0, ∀ν ∈ N_{X}(x) } .

Further, we let

proj(x, S) = arg min_{y∈S} ∥ y − x ∥  and  dist(x, S) = min_{y∈S} ∥y − x∥

denote the Euclidean projection of the vector x onto the set S, and the Euclidean distance from the point x to proj(x, S), respectively. The function dist(·, S) : ℜ^{n} ↦ ℜ_{+} is convex and continuous.

Optimality conditions for the program [P] and properties of its solution set are given in the next proposition (Hiriart-Urruty and Lemaréchal, 1993, Thm. VII:1.1.1 and Cond. VII:(1.1.3), and Le. 2 in Burke and Ferris, 1991).

Proposition 2.1. (Optimality conditions) x ∈ X^{∗} if and only if there exists a γ ∈ ∂f(x) such that proj(γ, −T_{X}(x)) = 0 or, equivalently, ∂f(x) ∩ −N_{X}(x) ≠ ∅. Further, the composite mapping (∂f) ∩ (−N_{X}) is constant on X^{∗} and the set ∂f(x) ∩ −N_{X}(x), x ∈ X^{∗}, is convex and compact.

We consider subgradient optimization methods for solving the program [P]. These methods originate in research made by N.Z. Shor in the early 60’s; see Shor (1991) for a review of the early history of nonsmooth optimization. These methods are conceptually simple, in general easy to implement, and have been shown to be practically useful. They have therefore been frequently applied, particularly in connection with Lagrangean duality (e.g., Fisher, 1985, and Beasley, 1993).

The ergodic convergence results to be presented are derived for the conditional subgradient optimization method (Larsson et al., 1996a), which generalizes the traditional subgradient optimization method in the sense that the feasible set X may be taken into account when determining the step direction. It was shown (ibid.) that the practical performance of the resulting method applied to three types of structured optimization models is better than that of the classical approach.

The conditional subdifferential of f with respect to the feasible set X at x ∈ X (see Dem’janov and Šomesova, 1978) is the nonempty, closed and convex set

∂_{X}f(x) = { γ ∈ ℜ^{n} | f(y) ≥ f(x) + γ^{T} (y − x), ∀y ∈ X } ,

the elements of which will be referred to as conditional subgradients. Clearly, for all x ∈ X, ∂_{X}f(x) ⊇ ∂f(x) holds. Dem’janov and Šomesova show that ∂_{X}f(x) = ∂f(x) + N_{X}(x) holds for all x ∈ X.

Given an initial iterate x^{0} ∈ X, the conditional subgradient optimization method (Larsson et al., 1996a) is defined by the iteration formula

x^{t+ \frac{1}{2}} = x^{t} − α_{t}γ_{X}^{t},  x^{t+1} = proj (x^{t+ \frac{1}{2}} , X) ,  t = 0, 1, …,  (3)

where α_{t} > 0 and γ_{X}^{t} is a conditional subgradient of f at x^{t}, that is, γ_{X}^{t} = γ^{t} + ν^{t}, with γ^{t} ∈ ∂f(x^{t}) and ν^{t} ∈ N_{X}(x^{t}). Note that the vector x^{t+ \frac{1}{2}} − x^{t+1} ∈ N_{X}(x^{t+1}). Clearly, if {ν^{t}} = {0}, then the method (3) reduces to the classical method.

Choosing the normal vector ν^{t} = proj(−γ^{t}, N_{X}(x^{t})) results in the conditional subgradient γ_{X}^{t} = proj(γ^{t}, −T_{X}(x^{t})) (see Larsson et al., 1996a, Le. 3.2), defining the special case of the method (3) that is called the subgradient projection method, and for the case of a polyhedral feasible set, the step direction −γ_{X}^{t} from x^{t} is then feasible.

We consider step lengths satisfying the divergent series conditions

α_{t} > 0, ∀t,  {α_{t}} → 0,  ∑_{t=0}^{∞} α_{t} = ∞,  and  ∑_{t=0}^{∞} α_{t}^{2} < ∞.  (4)

The next result was established in Larsson et al. (1996a, Thm. 2.7).

Proposition 2.2. (Convergence of conditional subgradient optimization) Let the method (3)–(4) be applied to the program [P]. If the sequences {γ^{t}} and {ν^{t}} are bounded, then {x^{t}} → x^{∞} ∈ X^{∗}.

The boundedness of the sequence {γ^{t}} is ensured if the program [P] has some suitable additional property, for example that X is bounded or that f is piecewise linear with a finite number of pieces. In contrast, the elements of the sequence {ν^{t}} may always be chosen to ensure its boundedness. If subgradient projection is used, then ∥ν^{t}∥ ≤ ∥γ^{t}∥ so that the sequence {ν^{t}} is bounded whenever this is the case for the sequence {γ^{t}}. We make the blanket assumption that the sequences {γ^{t}} and {ν^{t}} are bounded.

Although the step length condition (4) may seem to limit the choices of step lengths, it in fact allows for the use of almost any technique for step length selection, such as line searches and formulas involving estimates of the optimal value. This possibility rests on the observation that any sequence of step lengths chosen satisfies (4), whenever there exist two sequences of step lengths satisfying (4) which (respectively) majorizes and minorizes this sequence. This proof technique is known as the almost complete relaxation strategy (Dem’yanov and Vasil’ev, 1985, Sec. 3.4; see also Cor. 2.8 in Larsson et al., 1996a), and is reminiscent of the celebrated Spacer Step Theorem (e.g., Luenberger, 1984, p. 231).

We define the sequence {g^{t}} of weighted averages of subgradients used up to iteration t as

g^{t} = ∑_{s=0}^{t−1} \frac{α_{s}}{∑_{r=0}^{t−1} α_{r}} γ^{s}, t = 1, 2, ….

The central result of the paper (Thm. 3.9) is that the elements of the ergodic sequence {g^{t}} of subgradients in the limit satisfy the optimality conditions stated in Prop. 2.1.

We note that the construction of the ergodic sequence of subgradients is an example of a widely used technique for inducing convergence properties which are lacking in an original sequence. The typical situation where an averaging process is necessary is when the original sequence oscillates or contains stochastic noise; the averaging of the elements then has the effect of stabilizing the process by smoothing out the oscillations and filtering out the stochastic noise, respectively. For example applications, see Baillon (1975), Ruszczyński and Syski (1983), Higle and Sen (1991), Kim and Ahn (1991), Larsson and Liu (1997), and Petersson and Patriksson (1997).

The rest of the paper is organized as follows. In Sec. 3 we define ergodic sequences of subgradients, normal cone elements, and objective values generated by the method (3)–(4), and establish the core result of this work that these sequences verify optimality. In Sec. 4 we utilize the ergodic sequence of subgradients to finitely identify the face (of smallest dimension) of the feasible set that contains this optimal solution. Sec. 5 contains convergence results for ergodic sequences of Lagrange multipliers and multipliers associated with pieces of the objective function. These results are then used to derive a sensitivity analysis result for nonsmooth programming and to show a convergence result for solutions of systems of linear inequalities in the case of inconsistency. In Sec. 6 we present a convergent lower bounding procedure based on the minimization of affine underestimates of the nonsmooth objective function; this procedure provides a proper termination criterion for subgradient methods. An application to systems of linear inequalities is also presented. Finally, in Sec. 7, we discuss briefly some opportunities for future research.

Earlier versions of Secs. 1, 3, 5, and 6 have been published in Larsson et al. (1996b and 1996c). An expanded version of this paper, including a larger number of applications, appears in Strömberg (1997).

3 MAIN THEORETICAL RESULTS

3.1 Preliminaries

We denote by A_{t} the cumulative step length up to iteration t, namely,

A_{t} = ∑_{s=0}^{t−1} α_{s},  t = 1, 2, ….  (5)

Definition 3.1. The ergodic sequence of subgradients is defined by

g^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}γ^{s}, t = 1, 2, ….

The ergodic sequences {n_{c}^{t}} and {n_{p}^{t}} of normal terms of the conditional subgradients and projection steps are defined by n_{c}^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ν^{s} and n_{p}^{t} = A_{t}^{−1} ∑_{s=0}^{t−1}(x^{s+ \frac{1}{2}} − x^{s+1}), respectively, and the ergodic sequence of normal vectors is defined by

n^{t} = n_{c}^{t} + n_{p}^{t}, t = 1, 2, ….

The behaviour of the sequences {g^{t}} and {n^{t}} play a central role in the derivation of the results of this paper. A main source of inspiration for the study of these sequences was Shor’s (1985, pp. 116–118) study of Lagrangean relaxation applied to linear programs. Clearly, each vector g^{t} is a convex combination of the subgradients {γ^{s}}_{s=0}^{t−1}, and n_{c}^{t} is a convex combination of the normal terms of the conditional subgradients used up to iteration t of the method (3), while n_{p}^{t} is a positive linear combination of its projection steps. If the traditional subgradient optimization method is employed, then for all t, n_{c}^{t} = 0 and n^{t} = n_{p}^{t}. A recursive computation of g^{t} can be implemented using the formula

g^{1} = γ^{0},  g^{t} = \frac{A_{t−1}}{A_{t}} g^{t−1} + \frac{α_{t−1}}{A_{t}} γ^{t−1},  t = 2, 3, ….

Remark 3.2. We will utilize the properties in the limit of the sequence {g^{t}}. Since the information from the initial iterations of a subgradient optimization scheme is usually of low quality, the initialization of this sequence is preferably delayed until the iterates x^{t} are near-optimal. Any of the results of this paper can easily be modified to the initialization of the ergodic sequences at any iteration t_{0} ≥ 0.

The next result, which is a consequence of Def. 3.1 and the inequality ∥x^{s+ \frac{1}{2}} − x^{s+1}∥ ≤ α_{s}∥γ_{X}^{s}∥, is the first step towards a convergence result for the ergodic sequence {g^{t}}.

Lemma 3.3. The sequences {g^{t}} and {n^{t}} are bounded.

The ergodic sequence of objective values obtained in the method (3) is defined as

φ_{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}f(x^{s}),  t = 1, 2, ….  (6)

It follows that φ_{t} ≥ f^{∗} for all t, since, for all s, x^{s} ∈ X.

Utilizing that, for all s, γ^{s} ∈ ∂f(x^{s}), and the definition (1), we derive the surrogate inequalities

∑_{s=0}^{t−1} α_{s}f(x) ≥ ∑_{s=0}^{t−1} α_{s} (f(x^{s}) + (γ^{s})^{T} (x − x^{s})) ,  x ∈ ℜ^{n},  t = 1, 2, …,

and define the affine functions f_{t} : ℜ^{n} ↦ ℜ, t = 1, 2, …, as

f_{t}(x) = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s} (f(x^{s}) + (γ^{s})^{T} (x − x^{s})) ,  x ∈ ℜ^{n}.  (7)

Then, f_{t}(x) ≤ f(x) holds for all x ∈ ℜ^{n} and all t, that is, each function f_{t} is an affine underestimate of the objective f (see Fig. 1).

[Place of Figure 1]

Clearly, the hyperplane defined by the function f_{t} is a weighted average of all supporting hyperplanes generated in the previous iterations of the conditional subgradient optimization method. From Def. 3.1 it follows that ∇f_{t}(x) = g^{t} and f_{t}(x) = f_{t}(y) + (g^{t})^{T} (x − y) for any x, y ∈ ℜ^{n} and all t.

We let the convex functions δ_{t} : ℜ^{n} ↦ ℜ, t = 1, 2, …, describe the pointwise vertical distance between the functions f and f_{t}, that is,

δ_{t}(x) = f(x) − f_{t}(x),  x ∈ ℜ^{n}.  (8)

It follows that δ_{t}(x) ≥ 0 for all x ∈ ℜ^{n} and all t.

Further, we define the affine functions ϱ_{t} : ℜ^{n} ↦ ℜ, t = 1, 2, …, as

ϱ_{t}(x) = A_{t}^{−1} ∑_{s=0}^{t−1} (α_{s}(ν^{s})^{T} (x^{s}−x)+(x^{s+ \frac{1}{2}} −x^{s+1})^{T} (x^{s+1}−x)) , x ∈ ℜ^{n}. (9)

Using, for all s, that ν^{s} ∈ N_{X}(x^{s}) and x^{s+ \frac{1}{2}} −x^{s+1} ∈ N_{X}(x^{s+1}), and the definition (2), it follows that ϱ_{t}(x) ≥ 0 for x ∈ X and all t, that is, each of these inequalities is a valid inequality for the set X (see Fig. 2).

[Place of Figure 2]

From Def. 3.1 follows that ∇ϱ_{t}(x) = −n^{t} and ϱ_{t}(x) = ϱ_{t}(y) − (n^{t})^{T} (x − y) for any x, y ∈ ℜ^{n} and all t.

The following lemma is crucial for our continued analysis.

Lemma 3.4. {δ_{t}(x^{∞})} → 0, {ϱ_{t}(x^{∞})} → 0, and {φ_{t}} → f^{∗}. Further, {δ_{t}(x^{t})} → 0 and {ϱ_{t}(x^{t})} → 0.

Proof. By Prop. 2.2, {x^{t}} → x^{∞}. From the iteration formula (3) it follows that

∥x^{t+1} − x^{∞}∥^{2} ≤ ∥x^{t} − x^{∞}∥^{2} + α_{t}^{2} ∥γ_{X}^{t} ∥^{2}

−2 (α_{t}(γ_{X}^{t})^{T} (x^{t} − x^{∞}) + (x^{t+ \frac{1}{2}} − x^{t+1})^{T} (x^{t+1} − x^{∞})) .

Repeated application of the inequality and utilization of the definitions (8), (9), and (6), result in ∥x^{0} − x^{∞}∥^{2} + ∑_{s=0}^{t−1} α_{s}^{2}∥γ_{X}^{s}∥^{2} − 2A_{t}(δ_{t}(x^{∞}) + ϱ_{t}(x^{∞}) + φ_{t} − f^{∗}) ≥ 0. Since δ_{t}(x^{∞}) ≥ 0, ϱ_{t}(x^{∞}) ≥ 0, φ_{t} ≥ f^{∗}, and A_{t} > 0, the immediate result is that

0 ≤ δ_{t}(x^{∞}) + ϱ_{t}(x^{∞}) + φ_{t} − f^{∗} ≤ \frac{1}{2A_{t}} (∥x^{0} − x^{∞}∥^{2} + ∑_{s=0}^{t−1} α_{s}^{2} ∥γ^{s} + ν^{s}∥^{2}) .

Let t → ∞ and invoke the conditions (4).

For the latter result, we note that Definition 3.1, and the definitions (7) and (8), yield

0 ≤ δ_{t}(x^{t}) = δ_{t}(x^{∞}) + f(x^{t}) − f(x^{∞}) − (g^{t})^{T} (x^{t} − x^{∞}) , t = 1, 2, ….

From Definition 3.1, and the definition (9), follow that

0 ≤ ϱ_{t}(x^{t}) = ϱ_{t}(x^{∞}) − (n^{t})^{T} (x^{t} − x^{∞}) , t = 1, 2, ….

Proposition 2.2, Lemma 3.3, the continuity of f, and Lemma 3.4 yield that the right–hand–sides of both the above equations tend toward zero as t approaches infinity. The result follows. A small value of δ_{t}(x^{t}) ≥ 0 implies that the affine underestimate f_{t} of the function f defines a hyperplane that is close to a support to epi f at (x^{t}, f(x^{t})), where epi denotes epigraph. A small value of ϱ_{t}(x^{t}) means that the hyperplane {x ∈ ℜ^{n} | ϱ_{t}(x) = 0} is close to a support to X at x^{t} (while X ⊆ {x ∈ ℜ^{n} | ϱ_{t}(x) ≥ 0} always holds).

Remark 3.5. Should, for example, δ_{t}(x^{t}) = 0 hold at some iteration t, one can, however, not infer the optimality of x^{t}. An analogous statement applies to the quantity g^{t} + n^{t}, which is utilized next.

We will also utilize the following lemma in our continued analysis, when proving optimality fulfilment of the sequence {g^{t}} in the limit.

Lemma 3.6. {g^{t} + n^{t}} → 0.

Proof. By Def. 3.1 and the iteration formula (3), g^{t} + n^{t} = A_{t}^{−1} ∑_{s=0}^{t−1}(x^{s} − x^{s+ \frac{1}{2}} + x^{s+ \frac{1}{2}} − x^{s+1}) = A_{t}^{−1}(x^{0} − x^{t}). Prop. 2.2 yields that \{x^{t}\} → x^{∞}. The result then follows from the definition (5) and the condition (4).

3.2 Ergodic convergence of the sequence of subgradients

As concluded above, the affine functions f_{t}, t = 1, 2, …, underestimate the convex function f everywhere, and from Le. 3.4 it follows that {f_{t}(x^{∞})} → f(x^{∞}). Hence, in the limit, the sequence {f_{t}} provides supporting hyperplanes to epi f at (x^{∞}, f(x^{∞})); this observation is further developed in the following theorem.

Theorem 3.7 (Convergence of {g^{t}} to ∂f(x^{∞})). {dist(g^{t}, ∂f(x^{∞}))} → 0. Proof. Def. 3.1 and the definitions (7) and (8) imply that g^{t} is a δ_{t}(x)-subgradient

of f at x (e.g., Hiriart-Urruty and Lemaréchal, 1993, Def. XI:1.1.1) for any x ∈ ℜ^{n}; applying this result to x = x^{t} yields

f(y) ≥ f(x^{t}) + (g^{t})^{T} (y − x^{t}) − δ_{t}(x^{t}), ∀y ∈ ℜ^{n}.

By Le. 3.3, the sequence {g^{t}} is bounded. Let g̃ be an accumulation point of a convergent subsequence T . Then, by Le. 3.4, in the limit of T of the above inequality, we obtain that g̃ ∈ ∂f(x^{∞}). The boundedness of ∂f(x^{∞}) then yields the desired result.

Theorem 3.8 (Convergence of {g^{t}} to −N_{X}(x^{∞})). {dist(g^{t},−N_{X}(x^{∞}))} → 0.

Proof. From the definition (9) it follows that, for all t and any y ∈ X, (n^{t})^{T} (y − x^{∞}) = −ϱ_{t}(y) + ϱ_{t}(x^{∞}) ≤ ϱ_{t}(x^{∞}). By Le. 3.3, the sequence {n^{t}} is bounded. Let ñ be an accumulation point of the sequence {n^{t}}_{t∈T} for some convergent subsequence T . From Le. 3.4 it then follows that ñ^{T} (y − x^{∞}) ≤ 0 for any y ∈ X. By the continuity of the function dist(·, N_{X}(x^{∞})), for any ε > 0 and all t that are sufficiently large, dist(n^{t}, N_{X}(x^{∞})) < ε/2; further, by Le. 3.6, ∥g^{t} + n^{t}∥ < ε/2. This yields that dist(g^{t}, −N_{X}(x^{∞})) ≤ dist(−n^{t}, −N_{X}(x^{∞})) + ∥g^{t} + n^{t}∥ < ε, and the result follows.

Applying the Moreau decomposition (Zarantonello, 1971, Le. 2.2) to g^{t}, with respect to the polar cones N_{X}(x^{∞}) and T_{X}(x^{∞}), it can easily be established that {proj(g^{t}, −T_{X}(x^{∞}))} → 0 holds.

We go on to our main result, which establishes that the sequence {g^{t}} in the limit provides subgradients that verify the optimality of the solution x^{∞} to the program [P]; this follows from Thms. 3.7 and 3.8.

Theorem 3.9 (Optimality fulfilment). {dist(g^{t}, ∂f(x^{∞})∩−N_{X}(x^{∞}))} → 0. Further, if X = ℜ^{n}, then, {g^{t}} → 0.

This result and Le. 3.6 imply similar results for the sequence {n^{t}}.

Thm. 3.9 shows that the ergodic sequence {g^{t}} of subgradients inherits important properties from sequences of gradients of smooth functions.

4 FINITENESS RESULTS

In this section we demonstrate that the ergodic sequence {g^{t}} can be used to finitely determine a nontrivial face of the feasible set containing the limit point x^{∞} and in particular the constraints that are active at x^{∞}. This is achieved through the construction of an auxiliary sequence of feasible solutions that exhibits convergence properties that the original sequence {x^{t}} is lacking.

4.1 Preliminaries

The auxiliary sequence of feasible solutions to the program [P] is constructed in a manner akin to that of the gradient projection algorithm (see, for example, Bertsekas, 1976), the elements g^{t} taking the role of the gradient values.

Definition 4.1. Let the sequence {σ_{t}} satisfy inf_{t}{σ_{t}} > 0 and sup_{t}{σ_{t}} < ∞. The auxiliary sequence \{\overline{x}^{t}\} is defined by \overline{x}^{t} = proj (x^{t} − σ_{t}g^{t}, X).

Theorem 4.2. \{\overline{x}^{t}\} → x^{∞}.

Proof. The existence of a limit x^{∞} of {x^{t}} that solves [P] is a consequence of Prop. 2.2. By the relations ∥\overline{x}^{t}−x^{t}∥ = ∥proj(x^{t}−σ_{t}g^{t}, X)−x^{t}∥ ≤ ∥x^{t}−σ_{t}g^{t}−x^{t}∥ = σ_{t}∥g^{t}∥, and the boundedness of the sequences {x^{t}}, {g^{t}} and {σ_{t}}, the sequence \{\overline{x}^{t}\} is also bounded. The result then follows from Thm. 3.8 and the properties that proj(·, X) is continuous and proj(x + d, X) = x holds for any d ∈ N_{X}(x), x ∈ X (see also Equation (3.3) in Burke and Moré, 1994).

The gradient projection algorithm for differentiable optimization enjoys finite identification properties; these have been investigated in Calamai and Moré (1987), Dunn (1987), and Burke and Moré (1988 and 1994). We will subsequently show that natural extensions of these results to the nonsmooth case hold for the auxiliary sequence \{\overline{x}^{t}\}. Throughout this section we shall frequently utilize the notion of exposed faces.

Definition 4.3. The face of the closed and convex set S ⊆ ℜ^{n} that is exposed by a vector d ∈ ℜ^{n} is F_{S}(d) = arg max_{y∈S}{d^{T} y}.

Exposed faces are related to normal cones through the equivalence relation

d ∈ N_{S}(x) ⟺ x ∈ F_{S}(d).  (10)

Our first result establishes that for polyhedral feasible sets, given an accumulation point g̃ of the sequence \{g^{t}\}, the auxiliary points \overline{x}^{t} are finitely in the face of X that is exposed by −g̃.

Theorem 4.4 (\overline{x}^{t} is finitely in the face exposed by −g̃). Assume that the set X is polyhedral, let the assumptions of Thm. 4.2 hold and g̃ be the limit of the convergent subsequence \{g^{t}\}_{t∈T}. Then, for some t_{0}, \overline{x}^{t} ∈ F_{X}(−g̃), for all t ≥ t_{0}, t ∈ T .

Proof. Defining d^{t} = x^{t} − σ_{t}g^{t} − \overline{x}^{t}, it follows that d^{t} ∈ N_{X}(\overline{x}^{t}) holds for all t. From the equivalence (10) it then follows that \overline{x}^{t} ∈ F_{X}(d^{t}) for all t. By Thm. 4.2 we may assume that {d^{t}}_{t∈T} → −σ̃g̃ for some σ̃ > 0. Le. 3.5 in Robinson (1984) (see also Burke and Moré, 1994, Thm. 3.1) implies that F_{X}(d) ⊆ F_{X}(d^{∗}) for any d in a sufficiently small neighbourhood of d^{∗} ∈ ℜ^{n}. Applying this result to the above yields the theorem.

A direct consequence of Thm. 4.4 and the Moreau decomposition (Zarantonello, 1971, Le. 2.2) is the result that \{proj(g^{t}, −T_{X}(\overline{x}^{t}))\} → 0.

4.2 Non-degeneracy

Faces of polyhedral sets enjoy several properties that are not shared with faces of general convex sets; for example, every face of a polyhedral set is exposed by some vector in ℜ^{n}, which is not the case for general convex sets. Establishing finite identification results for non-polyhedral sets therefore require certain nondegeneracy assumptions on the feasible set and the optimal solution obtained by the algorithm under consideration.

It is well known (e.g., Burke and Moré, 1988) that every point in a convex set X belongs to the relative interior of a unique face of X. We let the face F_{X}^{∞} be defined by the relation

rint F_{X}^{∞} ∋ x^{∞},  (11)

where x^{∞} is the limit point of the sequence {x^{t}} generated by the conditional subgradient optimization algorithm. One of the assumptions employed in this section is that the face F_{X}^{∞} is quasi-polyhedral, as defined below; this definition is due to Burke and Moré (1988). Here, aff denotes the affine hull.

Definition 4.5. A face F_{X} of a convex set X is quasi-polyhedral if aff F_{X} = x + {T_{X}(x) ∩ −T_{X}(x)} for all x ∈ rint F_{X}.

Note that every face of a polyhedral set is quasi-polyhedral. For detailed analyses of the geometry of faces, see Burke and Moré (1988 and 1994). We will further employ a non-degeneracy assumption, which extends the one introduced by Dunn (1981) for the differentiable case.

Assumption 4.6. −G̃ ⊆ rint N_{X}(x^{∞}).

To discuss the meaning of this assumption, we represent the set X as X = {x ∈ ℜ^{n} | a_{i}(x) ≤ 0, i ∈ I}, where the functions a_{i} : ℜ^{n} ↦ ℜ, i ∈ I, are convex and differentiable (and the set I is finite) and denote by I(x) = { i ∈ I | a_{i}(x) = 0 } the set of constraints that are active at x ∈ X. The assumption, together with the Guignard (1969) constraint qualification (CQ) for X, is equivalent to the existence of a set of strictly complementary Lagrange multipliers for any accumulation point of {g^{t}}; to see this, we note that under the Guignard CQ,

N_{X}(x) = { ν ∈ ℜ^{n} | ν = ∑_{i∈I(x)} μ_{i}∇a_{i}(x); μ_{i} ≥ 0, i ∈ I } .

An equivalent expression of Ass. 4.6 is then that for every accumulation point g̃ of the sequence {g^{t}} there is a vector μ ∈ ℜ_{+}^{|I|} of Lagrange multipliers such that (cf. Le. 3.2 of Burke and Moré, 1988)

−g̃ = ∑_{i∈I(x^{∞})} μ_{i}∇a_{i}(x^{∞})  and  μ_{i} > 0, i ∈ I(x^{∞}).

We now establish that the auxiliary sequence \{\overline{x}^{t}\} finitely enters and remains in the face F_{X}^{∞}, defined by the relation (11); this result strengthens that of Thm. 4.4.

Theorem 4.7 (\overline{x}^{t} is finitely in the optimal face of X). Assume that the Guignard CQ holds for the set X, and that the face F_{X}^{∞}, given by the relation (11), is quasi-polyhedral. Further, let Ass. 4.6 and the assumptions of Thm. 4.2 hold. Then, for some t_{0}, \overline{x}^{t} ∈ rint F_{X}^{∞}, t ≥ t_{0}.

Proof. Let the sequence {d^{t}} be defined as in the proof of Thm. 4.4, and let g̃ be the limit of the convergent subsequence {g^{t}}_{t∈T}. By Thm. 4.2 we may assume that {d^{t}}_{t∈T} → −σ̃g̃ for some σ̃ > 0. Thm. 4.2 and Ass. 4.6 then enable us to invoke Le. 3.3 of Burke and Moré (1988) to arrive at the result that \overline{x}^{t} ∈ rint F_{X}^{∞} for all t ∈ T that are sufficiently large. But since, by Ass. 4.6 and Thm. 2.5 of Burke and Moré (1994), all vectors g̃ ∈ G̃ expose the same face of X, the result follows.

A direct consequence of this result is that \{proj(g^{t}, −T_{X}(\overline{x}^{t}))\} → 0.

For linearly constrained problems, where X = { x ∈ ℜ^{n} | a_{i}^{T} x ≤ b_{i}, i ∈ I }, the result of Thm. 4.7 can be expressed in terms of active constraints.

Theorem 4.8 (\overline{x}^{t} identifies finitely the active constraints at x^{∞}). Let the set X be polyhedral and the assumptions of Thm. 4.7 hold. Then, for some t_{0}, I(\overline{x}^{t}) = I(x^{∞}), for all t ≥ t_{0}.

Proof. The result follows from Thm. 4.7 and the fact that [cf. Burke and Moré, 1988, equation (2.7)] rint F_{X}^{∞} = {x ∈ X | a_{i}^{T} x = b_{i}, i ∈ I(x^{∞}); a_{i}^{T} x < b_{i}, i ∉ I(x^{∞})}.

Under a stronger non-degeneracy assumption than Ass. 4.6, the auxiliary sequence \{\overline{x}^{t}\} exhibits finite convergence to a solution to [P].

Definition 4.9. An solution x^{∗} to [P] is a sharp minimum of f on X if, for some constant δ_{f} > 0, f(x) ≥ f^{∗} + δ_{f} ∥x − x^{∗}∥ for all x ∈ X.

This definition is due to Polyak (1987, p. 205). We note that a sharp minimum is unique. A point x^{∗} is a sharp minimum of f on X if and only if 0 ∈ int(∂f(x^{∗}) + N_{X}(x^{∗})); the assumption made below is that −G̃ ⊂ int N_{X}(x^{∞}), which is a strengthening of Ass. 4.6 in the sense that the interior of N_{X}(x^{∞}) is presumed to be nonempty.

The following result strengthens those of Thms. 4.7 and 4.8.

Corollary 4.10 (\overline{x}^{t} identifies finitely the optimal solution). Let the assumptions of Thm. 4.7 hold. If int N_{X}(x^{∞}) ≠ ∅, then the sequence \{\overline{x}^{t}\} converges finitely to x^{∞}.

Proof. If N_{X}(x^{∞}) has a nonempty interior, then the set {x^{∞}} is a quasipolyhedral face of X (Burke and Moré, 1988, proof of Cor. 3.5). Then, Thm. 4.7 shows that \overline{x}^{t} = x^{∞} for all sufficiently large t.

5 ERGODIC CONVERGENCE OF SEQUENCES OF MULTIPLIERS

5.1 Multipliers of constraints

Throughout this subsection we assume that the feasible set X of the program [P] is explicitly described as

X = { x ∈ ℜ^{n} | a_{i}(x) ≤ 0, i ∈ I; b_{j}^{T} x = e_{j}, j ∈ E } ,  (12)

where the functions a_{i} : ℜ^{n} ↦ ℜ, i ∈ I, are convex and differentiable, b_{j} ∈ ℜ^{n} and e_{j} ∈ ℜ, j ∈ E, and the sets I and E are finite and disjoint. The convergence analysis for the sequences of multipliers associated with the constraints defining the set X relies on the assumption that this set fulfils the following strong Slater CQ (e.g., Hiriart-Urruty and Lemaréchal, 1993, Def. VII:2.3.1).

Assumption 5.1. The vectors b_{j}, j ∈ E, are linearly independent, and there exists an x ∈ X such that a_{i}(x) < 0, i ∈ I.

We let, for all x ∈ X, I(x) = {i ∈ I | a_{i}(x) = 0} denote the set of inequality constraints that are active at x, and Π_{X}(x) the set of multiplier values that satisfy the complementary slackness conditions for the program [P] at x, that is,

Π_{X}(x) = { π ∈ ℜ_{+}^{|I|} × ℜ^{|E|} | π_{i} = 0, i ∈ I \ I(x) } ∋ 0.

Letting ω ∈ ℜ^{|I|+|E|}, the normal cone of X at x ∈ X can then be expressed as

N_{X}(x) = { ν ∈ ℜ^{n} | ν = ∑_{i∈I} ω_{i}∇a_{i}(x) + ∑_{j∈E} ω_{j}b_{j}; ω ∈ Π_{X}(x) } .

For any x ∈ X, let

M_{X}(x) = {μ ∈ Π_{X}(x) | 0 ∈ ∂f(x) + ∑_{i∈I} μ_{i}∇a_{i}(x) + ∑_{j∈E} μ_{j}b_{j} }  (13)

be the (possibly empty) set of Lagrange multipliers associated with the constraints defining the set X. The optimality conditions for the program [P] can be stated in terms of this set.

Proposition 5.2 (Optimality condition). Let x ∈ X. Then, x ∈ X^{∗} if and only if M_{X}(x) ≠ ∅. Further, the mapping M_{X} is constant on X^{∗} and the set M_{X}(x), x ∈ X^{∗}, is convex and compact.

Proof. The first conclusion follows from Hiriart-Urruty and Lemaréchal, 1993, Thms. VII:2.1.4 and VII:2.3.2. The invariance of M_{X} over X^{∗} and its boundedness follow from Prop. VII:3.1.1 and Thm. VII:2.3.2, respectively, in ibid. The closedness and convexity of M_{X}(x) follow from its definition (13).

Our derivation of convergence results for the ergodic sequence of Lagrange multipliers starts with the following lemma.

Lemma 5.3. Let x ∈ X and π ∈ ℜ_{+}^{|I|} × ℜ^{|E|}. Then,

∑_{i∈I(x)} π_{i}∇a_{i}(x) + ∑_{j∈E} π_{j}b_{j} = 0,  π ∈ Π_{X}(x)  (14)

holds if and only if π = 0.

Proof. Clearly, π = 0 satisfies (14).

Conversely, suppose that π satisfies (14). From Ass. 5.1 follows that there is an x̂ ≠ x such that x̂ ∈ rint X. This fact together with the convexity and differentiability of the functions a_{i} and the fact that a_{i}(x) = 0 for all i ∈ I(x) implies that ∇a_{i}(x)^{T} (x̂ − x) ≤ a_{i}(x̂) < 0 for all i ∈ I(x). Since x, x̂ ∈ X it then follows from (14) and (12) that

0 = ∑_{i∈I(x)} π_{i}∇a_{i}(x)^{T} (x̂ − x) + ∑_{j∈E} π_{j}b_{j}^{T} (x̂ − x)
= ∑_{i∈I(x)} π_{i}∇a_{i}(x)^{T} (x̂ − x) ≤ ∑_{i∈I(x)} π_{i}a_{i}(x̂) ≤ 0.

Hence, ∑_{i∈I(x)} π_{i}a_{i}(x̂) = 0 and, since π_{i}a_{i}(x̂) ≤ 0 for all i ∈ I, therefore, π_{i} = 0 holds for all i ∈ I(x). The system (14) then reduces to the equations ∑_{j∈E} π_{j}b_{j} = 0 and π_{i} = 0, i ∈ I. By Ass. 5.1, the vectors b_{j}, j ∈ E, are linearly independent, thus implying that π_{j} = 0 for all j ∈ E. Hence, π = 0.

Definition 5.4. The sequences {ω^{s}} and {λ^{s}} are defined by

ω^{s} ∈ { ω ∈ Π_{X}(x^{s}) | ∑_{i∈I} ω_{i}∇a_{i}(x^{s}) + ∑_{j∈E} ω_{j}b_{j} = ν^{s} } , s = 0, 1, …,

and

λ^{s} ∈\{λ ∈ Π_{X}(x^{s+1}) | ∑_{i∈I} λ_{i}∇a_{i}(x^{s+1}) + ∑_{j∈E} λ_{j}b_{j} = x^{s+ \frac{1}{2}} − x^{s+1} \} , s = 0, 1, …,

where ν^{s} ∈ N_{X}(x^{s}) and x^{s+ \frac{1}{2}} − x^{s+1} ∈ N_{X}(x^{s+1}) for all s. The ergodic sequence {μ^{t}} of Lagrange multipliers is defined by

μ^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s} (ω^{s} + \frac{λ^{s}}{α_{s}} ) , t = 1, 2, ….

Note that μ_{i}^{t} ≥ 0 for all i ∈ I and all t.

Clearly, the value of the vector ω^{s} depends on the choice of the normal vector ν^{s} in the construction of the conditional subgradients used in the method (3). In the traditional subgradient optimization method, ν^{s} = 0 for all s, and then, from Le. 5.3, ω^{s} = 0 for all s. In the special case of the method (3) where γ_{X}^{s} is a projected subgradient, ν^{s} = arg minν{∥ν∥^{2} | ∇a_{i}(x^{s})^{T} (ν +γ^{s}) ≥ 0, i ∈ I(x^{s}); b_{j}^{T} (ν +γ^{s}) = 0, j ∈ E}, and the elements ω_{i}^{s}, i ∈ I(x^{s}), and ω_{j}^{s}, j ∈ E, are Lagrange multipliers associated with the constraints of this projection problem.

The vector λ^{s} always contains Lagrange multipliers associated with the constraints of the projection problem x^{s+1} = arg min_{x}\{∥x^{s+ \frac{1}{2}} − x∥^{2} | a_{i}(x) ≤ 0, i ∈ I; b_{j}^{T} x = e_{j}, j ∈ E}.

The following boundedness result is crucial for the convergence of the ergodic sequence {μ^{t}} of multipliers.

Lemma 5.5. The sequences {ω^{s}} and {λ^{s}/α_{s}} are bounded.

Proof. We first prove by contradiction that the sequence {ω^{s}} is bounded.

Suppose that this is not the case. Then there exists a subsequence S such that ∥ω^{s}∥ > 0 for all s ∈ S and {∥ω^{s}∥}_{s∈S} → ∞. Let π^{s} = ω^{s}/∥ω^{s}∥, implying that π^{s} ≥ 0 and ∥π^{s}∥ = 1 for all s ∈ S. According to Prop. 2.2, {x^{s}} → x^{∞}. Suppose that, for some i ∈ I, a_{i}(x^{∞}) < 0. By the continuity of the function a_{i}, it must then hold for all s which are sufficiently large that a_{i}(x^{s}) < 0, ω_{i}^{s} = 0, and π_{i}^{s} = 0; hence, for any i ∈ I \ I(x^{∞}), π_{i}^{s} = 0 for all s ∈ S that are large enough. The sequence {π^{s}}_{s∈S} is clearly bounded and thus has an accumulation point, say π̃. Then, from the preceding, π̃ ∈ Π_{X}(x^{∞}) and ∥π̃∥ = 1.

By Def. 5.4,

∑_{i∈I} π_{i}^{s}∇a_{i}(x^{s}) + ∑_{j∈E} π_{j}^{s}b_{j} = \frac{ν^{s}}{∥ω^{s}∥}, ∀s ∈ S.

In the limit of the subsequence of S corresponding to π̃, ∑_{i∈I(x^{∞})} π̃_{i}∇a_{i}(x^{∞}) + ∑_{j∈E} π̃_{j}b_{j} = 0, since {x^{s}} → x^{∞} and the functions ∇a_{i}, i ∈ I, are continuous, and since the sequence {ν^{t}} is bounded and the sequence {∥ω^{s}∥}_{s∈S} is presumed to tend to infinity. Then, by Le. 5.3, π̃ = 0 must hold, and we have arrived at a contradiction. Hence, the sequence {ω^{s}} is bounded.

To establish that the sequence {λ^{s}/α_{s}} is bounded, we first observe that, from (3), ∥x^{s+ \frac{1}{2}} − x^{s+1}∥/α_{s} ≤ ∥γ^{s} + ν^{s}∥ for all s, which implies that the sequence \{(x^{s+ \frac{1}{2}} − x^{s+1})/α_{s}\} is bounded. Assume then that \{λ^{s}/α_{s}\} is not bounded and define the index set S analogously to the above. Letting π^{s} = λ^{s}/∥λ^{s}∥ for all s ∈ S, Def. 5.4 yields that

∑_{i∈I} π_{i}^{s}∇a_{i}(x^{s+1}) + ∑_{j∈E} π_{j}^{s}b_{j} = \frac{(x^{s+ \frac{1}{2}} − x^{s+1})/α_{s}}{∥λ^{s}∥/α_{s}} , ∀s ∈ S.

Clearly, the right–hand–side of this equality tends to the zero vector and we may derive a contradiction which is analogous with the first part of the proof.

From Def. 5.4 and Le. 5.5 follow that under the conditions (4) the sequence {μ^{t}} is bounded. We conclude this subsection with its main result and an application thereof.

Theorem 5.6 (Convergence of {μ^{t}} to M_{X}(x^{∞})). {dist(μ^{t}, M_{X}(x^{∞}))} → 0.

Proof. From the continuity of the functions a_{i}, i ∈ I, it follows that I(x^{s}) ⊆ I(x^{∞}) for all s that are sufficiently large. From Def. 5.4 it then follows that ω_{i}^{s} = λ_{i}^{s} = 0 for all i ∈ I \ I(x^{∞}) and all s that are sufficiently large, so that {μ_{i}^{t}} → 0, i ∈ I \ I(x^{∞}). Hence, {dist(μ^{t}, Π_{X}(x^{∞}))} → 0.

To simplify the notation, we define ν^{t} = ∑_{i∈I} μ_{i}^{t}∇a_{i}(x^{∞}) + ∑_{j∈E} μ_{j}^{t}b_{j}. From Defs. 3.1 and 5.4 it then follows that

ν^{t} = n^{t} − ∑_{i∈I} A_{t}^{−1} (∑_{s=0}^{t−1} α_{s}ω_{i}^{s} (∇a_{i}(x^{s}) − ∇a_{i}(x^{∞}))

+ ∑_{s=0}^{t−1} λ_{i}^{s} (∇a_{i}(x^{s+1}) − ∇a_{i}(x^{∞}))) .  (15)

Let ε > 0. Le. 3.6 and Thm. 3.7 then yield that dist(n^{t}, −∂f(x^{∞})) ≤ ε/3 for all t that are sufficiently large. We next show that the second term of the right–hand– side of equation (15) tends to the zero vector. Le. 5.5 implies that the sequence {ω_{i}^{s}} is bounded for each i ∈ I. Hence, since the function ∇a_{i} is continuous, there is an iterate t(ε) such that, for all s ≥ t(ε), ω_{i}^{s}∥∇a_{i}(x^{s}) − ∇a_{i}(x^{∞})∥ ≤ ε/(6|I|). Therefore, for all t > t(ε),

A_{t}^{−1} ∑_{s=t(ε)}^{t−1} α_{s}ω_{i}^{s} ∥∇a_{i}(x^{s}) − ∇a_{i}(x^{∞})∥ ≤ A_{t}^{−1} ∑_{s=t(ε)}^{t−1} α_{s} \frac{ε}{6|I|} ≤ \frac{ε}{6|I|}.

Since {A_{t}} → ∞ we have, for all t large enough, A_{t}^{−1} ∑_{s=0}^{t(ε)−1} α_{s}ω_{i}^{s}∥∇a_{i}(x^{s}) − ∇a_{i}(x^{∞})∥ ≤ ε/(6|I|). From the derivations above it follows that, for all t > t(ε) large enough,

∥∑_{i∈I} A_{t}^{−1}∑_{s=0}^{t−1} α_{s}ω_{i}^{s} (∇a_{i}(x^{s})−∇a_{i}(x^{∞}))∥ ≤ ∑_{i∈I} A_{t}^{−1}∑_{s=0}^{t−1} α_{s}ω_{i}^{s} ∥∇a_{i}(x^{s})−∇a_{i}(x^{∞})∥
≤ \frac{ε}{3}.

Analogous to these derivations, it can be shown that the corresponding conclusion holds for the last term of the right–hand–side of equation (15). It then follows that dist(ν^{t}, −∂f(x^{∞})) ≤ ε for all t that are sufficiently large and, consequently, we have that {dist(ν^{t}, −∂f(x^{∞}))} → 0. Now, let T be a subsequence such that

lim_{{t∈T \atop t→∞}} dist (μ^{t}, M_{X}(x^{∞})) = lim sup_{t→∞} dist (μ^{t}, M_{X}(x^{∞})) ,

and μ̃ be an accumulation point of the sequence {μ^{t}}_{t∈T}. From this analysis and the closedness of the sets Π_{X}(x^{∞}) and ∂f(x^{∞}) it follows that the inclusions μ̃ ∈ Π_{X}(x^{∞}) and ∑_{i∈I} μ̃_{i}∇a_{i}(x^{∞}) + ∑_{i∈E} μ̃_{j}b_{j} ∈ −∂f(x^{∞}) hold, thus implying that μ̃ ∈ M_{X}(x^{∞}).

We consider an application of this result to the post-optimal analysis of a special case of the program [P] of the form

\begin{matrix}f^{∗} = min & f(x), \\ s.t. & a_{i}(x) & ≤ & 0, & i ∈ I, \end{matrix}  (16)

where the objective function has the explicit form

f(x) = max_{k∈K} c_{k}(x),  x ∈ ℜ^{n},  (17)

where the functions c_{k} : ℜ^{n} ↦ ℜ, k ∈ K, are convex and differentiable and the set K is finite.

The shadow prices associated with the constraints of the program (16) are the rates of change of the optimal objective value caused by perturbations of the right– hand–sides. Hence, the shadow price, p_{i}, for the i:th constraint is defined as the directional derivative of the perturbation function, v(u) = min{ f(x) | a_{i}(x) ≤ u_{i}, i ∈ I }, at the origin, along the i:th coordinate, that is, p_{i} = v′(0; e_{i}), i ∈ I. If v is differentiable at the origin, then [p_{i}]_{i∈I} = ∇v(0) (Rockafellar, 1970, Cor. 29.1.3). In this case, the ergodic sequence of multipliers provides estimates of the shadow prices, as stated next.

Corollary 5.7 (Shadow prices from multiplier estimates). If the perturbation function v is differentiable at 0, then M_{X}(x^{∞}) = {−∇v(0)}, and {μ^{t}} → −∇v(0).

Proof. It follows by Cor. 29.1.3 in Rockafellar (1970) that the set M_{X}(x^{∞}) is a singleton, which moreover equals −∇v(0). Thm. 5.6 then yields the result.

5.2 Multipliers of objective pieces

Throughout this subsection we assume that the nonsmooth objective function f of the program [P] has the form (17) and the feasible set X is given by (12).

We define the set of multipliers associated with the pieces c_{k} satisfying a complementary slackness condition at x ∈ ℜ^{n} as

Π_{f}(x) = {π ∈ ℜ_{+}^{|K|} | π_{k} (c_{k}(x) − f(x)) = 0, k ∈ K; ∑_{k∈K} π_{k} = 1} .  (18)

Letting ξ ∈ ℜ^{|K|}, the subdifferential of f at x can then be expressed as (e.g., Hiriart-Urruty and Lemaréchal, 1993, Cor. VI:4.4.4)

∂f(x) = { γ ∈ ℜ^{n} | γ = ∑_{k∈K} ξ_{k}∇c_{k}(x); ξ ∈ Π_{f}(x) } .  (19)

For any x ∈ X, let

M_{f}(x) = { η ∈ Π_{f}(x) | 0 ∈ ∑_{k∈K} η_{k}∇c_{k}(x) + N_{X}(x) }  (20)

be the (possibly empty) set of multipliers associated with the pieces c_{k} defining the function f. The optimality conditions for the program [P] can be stated in terms of this set.

Proposition 5.8 (Optimality condition). Let x ∈ X. Then, x ∈ X^{∗} if and only if M_{f}(x) ≠ ∅. Further, the mapping M_{f} is constant on X^{∗} and the set M_{f}(x), x ∈ X^{∗}, is convex and compact.

Proof. The first conclusion is a consequence of Prop. 2.1 and the expressions (19) and (20). The invariance of M_{f}(x) over X^{∗} follows from Prop. VII:3.1.1 in Hiriart-Urruty and Lemaréchal (1993) applied to the reformulation min{ z | z ≥ c_{k}(x), k ∈ K; x ∈ X } of the program [P], and its convexity and compactness are immediate from its definition.

Definition 5.9. The sequence {ξ^{s}} is defined by

ξ^{s} ∈ { ξ ∈ Π_{f}(x^{s}) | ∑_{k∈K} ξ_{k}∇c_{k}(x^{s}) = γ^{s} } , s = 0, 1, …,

where γ^{s} ∈ ∂f(x^{s}) for all s. The ergodic sequence {η^{t}} of multipliers is then defined by

η^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ξ^{s}, t = 1, 2, ….

Note that η^{t} ≥ 0 and ∑_{k∈K} η_{k}^{t} = 1 for all t, so that the sequence {η^{t}} is bounded. Theorem 5.10 (Convergence of {η^{t}} to M_{f}(x^{∞})). {dist(η^{t}, M_{f}(x^{∞}))} →

0.

Proof. As in the proof of Thm. 5.6 we can show that {dist(η^{t}, Π_{f}(x^{∞}))} → 0. Defining γ^{t} = ∑_{k∈K} η_{k}^{t}∇c_{k}(x^{∞}), it follows from Defs. 3.1 and 5.9 that

γ^{t} = g^{t} − ∑_{k∈K} A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ξ_{k}^{s} (∇c_{k}(x^{s}) − ∇c_{k}(x^{∞})) .

Let ε > 0. Thm. 3.7 then yields that dist(g^{t}, −N_{X}(x^{∞})) ≤ ε/2 for all t that are sufficiently large. Using the same technique as in the proof of Thm. 5.6 and utilizing the boundedness of the sequence {ξ^{s}}, we can show that

0 ≤ ∥ ∑_{k∈K} A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ξ_{k}^{s} (∇c_{k}(x^{s}) − ∇c_{k}(x^{∞})) ∥ ≤ \frac{ε}{2}.

It follows that dist(γ^{t}, −N_{X}(x^{∞})) ≤ ε for all t that are sufficiently large, and hence that {dist(γ^{t}, −N_{X}(x^{∞}))} → 0. Using the same technique as in the proof of Thm. 5.6, we can also show that all accumulation points, η̃, of the sequence {η^{t}} fulfil the inclusions η̃ ∈ Π_{f}(x^{∞}) and ∑_{k∈K} η̃_{k}∇c_{k}(x^{∞}) ∈ −N_{X}(x^{∞}), thus implying η̃ ∈ M_{f}(x^{∞}).

As a specialization of this result, let a_{i} ∈ ℜ^{n} and b_{i} ∈ ℜ for all i ∈ L (presumed finite) and consider the system

a_{i}^{T} x ≤ b_{i},  i ∈ L,  (21)

of linear inequalities with solution set Y.

Letting the piece-wise affine function f : ℜ^{n} ↦ ℜ be defined as

f(x) = max_{i∈L} {a_{i}^{T} x − b_{i}} ,  x ∈ ℜ^{n},  (22)

it follows that x ∈ Y if and only if f(x) ≤ 0.

By Farkas’ theorem of the alternative, exactly one of the systems (21) and

∑_{i∈L} η_{i}a_{i} = 0,  ∑_{i∈L} η_{i}b_{i} < 0,  η_{i} ≥ 0,  ∀i ∈ L,  (23)

has a solution. Therefore, the system (23) is consistent if and only if f^{∗} = min_{x∈ℜ^{n}} f(x) > 0. For this case, the next result, which is a consequence of Thm. 5.10, states that an ergodic sequence of multipliers generated within the conditional subgradient method applied to the minimization of f in (22), provides solutions to the system (23) in the limit.

Corollary 5.11 (A Farkas theorem). {∑_{i∈L} η_{i}^{t}a_{i}} → 0, {∑_{i∈L} η_{i}^{t}b_{i}} → −f^{∗}, and η_{i}^{t} ≥ 0, i ∈ L, for all t. Hence, if Y = ∅, then the sequence {η^{t}} tends towards the set of solutions to the system (23).

Proof. The first result follows from Theorem 3.9, identifying {∑_{i∈L} η_{i}^{t}a_{i}} with {g^{t}}. By Definition 5.9, the definitions (18) and (7), and Lemma 3.4,

∑_{i∈L} η_{i}^{t}b_{i} = ∑_{i∈L} A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ξ_{i}^{s}b_{i} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s} ∑_{i∈L} ξ_{i}^{s} (a_{i}^{T} x^{s} − f(x^{s}))

= A_{t}^{−1} ∑_{s=0}^{t−1} α_{s} ((γ^{s})^{T} x^{s} − f(x^{s})) = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s} (γ^{s})^{T} x^{∞} − f_{t}(x^{∞})
= (g^{t})^{T} x^{∞} − f_{t}(x^{∞}) → 0 − f(x^{∞}) = −f^{∗}.

The last result follows from Definition 5.9 and the definition (18).

Further aspects on this result are presented in the next section.

6 ERGODIC UNDERESTIMATING FUNCTIONS

The results established in Sec. 3 will now be utilized to derive a convergent sequence of lower bounds on the optimal value of the program [P]. The results obtained are then utilized to finitely detect the inconsistency and separation in a system of linear inequalities intersected by a convex set. We assume throughout this section that X is bounded.

Definition 6.1. The sequence {f_{t}^{∗}} of lower bounds on f^{∗} is defined by f_{t}^{∗} = min_{x∈X} f_{t}(x).

We show that the sequence {f_{t}^{∗}} of lower bounds converges to the optimal value. Theorem 6.2 (Convergence of lower bounds). f_{t}^{∗} ∈ (−∞, f^{∗}] for all t, and

{f_{t}^{∗}} → f^{∗}.

Proof. From Def. 6.1, and the definitions (7) and (1) it follows that f_{t}^{∗} ≤ f^{∗} for all t. Since X is bounded, f_{t}^{∗} is finite for all t.

By the same definitions, f_{t}^{∗} = f_{t}(x^{∞}) + min_{x∈X}(g^{t})^{T} (x − x^{∞}) for all t. From Thm. 3.8 follows that lim inf_{t→∞}(g^{t})^{T} (x − x^{∞}) ≥ 0 for all x ∈ X, and from Le. 3.4 that {f_{t}(x^{∞})} → f^{∗}. Hence, lim inf_{t→∞} f_{t}^{∗} ≥ f^{∗}. Since f_{t}^{∗} ≤ f^{∗} for all t it follows that lim_{t→∞} f_{t}^{∗} = f^{∗}.

In an application context it is natural to repeatedly save the best upper and lower bounds on the optimal value found so far. In such a manner, the convergent sequence {f_{t}^{∗}} → f^{∗} of lower bounds can be utilized in a termination criterion for the conditional subgradient method (3)–(4). The following result, which is a consequence of Prop. 2.2 and Thm. 6.2, implies that an ε-optimal solution is found finitely.

Corollary 6.3 (Finite termination). Define u_{t} = min_{0≤s≤t} f(x^{s}) and l_{t} = max_{1≤s≤t} f_{s}^{∗} for all t. Then, l_{t} ≤ f^{∗} ≤ u_{t} holds for all t, and for any ε > 0 there is a t(ε) such that u_{t} − l_{t} ≤ ε holds for all t ≥ t(ε).

In Larsson et al. (1996c) the upper and lower bounds defined in the corollary is utilized in a resource directive decomposition scheme for the linear minimum cost multicommodity network flow problem. The results presented in that report illustrate the practical usefulness of the lower bounding procedure derived in this section.

In a forthcoming paper, we will utilize the lower bounding procedure for assessing the quality of solutions obtained within Lagrangean dualization schemes.

As a specialization of the theorem, we consider the generalization of the system (21) to

x ∈ X,  a_{i}^{T} x ≤ b_{i}, i ∈ L,  (24)

and the optimization setting of this system,

f^{∗} = min_{x∈X} f(x),  (25)

where f : ℜ^{n} ↦ ℜ is defined by (22). We define the set Y = {x ∈ ℜ^{n} | f(x) ≤ 0}, and consider solving the program (25) by the conditional subgradient optimization method (3)–(4) extended with the lower bounding procedure of Def. 6.1.

If the system (24) is consistent, then the conditional subgradient method either finds an x^{s} ∈ X ∩ Y, or the sequence \{x^{t}\} → \overline{x} ∈ X ∩ bd Y. The following result, which is a consequence of Thm. 6.2, deals with the case of inconsistency.

Corollary 6.4 (Finite detection of inconsistency and finite separation). If X ∩ Y = ∅, then there is an iteration t_{0} such that f_{t}^{∗} > 0 for all t ≥ t_{0}. If further Y ≠ ∅, then for every t ≥ t_{0} the hyperplane {x ∈ ℜ^{n} | f_{t}(x) = f_{t}^{∗}/2} strictly separates the sets X and Y.

Proof. The first part of the result is immediate from Thm. 6.2.

Since f_{t}(x) ≤ f(x) for all x ∈ ℜ^{n}, it follows that Y ⊆ {x ∈ ℜ^{n} | f_{t}(x) ≤ 0} for all t, and by definition of the sequence {f_{t}^{∗}}, X ⊆ {x ∈ ℜ^{n} | f_{t}(x) ≥ f_{t}^{∗}} for all t. Invoke the first part of the result.

7 CONCLUSIONS AND FURTHER RESEARCH

The analysis of ergodic sequences of subgradients within conditional subgradient optimization schemes reveals new and interesting characteristics of subgradient methods. In particular, they are used to establish the ergodic convergence of sequences of multipliers, thus enabling the performance of sensitivity analyses of solutions obtained by subgradient methods. As a consequence of these results we prove the convergence of a lower bounding procedure, providing a new termination criterion for subgradient methods.

In a forthcoming paper (Larsson et al., 1996d) we apply a conditional subgradient method to a Lagrange dual of a general convex program and establish the ergodic convergence of the sequence of primal subproblem solutions obtained.

The lower bounding procedure of Sec. 6 may be employed to assess the quality of the dual solutions obtained from the method (3) applied to a Lagrange dual of any optimization problem.

Sherali and Choi (1996) apply subgradient methods to Lagrange duals of linear programs and establish ergodic convergence of sequences of subproblem solutions, employing more general choices of subgradient step lengths and convexity weights than those of this paper.

An interesting subject for further research is the study of ergodic sequences of subgradients, normal components, and multipliers under similar, more general rules, as well as for more efficient computational schemes for nondifferentiable optimization. The use of ergodic sequences of subgradients for accelerating subgradient algorithms is another subject for further study.

ACKNOWLEDGEMENTS

We thank an anonymous referee for valuable comments that resulted in an improved presentation. The research was financially supported by grants (Nos. 94-292 and 282-93-1195) from the Swedish Research Council for Engineering Sciences (TFR).

REFERENCES

1. J.-B. Baillon (1975), Un théorème de type ergodique pour les contractions non linéaires dans un espace de Hilbert, Comptes Rendus Hebdomadaires des Séances de l’Académie des Sciences (Paris), Série A, 280, pp. 1511–1514.

2. D.P. Bertsekas (1976), On the Goldstein–Levitin–Polyak gradient projection method, IEEE Transactions on Automatic Control, ac-21, pp. 174–184.

3. J.V. Burke and M.C. Ferris (1991), Characterization of solution sets of convex programs, Operations Research Letters, 10, pp. 57–60.

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

5. J.V. Burke and J.J. Moré (1994), Exposing constraints, SIAM Journal on Optimization, 3, pp. 573–595.

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

7. V.F. Dem’janov and V.K. Šomesova (1978), Conditional subdifferentials of convex functions, Soviet Mathematics Doklady, 19, pp. 1181–1185.

8. V.F. Dem’yanov and L.V. Vasil’ev (1985), Nondifferentiable Optimization, Optimization Software, New York, NY.

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

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

11. M.L. Fisher (1985), An applications oriented guide to Lagrangian relaxation, Interfaces, 15, pp. 10–21.

12. M. Guignard (1969), Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space, SIAM Journal on Control, 7, pp. 232–241.

13. J.L. Higle and S. Sen (1991), Stochastic decomposition: An algorithm for two-stage linear programs with recourse, Mathematics of Operations Research, 16, pp. 650–669.

14. J.-B. Hiriart-Urruty and C. Lemaréchal (1993), Convex Analysis and Minimization Algorithms I & II, Springer-Verlag, Berlin.

15. S. Kim and H. Ahn (1991), Convergence of a generalized subgradient method for nondifferentiable convex optimization, Mathematical Programming, 50, pp. 75–80.

16. T. Larsson and Z. Liu (1997), A Lagrangean relaxation scheme for structured linear programs with application to multicommodity network flows, Optimization, 40, pp. 247–284.

17. T. Larsson, M. Patriksson and A.-B. Strömberg (1996a), Conditional subgradient optimization: Theory and applications, European Journal of Operational Research, 88, pp. 382–403.

18. T. Larsson, M. Patriksson and A.-B. Strömberg (1996b), Ergodic results in subgradient optimization, in: Nonlinear Optimization and Applications, G. Di Pillo, F. Giannessi, eds., Proceedings of the International School of Mathematics “G. Stampacchia” 21st Workshop on Nonlinear Optimization and Applications, Erice, Italy, June, 1995, Plenum Press, New York, pp. 229–248.

19. T. Larsson, M. Patriksson and A.-B. Strömberg (1996c), Ergodic results and bounds on the optimal value in subgradient optimization, in: Operations Research Proceedings 1995, P. Kleinschmidt, A. Bachem, U. Derigs, D. Fischer, U. Leopold-Wildburger, R. Möhring, eds., Selected papers of the Symposium on Operations Research, Passau, Germany, September, 1995, Springer-Verlag, Berlin, pp. 30–35.

20. T. Larsson, M. Patriksson and A.-B. Strömberg (1996d), Ergodic, primal convergence in dual subgradient schemes for convex programming, Report LiTH-MAT-R-96-26, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden.

21. D. G. Luenberger (1984), Linear and Nonlinear Programming, second ed. Addison-Wesley, Reading, MA.

22. J. Petersson and M. Patriksson (1997), Topology optimization of sheets in contact by a subgradient method, International Journal of Numerical Methods in Engineering, 40, pp. 1295–1321.

23. B.T. Polyak (1987), Introduction to optimization, Optimization Software, New York, NY.

24. S.M. Robinson (1984), Local structure of feasible sets in nonlinear programming, part II: Nondegeneracy, Mathematical Programming Study, 22, pp. 217–230.

25. R.T. Rockafellar (1970), Convex Analysis, Princeton University Press, Princeton, NJ.

26. A. Ruszczyński and W. Syski (1983), Stochastic approximation method with gradient averaging for unconstrained problems, IEEE Transactions on Automatic Control, ac-28, pp. 1097–1105.

27. H.D. Sherali and G. Choi (1996), Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs, Operations Research Letters, 19, pp. 105–113.

28. N.Z. Shor (1985), Minimization Methods for Non-Differentiable Functions, Springer-Verlag, Berlin.

29. N.Z. Shor (1991), The development of numerical methods for nonsmooth optimization in the USSR, in: History of Mathematical Programming: A Collection of Personal Reminiscences, J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver, eds., North-Holland, Amsterdam, pp. 135– 139.

30. A.-B. Strömberg (1997), Conditional Subgradient Methods and Ergodic Convergence in Nonsmooth Optimization, PhD Thesis, Linköping Studies in Science and Technology, Dissertations, No. 467, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden.

31. E.H. Zarantonello (1971), Projections on convex sets in Hilbert space and spectral theory, in: Contributions to Nonlinear Functional Analysis, E.H. Zarantonello, ed., Proceedings of a Symposium Conducted by the Mathematics Research Center, University of Wisconsin, Madison, April 1971, Academic Press, New York, NY, pp. 237–424.

[figure: f(x); [x^{1},f(x^{1})]; [x^{2},f(x^{2})]; [x^{3},f(x^{3})]; [x^{∞},f^{∗}]; f_{1}(x); f_{2}(x); f_{3}(x); f_{∞}(x)]

FIGURE 1: Iteration points and affine underestimates of f.

[figure: X; x^{∗}; ^{f(x)= \frac{1}{6}}; ^{f(x)= \frac{1}{3}}; ^{f(x)= \frac{1}{2}}; a); X; x^{0}; x^{3}; x^{2}; x^{1}; x^{∞}; ϱ_{1}(x)=0; ϱ_{3}(x)=0; ϱ_{2}(x)=0; ϱ_{∞}(x)=0; b)]

FIGURE 2: a) The set X and level curves of f. b) Iteration points and hyperplanes defining valid inequalities for X.