Journal of Convex Analysis Volume 1 (1994), No.1, 75–86

Bounded Diagonally Stationary Sequences in Convex Optimization

B. Lemaire

Université Montpellier II, Place E. Bataillon, F-34095 Montpellier Cedex 5

Received 2 December 1993 Revised manuscript received 13 June 1994

Let X be a real normed linear space, f, f^{n}, n ∈ IN, be extended real-valued proper closed convex functions on X. A sequence {x_{n}} in X is called diagonally stationary for {f^{n}} if for all n there exists x_{n}^{⋆} ∈ ∂f^{n}(x_{n}) such that ∥x_{n}^{⋆}∥_{⋆} → 0. Such sequences arise in approximation methods for the problem of minimizing f. We present some general quantitative convergence results based upon metric variational convergence theory, appropriate equi-well-posedness and conditioning concepts for the limit function f, and Fejér monotonicity.

Keywords : Asymptotical behaviour, conditioning, convex optimization, diagonal stationarity, error estimate, Fejér monotonicity, variational convergence, well-posedness.

1991 Mathematics Subject Classification: 65K10, 90C25, 49D07.

1. Introduction

Let X be a real normed linear space, f, f^{n}, n ∈ IN, be extended real-valued proper closed convex functions on X, and {x_{n}} be a diagonally stationary sequence for {f^{n}}, in other words, for all n there exists x_{n}^{⋆} ∈ ∂f^{n}(x_{n}) such that ∥x_{n}^{⋆}∥_{⋆} → 0. Such sequences are generated by perturbed (or diagonal) constructive processes like regularization or gradient method combined with approximation like discretization or penalization (see the bibliography of [9]). Some convergence results for such diagonally stationary sequences based upon variational convergence theory and appropriate equi-well-posedness concepts have been presented in [9]. These previous results were of qualitative kind: the distance d(x_{n}, S) from x_{n} to the optimal set S := Argminf tends to 0, or, in a reflexive Banach space setting, any weak accumulation point of {x_{n}} is in S. The present work is devoted to more precise results for bounded (∥x_{n}∥ ≤ ρ) diagonally stationary sequences based upon metric variational convergence theory, suitable well-posedness and conditioning concepts for the limit function f, and Fejér monotonicity. Two main results are established. The first one is an error estimate: if f is “sufficiently well” conditioned and if the ρ-Hausdorff excess e_{ρ}(∂f^{n}, ∂f) tends to 0, then d(x_{n}, S) can be estimated in terms of ∥x_{n}^{⋆}∥_{⋆} and e_{ρ}(∂f^{n}, ∂f); these two quantities are under control during the constructive process that

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag Berlin

76 B. Lemaire / Bounded diagonally stationary sequences in convex optimization

generates {x_{n}}. Therefore, such an estimate would be of practical interest for deriving a stopping rule in such a process, at least when it is possible to estimate the appropriate constants arising in the error estimating formula. Nevertheless, this gives information on the rate of convergence of the error. In particular, finite termination holds (x_{n} ∈ S for n large enough) if f is linearly conditioned and if (what we call exact approximation) e_{ρ}(∂f^{n}, ∂f) = 0 for n large enough. The second main result is norm convergence to some minimizer (which is stronger than d(x_{n}, S) → 0). For that, two key concepts are used: well posedness and Fejér monotonicity, a property currently encountered in iterative processes but not so much exploited on its own. As a consequence, we show that well posedness gives a new infinite dimensional case of strong convergence for the Martinet-Rockafellar’s proximal method. The paper is organized as follows. Section 2 recalls some definitions about metric variational convergence theory and diagonal stationarity. Section 3 is devoted to the error estimate and finite termination. In section 4 we prove that in case of quadratic penalization in convex programming, e_{ρ}(∂f^{n}, ∂f) is of order 1/\sqrt{r_{n}} where r_{n} is the penalty parameter (r_{n} → +∞), and that exact approximation holds true in case of linear penalty. Finally, in section 5 we show that (quasi) Fejér monotonicity jointly with well posedness leads to norm convergence of {x_{n}} to some minimizer of f.

2. Notations and definitions

First let us recall some definitions about metric variational convergence theory. Let (X, ∥.∥) be a normed linear space and (X^{⋆}, ∥.∥_{⋆}) its dual. For all subset C in X (resp. in X^{⋆}) we denote the distance from some point x in X (resp. x^{⋆} in X^{⋆}) to C by

d(x, C) := inf_{y∈C} ∥x − y∥ (resp. d_{⋆}(x^{⋆}, C))

For all ρ ≥ 0, we denote by ρB the closed ball of radius ρ. For C and D subsets of X, the Hausdorff excess of C over D is defined by e(C, D) := sup_{x∈C} d(x, D) and the ρ-Hausdorff excess of C over D by e_{ρ}(C, D) := e(C_{ρ}, D) where C_{ρ} := C∩ρB. The ρ-Hausdorff distance between C and D is defined by

haus_{ρ}(C, D) := max{e_{ρ}(C, D), e_{ρ}(D, C)}.

A sequence of extended real valued functions f^{n} epi-distance (or Attouch-Wets) converges to some function f iff for all ρ ≥ 0, haus_{ρ}(f^{n}, f) → 0, the involved functions being identified with their epigraphs in the product space X × IR endowed with the “box” norm max{∥.∥, |.|} [6]. A sequence of set valued operators A^{n} from X into X^{⋆} graph-distance converges to some operator A iff for all ρ ≥ 0, haus_{ρ}(A^{n}, A) → 0, the involved operators being identified with their graphs in the product space X × X^{⋆} endowed with the “box” norm max{∥.∥, ∥.∥_{⋆}}.

Definition 2.1. Let {f^{n}} be a sequence of extended real-valued proper closed convex functions on X. A sequence {x_{n}} in X is diagonally stationary for {f^{n}} (for short : {f^{n}} − DS) iff

lim_{n→+∞} d_{⋆}(0, ∂f^{n}(x_{n})) = 0

where ∂f^{n} denotes the subdifferential of Convex Analysis. In other words, for each n ∈ IN, there exists a subgradient x_{n}^{⋆} ∈ ∂f^{n}(x_{n}) such that x_{n}^{⋆} → 0 strongly in X^{⋆}. It is an easy consequence of the Brøndsted-Rockafellar’s theorem [12] that a {f^{n}} − DS sequence does exist if X is a Banach space and if, for all n in IN, f^{n} is bounded from below [17], [9].

3. Error estimate and finite termination

In all this section, f, f^{n}, n = 1, 2, ... are extended real-valued proper closed convex functions on X, S := Argminf and {x_{n}} is any bounded {f^{n}} − DS sequence (∥x_{n}∥ ≤ ρ for some ρ > 0), {x_{n}^{⋆}} is a sequence of subgradients associated with {x_{n}} according to definition 2.1. Let us recall the definition of conditioning.

Definition 3.1. A real extended valued function g on X is said to be conditioned if S := Argming ≠ ∅ and if ∃ψ : IR_{+} → IR_{+} ∪ {+∞}, ψ(0) = 0 such that

∀x, g(x) ≥ min g + ψ(d(x, S))

Remark 3.2. It is known [24], [11], [17] that firm conditioning (this means that, in definition 3.1, ψ has the firmness property: ∀{t_{n}} ⊂ IR_{+}, ψ(t_{n}) → 0 ⇒ t_{n} → 0) is equivalent to well posedness (see definition in proposition 5.1 below). In the following we need more than firmness.

Proposition 3.3. Let us assume that e_{ρ}(∂f^{n}, ∂f) tends to 0 as n tends to +∞ and that f is conditioned with a conditioning function ψ such that the function φ defined by

φ(t) := ψ(t)/t if t > 0, φ(0) := 0,

is finite valued, strictly increasing and continuous on [0, \overline{t}] for some \overline{t} > 0. Then (S := Argminf), for n large enough,

d(x_{n}, S) ≤ e_{ρ}(∂f^{n}, ∂f) + φ^{−1}(∥x_{n}^{⋆}∥_{⋆} + e_{ρ}(∂f^{n}, ∂f)).

Proof. First it must be noted that φ^{−1} the inverse of φ exists, is finite valued, strictly increasing and continuous on [0, φ(\overline{t})]. As ∥x_{n}^{⋆}∥_{⋆} → 0, for n large enough, ∥x_{n}^{⋆}∥_{⋆} ≤ ρ and so, from the definition of the ρ-Hausdorff excess, d((x_{n}, x_{n}^{⋆}), ∂f) ≤ e_{ρ}(∂f^{n}, ∂f). Then, from the definitions of the box norm and the distance to some subset, for all ϵ > 0, there exists x_{n}^{ϵ} and x_{n}^{ϵ⋆} such that

∥x_{n}^{ϵ} − x_{n}∥ ≤ e_{ρ}(∂f^{n}, ∂f) + ϵ, ∥x_{n}^{ϵ⋆} − x_{n}^{⋆}∥_{⋆} ≤ e_{ρ}(∂f^{n}, ∂f) + ϵ

and x_{n}^{ϵ⋆} ∈ ∂f(x_{n}^{ϵ}). So

∀x ∈ S, f(x) ≥ f(x_{n}^{ϵ}) + ⟨x_{n}^{ϵ⋆}, x − x_{n}^{ϵ}⟩

Therefore

f(x_{n}^{ϵ}) − min f ≤ ∥x_{n}^{ϵ⋆}∥_{⋆}d(x_{n}^{ϵ}, S) ≤ α_{n}^{ϵ}d(x_{n}^{ϵ}, S)

where

α_{n}^{ϵ} := ∥x_{n}^{⋆}∥_{⋆} + e_{ρ}(∂f^{n}, ∂f) + ϵ

Furthermore, from conditioning, ψ(d(x_{n}^{ϵ}, S)) ≤ f(x_{n}^{ϵ}) − min f. Then,

φ(d(x_{n}^{ϵ}, S) ≤ α_{n}^{ϵ}

For ϵ small enough and n large enough, α_{n}^{ϵ} ≤ φ(\overline{t}). Therefore, as φ^{−1} is increasing on [0, φ(\overline{t}], we get

d(x_{n}^{ϵ}, S) ≤ φ^{−1}(α_{n}^{ϵ}).

We conclude from

d(x_{n}, S) ≤ ∥x_{n} − x_{n}^{ϵ}∥ + d(x_{n}^{ϵ}, S) ≤ e_{ρ}(∂f^{n}, ∂f) + ϵ + φ^{−1}(α_{n}^{ϵ})

and passing to the limit as ϵ → 0.

Corollary 3.4. If ψ(t) = γt^{p}, γ > 0, p > 1, then

d(x_{n}, S) ≤ (1 + 1/γ′)(∥x_{n}^{⋆}∥_{⋆} + e_{ρ}(∂f^{n}, ∂f))^{\frac{1}{p−1}} , ∀n

where γ′ := γ^{\frac{1}{p−1}} .

Proof. Take \overline{t} as large as needed and

φ^{−1}(s) = \frac{s^{\frac{1}{p−1}}}{γ}

Corollary 3.5. If for all ρ > 0, for all n large enough, e_{ρ}(∂f^{n}, ∂f) = 0 (we then say that exact approximation holds true), then, for n large enough,

d(x_{n}, S) ≤ φ^{−1}(∥x_{n}^{⋆}∥_{⋆}).

Remark 3.6. The assumption of exact approximation implies that {x_{n}}_{n≥n_{0}}, for some n_{0}, is f-stationary because e_{ρ}(∂f^{n}, ∂f) = 0 is equivalent to (∂f^{n})_{ρ} ⊂ ∂f and therefore x_{n}^{⋆} ∈ ∂f(x_{n}) for n large enough.

Remark 3.7. By [6], [7], [21], for a given ρ > 0 large enough the ρ-Hausdorff distance between ∂f^{n} and ∂f can be controled by the γ-Hausdorff distance between f^{n} and f for some γ > 0 (that depends on ρ). But the first distance can be nul for n large enough whereas the second one can be different from zero for all n, as it is shown by the following example: X := IR,

f(x) := e^{x} if x ≥ 0, +∞ otherwise

f^{n}(x) := e^{x} if x ≥ 0, e^{x} − r_{n}x otherwise, with r_{n} ↑ +∞.

It is proved in [16] that if f has a linear conditioning then any f-stationary sequence finitely converges to S := Argminf (for instance this is the case for the sequence generated by the Martinet-Rockafellar’s proximal method [15]), the converse being true if X is a Banach space. The purpose of the following is to show that, under exact approximation, finite termination is preserved for any {f^{n}} − DS sequence.

Proposition 3.8. If f is linearly condioned: ψ(t) := γt for some γ > 0, then, for n large enough,

d(x_{n}, S) ≤ e_{ρ}(∂f^{n}, ∂f).

Proof. Returning to the proof of proposition 3.3 we get

γd(x_{n}^{ϵ}, S) ≤ α_{n}^{ϵ}d(x_{n}^{ϵ}, S)

Taking ϵ < γ, for n large enough we have

∥x_{n}^{⋆}∥_{⋆} + e_{ρ}(∂f^{n}, ∂f) < γ − ϵ

and then d(x_{n}^{ϵ}, S) = 0. Therefore

d(x_{n}, S) ≤ e_{ρ}(∂f^{n}, ∂f) + ϵ ∀ ϵ > 0

The finite termination result is then immediate:

Corollary 3.9. If f is linearly conditioned and if exact approximation holds true, then {x_{n}} is finitely convergent: for all n large enough x_{n} is in S.

4. Penalization in Convex Programming

In this section we give some estimate of e_{ρ}(∂f^{n}, ∂f) in case of exterior penalization in convex programming. In particular, we prove that exact approximation holds true in case of linear penalty.

X := IR^{d}, f := f_{0} + ψ_{C} with

C := {x ∈ X; f_{i}(x) ≤ 0, i = 1, ..., m}

where the f′_{i}s are convex functions from X into IR. Let us recall the definitions of linear and quadratic penalty approximations.

Linear penalty : f_{L}^{n} := f_{0} + r_{n} ∑_{i=1}^{m} f_{i}^{+}, 0 ≤ r_{n} ↑ +∞.

Quadratic penalty : f_{Q}^{n} := f_{0} + \frac{r_{n}}{2} ∑_{i=1}^{m}(f_{i}^{+})^{2}, 0 ≤ r_{n} ↑ +∞.

80 B. Lemaire / Bounded diagonally stationary sequences in convex optimization

Let us assume the Slater constraint qualification:

∃x̃ ∈ X, f_{i}(x̃) < 0 i = 1, ..., m

Lemma 4.1. For all ρ > 0 there exists γ_{ρ} > 0 such that for all x ∉ C, ∥x∥ ≤ ρ, there exists i such that

f_{i}(x) ≥ γ_{ρ} d(x, C)

Proof. Let −ϵ := max_{i} f_{i}(x̃) < 0 and let \overline{x} := λx̃ + (1 − λ)x where 0 < λ < 1, be the boundary point in C that belongs to the open segment ]x̃, x[. We have f_{i}(\overline{x}) = 0 for some i and, by convexity,

f_{i}(x) ≥ \frac{λϵ}{1 − λ} ≥ λϵ

But λ = ∥\overline{x} − x∥/∥x̃ − x∥. Therefore, as ∥\overline{x} − x∥ ≥ d(x, C), we are done with γ_{ρ} := ϵ/(∥x̃∥ + ρ).

Remark 4.2. If C is bounded, γ_{ρ} doesn’t depend on ρ (in the previous proof take γ_{ρ} := ϵ/2c where c is some norm bound of C), a result already stated in [20]. Then conditioning results on the penalty functions follow immediately. Proposition 4.3.

(i) The linear penalty function has a local linear conditioning:

∥x∥ ≤ ρ ⇒ ∑_{i=1}^{m} f_{i}^{+}(x) ≥ γ_{ρ} d(x, C).

(ii) The quadratic penalty function has a local quadratic conditioning:

∥x∥ ≤ ρ ⇒ ∑_{i=1}^{m}(f_{i}^{+}(x))^{2} ≥ γ_{ρ}^{2} d(x, C)^{2}.

From proposition 4.3 we get the following metric estimates. Theorem 4.4.

(i) For all ρ > 0, haus_{ρ}(∂f_{Q}^{n}, ∂f) = O_{ρ}(r_{n}^{− \frac{1}{2}} ). (ii) For all ρ > 0, for n large enough, haus_{ρ}(∂f_{L}^{n}, ∂f) = 0 (⇔ (∂f_{L}^{n})_{ρ} = (∂f)_{ρ}).

Proof. (i) 1. Let us prove e_{ρ}(∂f, ∂f_{Q}^{n}) = O_{ρ}(r_{n}^{− \frac{1}{2}} ). Let (x, x^{⋆}) ∈ (∂f)_{ρ}. It is easily proved that x minimizes f_{0} − ⟨x^{⋆}, .⟩ on C. So, thanks to the Slater condition, there exists a Kuhn-Tucker vector λ ∈ IR_{+}^{m} ([22], theorem 28.2):

∀z ∈ X, f_{0}(x) − ⟨x^{⋆}, x⟩ ≤ f_{0}(z) − ⟨x^{⋆}, z⟩ + ∑_{i=1}^{m} λ_{i}f_{i}(z)

that implies λ bounded (dependently on ρ):

∑_{i=1}^{m} λ_{i} ≤ [f_{0}(x̃) − min_{∥y∥≤ρ} f_{0}(y) + ρ(ρ + ∥x̃∥)]/ϵ

(where x̃ is a Slater point and −ϵ := max_{i} f_{i}(x̃) < 0) and (using the trick: 2⟨a, b⟩ = ∥a∥^{2}/α + α∥b∥^{2}, α > 0),

∀z ∈ X, f_{Q}^{n}(z) ≥ f_{0}(x) + ⟨x^{⋆}, z − x⟩ − α_{n}

viz. x^{⋆} ∈ ∂_{α_{n}}f_{Q}^{n}(x) where α_{n} := (∑_{i=1}^{m} λ_{i})/2r_{n} = O_{ρ}(r_{n}^{−1}).

Finally, thanks to Brøndsted-Rockafellar’s theorem [12], there exists (x_{n}, x_{n}^{⋆}) ∈ ∂f_{Q}^{n} such that ∥(x_{n}, x_{n}^{⋆}) − (x, x^{⋆})∥ = O_{ρ}(r_{n}^{− \frac{1}{2}} ).

2. Let us prove e_{ρ}(∂f_{Q}^{n}, ∂f) = O_{ρ}(r_{n}^{− \frac{1}{2}} ). Let (x_{n}, x_{n}^{⋆}) ∈ (∂f_{Q}^{n})_{ρ}, \overline{x}_{n} := proj _{C}x_{n} and \overline{x}_{n}^{⋆} ∈ ∂f_{0}(\overline{x}_{n}). As \{x_{n}\} is bounded (by ρ), \{\overline{x}_{n}\} and \{\overline{x}_{n}^{⋆}\} are bounded (by some constant depending on ρ). Moreover we have

∀z ∈ C, f_{0}(z) ≥ f_{0}(\overline{x}_{n}) + ⟨x_{n}^{⋆}, z − \overline{x}_{n}⟩ + ⟨x_{n}^{⋆}, \overline{x}_{n} − x_{n}⟩ + ⟨\overline{x}_{n}^{⋆}, x_{n} − \overline{x}_{n}⟩ + \frac{1}{2}r_{n}γ_{ρ}^{2}∥x_{n} − \overline{x}_{n}∥^{2}

from which we get (using again the above trick) x_{n}^{⋆} ∈ ∂_{α_{n}}f(\overline{x}_{n}) where α_{n} := \frac{∥x_{n}^{⋆} − \overline{x}_{n}^{⋆}∥^{2}}{2γ_{ρ}^{2}r_{n}} =

O_{ρ}(r_{n}^{−1}). Again apply the Brøndsted-Rockafellar’s theorem to get (x̃_{n}, x̃_{n}^{⋆}) ∈ ∂f such that ∥(x_{n}, x_{n}^{⋆}) − (x̃_{n}, x̃_{n}^{⋆})∥ = O_{ρ}(r_{n}^{− \frac{1}{2}} ).

(ii) 1. Let us prove (∂f)_{ρ} ⊂ ∂f_{L}^{n} for n large enough. Let (x, x^{⋆}) ∈ (∂f)_{ρ}. Returning to previous (i) 1. and using

∑_{i=1}^{m} λ_{i}f_{i}(z) ≤ max_{i} λ_{i} ∑_{i=1}^{m} f_{i}^{+}(z) ≤ r_{n} ∑_{i=1}^{m} f_{i}^{+}(z) ∀n large enough

we get (x, x^{⋆}) ∈ ∂f_{L}^{n}.

2. Let us prove (∂f_{L}^{n})_{ρ} ⊂ ∂f for n large enough. Let (x_{n}, x_{n}^{⋆}) ∈ (∂f_{L}^{n})_{ρ}. The main point is to show that, for n large enough, x_{n} ∈ C. Let \overline{x}_{n} := proj _{C}x_{n} and \overline{x}_{n}^{⋆} ∈ ∂f_{0}(\overline{x}_{n}). As \{x_{n}\} is bounded, so are \{\overline{x}_{n}\} and \{\overline{x}_{n}^{⋆}\}, we get

r_{n}γ_{ρ}d(x_{n}, C) ≤ r_{n} ∑_{i=1}^{m} f_{i}^{+}(x_{n}) ≤ c_{ρ}d(x_{n}, C), for some c_{ρ} > 0

Now if r_{n} > c_{ρ}/γ_{ρ} then d(x_{n}, C) = 0.

From corollary 3.4, corollary 3.9 and theorem 4.4, we get the following error estimates.

Corollary 4.5.

(i) Let {x_{n}} be a bounded {f_{Q}^{n}} − DS sequence. If f has a quadratic conditioning (cf. corollary 3.4 with p = 2) then

d(x_{n}, S) = O(∥x_{n}^{⋆}∥_{⋆} + r_{n}^{− \frac{1}{2}} ).

(ii) Let {x_{n}} be a bounded {f_{L}^{n}} − DS sequence. If f has a linear conditioning then {x_{n}} is finitely convergent to S.

Remark 4.6. As the extended real valued function associated with the linear programming problem is linearly conditioned ([20], [16]), from corollary 4.5 (ii), we recover the finite termination property of the linear penalty-prox method for linear programming [8]. Moreover, in this case the Slater condition is no more needed because the linear penalty function being polyhedral condition i) in proposition 4.3 is (even globally) fulfilled.

5. Fejér monotonicity and norm convergence

5.1. Quasi Fejér monotonicity

As noted in [10], the notion of Fejér monotonicity goes back at least to [18]. Here we relax this notion in the following definition (cf. [13] for a slightly more general extension).

Definition 5.1. Let (X, d) be a metric space and S be a non empty subset in X. A sequence {x_{n}} in X is quasi Fejér monotone with respect to S (in short S-QFM) iff there exists a sequence of non negative reals {ϵ_{n}} such that ∑_{n=1}^{+∞} ϵ_{n} < +∞ and

∀x ∈ S, d(x_{n}, x) ≤ d(x_{n−1}, x) + ϵ_{n}, n = 1, 2, ...

Remark 5.2. Fejér monotonicity refers to the case where ϵ_{n} = 0 for all n. A typical example is then given by the iterations of a non expansive mapping with non empty fixed points set S. The notion of quasi Fejér monotonicity is motivated by the following result.

Theorem 5.3. Let us assume X to be complete and S to be closed. For all S-QFM sequence {x_{n}}, if d(x_{n}, S) → 0 then there exists x_{∞} ∈ S such that x_{n} → x_{∞} (of course the converse being always true) with the estimate

d(x_{n}, x_{∞}) ≤ 2 d(x_{n}, S) + ∑_{k=n+1}^{+∞} ϵ_{k}, ∀n ∈ IN.

Proof. First let us show that {x_{n}} is a Cauchy sequence. Let m > n.

∀x ∈ S, d(x_{m}, x_{n}) ≤ d(x_{m}, x) + d(x, x_{n}) ≤ 2d(x_{n}, x) + ∑_{k=n+1}^{m} ϵ_{k}

or d(x_{m}, x_{n}) ≤ 2d(x_{n}, S) + ∑_{k=n+1}^{m} ϵ_{k} that tends to 0 as m and n tend to +∞.

Therefore x_{n} tends to some x_{∞} and, thanks to the continuity of the function d(., S) we have d(x_{∞}, S) = 0 and, as S is closed, x_{∞} ∈ S. Finally let m tend to +∞ in the above estimate.

Remark 5.4. Generally, if S is a non empty closed subset in X and if some sequence {x_{n}} is compact then d(x_{n}, S) → 0 is equivalent to: any accumulation point of {x_{n}} is in S. If X is a reflexive Banach space, f, f^{n}, n = 1, 2, ... are extended real-valued proper closed convex functions on X such that f^{n} Mosco-converges to f and if {x_{n}} is a bounded {f^{n}} − DS sequence then f^{n}(x_{n}) → inf f and any weak accumulation point of {x_{n}} is a minimizer of f ( [9], Proposition 4.3). Furthermore if X is a Hilbert space and {x_{n}} is Argminf − QF M a classical argument (for instance used in the convergence proof of the proximal method) shows that the whole sequence {x_{n}} weakly converges to some minimizer of f. In the finite dimensional setting theorem 5.3 furnishes an alternative argument of this fact since, in this setting, saying that any accumulation point of a bounded sequence is in S is equivalent to saying that d(x_{n}, S) → 0.

5.2. Connection with well posedness and diagonal stationarity

As an immediate consequence of theorem 5.3 we get the following proposition.

Proposition 5.5. Let f be an extended real-valued proper closed function on the complete metric space X. Let us assume f to be well-posed: S := Argminf is non empty and

f(x_{n}) → inf f ⇒ d(x_{n}, S) → 0.

Then any S-QFM f-minimizing sequence converges to some minimizer of f.

Example 5.6. Approximate prox. Let X be a real Hilbert space and f an extended real-valued proper closed convex function on X such that S := Argminf ≠ ∅. Let {λ_{n}} and {ϵ_{n}} be sequences of positive reals such that

λ_{n} ≥ \underline{λ} > 0, ∑_{n=1}^{+∞} \sqrt{λ_{n}ϵ_{n}} < +∞

x_{0} be given in X, the Auslender’s approximate prox method [2] generates a sequence {x_{n}} such that

x_{n} ∈ ϵ_{n} − Argmin\{\frac{1}{2λ_{n}} ∥. − x_{n−1}∥^{2} + f\}, n = 1, 2, ...

It is known [2] that such a sequence satisfies

∥x_{n} − prox_{λ_{n}f} x_{n−1}∥ ≤ \sqrt{2λ_{n}ϵ_{n}}, n = 1, 2, ...

viz. {x_{n}} is generated by the Rockafellar’s approximate prox method [23]. Therefore, it is a direct consequence of the non expansiveness of the prox mapping and because the set of fixed points of this prox mapping is S, that {x_{n}} is S − QF M. Moreover [15] {x_{n}} is minimizing (and this does not depend neither of the non vacuity of S nor of the finiteness of inf_{X} f). It is well known that the sequence generated by the Rockafellar’s approximate prox method is weakly convergent to some minimizer of f. Actually, if f is well posed, proposition 5.5 shows that, in the Auslender’s approximate (and a fortiori in the exact) prox method, the convergence holds true for the norm topology.

Proposition 5.7. Let X be a real Banach space and f, f^{n}, n = 1, 2, ... be extended real-valued proper closed convex functions on X. We assume that f is well posed and that ∂f^{n} graph-distance converges to ∂f. Then any S-QFM (where S := Argminf) {f^{n}} − DS sequence {x_{n}} is norm convergent to some minimizer of f.

Proof. As a S − QF M sequence, {x_{n}} is bounded. Then, as ∂f^{n} graph-distance converges to ∂f, ∃\{\overline{x}_{n}\} stationary for f such that ∥x_{n} − \overline{x}_{n}∥ → 0. Moreover, f well posed is equivalent to f has a well asymptotical behaviour in solution (for any f-stationary sequence \{z_{n}\}, d(z_{n}, S) tends to 0) [17]. Therefore d(\overline{x}_{n}, S) → 0. Finally apply theorem 5.3.

Remark 5.8. We recall that in a Banach space the graph-distance convergence of ∂f^{n} to ∂f is implied by the epi-distance convergence of f^{n} to f [4], [21], [7].

Example 5.9. Diagonal prox.

Let X and f be as in the previous example and 0 < \underline{λ} ≤ λ_{n} ≤ \overline{λ} < +∞. Let \{f^{n}\} be a sequence of extended real-valued proper closed convex functions on X such that

∀ρ > 0, ∑_{n=1}^{+∞} haus_{ρ}(∂f^{n}, ∂f) < +∞

x_{0} be given in X we consider the sequence {x_{n}} generated by the diagonal prox method [14], [1]:

x_{n} := prox_{λ_{n}f^{n}} x_{n−1} := argmin\{\frac{1}{2λ_{n}} ∥. − x_{n−1}∥^{2} + f^{n}\}, n = 1, 2, ...

Lemma 5.10.

∃ρ > 0, ∥x_{n} − prox_{λ_{n}f} x_{n−1}∥ ≤ (2 + \overline{λ}) haus_{ρ}(∂f^{n}, ∂f)

Proof. Following [19], let us consider the Yosida semi distance between maximal monotone operators [5]

∀ρ ≥ 0, ∀λ > 0, d_{λ,ρ}(A, B) := sup_{∥x∥≤ρ} ∥J_{λ}^{A} − J_{λ}^{B}∥

where J_{λ}^{A} denotes the resolvant of A with parameter λ (recall that prox_{λf} is nothing but

J_{λ}^{∂f}). A direct application of [6] (theorem 5.1) or [3] (proposition 1.2) gives the following estimate.

∀ρ ≥ 0 ∃ρ′ > 0 d_{λ_{n},ρ}(∂f^{n}, ∂f) ≤ (2 + \overline{λ}) haus_{ρ′}(∂f^{n}, ∂f)

From the non expansiveness of the prox mapping we get easily

∀x ∈ S, ∥x_{n} − x∥ ≤ ∥x_{n−1} − x∥ + d_{λ_{n},∥x∥}(∂f^{n}, ∂f)

that combined with the above estimate shows that {x_{n}} is bounded (∥x_{n}∥ ≤ ρ). Then the result comes from the immediate estimate

∥x_{n} − prox_{λ_{n}f}x_{n−1}∥ ≤ d_{λ_{n},ρ}(∂f^{n}, ∂f)

As in the previous example {x_{n}} is generated by the Rockafellar’s approximate prox

method and so is S − QF M and, [23], ∥x_{n} − x_{n−1}∥ → 0. Moreover, as \frac{x_{n} − x_{n−1}}{λ_{n}} ∈

∂f^{n}(x_{n}), {x_{n}} is {f^{n}} − DS. If f is well posed, proposition 5.7 shows that, still here, the convergence is strong. Taking f^{n} = f for all n, we again recover (cf. sub-section 6.1) the strong convergence for the (exact) prox method.

Acknowledgment.The author would like to thank an anonymous referee for his valuable remarks and suggestions.

References

[1] P. Alart, B. Lemaire: Penalization in non-classical convex programming via variational convergence, Math. Progr. 51, 1991, 307–331.

[2] A. Auslender: Numerical methods for non-differentiable convex optimization, in Math. Progr. Studies, 30, 1985

[3] H. Attouch, A. Moudafi, H. Riahi: Quantitative stability analysis for maximal monotone operators and semi-groups of contractions, Séminaire d’Analyse Convexe de Montpellier, Vol. 21, 1991.

[4] H. Attouch, J.L. Ndoutoumé, M. Théra: Epigraphical convergence of functions and convergence of their derivatives in Banach spaces, Séminaire d’Analyse Convexe de Montpellier, Vol. 20, exposé n^{∘} 9, 1990.

[5] H. Attouch, R. Wets: Isometries for the Legendre-Fenchel transform, Trans. A.M.S., Vol. 296, 1986, 33–60.

[6] H. Attouch, R. Wets: Quantitative stability of variational systems: I. The epigraphical distance, Trans. A.M.S., Vol. 328, 1991, 695-729.

[7] D. Azé, J.P. Penot: Recent quantitative results about the convergence of set and functions, Functional Analysis and Approximation, P.L. Papini ed., Pitagora Editrice, Bologna, 1989, 90-110.

[8] A. Auslender, J.P. Crouzeix, P. Fedit: Penalty proximal methods in convex programming, Journal of Optimization Theory and Applications, Vol. 55, 1, 1987, 1-21.

[9] M.A. Bahraoui, B. Lemaire: Convergence of diagonally stationary sequences in Convex Optimization, Set-Valued Analysis 2, 1994, 1–13

[10] H.H. Bauschke, J.M. Borwein: On the convergence of Von Neumann’s Alternating Projection Algorithm for Two Sets, CORR 92–37, Faculty of Mathematics University of Waterloo, nov. 1992.

[11] E. Bednarczuk, J.P. Penot: Metrically well-set minimization problems, Applied Mathematics and Optimization, 26: 273–285, Springer-Verlag, 1992.

[12] A. Brøndsted, R.T. Rockafellar: On the subdifferentiability of convex functions, Proc. Amer. Math. Soc. 16, 1965, 605–611.

[13] A.N. Iusemi, B.F. Svaiter, M. Teboulle: Entropy-like proximal methods in convex programming, Research Report 92–09, Mathematics University of Maryland, May 1992.

[14] B. Lemaire: Coupling optimization methods and variational convergence, in Trends in Mathematical Optimization, International Series of Numerical Mathematics, Vol 84(c), Birkhäuser Verlag, 1988, 163–179.

[15] B. Lemaire: About the convergence of the proximal method, Advances in Optimization, Proceedings Lambrecht 1991, Lecture Notes in Economics and Mathematical Systems 382, Springer-Verlag, 1992, 39–51.

[16] B. Lemaire: Bons comportements et conditionnement linéaire, Journées d’Optimisation et Analyse Non-Linéaire, Avignon, nov. 1991.

[17] B. Lemaire: Bonne position, conditionnement, et bon comportement asymptotique, Séminaire d’Analyse Convexe de Montpellier, exposé n^{0}5, 1992.

[18] T.S. Motzkin, I.J. Schoenberg: The relaxation method for linear inequalities, Canadian Journal of Mathematics, 6: 393–404, 1954.

[19] A. Moudafi: Coupling proximal methods and variational convergence, to appear in Zeit. Operation Research.

[20] B.T. Polyak: Sharp minimum, International Workshop on Augmented Lagragians, Vienna, 1979.

[21] H. Riahi: Quelques résultats de stabilité en analyse épigraphique : approche topologique et quantitative, Thèse Université Montpellier 2, 1989.

[22] R.T. Rockafellar: Convex Analysis, Princeton University Press, 1970.

[23] R.T. Rockafellar: Monotone Operators and the proximal point algorithm, SIAM J. Control and Optimisation, 1976, 877–898.

[24] T. Zolezzi: On Equiwellset Minimum Problems, Appl. Math. Optim. 4, 1978, 209–223.