On the convergence of conditional ε-subgradient methods for convex programs and convex–concave saddle-point problems

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

September 20, 2002

1Department of Mathematics, Linköping Univeristy, SE-581 83 Linköping, Sweden. Email address: tolar@mai.liu.se

2Department of Mathematics, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden. Email address: mipat@math.chalmers.se

3Corresponding author address details: Department of Mathematics, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden. Email address: mipat@math.chalmers.se. Telephone: +46 31 7723529. Fax: +46 31 161973

4Fraunhofer–Chalmers Research Center for Industrial Mathematics, SE-412 88 Gothenburg, Sweden. Email address: Ann-Brith.Stromberg@fcc.chalmers.se

Abstract

The paper provides two contributions. First, we present new convergence results for conditional ε-subgradient algorithms for general convex programs. The results obtained here extend the classical ones by Polyak [Pol67, Pol69, Pol87] as well as the recent ones in [CoL93, LPS96, AIS98] to a broader framework. Secondly, we establish the application of this technique to solve non-strictly convex–concave saddle point problems, such as primal-dual formulations of linear programs. Contrary to several previous solution algorithms for such problems, a saddlepoint is generated by a very simple scheme in which one component is constructed by means of a conditional ε-subgradient algorithm, while the other is constructed by means of a weighted average of the (inexact) subproblem solutions generated within the subgradient method. The convergence result extends those of [Sho85, ShC96, LPS99] for Lagrangian saddle-point problems in linear and convex programming, and of [PeP97] for a linear–quadratic saddle-point problem arising in topology optimization in contact mechanics.

Key words: Convex programming, nonlinear programming, game theory, large-scale optimization

1 Introduction

Consider the convex–concave saddle-point problem to find

(x^{∗}, y^{∗}) ∈ X × Y :  L(x^{∗}, y) ≤ L(x^{∗}, y^{∗}) ≤ L(x, y^{∗}), ∀(x, y) ∈ X × Y.  [SP]

We assume that X ⊂ ℜ^{n} and Y ⊂ ℜ^{m} are non-empty, convex and compact sets, and L : X ×Y ↦ ℜ is convex–concave and finite (hence continuous) on X ×Y, that is, convex (concave) in x (y) on X (Y) for every fixed value of y ∈ Y (x ∈ X). We note that in what is to follow, the compactness assumption on X × Y can be replaced by some coercivity assumption on L with respect to X × Y (e.g., Hiriart-Urruty and Lemaréchal [HiL93, p. 334]).

Under the above assumptions on the problem [SP], there exists a saddle-point, (x^{∗}, y^{∗}), of L on X × Y, the set of which is a Cartesian product which we will denote by X^{∗} × Y^{∗}. Further, for any choice of (x^{∗}, y^{∗}) ∈ X^{∗} × Y^{∗},

v^{∗} = L(x^{∗}, y^{∗}) = minimum_{x∈X} maximum_{y∈Y} L(x, y) = maximum_{y∈Y} minimum_{x∈X} L(x, y).

(These results are collected, for example, in [HiL93, Section VII.4].)

The algorithm to be presented in the next section attacks the problem by means of solving the following equivalent convex problem:

minimize_{x∈X} f(x),  [P]

where

f(x) := maximum_{y∈Y} L(x, y),  x ∈ X.  (1)

We shall denote the set of solutions to the problem (1) by Y (x). An ε-optimal solution, ỹ, to the problem (1) is characterized by the relation

L(x, ỹ) ≥ f(x) − ε,  (2)

for some ỹ ∈ Y and ε ≥ 0.

Example 1 (Convex programming). An interesting application of [SP] is to convex programming, where L(x, y) := h(x) + y^{T}g(x), corresponding to the Lagrangian of the problem to

minimize_{x∈X∩G} h(x),  [CP]

where h : ℜ^{n} ↦ ℜ is a convex function, the convex set G is described by means of convex inequalities,

G := { x ∈ ℜ^{n} | g_{i}(x) ≤ 0, i = 1, …, m },

where g_{i} : ℜ^{n} ↦ ℜ is convex for each i, and Y = ℜ_{+}^{m}. For this problem, we assume that X is bounded, and the Slater constraint qualification that the set { x ∈ X | g(x) < 0 } is nonempty (see Bazaraa et al. [BSS93, Theorem 6.2.4]). Under this CQ, the set Y^{∗} is compact. Assuming we may somehow restrict the set Y to be a convex and compact set including Y^{∗}, we thereby fulfill all the conditions on the problem [SP]. The problem [P] corresponds to the (convex) Lagrangian dual problem to maximize_{y∈ℜ_{+}^{m}} θ(y), where θ(y) := minimum_{x∈X} L(x, y).

For solving the problem [P], we utilize conditional ε-subgradient optimization, which extends traditional subgradient optimization, as analyzed, for example, in Shor [Sho85], to possibly inexact calculations of subgradients and to generating search directions which take the feasible set X into account. (The latter extension of traditional subgradient optimization was analyzed in depth first in [LPS96].) Thus, we generate a point in X^{∗}. In order to generate a point in Y^{∗}, we propose to build the sequence of weighted averages of the (possibly inexact) solutions to (1), generated while searching for a point in X^{∗}. We establish that this sequence converges to the set Y^{∗}, provided that the step lengths utilized in the process of finding a point in X^{∗} by the subgradient algorithm, and the weights used in constructing a point in Y^{∗}, are both chosen appropriately.

Some words on notation. The notation ∥ · ∥ denotes the Euclidean norm; for a nonempty, closed, and convex set S ⊆ ℜ^{n}, the normal cone to S is

N_{S}(x) := \begin{cases}\{ z ∈ ℜ^{n} | z^{T}(y − x) ≤ 0, ∀y ∈ S \}, & x ∈ S, \\ ∅, & x ∉ S; \end{cases}

the indicator function to S is

ψ_{S}(x) := \begin{cases}0, & x ∈ S, \\ +∞, & x ∉ S. \end{cases}

We have that the subdifferential operator of ψ_{S}, ∂ψ_{S}, equals N_{S}. Further,

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

denotes the (Euclidean) projection of the vector x onto the set S; we further introduce

dist (x, S) := min_{y∈S} ∥y − x∥

to denote the Euclidean distance from the point x to its projection proj (x, S) onto S. Finally, we introduce, for any ν ≥ 0,

X^{ν} := { x ∈ X | f(x) ≤ f^{∗} + ν },

that is, the lower level set of f corresponding to ν-optimal solutions to the problem [P]. (So, X^{0} = X^{∗}.)

The subject of the next section is the convergence of conditional ε-subgradient optimization algorithms. Section 3 presents the overall algorithm and establishes its convergence to a saddlepoint.

2 Convergence of conditional ε-subgradient optimization

Our first result establishes a simple relationship between ε-optimal solutions to (1) given x ∈ X and ε-subgradients of f at x. We first note that γ_{ε}(x) is an ε-subgradient of f at x [that is, γ_{ε}(x) is an element of the ε-subdifferential, ∂_{ε}f(x), of f at x] for some ε ≥ 0 if and only if

f(z) ≥ f(x) + γ_{ε}(x)^{T}(z − x) − ε,  z ∈ ℜ^{n};  (3)

the definition of a subgradient [that is, an element of the subdifferential] follows by setting ε = 0.

Proposition 2 (ε-optimal solutions provide ε-subgradients). Suppose that, given x ∈ X, ỹ is an ε-optimal solution to (1). Then, any subgradient γ̃(x) of L(·, ỹ) at x is an ε-subgradient to f at x.

Proof. Fix any x ∈ X and ε ≥ 0. For an arbitrary z ∈ X then follows that

f(z) ≥ L(z, ỹ) ≥ f(x) + [L(z, ỹ) − L(x, ỹ) − ε] ≥ f(x) + γ̃(x)^{T}(z − x) − ε,

which yields that γ̃(x) ∈ ∂_{ε}f(x), the first inequality coming from the definition of the value f(z), the second inequality following from the ε-optimality of ỹ in (1), and the right-most inequality following from the convexity of L(·, ỹ).

Example 1 (continued). For the special case of the problem [CP], the above result states that an ε-optimal solution to the Lagrangian subproblem provides an ε-subgradient of the Lagrangian dual function θ. This property was described independently by Larsson et al. [LPS99] and Bertsekas [Ber99, p. 615], but is most probably folklore, and a much older result.

Given the iteration point x^{t} at iteration t, let γ_{ε_{t}}(x^{t}) be an ε_{t}-subgradient of f at x^{t} ∈ X. Let γ_{ε_{t}}^{X}(x^{t}) be a conditional ε_{t}-subgradient of f at x^{t} ∈ X, that is, γ_{ε_{t}}^{X}(x^{t}) = γ_{ε_{t}}(x^{t}) + ν(x^{t}) for some ν(x^{t}) ∈ N_{X}(x^{t}). (This is equivalent to replacing z ∈ ℜ^{n} with z ∈ X in (3) or, in other words, γ_{ε_{t}}^{X}(x^{t}) is an element of the ε_{t}-subdifferential of the function f + ψ_{X} at x^{t}; see [DeS78, LPS96].) We will in the following analyze the convergence of conditional ε-subgradient algorithms for the solution of [P] using the divergent series step length rule,

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

in cases also under the additional requirement that

∑_{t=0}^{∞} α_{t}^{2} < ∞,  (5)

and under different scalings of the search directions.

In the analysis that follows, it is assumed that the sequences are infinite. In the case that γ_{ε_{t}}^{X}(x^{t}) = 0 for some t, x^{t} is ε_{t}-optimal in [P], and the procedure may be terminated (or the iteration considered void and the value of ε_{t} decreased).

For the sake of reaching a maximal generality, the analysis in this section for the problem [P] will ignore that its origin is the saddle-point problem discussed in the previous section, and hence assume temporarily that f : ℜ^{n} ↦ ℜ is a general convex function, and drop the assumption that the nonempty, closed and convex set X is necessarily bounded. Although we will study the problem only under the assumption that there exist optimal solutions to [P], we note that the algorithms described below are optimizing in the sense that lim inf_{t→∞} f(x^{t}) = f^{∗} := inf_{x∈X} f(x) holds even if X^{∗} is empty.

2.1 Divergent series step lengths, unscaled direction

We begin by considering unscaled directions.

The conditional ε-subgradient optimization method is given by

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

We note that the requirements of the algorithm are (a) that we have at hand a convergent algorithm for solving the problem (1), (b) a procedure for generating subgradients of L(·, y_{ε_{t}}^{t}), where y_{ε_{t}}^{t} is an ε_{t}-optimal solution to the problem (1) given x^{t}, and (c) that projections onto X are easily performed. In the case of the problem [CP] solved via its Lagrangian dual, the latter two requirements are of course trivial to fulfill.

Our main convergence result for the method (6), (4) establishes convergence to the optimal set X^{∗}.

Theorem 3 (Convergence to the optimal set using divergent series step lengths). Let {x^{t}} be generated by the method (6), (4) applied to [P]. If X^{∗} is bounded, ℜ_{+} ∋ {ε_{t}} → 0, and the sequence {γ_{ε_{t}}^{X}(x^{t})} is bounded, then {f(x^{t})} → f^{∗} and {dist (x^{t}, X^{∗})} → 0.

Proof. Let δ > 0 and B^{δ} = { x ∈ ℜ^{n} | ∥x∥ ≤ δ }. Since f is convex, X is nonempty, closed and convex, and X^{∗} is bounded, it follows (from Rockafellar [Roc70, Theorem 27.2], applied to the lower semicontinuous, proper and convex function f + ψ_{X}) that there exist ϵ = ϵ(δ) > 0 and σ = σ(δ) > 0 such that the lower level set X^{ϵ(1+σ)} ⊆ X^{∗} + B^{δ/2}. Moreover, since {γ_{ε_{t}}^{X}(x^{t})} is bounded and {α_{t}} → 0, there exists an N(δ) such that α_{t}∥γ_{ε_{t}}^{X}(x^{t})∥^{2} ≤ ϵ, ε_{t} ≤ σϵ, and α_{t}∥γ_{ε_{t}}^{X}(x^{t})∥ ≤ δ/2 for all t ≥ N(δ).

The sequel of the proof is based on induction and is organized as follows. In the first part, we show that there exists a finite t(δ) ≥ N(δ) such that x^{t(δ)} ∈ X^{∗} + B^{δ}. In the second part, we establish that if x^{t} belongs to X^{∗} + B^{δ} for some t ≥ N(δ) then so does x^{t+1}; this is done by showing that dist (x^{t+1}, X^{∗}) < dist (x^{t}, X^{∗}), or x^{t} ∈ X^{ϵ} so that x^{t+1} ∈ X^{∗} + B^{δ} since the step taken is not longer than δ/2.

Let x^{∗} ∈ X^{∗} be arbitrary. In every iteration t we then have

∥x^{∗} − x^{t+1}∥^{2} = ∥x^{∗} − proj (x^{t} − α_{t}γ_{ε_{t}}^{X}(x^{t}), X)∥^{2} ≤ ∥x^{∗} − x^{t} + α_{t}γ_{ε_{t}}^{X}(x^{t})∥^{2}
= ∥x^{∗} − x^{t}∥^{2} + α_{t} (2γ_{ε_{t}}^{X}(x^{t})^{T} (x^{∗} − x^{t}) + α_{t} ∥γ_{ε_{t}}^{X}(x^{t})∥^{2}) ,  (7)

where the inequality follows from the projection property. Now, suppose that

2γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) + α_{s} ∥γ_{ε_{s}}^{X}(x^{s})∥^{2} < −ϵ  (8)

for all s ≥ N(δ). Then, using (7) repeatedly, we obtain that for any t ≥ N(δ),

∥x^{∗} − x^{t+1}∥^{2} < ∥x^{∗} − x^{N(δ)}∥^{2} − ϵ ∑_{s=N(δ)}^{t} α_{s},

and from (4) it follows that the right-hand side of this inequality tends to minus infinity as t → ∞, which clearly is impossible. Therefore,

2γ_{ε_{t}}^{X}(x^{t})^{T} (x^{∗} − x^{t}) + α_{t} ∥γ_{ε_{t}}^{X}(x^{t})∥^{2} ≥ −ϵ  (9)

holds for at least one t ≥ N(δ), say t = t(δ). From the definition of N(δ), it follows that γ_{ε_{t(δ)}}^{X}(x^{t(δ)})^{T} (x^{∗} − x^{t(δ)}) ≥ −ϵ. By convexity we have that f(x^{∗}) − f(x^{t(δ)}) ≥ γ_{ε_{t(δ)}}^{X}(x^{t(δ)})^{T} (x^{∗} − x^{t(δ)}) − ε_{t(δ)}, since x^{∗}, x^{t(δ)} ∈ X. Hence, f(x^{t(δ)}) ≤ f^{∗} + ϵ + ε_{t(δ)}, that is, x^{t(δ)} ∈ X^{ϵ+ε_{t(δ)}} ⊆ X^{ϵ(1+σ)} ⊆ X^{∗} + B^{δ/2} ⊂ X^{∗} + B^{δ}.

Now, suppose that x^{t} ∈ X^{∗} + B^{δ} for some t ≥ N(δ). If (8) holds, then, using (7), we have that ∥x^{∗} − x^{t+1}∥ < ∥x^{∗} − x^{t}∥ for any x^{∗} ∈ X^{∗}. Hence,

dist (x^{t+1}, X^{∗}) ≤ ∥proj (x^{t}, X^{∗}) − x^{t+1}∥ < ∥proj (x^{t}, X^{∗}) − x^{t}∥ = dist (x^{t}, X^{∗}) ≤ δ.

Thus, x^{t+1} ∈ X^{∗} + B^{δ}. Otherwise, (9) must hold and, using the same arguments as above, we obtain that f(x^{t}) ≤ f^{∗} + ϵ + ε_{t} ≤ f^{∗} + ϵ(1 + σ), i.e., x^{t} ∈ X^{ϵ(1+σ)} ⊆ X^{∗} + B^{δ/2}. As

∥x^{t+1} − x^{t}∥ = ∥proj (x^{t} − α_{t}γ_{ε_{t}}^{X}(x^{t}), X) − x^{t}∥ ≤ ∥x^{t} − α_{t}γ_{ε_{t}}^{X}(x^{t}) − x^{t}∥ = α_{t} ∥γ_{ε_{t}}^{X}(x^{t})∥ ≤ \frac{δ}{2}

whenever t ≥ N(δ), it follows that x^{t+1} ∈ X^{∗} + B^{δ/2} + B^{δ/2} = X^{∗} + B^{δ}.

By induction with respect to t ≥ t(δ), it follows that x^{t} ∈ X^{∗} + B^{δ} for all t ≥ t(δ). Since this holds for arbitrarily small values of δ > 0 and f is continuous, the theorem follows.

Remark 4 (On the convergence conditions). From the proof, the requirement that {γ_{ε_{t}}^{X}(x^{t})} is bounded can be replaced by the weaker requirement that {α_{t}∥γ_{ε_{t}}^{X}(x^{t})∥^{2}} → 0 holds. Further, if X is bounded, and not just the set X^{∗}, then the sequence {γ_{ε_{t}}(x^{t})} is bounded automatically, while the sequence {ν(x^{t})} may always be constructed so that it is bounded. For more details on the possible choices of this sequence, we refer to [LPS96].

Remark 5 (Relations). With ε_{t} = 0, Theorem 3 reduces to a result by Larsson et al. [LPS96]. Further letting ν^{t} = 0^{n} reduces the algorithm to traditional subgradient optimization, and the result to one by Ermol’ev [Erm66, Section 9].

2.2 Divergent series step lengths, scaled direction

The scaled conditional ε-subgradient optimization method is given by

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

given some rule for choosing {α_{t}}.

This scaling of the search direction allows us to remove the condition that the sequence {γ_{ε_{t}}^{X}(x^{t})} is bounded.

Theorem 6 (Convergence to the optimal set using divergent series step lengths). Let {x^{t}} be generated by the method (10), (4) applied to [P]. If X^{∗} is bounded and ℜ_{+} ∋ {ε_{t}} → 0, then {f(x^{t})} → f^{∗} and {dist (x^{t}, X^{∗})} → 0.

Proof. The proof technique is similar to that of Theorem 3. We define μ_{t} := ∥γ_{ε_{t}}^{X}(x^{t})∥. The definition of N(δ) is here altered to mean that for all t ≥ N(δ), α_{t} ≤ ϵ, ε_{t} ≤ σϵ and α_{t} ≤ δ/2.

The inequality (7) is here replaced by

∥x^{∗} − x^{t+1}∥^{2} ≤ ∥x^{∗} − x^{t}∥^{2} + α_{t} (\frac{2}{μ_{t}} γ_{ε_{t}}^{X}(x^{t})^{T} (x^{∗} − x^{t}) + α_{t}) ,

and, consequently, (8) by

\frac{2}{μ_{t}} γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) + α_{s} < −ϵ.

We conclude as in the previous proof that

\frac{2}{μ_{t}} γ_{ε_{t}}^{X}(x^{t})^{T} (x^{∗} − x^{t}) + α_{t} ≥ −ϵ

holds for at least one t ≥ N(δ), say t = t(δ), which implies that γ_{ε_{t(δ)}}^{X}(x^{t(δ)})^{T} (x^{∗}−x^{t(δ)}) ≥ −ϵμ_{t(δ)}, and, by convexity, that f(x^{t(δ)}) ≤ f^{∗} + ϵμ_{t(δ)} + ε_{t(δ)}, that is, x^{t(δ)} ∈ X^{ϵμ_{t(δ)}+ε_{t(δ)}} ⊆ X^{ϵ(μ_{t(δ)}+σ)} ⊆ X^{∗} + B^{δ/2} ⊂ X^{∗} + B^{δ}.

The rest of the proof follows as in the proof of Theorem 3, noting that

∥x^{t+1} − x^{t}∥ = ∥proj (x^{t} − α_{t} \frac{γ_{ε_{t}}^{X}(x^{t})}{μ_{t}}, X) − x^{t}∥ ≤ ∥x^{t} − α_{t} \frac{γ_{ε_{t}}^{X}(x^{t})}{μ_{t}} − x^{t}∥ = α_{t} ≤ \frac{δ}{2}, t ≥ t(δ).

The result follows.

Remark 7 (Relations). With ν^{t} = 0^{n}, the result reduces essentially to one by Polyak [Pol67], [Pol87, pp. 144–145] (the first one also assumes that ε_{t} = 0, while the second one also assumes that X = ℜ^{n}). Convergence is there established only for the sequence {f(x^{t})}). In [Alb83, SoZ98], convergence results are established for a subgradient algorithm (still assuming that ν^{t} = 0^{n} holds), where the search direction is given by −(γ(x^{t}) + r^{t}), where {r^{t}} ⊂ ℜ^{n} is a sequence of error vectors which tends to zero ([Alb83]) or stays bounded ([SoZ98]).

2.3 Quadratically convergent step lengths, non-scaled direction

We now introduce the additional requirement that (5) holds. As can be seen from the proof of the below theorem, this step length condition implies the boundedness of the sequence of iterates, whence that boundedness condition, present in Theorem 3, here can be removed.

Theorem 8 (Convergence to an optimal solution using divergent series step lengths). Let {x^{t}} be generated by the method (6), (4), (5) applied to [P]. If ℜ_{+} ∋ {ε_{t}} → 0, the sequence {γ_{ε_{t}}^{X}(x^{t})} is bounded, and if ∑_{s=0}^{∞} α_{s}ε_{s} < ∞, then {x^{t}} converges to an element of X^{∗}.

Proof. Let x^{∗} ∈ X^{∗}. Define μ_{t} := ∥γ_{ε_{t}}^{X}(x^{t})∥. In every iteration t we have that

∥x^{∗} − x^{t+1}∥^{2} = ∥x^{∗} − proj (x^{t} − α_{t}γ_{ε_{t}}^{X}(x^{t}), X^{∗})∥^{2} ≤ ∥x^{∗} − x^{t} + α_{t}γ_{ε_{t}}^{X}(x^{t})∥^{2}
= ∥x^{∗} − x^{t}∥^{2} + α_{t} (2γ_{ε_{t}}^{X}(x^{t})^{T} (x^{∗} − x^{t}) + α_{t}μ_{t}^{2}) ,  (11)

where the inequality follows from the projection property. Repeated application of (11) yields that

∥x^{∗} − x^{t}∥^{2} ≤ ∥x^{∗} − x^{0}∥^{2} + 2 ∑_{s=0}^{t−1} α_{s}γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) + ∑_{s=0}^{t−1} α_{s}^{2}μ_{s}^{2}.  (12)

Since x^{∗} ∈ X^{∗} and γ_{ε_{s}}^{X}(x^{s}) ∈ ∂_{ε_{s}}^{X}f(x^{s}) for all s ≥ 0 we obtain that

f(x^{s}) ≥ f^{∗} ≥ f(x^{s}) + γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) − ε_{s},  s ≥ 0,  (13)

and hence that γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) ≤ ε_{s} for all s ≥ 0. We define c := sup_{t}{μ_{t}}, p := ∑_{t=0}^{∞} α_{t}^{2}, and d := ∑_{s=0}^{∞} α_{s}ε_{s}. From (12) we then conclude that ∥x^{∗} − x^{t}∥^{2} < ∥x^{∗} − x^{0}∥^{2} + pc^{2} + 2d for any t ≥ 1, and thus that the sequence {x^{t}} is bounded.

Assume now that there is no subsequence {x^{t_{i}}} of {x^{t}} with {γ_{ε_{t_{i}}}^{X} (x^{t_{i}})^{T} (x^{∗} − x^{t_{i}})} → 0. Then there must exist an ϵ > 0 with γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) ≤ −ϵ for all sufficiently large values of s. From (12) and the conditions on the step lengths it follows that {∥x^{∗} − x^{t}∥} → −∞, which clearly is impossible. The sequence {x^{t}} must therefore contain a subsequence {x^{t_{i}}} such that {γ_{ε_{t_{i}}}^{X} (x^{t_{i}})^{T} (x^{∗} − x^{t_{i}})} → 0. From (13) and the assumption that {ε_{t}} → 0 it follows that {f(x^{t_{i}})} → f^{∗}. The boundedness of {x^{t}} implies the existence of an accumulation point of {x^{t_{i}}}, say x^{∞}. From the continuity of f follows that x^{∞} ∈ X^{∗}.

To show that x^{∞} is the only accumulation point of {x^{t}}, let δ > 0 and let M(δ) be such that ∥x^{∞} − x^{M(δ)}∥^{2} ≤ δ/3, ∑_{s=M(δ)}^{∞} α_{s}^{2} ≤ δ/(3c^{2}), and ∑_{s=M(δ)}^{∞} α_{s}ε_{s} ≤ δ/6. Consider any t > M(δ). Analogously to the derivation of (12), and using (13), we then obtain that

∥x^{∞} − x^{t}∥^{2} ≤ ∥x^{∞} − x^{M(δ)}∥^{2} + ∑_{s=M(δ)}^{t−1} α_{s}^{2}μ_{s}^{2} + 2 ∑_{s=M(δ)}^{t−1} α_{s}ε_{s} < \frac{δ}{3} + \frac{δ}{3c^{2}} c^{2} + \frac{2δ}{6} = δ.

Since this holds for arbitrarily small values of δ > 0, the theorem follows.

Remark 9 (Relations). With ν^{t} = 0^{n} and X = ℜ^{n}, the result reduces to one in Correa and Lemaréchal [CoL93]. With ε_{t} = 0 the result reduces to one obtained in Larsson et al. [LPS96]. Under the assumption that X = ℜ^{n}, Polyak [Pol87, Section 5.5] establishes the convergence of inexact subgradient algorithms where the search direction is −(γ(x^{t}) + r^{t}), and where the error sequence {r^{t}} tends to zero, stays bounded or is some random sequence of vectors with bounded variance.

2.4 Quadratically convergent step lengths, scaled direction

When introducing a scaling of the step direction in the case of ε-subgradients and the use of the quadratically convergent step length rule (5), not only do we need to introduce the condition that ∑_{s=0}^{∞} α_{s}ε_{s} < ∞ holds (as in Section 2.3), but we also need to ensure that the length of the step direction does not tend to zero too quickly. Hence, the norm of the direction vector is projected onto the half-line { ℓ | ℓ ≥ 1 }. We further note that the scaling again allows us to remove the condition that {γ_{ε_{t}}^{X}(x^{t})} is bounded.

The scaled conditional ε-subgradient optimization method is given by

x^{t+ \frac{1}{2}} := x^{t} − α_{t} \frac{γ_{ε_{t}}^{X}(x^{t})}{max\{1, ∥γ_{ε_{t}}^{X}(x^{t})∥\}}, x^{t+1} = proj (x^{t+ \frac{1}{2}} , X) ,  t = 0, 1, ….  (14)

Theorem 10 (Convergence to an optimal solution using divergent series step lengths). Let {x^{t}} be generated by the method (14), (4), (5) applied to [P]. If ℜ_{+} ∋ {ε_{t}} → 0 and ∑_{s=0}^{∞} α_{s}ε_{s} < ∞, then {x^{t}} converges to an element of X^{∗}.

Proof. The proof follows the same line of arguments as that of Theorem 8. Let μ_{t} := ∥γ_{ε_{t}}^{X}(x^{t})∥ and η_{t} := max{1, μ_{t}}. Let x^{∗} ∈ X^{∗}. Analogously to the proof of Theorem 8, we obtain for every t that

∥x^{∗} − x^{t+1}∥^{2} ≤ ∥x^{∗} − x^{t}∥^{2} + \frac{α_{t}}{η_{t}} (2γ_{ε_{t}}^{X}(x^{t})^{T} (x^{∗} − x^{t}) + \frac{α_{t}μ_{t}^{2}}{η_{t}} ) .

Used repeatedly, we obtain

∥x^{∗} − x^{t}∥^{2} ≤ ∥x^{∗} − x^{0}∥^{2} + 2 ∑_{s=0}^{t−1} \frac{α_{s}}{η_{s}} γ_{ε_{s}}^{X}(x^{s})^{T} (x^{∗} − x^{s}) + ∑_{s=0}^{t−1} \frac{α_{s}^{2}μ_{s}^{2}}{η_{s}^{2}} .  (15)

From (13) and (15) we then obtain that

∥x^{∗} − x^{t}∥^{2} ≤ ∥x^{∗} − x^{0}∥^{2} + 2 ∑_{s=0}^{t−1} \frac{α_{s}ε_{s}}{η_{s}} + ∑_{s=0}^{t−1} \frac{α_{s}^{2}μ_{s}^{2}}{η_{s}^{2}} ≤ ∥x^{∗} − x^{0}∥^{2} + 2 ∑_{s=0}^{t−1} α_{s}ε_{s} + ∑_{s=0}^{t−1} α_{s}^{2},

so the sequence {x^{t}} is bounded, from the assumptions on the step lengths.

That every accumulation point of {x^{t}} is optimal then follows as in the proof of Theorem 8, using (15) in place of (12), and noting that μ_{t}/η_{t} ≤ 1 for all t.

To show that x^{∞} is the only limit point of {x^{t}}, let δ > 0 and let M(δ) be such that ∥x^{∞} − x^{M(δ)}∥^{2} ≤ δ/3, ∑_{s=M(δ)}^{∞} α_{s}^{2} ≤ δ/3, and ∑_{s=M(δ)}^{∞} α_{s}ε_{s} ≤ δ/6. Consider any t > M(δ). Analogously to the derivation of (15), and using (13) and again noting that μ_{t}/η_{t} ≤ 1 for all t, we then obtain that

∥x^{∞} − x^{t}∥^{2} ≤ ∥x^{∞} − x^{M(δ)}∥^{2} + ∑_{s=M(δ)}^{t−1} \frac{α_{s}^{2}μ_{s}^{2}}{η_{s}^{2}} + 2 ∑_{s=M(δ)}^{t−1} \frac{α_{s}ε_{s}}{η_{s}} < \frac{δ}{3} + \frac{δ}{3} + \frac{2δ}{6} = δ.

Since this holds for arbitrarily small values of δ > 0, this completes the proof.

Remark 11 (Relations). With ε_{t} = 0 the result reduces to one in Larsson et al. [LPS96]. With ν^{t} = 0^{n} the result reduces to ones previously reached by Polyak [Pol67] and Alber et al. [AIS98] (where the condition that ∑_{s=0}^{∞} α_{s}ε_{s} < ∞ holds is replaced by the condition that ε_{t} ≤ ηα_{t}, η > 0 for all t).

Having presented some generally useful results on the convergence of conditional ε-subgradient algorithms in constrained, convex optimization, we now turn to the solution of the saddle-point problem [SP] which will use a subset of the results obtained in this section.

3 Ergodic convergence to the set of saddle-points

In order to solve the saddle-point problem [SP] it is in general not enough to find any solution to the maximization problem over y with x fixed to a value x^{∗} ∈ X^{∗}, as discussed, for example, in Hiriart-Urruty and Lemaréchal [HiL93, Remark VII.4.2.6], unless L is strictly concave in y. (The corresponding result in the case of the convex program [CP] is known as the non-coordinability phenomenon; see, e.g., [Las70].) We will establish that an ergodic (that is, averaged) sequence of the inexact solutions y_{ε_{t}}^{t} to the problem (1), generated from the sequence x^{t} in the above subgradient algorithm, tends to Y^{∗}. Before moving on to state and establish this result, we will however discuss some related algorithms.

Under an assumption that L is strictly convex–concave, it is known that f, defined in (1), is continuously differentiable, with ∇f(x) = ∇_{x}L(x, y) from Danskin’s Theorem [Dan67], y being the unique solution to (1) given x. In order to produce a saddle-point in this situation, it is enough to find the minimizer of f over X, and apply (1) to get the corresponding component y of the saddle-point. Algorithms of this type include the descent algorithm of Demyanov and Malozemov [DeM74, p. 230] and the gradient projection algorithm of Zhu and Rockafellar [ZhR93]. The former reference also suggests adding a strictly convex–concave quadratic term in the absence of strict convex–concavity, in effect thus producing a proximal point-like algorithm. Kallio and Ruszczyński [KaR94] (see also [HeL89, KaR99, Ouo00]) propose a gradient projection algorithm defined by the partial gradients of the function L evaluated at perturbed points. (We, however, do not assume L to be differentiable.) Kiwiel [Kiw95] solves the saddle-point problem through the use of a bundle method for the problem [P], and establishes that a convergent component in y is generated automatically in the search-direction finding quadratic programming problems. As for the special case of the convex program [CP], one can also envisage applying column generation and/or cutting plane approaches, where coordinability is induced through the solution of restricted master problems; see [LPS99] for more detailed discussions.

The inspiration for the algorithm proposed here is however much more simple approaches to the solution of the problem [CP] through the use of Lagrangian dualization, subgradient optimization, and the construction of an optimal primal solution as simple or weighted averages of the Lagrangian subproblem solutions. Thus, a saddle-point is generated without solving any auxiliary problems. The origin is Shor’s [Sho85, pp. 116–118] work on linear programming, followed by [LaL97, ShC96, BaA00] (still in the context of linear programming, and the latter reference lacking a convergence proof), [LLP97] for a special large-scale convex programming problem arising in transportation planning, and [LPS99] for the general convex program [CP]. The first convergence result of this type for saddle-point problems not arising from a Lagrangian was given by Petersson and Patriksson [PeP97], who studied a special such large-scale problem arising in contact mechanics.

In the above algorithms, it is assumed that the computations of the subproblems are performed exactly. We extend the scope of these algorithm not only to the more general convex– concave saddle-point problems, but also to possibly inexact solutions of the subproblems. In the context of the problem [CP] and subgradient methods, it has previously been shown in [Ber99, ZLW99, ZhL02] that convergence to the solution to [P] can be achieved through the solution of inexact subproblem solutions, but primal convergence results that can be extracted from this development have not been studied previously.

The interest in inexact computations is perhaps the most pronounced in the solution of combinatorial optimization problems through Lagrangian dualization. (This area is also one where Lagrangian dualization is quite popular.) Although combinatorial optimization problems are not convex problems in general, and there may not exist a saddle point to such a Lagrangian, there does however exist a saddle point for the convexified problem associated with the combinatorial problem and its Lagrangian formulation, and the maximum value of the Lagrangian dual function is the optimal value of the convexified problem. (Some of this theory is outlined by Wolsey [Wol98, Section 10.2].) If the relaxation does not satisfy the integrality property (so that the Lagrangean subproblem cannot be reduced to a linear program), then the Lagrangian subproblem will be a (potentially) computationally difficult combinatorial problem, and the use of inexact methods such as heuristics to solve them will therefore be of computational advantage; then, also, the resulting solution will provide an ε-subgradient of the Lagrangian dual function.

The scope is also extended to include the possible use of conditional subgradients. Although such an algorithm can, in principle, be incorporated into a standard subgradient algorithm for the extended objective function f + ψ_{X}, this function is not finite everywhere, and moreover, it has been found in the numerical investigations performed in [LPS96] that adding a normal cone element to the search direction can substantially enhance convergence in practice for some difficult problems.

3.1 Preliminaries

The optimality conditions for x^{∗} in [P] is given by

−∂f(x^{∗}) ∩ N_{X}(x^{∗}) ≠ ∅  (16)

(e.g., [Roc81, Proposition 5A and Equation (5.5)]). The non-coordinability phenomenon discussed above, which is inherent in every non-strictly convex–concave saddle-point problem, can be equivalently described as the failure of the entire set −∂f(x^{∗}) to be included in N_{X}(x^{∗}), something which obviously does hold whenever f is differentiable at x^{∗}. We will establish the convergence of an averaged (or, ergodic) sequence of subproblem solutions by means of establishing that an averaged sequence of the ε_{t}-subgradients γ_{ε_{t}}(x^{t}) accumulates at subgradients which verify optimality in accordance with (16). The representative algorithm which we have chosen among those in the previous section is that validated in Theorem 8.

The properties of ergodic sequences of elements generated in a subgradient scheme have previously been analyzed in [LPS98]. We extend some of their analysis to the use of ε-subgradients.

Let

A_{t} := ∑_{s=0}^{t−1} α_{s},  (17)

ŷ^{t} := A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}y_{ε_{s}}^{s},  (18)

g^{t} := A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}γ_{ε_{s}}(x^{s}),  (19)

n_{c}^{t} := A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ν^{s},  (20)

n_{p}^{t} := A_{t}^{−1} ∑_{s=0}^{t−1}(x^{s+ \frac{1}{2}} − x^{s+1}),  (21)
n^{t} := n_{c}^{t} + n_{p}^{t},  (22)
φ^{t} := A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}f(x^{s}),  (23)

f_{t}(x) := A_{t}^{−1} ∑_{s=0}^{t−1} α_{s} [f(x^{s}) + (γ_{ε_{s}}(x^{s}))^{T}(x − x^{s}) − ε_{s}] ,  x ∈ X,  (24)
δ_{t}(x) := f(x) − f_{t}(x),  x ∈ X,  (25)
ϱ_{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 ∈ X.  (26)

Here, A_{t} is the accumulated step length up to iteration t, ŷ^{t} the weighted average of the inexact solutions to (1), g^{t} the weighted average of the ε_{s}-subgradients of f, and n_{c}^{t} and n_{p}^{t} ergodic normal elements and projection steps, respectively. We note that {ŷ^{t}} ⊂ Y, and this sequence is therefore bounded, by the boundedness assumption on Y. Continuing, φ^{t} ≥ v^{∗} clearly holds. The affine function f_{t} is derived as a surrogate of the convexity inequality, and therefore δ_{t}(x) ≥ 0 on X. Further, since ν^{s} ∈ N_{X}(x^{s}) and x^{s+ \frac{1}{2}} − x^{s+1} ∈ N_{X}(x^{s+1}), ϱ_{t}(x) ≥ 0 on X, and thus defines a valid inequality for X.

We will establish that any accumulation point, ŷ^{∞}, of the sequence {ŷ^{t}} together with the solution x^{∞} obtained from the subgradient scheme forms a saddle-point of L.

Lemma 12 (Y (·) is a closed map). Let the sequence {x^{t}} ⊂ X, {ε_{t}} ⊂ ℜ_{+}, the map Y_{ε}(·) : X ↦ 2^{Y} be given by the definition

Y_{ε}(x) := { y ∈ Y | L(x, y) ≥ f(x) − ε }, x ∈ X,

and the sequence {y_{ε_{t}}^{t}} be given by the inclusion y_{ε_{t}}^{t} ∈ Y_{ε_{t}}(x^{t}). If the sequences {x^{t}} → x and {ε_{t}} → 0, then {dist (y_{ε_{t}}^{t}, Y (x))} → 0. If, in addition, Y (x) = {y}, then {y_{ε_{t}}^{t}} → y.

Proof. By the definition of Y_{ε_{t}}(x^{t}), L(x^{t}, y_{ε_{t}}^{t}) ≥ f(x^{t}) − ε_{t} holds for all t. It follows from the continuity of the functions L and f, the compactness of X and the construction of the sequence {ε_{t}} that y ∈ Y (x) holds for any accumulation point y of the sequence {y_{ε_{t}}^{t}}. The result {dist (y_{ε_{t}}^{t}, Y (x))} → 0 then follows from the boundedness of the sequence {y_{ε_{t}}^{t}}. The second result is then immediate.

3.2 Main results

We next utilize this result to establish that the sequence {ŷ^{t}} accumulates in the set Y (x^{∞}), establishing the left-most inequality in [SP].

Theorem 13 (L(x^{∞}, ŷ^{∞}) ≥ L(x^{∞}, y) for all y ∈ Y). {dist (ŷ^{t}, Y (x^{∞}))} → 0.

Proof. Fix any ϵ > 0. By Theorem 8 and Lemma 12, for any large enough τ,

dist (y_{ε_{s}}^{s}, Y (x^{∞})) ≤ ϵ/2, s ≥ τ.

By the convexity of the function dist (·, Y (x^{∞})) (e.g., [Roc70, Theorem 4.3]), we have that

dist (ŷ^{t}, Y (x^{∞})) ≤ A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}dist (y_{ε_{s}}^{s}, Y (x^{∞})), s ≥ τ.

Since {A_{t}} → ∞ and τ is fixed, A_{t}^{−1} ∑_{s=τ}^{t−1} α_{s}dist (y_{ε_{s}}^{s}, Y (x^{∞})) ≤ (1 − A_{t}^{−1}A_{τ})ϵ/2 holds for every t > τ. Hence, dist (ŷ^{t}, Y (x^{∞})) ≤ ϵ holds for all t > τ that are large enough, and the desired result follows.

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

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

The following lemma concerns the convergence properties of some of our ergodic sequences.

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

Proof. By Theorem 8, {x^{t}} → x^{∞}. From the iteration formula (6) it follows that

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

Repeated application of this inequality and utilizing the definitions (23), (25), and (26) result in

∥x^{0} − x^{∞}∥^{2} + ∑_{s=0}^{t−1} α_{s}^{2}∥γ_{ε_{s}}^{X}(x^{s})∥^{2} − 2A_{t} (δ_{t}(x^{∞}) + ϱ_{t}(x^{∞}) + φ_{t} − v^{∗} − A_{t}^{−1} ∑_{s=0}^{t−1} α_{s}ε_{s}) ≥ 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}}^{X}(x^{s})∥^{2} + α_{s}ε_{s}]) .

Let t → ∞ and invoke the conditions of Theorem 8.

For the latter result, we note that the definitions (19), (24) and (25) yield

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

From the definitions (19) and (26) follow that

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

Theorem 8, Lemma 14, the continuity of f, and the first part of this Lemma yield that the righthand sides of both the above equations tend to zero as t approaches infinity. The result follows.

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

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

Proof. By the definition (19) and the iteration formula (6),

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}).

Theorem 8 yields that {x^{t}} → x^{∞}. The result then follows from the definition (17) and the condition (4).

We are now ready to establish that the ergodic sequence {g^{t}} of subgradients accumulates at subgradients which verify optimality, according to (16). We divide the result into two parts, extending, respectively, Theorem 3.7 and Theorem 3.8 in [LPS98] to the use of ε-subgradients.

Proposition 17 (Convergence of {g^{t}} to ∂f(x^{∞})). {dist (g^{t}, ∂f(x^{∞}))} → 0.

Proof. The definitions (19), (24) and (25) imply that g^{t} is a δ_{t}(x)-subgradient of f at any x ∈ X; applying this result to x = x^{t} yields

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

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

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

Proof. From the definition (26) it follows that, for all t and any z ∈ X, (n^{t})^{T}(z − x^{∞}) = −ϱ_{t}(z) + ϱ_{t}(x^{∞}) ≤ ϱ_{t}(x^{∞}). By Lemma 14, the sequence {n^{t}} is bounded. Let ñ be an accumulation point of the sequence {n^{t}}_{t∈T} for some convergent subsequence T . From Lemma 15 it then follows that ñ^{T} (z − x^{∞}) ≤ 0 for any z ∈ 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 Lemma 16, ∥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.

Theorem 13 established one of the inequalities in the definition of [SP]; the second inequality now follows. (Note that the accumulation point ŷ^{∞} still is arbitrary.)

Theorem 19 (L(x, ŷ^{∞}) ≥ L(x^{∞}, ŷ^{∞}) for all x ∈ X). {dist (x^{t}, X(ŷ^{∞}))} → 0.

Proof. For every x ∈ X,

L(x, ŷ^{∞}) − L(x^{∞}, ŷ^{∞}) ≥ f(x) − L(x^{∞}, ŷ^{∞}) = f(x) − f(x^{∞}) ≥ g̃^{T}(x − x^{∞}) ≥ 0,

where the first inequality follows from the definition of f(x) and the fact that ŷ^{∞} ∈ Y, the equality from Theorem 13, and the two final inequalities from the convexity of f and, respectively, Propositions 17 and 18.

We summarize the results of the Theorems 13 and 19 as follows.

Theorem 20 ((x^{∞}, ŷ^{∞}) solves [SP]). {dist ((x^{t}, ŷ^{t}), {x^{∞}} × Y^{∗})} → 0.

4 Further research

As outlined at the beginning of Section 3, among the possible application areas of this type of methods perhaps the most interesting one is to use them in order to generate an approximate solution to the convexification of an integer program. The ergodic sequence would then be terminated finitely, for example when the duality gap fails to be reduced significantly. The averaged solution, or the result of a primal feasibility heuristic applied from it, is there after used as a starting point for (or is embedded within) an algorithm devised to close the duality gap, such as a cutting plane or branch and bound algorithm. The use of this technique is well-known in circumstances when the relaxation has the integrality property, because it is then equivalent to solve the linear relaxation, but it has been tested only to a limited extent for more difficult Lagrangian subproblems. In theory, these subproblems must of course be solved exactly in the limit according to our convergence conditions, and this may not be practically feasible. Two of the authors of this article are currently investigating the theory and practice of using Lagrangian near-optimal solutions and ergodic sequences in computations in combinatorial optimization, combined with approximate solution methods using core problems and column generation; cf. [LaP02].

The proofs of the results of the previous section relies on the essential element that the sequence {x^{t}} converges. Moreover, the analysis at present utilizes rather heavily the condition (5) on the sequence of step lengths. It would be of interest for practical purposes to be able to avoid this condition, as the possibility to enable the use of the algorithm of Theorem 3 in place of that of Theorem 8 would also imply that the condition that ∑_{s=0}^{∞} α_{s}ε_{s} < ∞ holds can be removed, which in turn would allow for the subproblem solutions to be even less exact.

The possible use of the algorithms of Theorem 6 and 10, where the search directions are scaled, are left as a topic for further research, as are the possibilities to use other convexity weights in the construction of the ergodic sequence {ŷ^{t}} as well as other step length rules in the subgradient algorithm.

Acknowledgement

The authors thank an anonymous referee for pertinent remarks which improved the presentation.

References

[Alb83] Ya. I. Alber, Recurrence relations and variational inequalities, Soviet Mathematics Doklady, 27 (1983), pp. 511–517.

[AIS98] Ya. I. Alber, A. N. Iusem and M. V. Solodov, On the projected subgradient method for nonsmooth convex optimization in a Hilbert space, Mathematical Programming, 81 (1998), pp. 23–35.

[BaA00] F. Barahona and R. Anbil, The volume algorithm: Producing primal solutions with a subgradient method, Mathematical Programming, 87 (2000), pp. 385–399.

[BSS93] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, John Wiley & Sons, New York, NY, second ed., 1993.

[Ber99] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, second ed., 1999.

[CoL93] R. Correa and C. Lemaréchal, Convergence of some algorithms for convex minimization, Mathematical Programming, 62 (1993), pp. 261–275.

[Dan67] J. M. Danskin, The Theory of Max-Min, Springer-Verlag, Berlin, 1967.

[DeM74] V. F. Demyanov and V. N. Malozemov, Introduction to Minimax, John Wiley & Sons, New York, NY.

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

[Erm66] Yu. M. Ermol’ev, Methods for solving nonlinear extremal problems, Cybernetics, 2 (1966), pp. 1–17.

[HeL89] D. W. Hearn and S. Lawphongpanich, Operations Research Letters, 8 (1989), pp. 189–196.

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

[KaR99] M. Kallio and C. H. Rosa, Large-scale convex optimization via saddle point computation, Operations Research, 47 (1999), pp. 93–101.

[KaR94] M. Kallio and Ruszczyński, Perturbation methods for saddle point computation. Working Paper WP-94-38, IIASA, Laxenburg, Austria.

[Kiw95] K. C. Kiwiel, Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities, Mathematical Programming, 69 (1995), 89–109.

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

[LLP97] T. Larsson, Z. Liu, and M. Patriksson, A dual scheme for traffic assignment problems, Optimization, 42 (1997), pp. 323–358.

[LaP02] T. Larsson and M. Patriksson, Global optimality conditions and Lagrangian heuristics for nonconvex optimization, report, Department of mathematics, Chalmers University of Technology, Gothenburg, 2002 (in preparation).

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

[LPS98] T. Larsson, M. Patriksson, and A.-B. Strömberg, Ergodic convergence in subgradient optimization, Optimization Methods & Software, 9 (1998), pp. 93–120.

[LPS99] T. Larsson, M. Patriksson, and A.-B. Strömberg, Ergodic, primal convergence in dual subgradient schemes for convex programming, Mathematical Programming, 86 (1999), pp. 283–312.

[Las70] L. S. Lasdon, Optimization Theory for Large Systems, Macmillan, New York, NY, 1970.

[Ouo00] A. Ouorou, A primal–dual algorithm for monotropic programming and its application to network optimization, Computational Optimization and Applications, 15 (2000), pp. 125–143.

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

[Pol67] B. T. Polyak, A general method of solving extremum problems, Soviet Mathematics Doklady, 8 (1967), pp. 593–597.

[Pol69] B. T. Polyak, Minimization of unsmooth functionals, USSR Computational Mathematics and Mathematical Physics, 9 (1969), pp. 14–29.

[Pol87] B. T. Polyak, Introduction to Optimization, Optimization Software, New York, NY, 1987.

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

[Roc81] R. T. Rockafellar, The Theory of Subgradients and its Applications to Problems of Optimization: Convex and Nonconvex Functions, Heldermann Verlag, Berlin, 1981.

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

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

[SoZ98] M. V. Solodov and S. K. Zavriev, Error stability properties of generalized gradient-type algorithms, Journal of Optimization Theory and Applications, 98 (1998), pp. 663–680.

[Wol98] L. A. Wolsey, Integer Programming, John Wiley & Sons, New York, New York, 1998.

[ZhL02] X. Zhao and P. B. Luh. Wang, New bundle methods for solving Lagrangian relaxation dual problems, Journal of Optimization Theory and Applications, 113 (2002), pp. 373–397.

[ZLW99] X. Zhao, P. B. Luh, and J. Wang, Surrogate gradient algorithm for Lagrangian relaxation, Journal of Optimization Theory and Applications, 100 (1999), pp. 699–712.

[ZhR93] C. Zhu and R. T. Rockafellar, Primal–dual projected gradient algorithms for extended linear– quadratic programming, SIAM Journal on Optimization, 3 (1993), pp. 751–783.