ERGODIC RESULTS IN SUBGRADIENT OPTIMIZATION^{∗}

Torbjörn Larsson,^{1} Michael Patriksson,^{2} and Ann-Brith Strömberg^{3}

1,3 Division of Optimization Department of Mathematics Linköping Institute of Technology S-581 83 Linköping, Sweden 1 e-mail: tl@math.liu.se 3 e-mail: anstr@math.liu.se 2 Department of Mathematics, Box 354350 University of Washington Seattle, WA 98195-4350 e-mail: patrikss@math.washington.edu or mipat@math.liu.se

Abstract: Subgradient methods are popular tools for nonsmooth, convex minimization, especially in the context of Lagrangean relaxation; their simplicity has been a main contribution to their success. As a consequence of the nonsmoothness, it is not straightforward to monitor the progress of a subgradient method in terms of the approximate fulfilment of optimality conditions, since the subgradients used in the method will, in general, not accumulate to subgradients that verify optimality of a solution obtained in the limit. Further, certain supplementary information, such as convergent estimates of Lagrange multipliers, is not directly available in subgradient schemes.

As a means for overcoming these weaknesses of subgradient optimization 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 (of which the traditional subgradient optimization method is a special case) with divergent series step lengths, which generates a sequence of iterates that converges to an optimal solution. We show that the elements of the ergodic sequence of subgradients in the limit fulfil the optimality conditions at this optimal solution. Further, we use the convergence properties of the ergodic sequence of subgradients to establish convergence of an ergodic sequence of Lagrange multipliers. Finally, some potential applications of these ergodic results are briefly discussed. Key Words: Nonsmooth minimization, Conditional subgradient optimization, Ergodic sequences, Lagrange multipliers.

1 INTRODUCTION

1.1 Background and motivation

Let the function f : ℜ^{n} ↦ ℜ be nonsmooth and convex and thus everywhere continuous and subdifferentiable. Further, let X ⊆ ℜ^{n} be a nonempty, closed and convex set, and 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).

Defining the lower level set of the function f as

L_{f}(z) = { x ∈ ℜ^{n} | f(x) ≤ z } , z ∈ ℜ,

the solution set of the program [P] is the nonempty, closed and convex set X^{∗} = X ∩ L_{f}(f^{∗}).

To enable the statement of optimality conditions for the program [P], we first give some basic definitions (e.g., Rockafellar, 1970a, and Hiriart-Urruty and Lemaréchal, 1993a). The subdifferential of f at x ∈ ℜ^{n} is the nonempty, convex and compact set

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

the elements of which are called subgradients. The normal cone to the set X at some x ∈ X is (e.g., Lemaréchal and Hiriart-Urruty, 1993a, Definition III:5.2.3) the set

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

which is nonempty, closed, and convex. The tangent cone to the set X at x ∈ X (ibid., Definition III:5.1.1) may be expressed as the polar cone to N_{X}(x) (ibid., Corollary III:5.2.5), that is, the set

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

which is nonempty, closed and convex. Conversely, N_{X}(x) is the polar cone to T_{X}(x) (ibid., Proposition III:5.2.4). If x ∈ int X, then N_{X}(x) = {0} and T_{X}(x) = ℜ^{n}.

Optimality conditions for the program [P] are given in the next proposition (ibid., Theorem VII:1.1.1 and Condition VII:(1.1.3)). Here, and in the following,

P_{S}(v) = arg min_{u∈S} ∥ u − v ∥

denotes the Euclidean projection of a vector v ∈ ℜ^{n} onto a nonempty, closed and convex set S ⊆ ℜ^{n}.

Proposition 1.1 (Optimality conditions). x ∈ X^{∗} if and only if there exists a γ ∈ ∂f(x) such that P_{−T_{X}(x)}(γ) = 0 or, equivalently, ∂f(x) ∩ −N_{X}(x) ≠ ∅. □

The next proposition states important properties of the set ∂f(x)∩−N_{X}(x), x ∈ X^{∗}, and follows from the results given above and a result of Burke and Ferris (1991, Lemma 2). It will be useful later in our analysis.

Proposition 1.2 For any x ∈ X^{∗}, the nonempty set ∂f(x) ∩ −N_{X}(x) is convex and compact, and ∂f(y) ∩ −N_{X}(y) = ∂f(x) ∩ −N_{X}(x) for all y ∈ X^{∗}. □

The following proposition, which is easily established, gives a geometric interpretation of the elements of the set ∂f(x) ∩ −N_{X}(x), x ∈ X^{∗}.

Proposition 1.3 (Separation). Let x ∈ X^{∗}. Then, the hyperplane

Hγ(x) = { y ∈ ℜ^{n} | γ^{T} (y − x) = 0 }

separates X and L_{f}(f^{∗}) if and only if γ ∈ ∂f(x) ∩ −N_{X}(x). □

As compared to the case of smooth convex minimization, the task of determining whether or not a certain x ∈ X solves the program [P] is, in general, computationally more expensive; recall in particular that even if an optimal solution x ∈ X^{∗} is at hand, it is, in general, nontrivial to find a γ ∈ ∂f(x) that verifies optimality (e.g., satisfies the conditions of Proposition 1.1). Both these tasks may be performed by, for example, solving the optimization problem

v(x) = min_{γ∈∂f(x)} ∥ P_{−T_{X}(x)}(γ) ∥^{2}.

The value v(x) is zero if and only if x ∈ X^{∗}.^{1} If, for example, the subdifferential set and the tangent cone are polyhedral with explicit representations, then the function v is evaluated by solving a quadratic program. If the function f is implicitly defined, for example when the program [P] is a Lagrangean dual problem, one may have to invoke a column (i.e., a subgradient) generation scheme to enable the evaluation of v.

We consider subgradient optimization methods for solving the program [P]. These methods originate in a work by N.Z. Shor from 1962; 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 shown to be practically useful. They have therefore been frequently applied, particularly in connection with Lagrangean duality (e.g., Fisher, 1981 and 1985, and Beasley, 1993).

Given an initial iterate x^{0} ∈ X, the traditional subgradient optimization method for solving the program [P] (e.g., Polyak, 1969, or Shor, 1985) is given by the iteration formula

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

where γ(x^{t}) ∈ ∂f(x^{t}) and α_{t} > 0 is the step length.

For the case of unconstrained optimization, Ermol’ev (1966) proved convergence of the method (1.4) using step lengths according to a divergent series, and Polyak (1967 and 1969) extended it to the case of convex constraints and gave additional convergence results.

Even though subgradient optimization methods are proven convergent, the objective value can not be guaranteed to descend in each iteration.^{2} Further, in general {P_{−T_{X}(x^{t})}(γ(x^{t}))} ↛ 0, and even if x^{t} ∈ X^{∗} it is quite likely that P_{−T_{X}(x^{t})}(γ(x^{t})) ≠ 0. Hence, the progress of subgradient optimization methods can not be monitored in terms of the approximate fulfilment of optimality conditions (e.g., those of Proposition 1.1).

1The function v : X ↦ ℜ_{+} is an example of a merit function for the problem [P].

2However, their computational burden in each iteration is low in comparison with that of descent methods for nonsmooth minimization, and a larger number of iterations can therefore be allowed.

In contrast, termination criteria in descent methods (for smooth or nonsmooth minimization) are often based on the approximate fulfilment of optimality conditions. Further, such methods enable the calculation of supplementary and useful information. An example of this is the convergent lower bound on the optimal value in the method of Frank and Wolfe (1956) for constrained, smooth, convex minimization. Another example is the availability of convergent multiplier estimates from the solutions to the direction finding subproblems in bundle methods; their values are of particular interest in applications where the multipliers have physical interpretations (e.g., Ben-Tal and Bendsøe, 1993).

A frequently used technique for inducing properties that an original sequence is lacking is to construct an auxiliary, ergodic, sequence from the original one, that is, a sequence with elements that are weighted averages of those of the original sequence. Typical applications of such averaging processes are the smoothing of oscillations in a nonconvergent sequence and the filtering out of stochastic noise (see, e.g., Kornai and Lipták, 1965; Dunn, 1973; and Powell and Sheffi, 1982).

We will show that the elements of an ergodic sequence of subgradients will, in the limit, fulfil the optimality conditions of Proposition 1.1; hence, the construction of such a sequence introduces the possibility to employ a termination criterion which is related to the approximate fulfilment of these conditions and, further, it enables the calculation of convergent Lagrange multiplier estimates. Subgradient optimization methods thus have an inherent capability of utilizing information assembled during the iteration process. This observation reveals a new characteristic of subgradient optimization methods and deepens the understanding of their behaviour. The practical usefulness of the ergodic results in this work will be demonstrated in a subsequent report.

1.2 Basic concepts

The ergodic results to be presented are derived for the conditional subgradient optimization method (Larsson et al., 1992), which generalizes the method (1.4) 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 when applied to three types of structured optimization models is better than that of the method (1.4).

The basis for the development of the generalized method is a relaxation of the subdifferential definition (1.1). The conditional subdifferential of f with respect to the feasible set X at x ∈ X (see Dem’janov and Šomesova, 1978 and 1980) 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). Dem’janov and Šomesova (1978 and 1980) show the following result.

Proposition 1.4 (Conditional subdifferential). ∂^{X}f(x) = ∂f(x) + N_{X}(x), x ∈ X. □

The optimality conditions in Proposition 1.1 can be stated in terms of the conditional subdifferential.

Proposition 1.5 (Optimality condition). x ∈ X^{∗} if and only if 0 ∈ ∂^{X}f(x). □

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

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

where α_{t} > 0 and γ^{X}(x^{t}) is a conditional subgradient of f at x^{t}, that is,

γ^{X}(x^{t}) = γ(x^{t}) + ν(x^{t}), with γ(x^{t}) ∈ ∂f(x^{t}) and ν(x^{t}) ∈ N_{X}(x^{t}).

Note that the vector x^{t+ \frac{1}{2}} − x^{t+1} ∈ N_{X}(x^{t+1}). Clearly, if \{ν(x^{t})\} = \{0\}, then the method (1.5) reduces to the method (1.4). In the case where the set X is stated in terms of explicit constraints (and fulfils some constraint qualification) the normal vector ν(x^{t}) is a nonnegative linear combination of the outward normals of the constraints that are active at x^{t}.

Choosing ν(x^{t}) = P_{N_{X}(x^{t})}(−γ(x^{t})) results in γ^{X}(x^{t}) = P_{−T_{X}(x^{t})}(γ(x^{t})) (see Larsson et al., 1992, Lemma 3.2), defining the special case of the method (1.5) that is called the subgradient projection method; for the case of a polyhedral feasible set, the direction −γ^{X}(x^{t}) from x^{t} is then feasible.

We consider step lengths satisfying the divergent series conditions

α_{t} > 0, ∀t, {α_{t}} → 0, and ∑_{t=0}^{∞} α_{t} = ∞,  (1.6)

and the additional condition

∑_{t=0}^{∞} α_{t}^{2} < ∞.  (1.7)

The following convergence result, where the conditions (1.6) yield {f(x^{t})} → f^{∗} and the addition of the condition (1.7) leads to the convergence also of the sequence {x^{t}}, is given by Larsson et al. (1992, Theorem 2.7).

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

The boundedness of the sequence {γ(x^{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, boundedness of the sequence {ν(x^{t})} may always be imposed.^{3} If subgradient projection is used, then ∥ν(x^{t})∥ ≤ ∥γ(x^{t})∥ so that the sequence {ν(x^{t})} is bounded whenever this is the case for the sequence {γ(x^{t})}.

To establish convergence of the method (1.5) for adaptive step length selection rules, based on line searches or formulas involving estimates of the optimal value, the almost complete relaxation strategy of Dem’yanov and Vasil’ev (1985, Section 3.4) can be used (Corollary 2.8 in Larsson et al., 1992). It works as follows. Define two sequences, \{\underline{α}_{t}\} and \{\overline{α}_{t}\}, with \underline{α}_{t} ≤ \overline{α}_{t} for all t, and both satisfying the conditions (1.6) and (1.7).^{4} Suppose that, at some iteration t, an adaptive rule has generated a (tentative) step length β_{t}. The step length α_{t} used is defined as the projection of β_{t} onto the interval [\underline{α}_{t}, \overline{α}_{t}]. The sequence \{α_{t}\}, resulting from this safeguarding strategy, satisfies the conditions (1.6) and (1.7).^{5}

3For example, by choosing the elements to satisfy ∥ν(x^{t})∥ ≤ c for some c ≥ 0.

4It may, for example, be appropriate to let the sequences be given by \underline{α}_{t} = \underline{c}/(t+1) and \overline{α}_{t} = \overline{c}/(t+1), t = 0, 1, …, where \underline{c} > 0 and \overline{c} > 0 are very small and very large constants, respectively.

Now, consider the application of the method (1.5)–(1.7) to the program [P] and suppose that during the first t iterations the subgradients {γ(x^{s})}_{s=0}^{t−1} have been used to define the step directions. We then 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}} γ(x^{s}), t = 1, 2, ….

It will be shown (in Theorem 3.4) that, provided that the sequences {γ(x^{t})} and {ν(x^{t})} are bounded, the elements of the ergodic sequence {g^{t}} in the limit fulfil the optimality conditions given in Proposition 1.1.

Note that the sequence {g^{t}} is calculated beside the sequence {x^{t}} and that it therefore does not affect the course of the method (1.5)–(1.7). The use of the sequence {g^{t}} for accelerating subgradient optimization algorithms is a subject for further research.

1.3 Outline

In Section 2 we define ergodic sequences of subgradients, normal cone elements, and objective values evaluated in the method (1.5), and of certain auxiliary functions. We also state convergence properties of the sequences of auxiliary functions. Then, in Section 3, we derive the main result that the elements of the ergodic sequence of subgradients tend toward the set ∂f(x) ∩ −N_{X}(x), for some optimal solution x. We also give ergodic results for sequences of conditional subgradients. Section 4 contains convergence results for an ergodic sequence of Lagrange multipliers. It is shown that, under a strong Slater constraint qualification, the elements of this ergodic sequence tend toward the set of Lagrange multipliers at an optimal solution; a corresponding result holds for multipliers associated with objective pieces. Finally, in Section 5, we discuss some opportunities for further research.

2 TECHNICAL PRELIMINARIES

We first define the sequences to be studied; these are ergodic sequences of the subgradients and the normal cone elements, respectively, generated in the method (1.5). The weights employed in the construction of the ergodic sequences are based on the step lengths used in this method. Then, we establish properties of sequences of certain affine functions in order to derive convergence results for the ergodic sequence of subgradients.

We denote by A_{t} the cumulative step length of the method (1.5) up to iteration t, that is,

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

Definition 2.1 (Ergodic sequence of subgradients). Let the method (1.5) be applied to the program [P]. The ergodic sequence {g^{t}} of subgradients is defined by

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

5Traditionally, the divergent series conditions (1.6) and (1.7) are fulfilled through the choice of step lengths according to some appropriate and a priori determined formula, e.g., α_{t} = 1/(t+1), t = 0, 1, . . ..

This ergodic sequence of subgradients is of primary interest in this work. Clearly, each vector g^{t} is a convex combination of the subgradients {γ(x^{s})}_{s=0}^{t−1}. A recursive computation of g^{t} can be implemented using the formula^{6}

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

Definition 2.2 (Ergodic sequence of normal vectors). Let the method (1.5) be applied to the program [P]. The ergodic sequence of normal terms of the conditional subgradients is defined by

n_{c}^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ν(x^{s}), t = 1, 2, …,

the ergodic sequence of the projection steps is defined by

n_{p}^{t} = A_{t}^{−1} ∑_{s=0}^{t−1}(x^{s+ \frac{1}{2}} − x^{s+1}), t = 1, 2, …,

and the ergodic sequence of normal vectors is then defined by

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

Clearly, n_{c}^{t} is a convex combination of the normal terms of the conditional subgradients used up to iteration t of the method (1.5) while n_{p}^{t} is a positive linear combination of its projection steps. If the traditional subgradient optimization method (1.4) is employed then, for all t, n_{c}^{t} = 0 and n^{t} = n_{p}^{t}.

The following result is the first step towards a convergence result for the ergodic sequence {g^{t}}.

Lemma 2.3 (Boundedness of {g^{t}} and {n^{t}}). Let the sequences {g^{t}} and {n^{t}} be given by Definitions 2.1 and 2.2, respectively. If the sequences {γ(x^{s})} and {ν(x^{s})} are bounded, then this is also true for the sequences {g^{t}} and {n^{t}}.

Proof. Since the elements g^{t} are convex combinations of {γ(x^{s})}_{s=0}^{t−1}, the sequence {g^{t}} is also bounded. Analogously, since each n_{c}^{t} is a convex combination of {ν(x^{s})}_{s=0}^{t−1}, the sequence \{n_{c}^{t}\} is also bounded. By the iteration formula (1.5), ∥x^{s+ \frac{1}{2}} − x^{s+1}∥ ≤ α_{s}∥γ^{X}(x^{s})∥ ≤ α_{s}(∥γ(x^{s})∥ + ∥ν(x^{s})∥) for all s. Using the same arguments as above, it follows that the sequence {n_{p}^{t}} is bounded. Hence, the sequence {n^{t}} is bounded. □

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

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

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

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

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

6This remark applies to all ergodic sequences to be defined in this report.

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}) + γ(x^{s})^{T} (x − x^{s})) , x ∈ ℜ^{n}.  (2.3)

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. 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 (1.5). From Definition 2.1 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}.  (2.4)

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}ν(x^{s})^{T} (x^{s} − x) + (x^{s+ \frac{1}{2}} − x^{s+1})^{T} (x^{s+1} − x)) , x ∈ ℜ^{n}. (2.5)

Using that, for all s, ν(x^{s}) ∈ N_{X}(x^{s}) and x^{s+ \frac{1}{2}} − x^{s+1} ∈ N_{X}(x^{s+1}), and the definition (1.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. From Definition 2.2 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 2.4 (Convergence of {δ_{t}(x^{∞})} and {ϱ_{t}(x^{∞})} to 0 and of {φ_{t}} to f^{∗}). Let the method (1.5)–(1.7) be applied to the program [P] and let the sequences {δ_{t}(x)}, {ϱ_{t}(x)}, and {φ_{t}} be given by the definitions (2.4), (2.5), and (2.2), respectively. Suppose that the sequences {γ(x^{s})} and {ν(x^{s})} are bounded. Then, {δ_{t}(x^{∞})} → 0, {ϱ_{t}(x^{∞})} → 0, and {φ_{t}} → f^{∗}.

Proof. By Proposition 1.6, {x^{t}} → x^{∞}. From the iteration formula (1.5),

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

Repeated application of the second inequality and utilization of the definitions (2.4), (2.5), and (2.2), result in the inequality

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

Since δ_{t}(x^{∞}) ≥ 0, ϱ_{t}(x^{∞}) ≥ 0, φ_{t} ≥ f^{∗}, and A_{t} > 0, it is immediate that

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

Let t → ∞ and invoke the conditions (1.6) and (1.7). □

Corollary 2.5 Let the assumptions of Lemma 2.4 hold. Then, {δ_{t}(x^{t})} → 0 and {ϱ_{t}(x^{t})} → 0.

Proof. Definition 2.1, and the definitions (2.3) and (2.4), yield

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

From Definition 2.2, and the definition (2.5), follow that

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

Proposition 1.6, Lemma 2.3, the continuity of f, and Lemma 2.4 yield that the right hand sides of both the above equations tend to 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})), and a small value of ϱ_{t}(x^{t}) yields 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).

Lemma 2.6 ({g^{t}+n^{t}} tends to 0). Let the method (1.5)–(1.7) be applied to the program [P] and let the sequences {g^{t}} and {n^{t}} be given by Definitions 2.1 and 2.2, respectively. Suppose that the sequences {γ(x^{s})} and {ν(x^{s})} are bounded. Then, {g^{t} + n^{t}} → 0.

Proof. By Definitions 2.1 and 2.2, and the iteration formula (1.5),

g^{t} + n^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} (α_{s}γ^{X}(x^{s}) + x^{s+ \frac{1}{2}} − x^{s+1})
= 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}) .

Proposition 1.6 yields that {x^{t}} → x^{∞}. The result then follows from the definition (2.1) and the condition (1.6). □

In our continued analysis we will by d_{Y} (x) denote the Euclidean distance between a point x ∈ ℜ^{n} and a convex set Y ⊆ ℜ^{n}, that is,

d_{Y} (x) = min_{y∈Y} ∥y − x∥ .

The function d_{Y} : ℜ^{n} ↦ ℜ_{+} is convex and continuous.

3 ERGODIC RESULTS FOR SUBGRADIENTS

We first show that the distance between g^{t} and the set ∂f(x^{∞}) tends to zero. Then, we establish that the projection of g^{t} onto the set −T_{X}(x^{∞}) tends to zero. The combination of these results yields that the elements of the sequence {g^{t}} in the limit provide fulfilment of the optimality conditions given in Proposition 1.1. Finally, we give corresponding results for an ergodic sequence of conditional subgradients.

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

Theorem 3.1 (Convergence of {g^{t}} to ∂f(x^{∞})). Let the method (1.5)–(1.7) be applied to the program [P] and let the sequence {g^{t}} be given by Definition 2.1. Suppose that the sequences {γ(x^{s})} and {ν(x^{s})} are bounded. Then,

{d_{∂f(x^{∞})}(g^{t})} → 0.

Proof. By the properties of ∂f(x^{∞}), the sequence {d_{∂f(x^{∞})}(g^{t})} is well defined. Let T be a subsequence such that

lim_{t→∞^{t∈T}} d_{∂f(x^{∞})} (g^{t}) = lim sup_{t→∞} d_{∂f(x^{∞})} (g^{t}) .

By Lemma 2.3, the sequence {g^{t}}_{t∈T} is bounded and thus has an accumulation point, say g̃. From the definitions (2.3) and (2.4) follow that, for all t and any y ∈ ℜ^{n},

f(y) ≥ f_{t}(y) = f_{t}(x^{∞}) + (g^{t})^{T} (y − x^{∞}) = f(x^{∞}) + (g^{t})^{T} (y − x^{∞}) − δ_{t}(x^{∞}).

From Lemma 2.4 then follows that, for any y ∈ ℜ^{n},

g̃^{T} (y − x^{∞}) ≤ lim sup_{t→∞^{t∈T}} (g^{t})^{T} (y − x^{∞}) ≤ f(y) − f(x^{∞}) + lim_{t→∞^{t∈T}} δ_{t}(x^{∞}) = f(y) − f(x^{∞}).

Hence, g̃ ∈ ∂f(x^{∞}), implying that d_{∂f(x^{∞})}(g̃) = 0. By the continuity of the function d_{∂f(x^{∞})}, d_{∂f(x^{∞})}(g̃) = lim_{t∈T , t→∞} d_{∂f(x^{∞})}(g^{t}), and the result follows. □

For any ε ≥ 0, the ε-subdifferential of f at x ∈ ℜ^{n} is defined as (e.g., Hiriart-Urruty and Lemaréchal, 1993b, Definition XI:1.1.1)

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

For any ε_{2} > ε_{1} ≥ 0 and any x ∈ ℜ^{n}, ∂_{ε_{1}}f(x) ⊆ ∂_{ε_{2}}f(x), and ∂_{0}f(x) = ∂f(x). Using Definition 2.1 and the definitions (2.3) and (2.4) we derive that g^{t} is a δ_{t}(x)-subgradient of f at x for any x ∈ ℜ^{n}; note in particular that g^{t} is a δ_{t}(x^{t})-subgradient of f at x^{t} and that {δ_{t}(x^{t})} → 0 by Corollary 2.5.

From the definition (2.5) follows that, for every t, ϱ_{t}(x) ≥ 0 is a valid inequality for the convex set X, and from Lemma 2.4 that {ϱ_{t}(x^{∞})} → 0. Hence, in the limit, the sequence {ϱ_{t}} of affine functions provides supporting hyperplanes to the set X at x^{∞}; the next theorem further develops this remark.

Theorem 3.2 (Convergence of {g^{t}} to −N_{X}(x^{∞})). Let the method (1.5)–(1.7) be applied to the program [P] and let the sequence {g^{t}} be given by Definition 2.1. Suppose that the sequences {γ(x^{s})} and {ν(x^{s})} are bounded. Then,

{d_{−N_{X}(x^{∞})}(g^{t})} → 0.

Proof. By the properties of N_{X}(x^{∞}), the sequences {d_{−N_{X}(x^{∞})}(g^{t})} and {d_{N_{X}(x^{∞})}(n^{t})}, where n^{t} is given by Definition 2.2, are well defined. Let T be a subsequence such that

lim_{t→∞^{t∈T}} d_{N_{X}(x^{∞})} (n^{t}) = lim sup_{t→∞} d_{N_{X}(x^{∞})} (n^{t}) .

By Lemma 2.3, the sequence {n^{t}}_{t∈T} is bounded and thus has an accumulation point, say ñ. From the definition (2.5) follows that, for all t and any y ∈ X,

(n^{t})^{T} (y − x^{∞}) = −ϱ_{t}(y) + ϱ_{t}(x^{∞}) ≤ ϱ_{t}(x^{∞}).

From Lemma 2.4 follow that, for any y ∈ X,

ñ^{T} (y − x^{∞}) ≤ lim sup_{t→∞^{t∈T}} (n^{t})^{T} (y − x^{∞}) ≤ lim_{t→∞^{t∈T}} ϱ_{t}(x^{∞}) = 0.

Hence, ñ ∈ N_{X}(x^{∞}), implying that d_{N_{X}(x^{∞})}(ñ) = 0. By the continuity of the function d_{N_{X}(x^{∞})}, d_{N_{X}(x^{∞})}(ñ) = lim_{t∈T , t→∞} d_{N_{X}(x^{∞})}(n^{t}). Therefore, for any ε > 0 and all t that are sufficiently large, d_{N_{X}(x^{∞})}(n^{t}) < ε/2, and, by Lemma 2.6, ∥g^{t} + n^{t}∥ < ε/2, so that d_{−N_{X}(x^{∞})}(g^{t}) ≤ d_{−N_{X}(x^{∞})}(−n^{t}) + ∥g^{t} + n^{t}∥ < ε. The theorem follows. □

From Definition 2.2 and the definition (2.5) follow that, for any x ∈ X and all t,

n^{t} ∈ { ν ∈ ℜ^{n} | ν^{T} (y − x) ≤ ϱ_{t}(x), ∀y ∈ X } .

This set is nonempty, closed, and convex, and it clearly contains N_{X}(x) (cf. the relationship between the ε-subdifferential and the subdifferential).

Theorem 3.3 (Projection of g^{t} onto −T_{X}(x^{∞}) tends to 0). Let the assumptions of Theorem 3.2 hold and let T_{X}(x) be defined by (1.3). Then,

{P_{−T_{X}(x^{∞})}(g^{t})} → 0.

Proof. The sequence {P_{−T_{X}(x^{∞})}(g^{t})} is well defined. Applying the Moreau decomposition (Zarantonello, 1971, Lemma 2.2) to g^{t}, with respect to the polar cones N_{X}(x^{∞}) and T_{X}(x^{∞}), yields

g^{t} = P_{−N_{X}(x^{∞})} (g^{t}) + P_{−T_{X}(x^{∞})} (g^{t}) , ∀t,

which implies that ∥P_{−T_{X}(x^{∞})}(g^{t})∥ = ∥g^{t} − P_{−N_{X}(x^{∞})}(g^{t})∥ = d_{−N_{X}(x^{∞})}(g^{t}). The result then follows from Theorem 3.2. □

Theorem 3.4 (Optimality fulfilment). Let the method (1.5)–(1.7) be applied to the program [P] and let the sequence {g^{t}} be given by Definition 2.1. Suppose that the sequences {γ(x^{s})} and {ν(x^{s})} are bounded. Then,

{d_{∂f(x^{∞})∩−N_{X}(x^{∞})}(g^{t})} → 0

or, equivalently,

{d_{∂f(x^{∞})}(g^{t})} → 0 and {P_{−T_{X}(x^{∞})}(g^{t})} → 0.

Proof. The first statement follows from Theorems 3.1 and 3.2, and the second statement is then implied by Theorem 3.3. □

The corresponding ergodic result for the sequence {n^{t}} is {d_{N_{X}(x^{∞})∩−∂f(x^{∞})}(n^{t})} → 0 or, equivalently, {d_{−∂f(x^{∞})}(n^{t})} → 0 and {P_{T_{X}(x^{∞})}(n^{t})} → 0.

In the interesting special case of unconstrained minimization the optimality conditions given in Proposition 1.1 reduce to 0 ∈ ∂f(x) and Theorem 3.4 reduces to the following.

Corollary 3.5 (Convergence of {g^{t}} to 0). Suppose that X = ℜ^{n} and that the assumptions of Theorem 3.4 hold. Then,

{g^{t}} → 0. □

Finally in this section, we define the ergodic sequence of conditional subgradients by

g^{t} + n_{c}^{t} = A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}γ^{X}(x^{s}), t = 1, 2, …,  (3.1)

where g^{t} and n_{c}^{t} are given by Definitions 2.1 and 2.2, respectively.

Theorem 3.6 (Optimality fulfilment). Let the assumptions of Theorem 3.4 hold and let the sequence {g^{t} + n_{c}^{t}} be defined by (3.1). Then,

{d_{∂^{X}f(x^{∞})∩−N_{X}(x^{∞})}(g^{t} + n_{c}^{t})} → 0

or, equivalently,

{d_{∂^{X}f(x^{∞})}(g^{t} + n_{c}^{t})} → 0 and {P_{−T_{X}(x^{∞})}(g^{t} + n_{c}^{t})} → 0.

Proof. Analogously to the proof of Theorem 3.2 we can show that {d_{N_{X}(x^{∞})}(n_{c}^{t})} → 0 and {d_{N_{X}(x^{∞})}(n_{p}^{t})} → 0. From Lemma 2.6 and Definition 2.2, {g^{t} + n_{c}^{t} + n_{p}^{t}} → 0, which then implies that {d_{−N_{X}(x^{∞})}(g^{t} + n_{c}^{t})} → 0. From Theorem 3.1 then follows that {d_{∂f(x^{∞})+N_{X}(x^{∞})}(g^{t} + n_{c}^{t})} → 0. Utilizing the polarity of the normal and tangent cones we can, analogously to the proof of Theorem 3.3 show that the projection of g^{t} + n_{c}^{t} onto −T_{X}(x^{∞}) vanishes in the limit. □

The corresponding ergodic result for the sequence {n_{p}^{t}} is {d_{N_{X}(x^{∞})∩−∂^{X}f(x^{∞})}(n_{p}^{t})} → 0 or, equivalently, {d_{−∂^{X}f(x^{∞})}(n_{p}^{t})} → 0 and {P_{T_{X}(x^{∞})}(n_{p}^{t})} → 0.

4 ERGODIC RESULTS FOR LAGRANGE MULTIPLIERS

Here, we consider the cases when the feasible set and/or the objective function of the program [P] have explicit representations, and utilize the previous ergodic results to construct ergodic sequences of the Lagrange multipliers associated with these representations of the program [P]. In Subsection 4.1 we assume that the feasible set is defined by a finite number of smooth, convex inequality constraints and/or linear equality constraints, and satisfies a strong Slater constraint qualification. The ergodic sequences of multipliers associated with these constraints are shown to converge to Lagrange multipliers. In Subsection 4.2 we assume that the objective function is represented as the pointwise maximum of a finite number of smooth, convex functions. We show that the ergodic sequences of multipliers associated with the pieces of the objective function converge to Lagrange multipliers.

4.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 ∈ M; b_{j}^{T} x = e_{j}, j ∈ P } ,  (4.1)

where the functions a_{i} : ℜ^{n} ↦ ℜ, i ∈ M = {1, …, m}, are convex and differentiable, and b_{j} ∈ ℜ^{n} and e_{j} ∈ ℜ, j ∈ P = {m + 1, …, m + p}. The convergence analysis of this subsection relies on the assumption that the set X fulfils the following constraint qualification (e.g., Hiriart-Urruty and Lemaréchal, 1993a, Definition VII:2.3.1).

Assumption 4.1 (Strong Slater assumption). The vectors b_{j}, j ∈ P, are linearly independent, and the set X has a nonempty relative interior, that is,

{ x ∈ ℜ^{n} | a_{i}(x) < 0, i ∈ M; b_{j}^{T} x = e_{j}, j ∈ P } ≠ ∅. □

We let, for x ∈ X, I(x) = {i ∈ M | 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) = { π ∈ ℜ_{+}^{m} × ℜ^{p} | π_{i} = 0, i ∈ M \ I(x) } ∋ 0.

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

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

For any x ∈ X, let

M_{X}(x) = { μ ∈ Π_{X}(x) | 0 ∈ ∂f(x) + ∑_{i∈M} μ_{i}∇a_{i}(x) + ∑_{j∈P} μ_{j}b_{j} }  (4.2)

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 the set M_{X}(x) (e.g., Hiriart-Urruty and Lemaréchal, 1993a, Theorems VII:2.1.4 and VII:2.3.2).^{7}

Proposition 4.2 (Optimality conditions). Suppose that the set X, defined by (4.1), fulfils Assumption 4.1, and let x ∈ X. Then, x ∈ X^{∗} if and only if M_{X}(x) ≠ ∅. □

Proposition 4.3 (Properties of M_{X}(x), x ∈ X^{∗}). Suppose that the set X, defined by (4.1), fulfils Assumption 4.1. For any x ∈ X^{∗} the nonempty set M_{X}(x) is convex and compact, and M_{X}(y) = M_{X}(x) for all y ∈ X^{∗}.

Proof. The closedness and convexity of M_{X}(x) follow from its definition (4.2). The invariance over the set X^{∗} and the boundedness follow from Proposition VII:3.1.1 and Theorem VII:2.3.2, respectively, in Hiriart-Urruty and Lemaréchal (1993a). □

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

7Parts of Propositions 4.2 and 4.3 are true also under weaker constraint qualifications.

Lemma 4.4 Suppose that the set X, defined by (4.1), fulfils Assumption 4.1, and let x ∈ X and π ∈ ℜ^{m+p}. Then, the system

∑_{i∈I(x)} π_{i}∇a_{i}(x) + ∑_{j∈P} π_{j}b_{j} = 0  (4.3a)
π ∈ Π_{X}(x)  (4.3b)

is satisfied if and only if π = 0.

Proof. Clearly, π = 0 satisfies the system (4.3).

Conversely, suppose that π satisfies the system (4.3). From Assumption 4.1 follows that there is an x̂ ≠ x such that x̂ ∈ rint X. The convexity and differentiability of the functions a_{i}, together with the fact that a_{i}(x) = 0 for all i ∈ I(x), then yield that ∇a_{i}(x)^{T} (x̂−x) ≤ a_{i}(x̂) for all i ∈ I(x), and, since π_{i} ≥ 0 and a_{i}(x̂) < 0 for all i ∈ I(x), that

∑_{i∈I(x)} π_{i}∇a_{i}(x)^{T} (x̂ − x) ≤ ∑_{i∈I(x)} π_{i}a_{i}(x̂) ≤ 0.  (4.4)

However, since, for all j ∈ P, b_{j}^{T} (x̂ − x) = 0, it follows from the equations (4.3a) that ∑_{i∈I(x)} π_{i}∇a_{i}(x)^{T} (x̂ − x) = 0, and from (4.4) we then obtain that ∑_{i∈I(x)} π_{i}a_{i}(x̂) = 0. From the relations π_{i} ≥ 0 and a_{i}(x̂) < 0 for all i ∈ I(x) it follows that π_{i} = 0 for all i ∈ I(x). The system (4.3) then reduces to the equations ∑_{j∈P} π_{j}b_{j} = 0 and π_{i} = 0, i ∈ M. By Assumption 4.1, the vectors b_{j}, j ∈ P, are linearly independent, thus implying that π_{j} = 0 for all j ∈ P. Hence, π = 0. □

Definition 4.5 (Ergodic sequence of Lagrange multipliers). Let the set X be defined by (4.1), and let the method (1.5) be applied to the program [P]. The sequences {ω(x^{s})} and {λ(x^{s})} are defined by

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

and

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

where ν(x^{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} (ω(x^{s}) + \frac{λ(x^{s})}{α_{s}}) , t = 1, 2, …. □

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

Clearly, the value of the vector ω(x^{s}) depends of the choice of the normal term ν(x^{s}) in the conditional subgradients used in the method (1.5). In the special case of the traditional subgradient optimization method (1.4), ν(x^{s}) = 0 for all s, and then, from Lemma 4.4, ω(x^{s}) = 0 for all s. In the special case of the method (1.5) where γ^{X}(x^{s}) is a projected subgradient,

ν(x^{s}) = arg {min \atop ν} \{∥ν∥^{2} |∇a_{i}(x^{s})^{T} (ν +γ(x^{s}))≥0, i ∈ I(x^{s}); b_{j}^{T} (ν +γ(x^{s}))=0, j ∈ P\} ,

and the elements ω_{i}(x^{s}), i ∈ I(x^{s}), and ω_{j}(x^{s}), j ∈ P, are Lagrange multipliers associated with the constraints of this projection problem.

The vector λ(x^{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 ∈ M; b_{j}^{T} x = e_{j}, j ∈ P \} .

Lemma 4.6 (Boundedness of {ω(x^{s})} and {λ(x^{s})/α_{s}}). Suppose that the set X is defined by (4.1) and fulfils Assumption 4.1, and let the method (1.5)–(1.7) be applied to the program [P]. If the sequences {γ(x^{s})} and {ν(x^{s})} are bounded, then this is also true for the sequences {ω(x^{s})} and {λ(x^{s})/α_{s}}, given by Definition 4.5.

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

Suppose that this is not the case. Then there exists a subsequence S such that ∥ω(x^{s})∥ > 0 for all s ∈ S and {∥ω(x^{s})∥}_{s∈S} → ∞. Let π^{s} = ω(x^{s})/∥ω(x^{s})∥, implying that π^{s} ≥ 0 and ∥π^{s}∥ = 1 for all s ∈ S. According to Proposition 1.6, {x^{s}} → x^{∞}. Suppose that, for some i ∈ M, 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}(x^{s}) = 0, and π_{i}^{s} = 0; hence, for any i ∈ M \ 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.

From Definition 4.5 we have that

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

Taking the limit of the subsequence of S corresponding to π̃ we obtain

∑_{i∈I(x^{∞})} π̃_{i}∇a_{i}(x^{∞}) + ∑_{j∈P} π̃_{j}b_{j} = 0,

since {x^{s}} → x^{∞} and the functions ∇a_{i}, i ∈ M, are continuous, and since the sequence {ν(x^{t})} is bounded and the sequence {∥ω(x^{s})∥}_{s∈S} is presumed to tend to infinity. Then, by Lemma 4.4, π̃ = 0 must hold, and we have arrived at a contradiction. Hence, the sequence {ω(x^{s})} is bounded.

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

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

Clearly, the right hand side of this equality tends to the zero vector and we may analogously to the first part of the proof derive a contradiction. □

From Definition 4.5 and Lemma 4.6 follow that, under the conditions (1.6) and (1.7), the sequence {μ^{t}} is bounded.

Theorem 4.7 (Convergence of {μ^{t}} to M_{X}(x^{∞})). Suppose that the set X is defined by (4.1) and fulfils Assumption 4.1. Let the method (1.5)–(1.7) be applied to the program [P] and let the sequence {μ^{t}} be given by Definition 4.5. Suppose that the sequences {γ(x^{s})} and {ν(x^{s})} are bounded. Then,

{d_{M_{X}(x^{∞})}(μ^{t})} → 0.

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

To simplify the notation, we define ν^{t} = ∑_{i∈M} μ_{i}^{t}∇a_{i}(x^{∞}) + ∑_{j∈P} μ_{j}^{t}b_{j}. From Definitions 2.2 and 4.5 then follow that

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

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

Let ε > 0. Lemma 2.6 and Theorem 3.1 then yield that d_{−∂f(x^{∞})}(n^{t}) ≤ ε/3 for all t that are sufficiently large. We next show that the second term of the right hand side of the equation (4.5) tends to the zero vector. Lemma 4.6 implies that the sequence {ω_{i}(x^{s})} is bounded for each i ∈ M. Hence, since the function ∇a_{i} is continuous, there is an iterate t(ε) such that

ω_{i}(x^{s}) ∥∇a_{i}(x^{s}) − ∇a_{i}(x^{∞})∥ ≤ \frac{ε}{6m}, ∀s ≥ t(ε).

Therefore, for all t > t(ε),

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

Since {A_{t}} → ∞ we have, for all t that are large enough,

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

From the derivations above follow that, for all t > t(ε) that are large enough,

0 ≤ ∥ ∑_{i∈M} A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ω_{i}(x^{s}) (∇a_{i}(x^{s}) − ∇a_{i}(x^{∞})) ∥

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

It can, analogously to the preceding, be shown that the same conclusion holds for the last term of the right hand side of equation (4.5). It follows that d_{−∂f(x^{∞})}(ν^{t}) ≤ ε for all t that are sufficiently large, and hence that {d_{−∂f(x^{∞})}(ν^{t})} → 0. Now, let T be a subsequence such that

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

and let μ̃ be an accumulation point of the sequence {μ^{t}}_{t∈T}. From the preceding and the closedness of the sets Π_{X}(x^{∞}) and ∂f(x^{∞}) then follow that μ̃ ∈ Π_{X}(x^{∞}) and ∑_{i∈M} μ̃_{i}∇a_{i}(x^{∞}) + ∑_{i∈P} μ̃_{j}b_{j} ∈ −∂f(x^{∞}), thus implying that μ̃ ∈ M_{X}(x^{∞}). The theorem follows. □

4.2 Multipliers of objective pieces

Throughout this subsection we assume that the nonsmooth objective function f of the program [P] has the form

f(x) = max_{k∈L} c_{k}(x), x ∈ ℜ^{n},  (4.6)

where the functions c_{k} : ℜ^{n} ↦ ℜ, k ∈ L = {1, …, ℓ}, are convex and differentiable. We let K(x) = {k ∈ L | c_{k}(x) = f(x)} denote the set of objective pieces that are active at x ∈ ℜ^{n} and

Π_{f}(x) = { π ∈ ℜ_{+}^{ℓ} | π_{k} = 0, k ∈ L \ K(x); ∑_{k∈L} π_{k} = 1 } , x ∈ ℜ^{n}.

Letting ξ ∈ ℜ^{ℓ}, the subdifferential of f at x can then be expressed as

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

Let the program [P] be reformulated as

min z,  (4.7a)
s.t. c_{k}(x) − z ≤ 0, k ∈ L,  (4.7b)
x ∈ X,  (4.7c)

and introduce nonnegative multipliers η_{k}, k ∈ L, associated with the constraints (4.7b). Optimality of an x ∈ X can then be characterized in terms of the nonemptiness of the set

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

of Lagrange multipliers associated with the constraints (4.7b) (e.g., Hiriart-Urruty and Lemaréchal, 1993a, Theorem VII:2.1.4). Note that, in contrast to Propositions 4.2 and 4.3, a constraint qualification is here always fulfilled (since int(epi f) ≠ ∅).

Proposition 4.8 (Optimality conditions). Let x ∈ X. Then, x ∈ X^{∗} if and only if M_{f}(x) ≠ ∅. □

Proposition 4.9 (Properties of M_{f}(x), x ∈ X^{∗}). For any x ∈ X^{∗} the nonempty set M_{f}(x) is convex and compact, and M_{f}(y) = M_{f}(x) for all y ∈ X^{∗}.

Proof. The convexity and compactness of M_{f}(x) are immediate from its definition (4.8), and its invariance over X^{∗} follows from Proposition VII:3.1.1 in Hiriart-Urruty and Lemaréchal (1993a) applied to the reformulation (4.7) of the program [P]. □

Definition 4.10 (Ergodic sequence of multipliers). Let the objective function f be defined by (4.6) and let the method (1.5) be applied to the program [P]. The sequence {ξ(x^{s})} is defined by

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

where γ(x^{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}ξ(x^{s}), t = 1, 2, …. □

Note that η^{t} ≥ 0 and ∑_{k∈L} η_{k}^{t} = 1 for all t; obviously, the sequence {η^{t}} is bounded.

Theorem 4.11 (Convergence of {η^{t}} to M_{f}(x^{∞})). Let the objective function f be defined by (4.6), let the method (1.5)–(1.7) be applied to the program [P], and let the sequence {η^{t}} be given by Definition 4.10. Suppose that the sequences {γ(x^{t})} and {ν(x^{t})} are bounded. Then,

{d_{M_{f} (x^{∞})}(η^{t})} → 0.

Proof. Similarly to the proof of Theorem 4.7 we can show that {d_{Π_{f} (x^{∞})}(η^{t})} → 0. Defining γ^{t} = ∑_{k∈L} η_{k}^{t}∇c_{k}(x^{∞}), it follows from Definitions 2.1 and 4.10 that

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

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

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

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

5 FURTHER RESEARCH

The ergodic results of Section 4 can immediately be generalized to the case when both the objective function and the feasible set have explicit representations. A straightforward topic for continued studies is the derivation of ergodic results for multipliers when the constraint functions a_{i}, i ∈ M, and/or the objective pieces c_{k}, k ∈ L, are allowed to be nonsmooth.

We have recently constructed a convergent lower bounding procedure for the program [P] (cf. the lower bounding principle of the Frank–Wolfe method) based on the ergodic results presented in this paper, and studied its application in a subgradient scheme for a nonsmooth formulation of the linear minimum cost multicommodity network flow problem (Larsson et al., 1995). The application of the lower bounding procedure to other classes of structured, nonsmooth programs, especially Lagrangean dual problems, will be studied further.

A further application of the sequence {g^{t}} is the construction of an auxiliary, optimizing sequence \{\overline{x}^{t}\} of feasible solutions to the program [P], by

\overline{x}^{t} = P_{X} (x^{t} − σ_{t}g^{t}) , t = 1, 2, …,

where 0 < \underline{σ} ≤ σ_{t} ≤ \overline{σ} < +∞ for all t. This sequence, which is generated in a manner akin to gradient projection methods for smooth optimization, has stronger properties than the original sequence {x^{t}}; for example, under very mild assumptions it identifies finitely the set of active constraints at the optimal solution x^{∞}. This is an extension of results from the differentiable case, and it illustrates well the smoothing effect of the process defining the sequence {g^{t}}.

Consider the general problem of finding an x ∈ ℜ^{n} such that 0 ∈ F (x), where F : ℜ^{n} ↦ 2^{(ℜ∪{±∞})^{n}} is a maximal monotone point–to–set map. A natural method for solving this problem can be described as follows. Let

x^{0} ∈ dom F, γ^{t} ∈ F (x^{t}), α_{t} > 0, and x^{t+1} = P_{dom F} (x^{t} − α_{t}γ^{t}), t = 0, 1, …. (5.1)

For any nonempty, closed and convex set X ⊆ ℜ^{n} and any convex function f : ℜ^{n} ↦ ℜ, the mapping F ≡ ∂^{X}f is maximal monotone, since it equals the sum of the two maximal monotone operators ∂f and N_{X} (Rockafellar, 1970b, Theorem B, and 1970c, Theorem 1); by Proposition 1.5, the problem [P] is hence a special case of the general problem and, further, the conditional subgradient method (1.5) is a special case of the method (5.1). Proposition 1.6 then establishes that {d_{F^{−1}(0)}(x^{t})} → 0, that is, 0 ∈ F (x^{∞}). A subject for future research is to derive ergodic results for the method (5.1) applied to the general problem.

Acknowledgement The research was supported financially by grants (No. 94-292 and 282-93-1195) from the Swedish Research Council for Engineering Sciences (TFR).

References

[1] J.E. Beasley, 1993, “Lagrangean relaxation”, in: “Modern Heuristic Techniques for Combinatorial Problems,” C.R. Reeves, ed., Blackwell Scientific Publications, Oxford, pp. 243–303.

[2] A. Ben-Tal and M.P. Bendsøe, 1993, “A new method for optimal truss topology design”, SIAM Journal on Optimization, 3:322–358.

[3] J.V. Burke and M.C. Ferris, 1991, “Characterization of solution sets of convex programs”, Operations Research Letters, 10:57–60.

[4] V.F. Dem’janov and V.K. Šomesova, 1978, “Conditional subdifferentials of convex functions”, Soviet Mathematics Doklady, 19:1181–1185.

[5] V.F. Dem’yanov and V.K. Shomesova, 1980, “Subdifferentials of functions on sets”, Cybernetics, 16/1:24–31.

[6] V.F. Dem’yanov and L.V. Vasil’ev, 1985, “Nondifferentiable Optimization,” Optimization Software, New York, NY.

[7] J.C. Dunn, 1973, “On recursive averaging processes and Hilbert space extensions of the contraction mapping principle”, Journal of the Franklin Institute, 295:117–133.

[8] Yu.M. Ermol’ev, 1966, “Methods for solving nonlinear extremal problems”, Cybernetics, 2/4:1–14.

[9] M.L. Fisher, 1981, “The Lagrangian relaxation method for solving integer programming problems”, Management Science, 27:1–18.

[10] M.L. Fisher, 1985, “An applications oriented guide to Lagrangian relaxation”, Interfaces, 15:10–21.

[11] M. Frank and P. Wolfe, 1956, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3:95–110.

[12] J.-B. Hiriart-Urruty and C. Lemaréchal, 1993a, “Convex Analysis and Minimization Algorithms I: Fundamentals,” Springer-Verlag, Berlin.

[13] J.-B. Hiriart-Urruty and C. Lemaréchal, 1993b, “Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods,” Springer-Verlag, Berlin.

[14] J. Kornai and T. Lipták, 1965, “Two level planning”, Econometrica, 33:141–169.

[15] T. Larsson, M. Patriksson, and A.-B. Strömberg, 1992, “Conditional subgradient optimization— theory and applications”, Report LiTH-MAT-R-92-24, Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden. Revised 1994. European Journal of Operational Research (to appear).

[16] T. Larsson, M. Patriksson, and A.-B. Strömberg, 1995, “Ergodic results and bounds on the optimal value in subgradient optimization”, Paper presented at the Symposium on Operations Research (SOR’95), Annual Conference of the DGOR, GMÖOR, and ÖGOR, Universität Passau, September 13–15, Passau, Germany.

[17] B.T. Polyak, 1967, “A general method of solving extremum problems”, Soviet Mathematics Doklady, 8/3:593–597.

[18] B.T. Polyak, 1969, “Minimization of unsmooth functionals”, USSR Computational Mathematics and Mathematical Physics, 9:14–29.

[19] W.B. Powell and Y. Sheffi, 1982, “The convergence of equilibrium algorithms with predetermined step sizes”, Transportation Science, 16:45–55.

[20] R.T. Rockafellar, 1970a, “Convex Analysis,” Princeton University Press, Princeton, NJ.

[21] R.T. Rockafellar, 1970b, “On the maximal monotonicity of subdifferential mappings”, Pacific Journal of Mathematics, 33:209–216.

[22] R.T. Rockafellar, 1970c, “On the maximality of sums of nonlinear monotone operators”, Transactions of the American Mathematical Society, 149:75–88.

[23] N.Z. Shor, 1985, “Minimization Methods for Non-Differentiable Functions,” Springer-Verlag, Berlin.

[24] 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. Rinnoy Kan and A. Schrijver, eds., CWI and North-Holland, Amsterdam, pp. 135–139.

[25] 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.