Journal of Convex Analysis Volume 3 (1996), No.1, 63–70

An Asymptotical Variational Principle Associated with the Steepest Descent Method for a Convex Function

B. Lemaire

Université Montpellier II, Place E. Bataillon, 34095 Montpellier Cedex 5, France. e-mail:lemaire@math.univ-montp2.fr

Received July 5, 1994 Revised manuscript received January 22, 1996

Dedicated to R. T. Rockafellar on his 60th Birthday

The asymptotical limit of the trajectory defined by the continuous steepest descent method for a proper closed convex function f on a Hilbert space is characterized in the set of minimizers of f via an asymptotical variational principle of Brezis-Ekeland type. The implicit discrete analogue (prox method) is also considered.

Keywords : Asymptotical, convex minimization, differential inclusion, prox method, steepest descent, variational principle.

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

1. Introduction

Let X be a real Hilbert space endowed with inner product ⟨., .⟩ and associated norm ∥.∥, and let f be a proper closed convex function on X. The paper considers the problem of minimizing f, that is, of finding inf_{X} f and some element in the optimal set S := Argmin f, this set assumed being non empty. Letting ∂f denote the subdifferential operator associated with f, we focus on the continuous steepest descent method associated with f, i.e., the differential inclusion

−\frac{du}{dt} ∈ ∂f(u), t > 0

with initial condition

u(0) = u_{0}.

This method is known to yield convergence under broad conditions summarized in the following theorem. Let us denote by A the real vector space of continuous functions from [0, +∞[ into X that are absolutely continuous on [δ, +∞[ for all δ > 0.

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

64 B. Lemaire / An asymptotical variational principle

Theorem 1.1.

(i) ([2]) For all u_{0} in cl dom f, the closure of the effective domain of f, there exists a

unique u in A such that:

∀t > 0, u(t) belongs to the domain of ∂f;

he differential inclusion is verified for a.e. t > 0 (recall that u is strongly derivable for a.e. t > 0);

∀δ > 0, u is Lipschitz continuous on [δ, +∞[ i.e. u′(:= \frac{du}{dt}) ∈ L^{∞}([δ, +∞[; X); f ∘ u is convex, non increasing, Lipschitz continuous on [δ, +∞[ ∀δ > 0; u has a derivative to the right for all t > 0 and, if S := Argmin f is non empty,

then lim_{t→+∞} ∥\frac{du}{dt}^{+}(t)∥ = 0.

(ii) ([5]) If S ≠ ∅ then the weak limit u_{∞} := w − lim_{t→+∞} u(t) exists and belongs to S, this asymptotic convergence being true for the norm topology if f is even ([5]) or if Int S ≠ ∅ ([2]).

Assuming henceforth that the optimal set S is non empty, Theorem 1.1 motivates us to consider the following problem:

For a given u_{0} ∈ cl dom f, characterize the asymptotic limit u_{∞} as the unique solution to some convex optimization problem with feasible set S.

This task amounts to show that, like regularization procedures à la Tikhonov ([15], [7], [1]), the steepest descent method enables us to select a particular optimal solution respectively to some auxiliary criterium. As we shall see, unlike regularization procedures, this auxiliary criterium is not at our disposal independently from the data f but is defined from this data. Indeed, the result is based upon a variational principle of Brezis-Ekeland type for an infinite horizon. An analogue holds true for the Euler’s implicit discretization of the differential inclusion i.e. the proximal method of Martinet-Rockafellar.

The paper is organized as follows. Before reaching the main objective stated above, we show in section 2, that the trajectory u is always (even S is empty) minimizing and, if S is non empty, we give a localization result of u_{∞} in S with respect to u_{0}. Section 3 is devoted to the variational principle for an infinite horizon. In section 4 we state the asymptotic variational principle characterizing u_{∞} in S. The analogue for the discrete case is discussed in section 5.

In sections 2, 3, 4, u always denotes the solution mentioned in Theorem 1.1.

2. Localization of u_{∞}

First let us recall an estimate.

Proposition 2.1. [9]

∀x ∈ X, ∀t > 0, \frac{∥u(t) − x∥^{2}}{2t} + f(u(t)) ≤ f(x) + \frac{∥u_{0} − x∥^{2}}{2t}

Proof. By definition of the subdifferential we have

∀x ∈ X, for a.e. s > 0, f(x) ≥ f(u(s)) − ⟨u′(s), x − u(s)⟩

Then, integrating between δ and t with 0 < δ < t, and thanks to the non increasingness of f(u(.)) and the absolute continuity of u on [δ, +∞[, we get

(t − δ)f(x) ≥ (t − δ)f(u(t)) + (∥u(t) − x∥^{2} − ∥u(δ) − x∥^{2})/2

Finally, since u is continuous at 0 we get the result.

Corollary 2.2.

(i) In all cases, that is, whether inf_{X} f be finite or not, achieved or not, lim_{t→+∞} f(u(t)) = inf_{X} f.

(ii) If S ≠ ∅, then ∥u_{∞} − proj_{S}u_{0}∥ ≤ d(u_{0}, S) and therefore, ∥u_{∞} − u_{0}∥ ≤ 2d(u_{0}, S),

where proj_{S} denotes the projection operator onto the closed convex set S. (iii) If S is an affine subspace then u_{∞} = proj_{S}u_{0}.

Proof. (i) Trivial. (ii) Taking x ∈ S in the estimate we get ∥u(t) − x∥ ≤ ∥u_{0} − x∥. Passing to the lim inf as t → +∞, thanks to the weak lower semi-continuity of the norm, and taking as x the projection of u_{0} onto S, we get the result. (iii) Let e := u_{∞} − proj_{S}u_{0} and assume e ≠ 0. As S is an affine subspace, x := proj_{S}u_{0} − td(u_{0}, S)e/∥e∥ is in S for all t ≥ 0. We have ∥u_{∞} − x∥ = td(u_{0}, S) + ∥e∥ and, thanks to Pythagore, ∥u_{0} − x∥ = \sqrt{t^{2} + 1}d(u_{0}, S). Therefore, ∥u_{0} − x∥ − ∥u_{∞} − x∥ = (\sqrt{t^{2} + 1} − t)d(u_{0}, S) − ∥e∥. Referring to the proof of (ii) above we get ∥e∥ ≤ (\sqrt{t^{2} + 1} − t)d(u_{0}, S) for all t ≥ 0, which is a contradiction.

Remark 2.3. (iii) in corollary 2.2 gives a complete and simple characterization of u_{∞} in S, actually the same than the Tikhonov regularization method. This characterization has yet been obtained in [4] for the discrete method (cf. section 5 below) when f is a quadratic form (a case where S is a subspace). Unfortunately this simple characterization fails to be true in general.

3. Variational principle, infinite horizon

First, let T > 0 be fixed. We denote by L_{sc}^{1}(0, T) the set of functions ψ from [0, T] into IR that belong to L^{1}(δ, T) for all δ, 0 < δ < T, and such that ∫_{0}^{T} ψ(t)dt := lim_{δ→0} ∫_{δ}^{T} ψ(t)dt exists in IR. We define the set of feasible trajectories which reach some v_{∞} ∈ X from u_{0}, possibly using infinite time, arriving asymptotically with nul velocity:

K(u_{0}) := {v ∈ A; f ∘ v + f^{∗} ∘ (−v′) ∈ L_{sc}^{1}(0, T) ∀T > 0,

v(0) = u_{0}, v_{∞} := w − lim_{t→+∞} v(t) exists, s − ess − lim_{t→+∞} v′(t) = 0},

where w is short notation for weak, s is for strong, ess is for essential, and the ∗ denotes the Fenchel conjugacy. We note that, if v is in K(u_{0}) then v(t) is in dom f for all t > 0 and −v′(t) is in dom f^{∗} for a.e. t > 0.

Proposition 3.1. K(u_{0}) is a convex subset of A containing u.

Proof. Convexity is easy. For the second assertion, integrating the equality

f(u(t)) + f^{∗}(−u′(t)) = −⟨u′(t), u(t)⟩ for a.e. t > 0

between δ and T for δ > 0 and passing to the limit as δ tends to 0, we get

∫_{0}^{T} [f(u(t)) + f^{∗}(−u′(t))]dt = \frac{1}{2}(∥u_{0}∥^{2} − ∥u(T)∥^{2})

The last condition is fulfilled since (cf. Theorem 1.1) lim_{t→+∞} ∥\frac{du}{dt}^{+}(t)∥ = 0.

Motivated by Proposition 3.1 we define the cost function for the finite horizon T, J_{T} : K(u_{0}) → IR by

J_{T} (v) := ∫_{0}^{T} [f(v(t)) + f^{∗}(−v′(t)) + ⟨v′(t), v(t)⟩]dt

= ∫_{0}^{T} [f(v(t)) + f^{∗}(−v′(t))]dt + \frac{1}{2}(∥v(T)∥^{2} − ∥u_{0}∥^{2})

As u_{0} is fixed, we note that J_{T} is convex. Moreover, via Fenchel’s inequality we have J_{T} ≥ 0.

Remark 3.2. According to Moreau’s theory for elastoplastic systems [11,12,13], J_{T} (v) can be interpreted as the total energy of such a system in the time interval [0, T] if it moves with the velocity v. Indeed, f is then the support function of some closed convex subset C containing the origin (therefore Argmin f is the normal cone to C at 0), f(v(t)) is the dissipated power and ⟨v′(t), v(t)⟩ is the kinetic power.

Now let us define the (convex) cost function for an infinite horizon J : K(u_{0}) → IR_{+} ∪ {+∞} by

J(v) := lim_{T →+∞} J_{T} (v) = sup_{T >0} J_{T} (v)

Theorem 3.3. (Variational principle, variant of [3]). u is the unique minimizer of J on K(u_{0}) and the minimum value is nul.

Proof. Clearly J(u) = 0 and J(v) = 0 if and only if J_{T} (v) = 0 for all T > 0 i.e. v satisfies the differential inclusion on [0, T] for all T > 0 i.e. v = u.

The following result will be of importance in section 5.

Proposition 3.4.

∀v ∈ K(u_{0}), J(v) ≥ \frac{1}{2}∥v_{∞} − u_{∞}∥^{2}.

Proof. From the definition of a subgradient and as −u′ ∈ ∂f(u) ⇔ u ∈ ∂f^{∗}(−u′), we have

f(v) − f(u) + f^{∗}(−v′) − f^{∗}(−u′) ≥ −⟨u′, v − u⟩ + ⟨u, u′ − v′⟩

Therefore, adding ⟨v′, v⟩ − ⟨u′, u⟩ to both sides, we obtain

∀T > 0, J_{T} (v) = J_{T} (v) − J_{T} (u) ≥ lim_{δ→0} ∫_{δ}^{T} ⟨v′ − u′, v − u⟩dt = \frac{1}{2}∥v(T) − u(T)∥^{2}

Then use the weak lower semi-continuity of the norm as T → +∞.

We end this section by studying some properties of the cost function J that make the optimization problem involved in theorem 3.3 non trivial in the sense that J is finite not only at u.

Proposition 3.5.

(i) For all v ∈ K(u_{0}) such that v_{∞} ∉ Argmin f then J(v) = +∞. (ii) If f is coercive then for all x ∈ Argmin f there exists v in K(u_{0}) such that v_{∞} = x

and J(v) < +∞.

Proof. (i) By (weak and strong) lower semi-continuity of f and f^{∗}, we get

lim inf_{t→+∞}[f(v(t)) + f^{∗}(−v′(t)) + ⟨v′(t), v(t)⟩] ≥ f(v_{∞}) + f^{∗}(0) > 0

where the last inequality follows from 0 ∉ ∂f(v_{∞}). Evidently, this inequality implies J(v) = +∞. (ii) Let 0 < δ < τ. For x ∈ X, let us define the function v from [0, +∞[ into X by

v(t) := \{ \begin{matrix}u(t) & 0 ≤ t ≤ δ \\ u(δ) + (t − δ)\frac{x − u(δ)}{τ − δ} & δ ≤ t ≤ τ \\ x & τ ≤ t \end{matrix}

Clearly v is in A, v_{∞} = v(τ) = x and v′(t) = 0 for all t > τ. Since x is in dom f then v(t) is in dom f for all t > 0. Since f is weakly inf-compact i.e. f^{∗} is strongly continuous at 0, if τ is large enough then −v′(t) is in dom f^{∗} for a.e. t > 0. Finally, because f(x) + f^{∗}(0) = 0 and f ∘ v is integrable on [δ, τ], we have

∀ T ≥ τ, J(v) = J_{T} (v) = J_{τ}(v) = ∫_{δ}^{τ} f(v(t))dt + (τ − δ)f^{∗}(\frac{u(δ) − x}{τ − δ})

+\frac{1}{2}(∥x∥^{2} − ∥u(δ)∥^{2}) < +∞,

taking into account that J_{δ}(v) = J_{δ}(u) = 0.

4. Asymptotical variational principle

Let us define the asymptotic cost function φ_{u_{0}} : X → IR_{+} ∪ {+∞} by

φ_{u_{0}}(x) := inf{J(v); v ∈ K(u_{0}), v_{∞} = x}

Proposition 4.1. φ_{u_{0}} is convex; φ_{u_{0}}(u_{∞}) = J(u) = 0;

∀x ∈ X, φ_{u_{0}}(x) ≥ \frac{1}{2}∥x − u_{∞}∥^{2}.

Proof. Let x^{1}, x^{2} ∈ X, θ ∈ [0, 1] and v^{i} ∈ K(u_{0}) such that v_{∞}^{i} = x^{i}, i = 1, 2. As K(u_{0}) is convex, v^{θ} := θv^{1} + (1 − θ)v^{2} ∈ K(u_{0}). Moreover v_{∞}^{θ} = x^{θ} := θx^{1} + (1 − θ)x^{2}. Then

φ_{u_{0}}(x^{θ}) ≤ J(v^{θ}) ≤ θJ(v^{1}) + (1 − θ)J(v^{2})

As this holds for all v^{i} ∈ K(u_{0}) such that v_{∞}^{i} = x^{i}, we are done for the first statement. The second statement is immediate, the third one comes directly from proposition 3.4.

Now, as a direct consequence of proposition 4.1, we can state the announced asymptotic variational principle.

Theorem 4.2. u_{∞} is the unique minimizer of φ_{u_{0}} on Argmin f (or on X) and the minimum value is zero.

Finally, in order that the optimization problem involved in theorem 4.2 be non trivial, refereing to proposition 3.5, we get

Proposition 4.3. If f is coercive then dom φ_{u_{0}} = Argmin f.

5. Discrete case

For the same convex function f there is an intimate relationship between the continuous steepest descent method and its Euler’s implicit discrete version, i.e., the proximal method of Martinet-Rockafellar [14], [8]. Thanks to this connexion, the proximal method inherits many of the nice asymptotical properties of the continuous steepest descent method [9]. For the problem under consideration here, concerning characterization of the asymptotical limit, a similar discussion for the proximal method is entirely parallel to the one above. The statements are the same, albeit now “time” is discrete. More precisely, let X and f be as in section 1 and {λ_{k}} be a sequence of positive reals. Let u_{0} ∈ X be given. The proximal method [14] generates a sequence u = {u_{k}} ∈ X, u_{k} being the unique solution of the iterative scheme

\frac{u_{k−1} − u_{k}}{λ_{k}} ∈ ∂f(u_{k}) ∀ k ≥ 1.

Thus this method coincides with the Euler’s implicit discretization of the differential inclusion arising in the continuous steepest descent (section 1). So, for all n ∈ IN, u_{n} approximates the continuous steepest descent trajectory at the point t_{n} := ∑_{1}^{n} λ_{k}. Let us recall some basic known results about the asymptotic behaviour.

Proposition 5.1. [14] If λ_{k} is bounded away from 0 and Argmin f ≠ ∅ then u_{k} weakly converges to u_{∞} some minimizer of f.

Note that here the asymptotic limit u_{∞} may be different from that one of the continuous case (for the same u_{0}).

Remark 5.2. In proposition 5.1, the convergence holds true for the norm topology if f is even [4] or if Int Argmin f ≠ ∅ [9] or if f is well-posed [10].

Proposition 2.1 holds true replacing u(t) by u_{n} and t by t_{n} := ∑_{1}^{n} λ_{k} ([6]), implying lim_{n→+∞} f(u_{n}) = inf_{X} f and the same localization results as in corollary 2.2.

Now, all statements in sections 3 and 4 still hold replacing A by X^{IN} and with the following new definitions.

Set of discrete feasible trajectories from u_{0}:

K(u_{0}) := {v = (v_{0}, v_{1}, ⋯); ∀ k ≥ 1
v_{k} ∈ dom f,

−d_{k} := \frac{v_{k−1} − v_{k}}{λ_{k}} ∈ dom f^{∗},

v_{0} := u_{0}, v_{k} ⇀^{w} v_{∞}, ∥d_{k}∥ → 0 }

Cost function for a finite horizon:

J_{n}(v) := ∑_{k=1}^{n} λ_{k}[f(v_{k}) + f^{∗}(−d_{k}) + ⟨v_{k}, d_{k}⟩]

= ∑_{k=1}^{n} λ_{k}[f(v_{k}) + f^{∗}(−d_{k}) + \frac{1}{2}λ_{k}∥d_{k}∥^{2}]

+\frac{1}{2}(∥v_{n}∥^{2} − ∥u_{0}∥^{2})

Cost function for an infinite horizon:

J(v) := lim_{n→+∞} J_{n}(v) = sup_{n} J_{n}(v)

Asymptotic cost function: exactly the same as in section 4.

The adaptation of proofs is left out as a simple exercise. The crucial trick is

2⟨u_{k−1} − u_{k}, x − u_{k}⟩ = ∥u_{k−1} − u_{k}∥^{2} + ∥x − u_{k}∥^{2} − ∥x − u_{k−1}∥^{2}

For the proof of the analogue of proposition 3.5 (ii), define v ∈ K(u_{0}) by:

v_{k} := \{ \begin{matrix}u_{k} & 0 ≤ k ≤ 1 \\ u_{1} + (t_{k} − t_{1})\frac{x − u_{1}}{t_{N} − t_{1}} & 1 < k ≤ N \\ x & k > N \end{matrix}

where N > 1 large enough in order that, for 1 < k ≤ N, −d_{k} = \frac{u_{1}−x}{t_{N} −t_{1}} be in dom f^{∗} since lim_{n→+∞} t_{n} = +∞.

Acknowledgment. The author would like to thank the referees for their valuable remarks and suggestions for improving the presentation.

70 B. Lemaire / An asymptotical variational principle

References

[1] H. Attouch: Viscosity methods. Application to Mechanics and Mathematical Programming, Working paper Université Montpellier II Mathématiques, 1993.

[2] H. Brezis: Opérateurs maximaux monotones, Lecture Note no. 5, North-Holland, 1973.

[3] H. Brezis, I. Ekeland: Un principe variationnel associé à certaines équations paraboliques. Le cas indépendant du temps, C.R. Acad. Sc. Paris, t. 282 (3 mai 1976) Série A, 971–974.

[4] H. Brezis, P.L. Lions: Produits infinis de résolvantes, Israël Journal of Mathematics, Vol 29, no. 4, 1978.

[5] R.E Bruck: Asymptotic Convergence of Nonlinear Contration Semigroups in Hilbert Space, Journal of Functional Analysis 18 (1975) 15–26.

[6] O. Güler: On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control and Optimization, Vol 29, no. 2 (1991) 403–419.

[7] B. Lemaire: Régularisation et pénalisation en optimisation convexe, Séminaire d’Analyse Convexe, Institut de Mathématiques USTL, exposé no. 21, 1971.

[8] B. Lemaire: The proximal algorithm, in New Methods in Optimization and their Industrial Uses, Proc. Symp. Pau and Paris 1987, Int. Ser. Numer. Math., Vol 87, Birkhäuser Verlag (1989) 73–89.

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

[10] B. Lemaire: Bounded Diagonally Stationary Sequences in Convex Optimization, Journal of Convex Analysis, Heldermann Verlag Berlin, 1 (1994) 75–86.

[11] J.J Moreau: Sur les lois de frottement, de plasticité et de viscosité, C.R. Acad. Sci. Paris, Sér. A, 271 (1970) 608–611.

[12] J.J Moreau: Sur l’évolution d’un système élasto-visco-plastique, C.R. Acad. Sci. Paris, Sér. A, 273 (1971) 118–121.

[13] J.J Moreau: Application of Convex Analysis to the treatment of elastoplastic systems, in Proceedings Symposium IUTAM/IMU, edited by P.Germain & B.Nayroles, Lecture Notes in Mathematics, vol. 503, Springer-Verlag (1976) 56–89.

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

[15] A. Tikhonov, V. Arsenine: Méthodes de résolution de problèmes mal posés, M.I.R, 1974.