Ergodic Results and Bounds on the Optimal Value in Subgradient Optimization

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

1 Linköping Institute of Technology, S-581 83 Linköping, Sweden 2 University of Washington, Seattle, WA 98195-4350, USA

1 Introduction

Subgradient methods for nonsmooth optimization have rendered considerable popularity, mainly in the context of Lagrangean relaxation; this is due to their simplicity and proven practical usefulness. We consider the minimization of a nonsmooth convex function over a convex and compact set, using a (conditional) subgradient optimization scheme with divergent series step lengths. We show that such a scheme may be augmented by a convergent lower bounding procedure based on the computation of an ergodic (averaged) sequence of subgradients and of affine functions underestimating the objective. The sequence of lower bounds enables a judgement of the quality of the solutions obtained, and can thus be used in a termination criterion. Numerical experience from an application of the bounding procedure within a subgradient scheme for a nonsmooth formulation of the linear multicommodity network flow problem is presented.

2 An Ergodic Result in Subgradient Optimization

Let the function f : ℜ^{n} ↦ ℜ be nonsmooth and convex and thus everywhere continuous and subdifferentiable, and let X ⊂ ℜ^{n} be a nonempty, convex, and compact set. The program considered is

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

with the nonempty, convex, and compact solution set X^{∗}. The subdifferential of f at x ∈ ℜ^{n} is (e.g., Hiriart-Urruty and Lemaréchal, 1993, Definition VI:1.2.1) the nonempty, convex, and compact set

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

the elements of which are called subgradients. The normal cone of the set X at some x ∈ X is (ibid., Definition III:5.2.3) the nonempty, closed, and convex set

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

An optimality condition for the program [P] is given in the next proposition (ibid., Theorem VII:1.1.1 and Condition VII:(1.1.3)).

Proposition 1. x ∈ X^{∗} if and only if ∂f(x) ∩ −N_{X}(x) ≠ ∅.

For any x ∈ X^{∗}, the nonempty set ∂f(x) ∩ −N_{X}(x) is convex and compact.

We consider subgradient optimization methods (e.g., Polyak, 1969, or Shor, 1985) for solving the program [P]. 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, 1985, and Beasley, 1993).

Given an initial iterate x^{0} ∈ X, the traditional subgradient optimization method for solving the program [P] is given by the iteration formula

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

where γ(x^{t})∈∂f(x^{t}), α_{t} > 0 is the step length, and 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}.

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

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, for example the convergent lower bound on the optimal value in the Frank–Wolfe method; these bounds are calculated using linearizations of the objective.

In a straightforward attempt to augment the method (2) with a similar lower bounding technique one would compute the values

h_{t}^{∗} = f(x^{t}) + min_{x∈X} γ(x^{t})^{T} (x − x^{t}) , t = 0, 1, ….  (3)

Clearly, for all t, h_{t}^{∗} ∈ (−∞, f^{∗}]. However, in general, {h_{t}^{∗}} ↛ f^{∗}, and even in the (unlikely) case when x^{t} ∈ X^{∗}, h_{t}^{∗} < f^{∗} generally holds; hence, the sequence {h_{t}^{∗}} does not possess the desired convergence properties.

A frequently used technique for inducing convergence 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 an ergodic sequence of subgradients can be used to calculate a convergent sequence of lower bounds on f^{∗}. This result is derived for the conditional subgradient optimization method (Larsson et al., 1996), which is a generalization of the method (2).

The conditional subdifferential of f with respect to X at x ∈ X (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 } = ∂f(x) + N_{X}(x).

Clearly ∂^{X}f(x) ⊇ ∂f(x), x ∈ X, and x ∈ X^{∗} if and only if 0 ∈ ∂^{X}f(x) (ibid.).

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

x^{t+1} = P_{X}(x^{t} − α_{t}γ^{X}(x^{t})), t = 0, 1, …,  (4)

where α_{t} > 0 and γ^{X}(x^{t}) = γ(x^{t}) + ν(x^{t}), with γ(x^{t}) ∈ ∂f(x^{t}) and ν(x^{t}) ∈ N_{X}(x^{t}). Clearly, if {ν(x^{t})} = {0}, then the method (4) reduces to the method (2). Choosing ν(x^{t}) = P_{N_{X}(x^{t})}(−γ(x^{t})) results (Larsson et al., 1996, Lemma 3.2) in the special case of the method (4) that is called the subgradient projection method. We consider step lengths satisfying the (divergent series) conditions

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

The below convergence result for the sequence {x^{t}} follows from Theorem 2.7 in Larsson et al. (1996).

Proposition 2. Let the method (4)–(5) be applied to the program [P]. If the sequence {ν(x^{t})} is bounded, then {x^{t}} → x^{∞} ∈ X^{∗}.

Boundedness of the sequence {ν(x^{t})} may be ensured by appropriate choices of γ^{X}(x^{t}) in the method (4). Clearly, the sequence {γ(x^{t})} is bounded since f is continuous and {x^{t}} ⊆ X is bounded, and if subgradient projection is used, then ∥ν(x^{t})∥ ≤ ∥γ(x^{t})∥, so that also the sequence {ν(x^{t})} is bounded.

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

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

Clearly, each vector g^{t} is a convex combination of the subgradients {γ(x^{s})}_{s=0}^{t−1}; hence, the sequence {g^{t}} is bounded. Note that it is calculated beside the sequence {x^{t}} (and does not affect the course of the method (4)), and that it can be computed recursively.

The below convergence result for the sequence {g^{t}} follows from Theorem 3.4 in Larsson et al. (1995).

Lemma 4. Let the method (4)–(5) be applied to the program [P] and let the sequence {g^{t}} be given by Definition 3. Suppose that the sequence {ν(x^{s})} is bounded. Then, {P_{∂f(x^{∞})∩−N_{X}(x^{∞})}(g^{t}) − g^{t}} → 0.

3 A Lower Bounding Procedure

The ergodic sequence of subgradients will now be used to define a convergent sequence of lower bounds on the optimal value of the program [P]. With this purpose in mind we define the affine functions f_{t} : ℜ^{n} ↦ ℜ, t = 1, 2, …, as

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

By the definition (1), and since, for all s, γ(x^{s}) ∈ ∂f(x^{s}), 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, and therefore, for all t, min_{x∈X} f_{t}(x) ≤ f^{∗}.

Definition 5. (Sequence of lower bounds.) Let the method (4) be applied to the program [P] and let, for all t, f_{t}(x) be given by the definition (6). The sequence {f_{t}^{∗}} of lower bounds on f^{∗} is defined by

f_{t}^{∗} = min_{x∈X}f_{t}(x), t = 1, 2, ….

The next lemma establishes that, in the limit, the sequence {f_{t}} of affine functions provides supporting hyperplanes to epif at (x^{∞}, f(x^{∞})); it follows from Lemma 2.4 in Larsson et al. (1995) and is used to show that the sequence of lower bounds converges to the optimal value, which is our main result.

Lemma 6. Let the method (4)–(5) be applied to the program [P] and let the sequence {f_{t}(x^{∞})} be given by the definition (6). If the sequence {ν(x^{s})} is bounded, then {f_{t}(x^{∞})} → f^{∗}.

Theorem 7. Let the method (4)–(5) be applied to the program [P] and let the sequence {f_{t}^{∗}} be given by Definition 5. If the sequence {ν(x^{s})} is bounded, then f_{t}^{∗} ∈ (−∞, f^{∗}] for all t, and {f_{t}^{∗}} → f^{∗}.

Proof. From Definition 5 and the definitions (6) and (1) follow that f_{t}^{∗} ≤ f^{∗} for all t. Further, since X is bounded, f_{t}^{∗} is finite for all t.

By Definitions 5 and 3, f_{t}^{∗} = f_{t}(x^{∞}) + min_{x∈X} (g^{t})^{T} (x − x^{∞}). Let, for all t, y^{t} ∈ X solve this minimization problem, so that (g^{t})^{T} (y^{t} − x^{∞}) = f_{t}^{∗} − f_{t}(x^{∞}), and let T be a subsequence such that lim_{t∈T ,t→∞}(g^{t})^{T} (y^{t} − x^{∞}) = lim inf_{t→∞}(g^{t})^{T} (y^{t} − x^{∞}). Since {g^{t}} and {y^{t}} are bounded, there exists a subsequence T̃ ⊆ T such that {y^{t}}_{t∈T̃} → ỹ and {g^{t}}_{t∈T̃} → g̃. Now,

0 ≤ g̃^{T} (ỹ − x^{∞}) = lim inf_{t→∞} (g^{t})^{T} (y^{t} − x^{∞}) ≤ lim sup_{t→∞} (f_{t}^{∗} − f_{t}(x^{∞})) ≤ 0,

since, by Lemma 4, g̃ ∈ −N_{X}(x^{∞}), and ỹ ∈ X, and since, for all t, f_{t}^{∗} ≤ f_{t}(x^{∞}). Hence, {f_{t}^{∗} − f_{t}(x^{∞})} → 0, and by Lemma 6, {f_{t}(x^{∞})} → f^{∗}, thus implying that {f_{t}^{∗}} → f^{∗}. ⊓ ⊔

Defining UBD_{t} = min_{0≤s≤t} f(x^{s}) and LBD_{t} = max_{1≤s≤t} f_{s}^{∗}, for all t, Proposition 2 and Theorem 7 yield that, for any ε > 0 there is an iteration t(ε) such that UBD_{t(ε)} − LBD_{t(ε)} ≤ ε (implying that UBD_{t(ε)} ≤ f^{∗} + ε); hence, this condition may be used as a termination criterion for the method (4)–(5).

4 Application to Multicommodity Network Flows

To illustrate the practical usefulness of the lower bounding procedure we here present numerical results from an application to a subgradient scheme for a nonsmooth formulation of the minimum cost multicommodity network flow problem.

Let N and A be the sets of nodes and arcs, respectively, of a directed network. Further, let K be a set of flow commodities, and let d_{k} be the demand vector and x_{k} the vector of arc flows for commodity k ∈ K. Associated with the commodity flows are vectors of unit transportation costs c_{k}, k ∈ K, and the total arc flows are upper bounded by b. Letting A denote the node-arc incidence matrix for the network, the problem of minimizing the total cost is given by

f^{∗} = min {∑_{k∈K} c_{k}^{T} x_{k}| Ax_{k} = d_{k}, k ∈ K; ∑_{k∈K} x_{k} ≤ b; x_{k} ≥ 0, k ∈ K} .

Kennington and Shalaby (1977) employ a subgradient optimization scheme which is based on allocations of the capacities of the total arc flows to separate commodities. Letting Y = { y ∈ ℜ_{+}^{|A|·|K|} | ∑_{k∈K} y_{k} = b } be the set of feasible commodity capacity allocations, the equivalent nonsmooth program

f^{∗} = min_{y∈Y} f(y) = min_{y∈Y} {∑_{k∈K} min { c_{k}^{T} x_{k} | Ax_{k} = d_{k}; 0 ≤ x_{k} ≤ y_{k} }}

is obtained. The objective f : ℜ_{+}^{|A|·|K|} ↦ ℜ is convex and piecewise linear; it is evaluated by solving |K| single-commodity network flow problems, and a subgradient of f at y is given by the optimal values of the dual variables for the constraints x_{k} ≤ y_{k}, k ∈ K. In Larsson et al. (1996) this subgradient scheme was improved through the use of projected subgradients; see this reference for a more detailed description of the algorithm.

The calculation of the lower bound f_{t}^{∗} amounts to the minimization of a linear objective over the set Y, and separates into |A| continuous knapsack problems.

The test problems have a transportation network structure and are randomly generated in accordance with the principles in Kennington and Shalaby (1977). We generated 10 instances, each having 10 sources, 10 sinks, and 10 commodities. The supply/demand for each source/sink and commodity is in the range 0–300, arc capacities in the range 100–400, and arc costs in the range 0–100. All data is uniformly distributed.

In order to receive a good starting point for the generation of the sequence of lower bounds, we used step lengths according to Polyak (1969) during the first 100 iterations. For each instance and iteration, the bounds f(x^{t}) and f_{t}^{∗} were computed; then we recorded the values UBD_{t} and LBD_{t}, normalized by the optimal value (which was computed in advance) of the instance. For each iteration t we computed the average (U_{t} and L_{t}, respectively) of these normalized values over the 10 instances. As a means for evaluating the effect of invoking the ergodic process we also recorded averages (H_{t}) of normalized values of the nonconvergent bounds max_{0≤s≤t} h_{s}^{∗}, t = 0, 1, …, where h_{s}^{∗} is given by the definition (3).

The results presented in Table 1 confirm that, in this application, the introduction of the ergodic process is an effective means for obtaining a judgement of the quality of the iterates produced by the subgradient scheme.

Table 1. Convergence of normalized bounds

t  U_{t}  L_{t}  H_{t}  \frac{U_{t}−L_{t}}{L_{t}} (%) \frac{U_{t}−H_{t}}{H_{t}} (%)
20 1.0331  0.8298  24.50
60 1.0075  0.9268  8.71
100 1.0023 0.9072 0.9547  10.48  4.99
105 1.0020 0.9842 0.9567  1.81  4.74
110 1.0018 0.9899 0.9567  1.20  4.71
120 1.0017 0.9940 0.9591  0.77  4.44
160 1.0014 0.9964 0.9605  0.50  4.26
200 1.0011 0.9972 0.9616  0.39  4.11

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

Beasley, J.E.: Lagrangean relaxation, in: “Modern Heuristic Techniques for Combina-

torial Problems.” C.R. Reeves, ed., Blackwell, Oxford (1993) pp. 243–303 Dem’janov, V.F., and Šomesova, V.K.: Conditional subdifferentials of convex functions.

Soviet Mathematics Doklady 19 (1978) 1181–1185 Dunn, J.C.: On recursive averaging processes and Hilbert space extensions of the con-

traction mapping principle. Journal of the Franklin Institute 295 (1973) 117–133 Fisher, M.L.: An applications oriented guide to Lagrangian relaxation. Interfaces 15

(1985) 10–21 Hiriart-Urruty, J.-B., and Lemaréchal, C.: “Convex Analysis and Minimization Algo-

rithms I: Fundamentals.” Springer, Berlin (1993) Kennington, J., and Shalaby, M.: An effective subgradient procedure for minimal cost

multicommodity flow problems. Management Science 23 (1977) 994–1004 Kornai, J., and Lipták, T.: Two level planning. Econometrica 33 (1965) 141–169 Larsson, T., Patriksson, M., and Strömberg, A.-B.: Ergodic results in subgradient

optimization. Report LiTH-MAT-R-95-21 (1995), Department of Mathematics, Linköping Institute of Technology, Linköping, Sweden. Also in: Proceedings of the International School of Mathematics “G. Stampacchia” 21st Workshop on Nonlinear Optimization and Applications, held June 13–21, 1995, in Erice, Italy, Plenum, New York (to appear)

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

Polyak, B.T.: Minimization of unsmooth functionals. USSR Computational Mathemat-

ics and Mathematical Physics 9 (1969) 14–29 Powell, W.B., and Sheffi, Y.: The convergence of equilibrium algorithms with prede-

termined step sizes. Transportation Science 16 (1982) 45–55 Shor, N.Z.: “Minimization Methods for Non-Differentiable Functions.” Springer, Berlin