Journal of Convex Analysis Volume 3 (1996), No. 2, 255–268

More Than First-Order Developments of Convex Functions: Primal-Dual Relations

C. Lemaréchal, C. Sagastizábal

INRIA, BP 105, 78153 Le Chesnay, France. e-mail: Claude.Lemarechal@inria.fr, Claudia.Sagastizabal@inria.fr

Received May 2, 1995 Revised manuscript received November 3, 1995

The subject of this paper concerns the remainder term in the first-order development of a (finite-valued) convex function. We study functions for which this term is comparable to a squared norm and we relate it to the corresponding remainder term of the conjugate function. We show that a convex function satisfies a quadratic growth condition if and only if its subdifferential satisfies a linear growth condition. Finally, we define a new concept of “tangential regularization”, involving a local decomposition of IR^{N}, along the subspace where the function is “smooth” and the subspace parallel to the subdifferential.

Keywords : Conjugate functions, first-order developments, regularization, growth conditions.

1991 Mathematics Subject Classification: 26B05, 52A41.

1. Introduction

The very first motivation of this paper is to study second-order properties of convex functions. More precisely, we want to relate the second-order elements of a convex function φ with those of its Moreau-Yosida regularization

Φ(x) := min_{y∈IR^{n}} \{φ(y) + \frac{1}{2}∥y − x∥^{2}\} ;

this is done in the companion paper [5]. A key property of such a regularization is the dual relation Φ^{∗} = φ^{∗} + 1/2∥ · ∥^{2}, which shows that Φ^{∗} and φ^{∗} share identical smoothness properties. This observation strongly motivates the following question: how are related the second-order elements of a convex function with those of its conjugate? It is precisely this last question that we investigate here. The answer is easy in the quadratic case: the Hessians of two mutually conjugate quadratic functions are inverse to each other, a result which has been generalized in [1] to the C^{2} case. What we need now is a more general study, in which no first-order differentiability is assumed. This does make sense: for example, the univariate function φ(ξ) := |ξ| + 1/2ξ^{2} is not C^{1} but its conjugate is C^{2}. A close look at this example confirms the intuition given by the C^{2} case: nonsmoothness of a function comes together with an affine behaviour of its conjugate.

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

256 C. Lemaréchal, C. Sagastizábal / More than first-order developments

The present paper gives a number of results related with the above question. They have an interest in their own right, and are exploited in [5], entirely devoted to a study of the Moreau-Yosida regularization and its Hessian. In Section 2, we start with some elementary properties of convex sets and normal cones, which will be instrumental for the sequel. The main content of the paper is then Section 3, which relates the remainder terms in the first-order developments of two mutually conjugate functions. Finally, Section 4 introduces a useful operation, which consists in “strong-convexifying” affine parts of a function, thereby regularizing its conjugate. We use standard notation; the working space is IR^{N}, in which the scalar product is ⟨·, ·⟩ and ∥ · ∥ is the associated norm. Our study considers finite-valued convex functions φ only. A function denoted by an upper-case letter (Φ) will be some regularized form of the corresponding lower-cased function (φ). Throughout this paper we will consider a particular subgradient g_{0} ∈ ∂φ(z_{0}) at a particular z_{0} ∈ IR^{N}; in general, N and T will denote the normal and tangent cones N_{∂φ(z_{0})}(g_{0}) and T_{∂φ(z_{0})}(g_{0}). We will use I, σ,_{∨}^{+} to denote the indicator and support functions and the infimal convolution respectively.

2. On the geometry of convex sets

The material in this section is quite elementary and departs from the general flow of the paper. It can therefore be skipped during a first reading. In the following results we characterize those convex cones that are subspaces. For the subspace M in Proposition 2.1, see Theorem 2.7 in [7].

Proposition 2.1. Let N be a closed convex cone and call M := N ∩ {−N } the largest subspace contained in N. Then

N is a subspace if and only if N ∩ M^{⊥} = {0} .

Moreover, for any ν_{0} ∈ M^{⊥} and ν ∈ N,

⟨ν_{0}, ν⟩ ≠ 0 ⟹ −ν ∉ N .  (1)

Proof. When the convex cone N is a subspace, it is symmetric: N = −N = M. In this case, N ∩ M^{⊥} = M ∩ M^{⊥} = {0}. Conversely, when N ∩ M^{⊥} = {0}, suppose for contradiction that N is not a subspace; we can take ν ∈ N \M, which can be expressed as a direct sum:

ν = ν_{m} + ν_{0} with ν_{m} ∈ M and 0 ≠ ν_{0} ∈ M^{⊥} .

Since M is a symmetric set, −ν_{m} ∈ M ⊂ N and, since N is a convex cone,

ν_{0} = ν + (−ν_{m}) ∈ N ;

thus we have exhibited a nonzero ν_{0} ∈ N ∩ M^{⊥}. This is the required contradiction. Finally, we have to prove (1). Take ν_{0} ∈ M^{⊥} and ν ∈ N. If −ν were in N, it would be also in M and this would contradict ⟨ν_{0}, ν⟩ ≠ 0.

The next result deals with N_{S}(g_{0}) and T_{S}(g_{0}), the normal and tangent cones to a closed convex set S at g_{0} ∈ S.

Proposition 2.2. Assume S ⊂ IR^{N} is a closed convex set and let g_{0} ∈ S. Then

N := N_{S}(g_{0}) is a subspace if and only if g_{0} ∈ ri S ,

where ri denotes the relative interior.

Proof. Call σ_{S} the support function of S. By definition of normal cones, s ∈ N exactly when ⟨s, g_{0}⟩ = σ_{S}(s). The convex cone N is a subspace if and only if it is symmetric. Thus, N is a subspace if and only if the following property holds:

s ∈ N ⟹ σ_{S}(s) + σ_{S}(−s) = 0 , [= ⟨s, g_{0}⟩ + ⟨−s, g_{0}⟩]

or equivalently

σ_{S}(d) + σ_{S}(−d) > 0 ⟹ d ∉ N ,

i.e., applying the definition of N:

σ_{S}(d) + σ_{S}(−d) > 0 ⟹ ∃g_{d} ∈ S : ⟨d, g_{d} − g_{0}⟩ > 0 ,

which in turn can be written

σ_{S}(d) + σ_{S}(−d) > 0 ⟹ σ_{S}(d) > ⟨d, g_{0}⟩ .

By Theorem 13.1 in [7] or Theorem V.2.2.3(ii) in [4], this last property just expresses g_{0} ∈ ri S.

We finish with an easy result.

Proposition 2.3. The only nonempty compact convex sets in IR^{N} that are relatively open are the singletons.

Proof. The relative interior of a convex set S is the interior for the topology relative to aff S, the affine hull of S; this last topological space being connected, it contains only two open and closed subsets: ∅ and itself. Thus, if the nonempty closed set S is relatively open, S = aff S. The result follows since the only bounded affine sets are the singletons.

A link between all these results, which will be useful for our purposes, is the following: if φ is a finite-valued convex function and z ∈ IR^{N} is such that N_{∂φ(z)}(g) is a subspace for all g ∈ ∂φ(z), then φ is differentiable at z.

3. On first-order developments of convex functions

We now present a theory analogous to that of §X.4.2(b) in [4], and of [6], relating upper bounds on a convex function with lower bounds on its conjugate. However, instead of finding bounds depending on a particular subgradient at a given point, we consider here the first-order expansion of a convex function φ:

φ(z_{0} + h) = φ(z_{0}) + φ′(z_{0}; h) + o(∥h∥) .

We want to estimate the remainder term (which is clearly nonnegative). To bound it from above means to find ε > 0 and some function r_{u} such that

φ(z_{0} + h) ≤ φ(z_{0}) + φ′(z_{0}; h) + r_{u}(h) + I_{B_{ε}}(h) for all h .  (2)

For a lower bound we need likewise ε and r_{l} such that

φ(z_{0} + h) + I_{B_{ε}}(h) ≥ φ(z_{0}) + φ′(z_{0}; h) + r_{l}(h) for all h .  (3)

Here and throughout, I_{B_{ε}} denotes the indicator function of B(0, ε). For both remainder functions r = r_{u} and r = r_{l}, the following properties will always be assumed without further mentioning:

r is convex, nonnegative, differentiable at 0, r(0) = 0, ∇r(0) = 0.

Besides, the following property will be crucial for our development:

there exists c > 0 such that r(h) ≥ \frac{1}{2}c∥h∥^{2} for all h .  (4)

Note that (3) and (4) with r = r_{l} hold whenever φ is strongly convex, and they imply that the conjugate φ^{∗} is finite-valued. Our aim is to study the duality between (2) and (3): if φ satisfies one of these inequalities, does φ^{∗} satisfy the other? The answer is given in Theorems 3.2 and 3.6 below, which play the role of Theorems X.4.2.7 and X.4.2.6 in [4] respectively.

3.1. On the Lipschitzian regularization

To derive dual relations, we will conjugate both sides of (2) and (3). For this, we will frequently compute conjugates of the type (ψ + I_{B_{ε}})^{∗}, i.e., infimal convolutions

Ψ_{ε}^{∗}(g) := (ψ + I_{B_{ε}})^{∗} (g) = min_{s∈IR^{N}}{ψ^{∗}(g − s) + ε∥s∥} .  (5)

The function Ψ_{ε}^{∗} is the so-called Lipschitzian regularization of ψ^{∗}, introduced in [2], and illustrated by Fig. 1. An important property of this function is that Ψ_{ε}^{∗} coincides with ψ^{∗} on a certain set.

Figure 1: Lipschitzian Regularization Lemma 3.1. Let ψ be a finite-valued convex function and denote by Ψ_{ε}^{∗} the Lipschitzian regularization of its conjugate ψ^{∗}.

(i) If there are c > 0 and δ > 0 such that

ψ(h) ≥ ψ(0) + ψ′(0; h) + \frac{1}{2}c∥h∥^{2} for ∥h∥ ≤ δ ,  (6)

then Ψ_{ε}^{∗}(s) = ψ^{∗}(s) for all ε ≤ δ and s ∈ ∂ψ(0) + B(0, εc/2). (ii) If ψ has the form ψ(h) = \frac{1}{2}C∥h∥^{2} (i.e. ψ^{∗} = \frac{1}{2C} ∥ · ∥^{2}) for some C > 0, then

Ψ_{ε}^{∗}(z) = \{ \begin{matrix}\frac{1}{2C} ∥z∥^{2} & if ∥z∥ ≤ εC \\ −\frac{ε^{2}C}{2} + ε∥z∥ & if not. \end{matrix}

(iii) With ψ as in (ii) and η ∈]0, ε], there holds

Ψ_{ε}^{∗}(z) ≥ −\frac{η^{2}C}{2} + η∥z∥ for all z.

Proof. [(i)] Apply Proposition XI.3.4.5 of [4]: ψ^{∗} and its regularization Ψ_{ε}^{∗} coincide on the set

{s ∈ IR^{N} : ψ^{∗}(s) = Ψ_{ε}^{∗}(s)} = {s ∈ IR^{N} : ∂ψ^{∗}(s) ∩ B(0, ε) ≠ ∅} .

Since s ∈ ∂ψ(0) means 0 ∈ ∂ψ^{∗}(s), this coincidence set contains in particular ∂ψ(0). To say that ∂ψ^{∗}(s) ∩ B(0, ε) ≠ ∅ is to say that ⟨s, ·⟩ − ψ(·) attains its maximum ψ^{∗}(s) on B(0, ε). Accordingly, let us find an upper bound for

A := sup_{∥h∥>ε}{⟨s, h⟩ − ψ(h)} .

For this, use the convexity of ψ on [0, h]: if h ∉ B(0, ε),

ψ(εh/∥h∥) ≤ ψ(0) + \frac{ε}{∥h∥}[ψ(h) − ψ(0)] ,

which, after some algebraic manipulations using (6), gives when ε ≤ δ:

ψ(h) ≥ ψ(0) + ψ′(0; h) + \frac{1}{2}cε∥h∥ .

Therefore

A ≤ sup_{∥h∥>ε}\{⟨s, h⟩ − ψ(0) − ψ′(0; h) − \frac{1}{2}cε∥h∥\}

≤ −ψ(0) + sup_{∥h∥∈IR^{N}}\{⟨s, h⟩ − ψ′(0; h) − \frac{1}{2}cε∥h∥\}

= −ψ(0) + (ψ′(0; ·) + \frac{1}{2}cε∥ · ∥)^{∗} (s)

= −ψ(0) + (I_{∂ψ(0)} _{∨}^{+} I_{B(0,εc/2)}) (s) .

The last infimal convolution is zero when s ∈ ∂ψ(0) + B(0, εc/2). For every such s which is not in ∂ψ(0), we thus have

A ≤ −ψ(0) = inf ψ^{∗} < ψ^{∗}(s) .

Then ⟨s, h⟩ − ψ(h) attains its maximum on B(0, ε); (i) is proved. [(ii)] For our quadratic function ψ, apply the dual definition (5):

Ψ_{ε}^{∗}(z) = (\frac{1}{2}C∥ · ∥^{2} + I_{B_{ε}})^{∗} (z) = sup_{x∈B(0,ε)}\{⟨z, x⟩ − \frac{1}{2}C∥x∥^{2}\}

= C sup_{x∈B(0,ε)}\{⟨z/C, x⟩ − \frac{1}{2}∥x∥^{2}\}

= C sup_{x∈B(0,ε)}\{\frac{1}{2}∥z/C∥^{2} − \frac{1}{2}∥x − z/C∥^{2}\}

= \frac{1}{2C} ∥z∥^{2} − \frac{C}{2} inf_{x∈B(0,ε)} ∥x − z/C∥^{2}

= \frac{1}{2C} ∥z∥^{2} − \frac{C}{2} d_{B(0,ε)}^{2}(z/C) .

To finish the proof observe that the distance function d_{B(0,ε)}(z/C) is equal to ε − ∥z∥/C whenever z/C ∉ B(0, ε). [(iii)] We consider two cases. If ∥z∥ ≤ εC, the result follows from

Ψ_{ε}^{∗}(z) − (−η^{2}C/2 + η∥z∥) = \frac{1}{2C} ∥z∥^{2} + \frac{1}{2}η^{2}C − η∥z∥ = \frac{1}{2C} (∥z∥ − ηC)^{2} .

In the other case, set q(η) := −η^{2}C/2 + η∥z∥ (so q = Ψ_{ε}^{∗} when η = ε). Compute q′(η) = −ηC + ∥z∥. We see that q is an increasing function when −ηC + ∥z∥ ≥ 0, in particular when η ≤ ε < ∥z∥/C.

We are now in a position to establish our duality relations between (2) and (3).

3.2. Bounding the conjugate from below

Let us return to our developments (2), (3). When the remainder term r_{u} does not increase too fast near the origin, (2) becomes a rather natural growth condition: it expresses that φ does not differ too much from its first order approximation. In this case, a lower bound on φ^{∗} does exist:

Theorem 3.2. Let φ be a finite-valued convex function satisfying (2) at a given z_{0}. Assume also that r = r_{u} satisfies (4) and

r_{u}(h) ≤ \frac{1}{2}C∥h∥^{2} for all h .  (7)

Then, for all g_{0} ∈ ∂φ(z_{0}) and s ∈ B(0, \frac{εc^{2}}{2C}), we have

φ^{∗}(g_{0} + s) ≥ φ^{∗}(g_{0}) + ⟨s, z_{0}⟩ + min_{γ∈∂φ(z_{0})} r_{u}^{∗}(g_{0} + s − γ) .  (8)

Proof. We conjugate both sides in (2): for all g ∈ IR^{N}

\begin{aligned}φ^{∗}(g) − ⟨g, z_{0}⟩ & ≥ [φ(z_{0}) + φ′(z_{0}; ·) + r_{u} + I_{B_{ε}}]^{∗} (g) \\ & = −φ(z_{0}) + (I_{∂φ(z_{0})} _{∨}^{+} (r_{u} + I_{B_{ε}})^{∗}) (g) \\ & = −φ(z_{0}) + (I_{∂φ(z_{0})} _{∨}^{+} R_{ε}^{∗}) (g) \\ & = −φ(z_{0}) + min_{γ∈∂φ(z_{0})} R_{ε}^{∗}(g − γ) , \end{aligned}  (9)

where R_{ε}^{∗} denotes the Lipschitzian regularization of r_{u}^{∗}, see (5). We will prove that, for g close enough to ∂φ(z_{0}), R_{ε}^{∗} can be replaced by r_{u}^{∗} in (9). First, observe that (4) and (7) are transformed in the dual space to

\frac{1}{2C} ∥ · ∥^{2} ≤ r_{u}^{∗} ≤ \frac{1}{2c}∥ · ∥^{2} .  (10)

These inequalities are transmitted to the Lipschitzian regularizations; by Lemma 3.1 (iii) we therefore have, for all η ∈]0, ε],

R_{ε}^{∗}(z) ≥ \frac{1}{2} (−η^{2}C + 2η∥z∥) for all z.

Apply (10) to obtain by division

\frac{r_{u}^{∗}(z)}{R_{ε}^{∗}(z)} ≤ \frac{∥z∥^{2}}{−η^{2}cC + 2ηc∥z∥}  for all z.  (11)

Let γ_{g} denote an optimal γ in (9). From (10) and (11),

\frac{1}{2C} ∥g − γ_{g}∥^{2} ≤ r_{u}^{∗}(g − γ_{g}) ≤ \frac{∥g − γ_{g}∥^{2}}{−η^{2}cC + 2ηc∥g − γ_{g}∥}R_{ε}^{∗}(g − γ_{g}) .

To this chain of inequalities, we append additional upper bounds, using the optimality of γ_{g}, R_{ε}^{∗} ≤ r_{u}^{∗}, and (10): for all γ ∈ ∂φ(z_{0}),

\frac{1}{2C} ≤ \frac{1}{−η^{2}cC + 2ηc∥g − γ_{g}∥} \frac{∥g − γ∥^{2}}{2c} .

After some algebra this results in

∥g − γ_{g}∥ ≤ \frac{C}{2ηc^{2}} ∥g − γ∥^{2} + \frac{ηC}{2}  for γ_{g} optimal in (9) , η ≤ ε and γ arbitrary in ∂φ(z_{0}).  (12)

To obtain (8), take η = \frac{εc}{2C}, g_{0} ∈ ∂φ(z_{0}) and s ∈ B(0, \frac{εc^{2}}{2C}). For g := g_{0} + s, let γ in (12) be the projection of g onto ∂φ(z_{0}): we do have ∥g − γ_{g}∥ ≤ εc/2. Then Lemma 3.1 (i) allows us to replace R_{ε}^{∗} by r_{u}^{∗} in (9). The result follows, since φ(z_{0}) + φ^{∗}(g_{0}) = ⟨g_{0}, z_{0}⟩.

The remainder term in (8) may be deemed abstract. However it can be relaxed to a more explicit form.

Corollary 3.3. Let φ be a finite-valued convex function satisfying (2), with r_{u} = \frac{1}{2}C∥·∥^{2}. Then, for all g_{0} ∈ ∂φ(z_{0}) and s ∈ B(0, εC/2), we have

φ^{∗}(g_{0} + s) ≥ φ^{∗}(g_{0}) + ⟨s, z_{0}⟩ + \frac{1}{2C} ∥g_{0} + s − P(g_{0} + s)∥^{2} ,  (13)

where P is the projection onto ∂φ(z_{0}). As a result

⟨s, x − z_{0}⟩ ≥ \frac{∥s∥^{2}}{2C} for all s ∈ N_{∂φ(z_{0})}(g_{0}) ∩ B(0, εC/2) and x ∈ ∂φ^{∗}(g_{0} + s) . (14)

Proof. Use Theorem 3.2 with r_{u} = \frac{1}{2}C∥ · ∥^{2}, so that r_{u}^{∗} = \frac{1}{2C} ∥ · ∥^{2}. To prove (14), use the subgradient inequality φ^{∗}(g_{0}) ≥ φ^{∗}(g_{0} + s) − ⟨s, x⟩ for x ∈ ∂φ^{∗}(g_{0} + s), and observe that g_{0} + s is projected onto g_{0}.

This result becomes even more suggestive in terms of the Moreau decomposition of the space IR^{N}. Recall that, if N and T are two mutually polar cones, then IR^{N} = N ⊕ T . More precisely, any s ∈ IR^{N} can be written

s = s_{N} + s_{T} where s_{N} := Proj_{N} (s) and s_{T} := Proj_{T} (s)

(see Theorem III.3.2.5 of [4], for example). We will use this decomposition with N = N_{∂φ(z_{0})}(g_{0}) and T = T_{∂φ(z_{0})}(g_{0}).

Proposition 3.4. Let φ^{∗} be a closed convex function satisfying (13) for all g_{0} ∈ ∂φ(z_{0}) and s ∈ B(0, εC/2). Then, for all such g_{0} and s, we have

φ^{∗}(g_{0} + s) ≥ φ^{∗}(g_{0}) + ⟨s, z_{0}⟩ + \frac{1}{2C} ∥s_{N} ∥^{2} .  (15)

Proof. By definition of a tangent cone, T contains ∪_{t>0}[∂φ(z_{0}) − g_{0}]/t, hence ∂φ(z_{0}) ⊂ g_{0}+T and ∥g_{0}+·−P(g_{0}+·)∥ ≥ ∥g_{0}+·−Proj_{g_{0}+_{T}} (g_{0}+·)∥ = ∥·− Proj_{T} (·)∥ = ∥ Proj_{N} (·)∥. Then (13) proves the result.

The Cauchy-Schwarz inequality in (14) suggests a sort of “tangential radial Lipschitz behaviour” of particular subgradients. Indeed, for x close to z_{0}, consider those g = g_{0} + s ∈ ∂φ(x) that are projected onto g_{0} ∈ ∂φ(z_{0}): they satisfy ∥g − g_{0}∥ ≤ 2C∥x − z_{0}∥. Instead of proving this informal observation, we rather state a more global result:

Corollary 3.5. For a finite-valued convex function φ and g_{0} ∈ ∂φ(z_{0}), the following statements are equivalent:

∃ε, C > 0 : ∥h∥ ≤ ε ⇒ φ(z_{0} + h) ≤ φ(z_{0}) + φ′(z_{0}; h) + \frac{C}{2} ∥h∥^{2} ,  (16)
∃δ, D > 0 : ∥h∥ ≤ δ ⇒ ∂φ(z_{0} + h) ⊂ ∂φ(z_{0}) + B(0, D∥h∥) .  (17)

Proof. Let ε and C be as in (16). Because ∂φ(z_{0}) is compact and ∂φ has a closed graph, we can find δ > 0 such that

∥h∥ ≤ δ ⇒ ∂φ(z_{0} + h) ⊂ ∂φ(z_{0}) + B(0, εC/2) .

Take now arbitrary h ∈ B(0, δ), g ∈ ∂φ(z_{0} + h) and set g_{0} := P(g). Then s := g − g_{0} ∈ N_{∂φ(z_{0})}(g_{0}) ∩ B(0, εC/2) and z_{0} + h ∈ ∂φ^{∗}(g). When (16) holds, Corollary 3.3 applies with r_{u} = \frac{1}{2}C∥ · ∥^{2} and (17) follows from (14). Conversely, write the Mean-Value Theorem: for some θ ∈]0, 1[ and some g_{θ} ∈ ∂φ(z_{0} +θh),

φ(z_{0} + h) − φ(z_{0}) − φ′(z_{0}; h) = ⟨g_{θ}, h⟩ − max_{g∈∂φ(z_{0})} ⟨g, h⟩

= min_{g∈∂φ(z_{0})} ⟨g_{θ} − g, h⟩

≤ min_{g∈∂φ(z_{0})} ∥g_{θ} − g∥ ∥h∥ .

Assume (17) and take h ∈ B(0, δ), hence θh ∈ B(0, δ). Then the last term is smaller than θD∥h∥^{2} ≤ D∥h∥^{2} and the growth property (16) holds.

When φ has a gradient at z_{0}, this result becomes a coarse form of Theorem 2.12 in [3]; the difference is that the latter deals with approximations, rather than inequalities or inclusions.

3.3. Bounding the conjugate from above

Now, we proceed to study the effect on φ^{∗} of the growth property (3), (4). We will see that this property is quite strong. It is not clear whether our assumptions (4) and (7) are really essential for Theorem 3.2. At least, (7) is natural: useful lower bounds for φ^{∗} need nontrivial upper bounds for φ; but the role of (4) is more obscure. By contrast, the assumptions in the following dual counterpart to Theorem 3.2 seem rather minimal.

Theorem 3.6. Let φ be a finite-valued convex function satisfying (3) at a given z_{0}, with r = r_{l} satisfying (4). Then, for all g_{0} ∈ ∂φ(z_{0}), φ^{∗} is differentiable at g_{0} (∇φ^{∗}(g_{0}) = z_{0}) and, for all s ∈ B(0, εc/2), we have

φ^{∗}(g_{0} + s) ≤ φ^{∗}(g_{0}) + ⟨s, z_{0}⟩ + min_{γ∈∂φ(z_{0})} r_{l}^{∗}(g_{0} + s − γ) .  (18)

Proof. Proceed as in the proof of Theorem 3.2. Clearly (6) holds with ψ = φ and δ = ε, so Lemma 3.1 (i) can be applied to conjugate the lefthand side of (3):

φ^{∗}(g) − ⟨g, z_{0}⟩ ≤ −φ(z_{0}) + min_{γ∈∂φ(z_{0})} r_{l}^{∗}(g − γ) for g ∈ ∂φ(z_{0}) + B(0, εc/2) .

Set g = g_{0} + s, with s as stated, and observe that φ(z_{0}) + φ^{∗}(g_{0}) = ⟨g_{0}, z_{0}⟩ to obtain (18). Now, in view of (4), r_{l}^{∗} ≤ \frac{1}{2c}∥ · ∥^{2}, so (18) gives

φ^{∗}(g_{0} + s) − φ^{∗}(g_{0}) − ⟨s, z_{0}⟩ ≤ \frac{1}{2c} min_{γ∈∂φ(z_{0})} ∥g_{0} + s − γ∥^{2} ≤ \frac{1}{2c}∥s∥^{2} .

Because the lefthand side is nonnegative, this clearly implies ∇φ^{∗}(g_{0}) = z_{0}.

It is interesting to compare this result with Proposition X.4.2.6 in [4]. Our upper bound (18) is stronger than (X.4.2.5) in [4], just because our starting assumption (3) is stronger. In §3.2, (8) was relaxed to (13) and also to (15). Here, (18) could likewise be relaxed to

φ^{∗}(g_{0} + s) ≤ φ^{∗}(g_{0}) + ⟨s, z_{0}⟩ + \frac{1}{2c}∥s∥^{2} .

Actually, we prefer another relaxed form of (18), which gives a counterpart to (15):

Corollary 3.7. Let φ be a finite-valued convex function satisfying (3), with r = r_{l} satisfying (4), and let g_{0} ∈ ∂φ(z_{0}). Take the Moreau decomposition s = s_{T} + s_{N} of an arbitrary s along T and N, the tangent and normal cones to ∂φ(z_{0}) at g_{0}. Then

lim sup_{t↓0} \frac{φ^{∗}(g_{0} + ts) − φ^{∗}(g_{0}) − t ⟨s, z_{0}⟩}{t^{2}} ≤ \frac{1}{2c}∥s_{N} ∥^{2} .  (19)

Proof. When t ↓ 0, by definition of the tangent cone, there is some g_{t} = g_{0} +ts_{T} +o(t) ∈ ∂φ(z_{0}). From here, the result is an easy consequence of Theorem 3.6. However, we prefer a more direct proof, which does not use the preceding machinery. From (3) and knowing that φ′(z_{0}; h) ≥ ⟨g_{0}, h⟩,

φ(z_{0} + h) ≥ φ(z_{0}) + ⟨g_{t}, h⟩ + \frac{1}{2}c∥h∥^{2} + o(∥h∥^{2})

for all h. Apply Proposition X.4.2.6 in [4]: for all ν,

φ^{∗}(g_{t} + ν) ≤ φ^{∗}(g_{t}) + ⟨ν, z_{0}⟩ + \frac{1}{2c}∥ν∥^{2} + o(∥ν∥^{2}).

Combining the subgradient inequality at g_{t}, this gives

φ^{∗}(g_{t} + ν) ≤ φ^{∗}(g_{0}) + ⟨g_{t} − g_{0} + ν, z_{0}⟩ + \frac{1}{2c}∥ν∥^{2} + o(∥ν∥^{2}) .

Take ν := ts − g_{t} + g_{0} = ts_{N} + o(t) and divide by t^{2}. The result follows because o(∥ν∥^{2}) = o(t^{2}).

Beware that (19) is much stronger than (15) (written in the dual space and mutatis mutandis). In particular, it implies the existence of ∇φ^{∗}(g_{0}) = z_{0}. In fact Theorem 3.6 explains why full duality cannot hold between the pairs (2), (7) and (3), (4). Indeed, suppose that the following statement were true: if (2), (7) hold, then (3), (4) hold with φ replaced by φ^{∗} and r_{l} = r_{u}^{∗}. Then Theorem 3.6, used with φ and φ^{∗} interchanged, would imply the existence of ∇φ(z_{0}).

4. A tangential regularization

We just mentioned that the growth properties (2), (7) and (3), (4) cannot be dual to each other, unless ∇φ(z_{0}) exists. In fact, Proposition 3.4 shows that, when φ satisfies an appropriate form of (2), then φ^{∗} satisfies (15). Now (15) is a weakened form of (3)-(4) (for φ^{∗}) and the following informal calculation shows that it cannot be improved because its last quadratic term cannot contain the s_{T} -component. Given a point z_{0} and g_{0} ∈ ∂φ(z_{0}), assume there is another g ∈ ∂φ(z_{0}) and set s_{T} := g − g_{0} ∈ T . Then, for t ∈]0, 1[,

φ^{∗}(g_{0} + ts_{T}) = −φ(z_{0}) + ⟨g_{0} + ts_{T} , z_{0}⟩ = φ^{∗}(g_{0}) + t ⟨s_{T} , z_{0}⟩ .

We conclude that φ^{∗} is locally affine in T . Knowing that (2), (7) imply (15) and nothing more, a natural question therefore arises: conversely, when (15) holds, what can be expected from φ in terms of the growth property (2)? The knack is to introduce an artificial s_{T} -term in φ^{∗}: indeed, the function

ϕ_{T}^{∗} (s) := φ^{∗}(g_{0} + s) + \frac{1}{2}∥s_{T} ∥^{2}  (20)

satisfies the appropriate growth condition (3) (for φ^{∗}) and triggers the dualization mechanism of section 3.3.

Proposition 4.1. Let φ be a finite-valued convex function and g_{0} ∈ ∂φ(z_{0}). The conjugate of ϕ_{T}^{∗} in (20) is

ϕ_{T} (x) = min_{y∈x+T} \{φ(y) − ⟨g_{0}, y⟩ + \frac{1}{2}∥x − y∥^{2}\} ,  (21)

whose subdifferential is

∂ϕ_{T} (x) = −g_{0} + {g ∈ ∂φ(p_{T} (x)) : Proj_{T} (g_{0} − g) = p_{T} (x) − x} .  (22)

Here p_{T} (x) is the unique minimizer in (21), characterized by

∃g ∈ ∂φ(p_{T} (x)) : p_{T} (x) = x + Proj_{T} (g_{0} − g) .  (23)

In particular, p_{T} (z_{0}) = z_{0}, ϕ_{T} (z_{0}) = φ(z_{0}) − ⟨g_{0}, z_{0}⟩ and ∇ϕ_{T} (z_{0}) = 0 exists.

Proof. Take the conjugates of the functions making up the sum in (20): (φ^{∗}(g_{0} + ·))^{∗} = φ(·) − ⟨g_{0}, ·⟩, and

(\frac{1}{2}∥ Proj_{T} (·)∥^{2})^{∗} = (\frac{1}{2}∥ · − Proj_{N} (·)∥^{2})^{∗} = (min_{u∈N} \{\frac{1}{2}∥ · −u∥^{2}\})^{∗}
= (\frac{1}{2}∥ · ∥^{2} _{∨}^{+} I_{N})^{∗} = \frac{1}{2}∥ · ∥^{2} + I_{T} .

Their infimal convolution is the righthand side in (21); this is a finite-valued convex function of x, which is therefore the conjugate of ϕ_{T}^{∗}. To obtain the expression of ∂ϕ_{T}, write

ϕ_{T} (x) = min_{y+z=x}\{φ(y) − ⟨g_{0}, y⟩ + \frac{1}{2}∥z∥^{2} + I_{T} (−z)\}

and apply Theorem XI.3.4.1 in [4]:

∂ϕ_{T} (x) = [∂φ(p_{T} (x)) − g_{0}] ∩ [x − p_{T} (x) − N_{T} (p_{T} (x) − x)] .

Thus the subgradients of ϕ_{T} at x are the vectors g − g_{0}, with g ∈ ∂φ(p_{T} (x)), such that x − p_{T} (x) − (g − g_{0}) ∈ N_{T} (p_{T} (x) − x), i.e., x − p_{T} (x) − (g − g_{0}) ∈ N_{T} (p_{T} (x) − x). Use

γ ∈ N_{T} (p_{T} (x) − x) ⟺ p_{T} (x) − x = Proj_{T} (γ + p_{T} (x) − x) ,  (24)

with γ = x − p_{T} (x) − (g − g_{0}): altogether, the subgradients of ϕ_{T} at x are the vectors g − g_{0}, with g ∈ ∂φ(p_{T} (x)) such that p_{T} (x) − x = Proj_{T} (g_{0} − g). This is just (22). The optimality condition characterizing the unique minimum in (21) is 0 ∈ ∂φ(p_{T} (x)) − g_{0} + p_{T} (x) − x + N_{x+T} (p_{T} (x)), i.e.,

∃g ∈ ∂φ(p_{T} (x)) : g_{0} − g + x − p_{T} (x) ∈ N_{x+T} (p_{T} (x)) .

Observe that N_{x+T} (p_{T} (x)) = N_{T} (p_{T} (x) − x), and use again the equivalence (24): the characterization above can be written p_{T} (x) − x = Proj_{T} (g_{0} − g), which is just (23). In particular, when x = z_{0}, we can take g = g_{0} ∈ ∂φ(z_{0}), and this shows that z_{0} satisfies the characterization (23) of p_{T} (z_{0}). In other words, p_{T} (z_{0}) = z_{0}, and the value ϕ_{T} (0) follows easily. Finally, we have

∂ϕ_{T} (0) = [∂φ(z_{0}) − g_{0}] ∩ N_{T} (0) ⊂ T ∩ N_{T} (0) = T ∩ N ,

which is the singleton {0}.

From its definition (21), ϕ_{T} appears as a “tangential” Moreau-Yosida regularization in the cone T ; and p_{T} appears likewise as a “tangential” proximal operator. This explains our notation. The above result is true for a rather arbitrary closed convex function φ^{∗}. When additional properties are assumed, ϕ_{T} enjoys the properties involved in Corollary 3.5.

Proposition 4.2. Let the convex functions φ and φ^{∗} be both finite-valued, with φ^{∗} satisfying (13) for g_{0} ∈ ∂φ(z_{0}) and ∥s∥ small enough. Then

∃ε, C′ : ∥h∥ ≤ ε ⇒ ϕ_{T} (z_{0} + h) ≤ ϕ_{T} (z_{0}) + \frac{C′}{2} ∥h∥^{2} ,

or equivalently

∃δ, D > 0 : ∥h∥ ≤ δ ⇒ ∂ϕ_{T} (z_{0} + h) ⊂ B(0, D∥h∥) .  (25)

Proof. From its definition (20), ϕ_{T}^{∗} is finite-valued. Using Proposition 3.4, ϕ_{T}^{∗} (s) ≥ ϕ_{T}^{∗} (0) + \frac{1}{2C′} |s∥^{2}, with C′ := max\{1, C\}; so (3) holds, with φ replaced by ϕ_{T}^{∗} and r_{l} = \frac{1}{2C′} ∥·∥^{2}. Then Theorem 3.6 can be applied. Knowing that ∇ϕ_{T} (z_{0}) = 0 (Proposition 4.1), we obtain the growth property on ϕ_{T}. The radial Lipschitz property (25) then follows from Corollary 3.5.

Another closely related question concerns the regularity of the mapping p_{T} (·). More precisely, is this tangential proximal operator Lipschitzian? Our next result gives a partial answer: under mild assumptions, p_{T} (·) is radially Lipschitzian at z_{0}.

Corollary 4.3. Let the convex functions φ and φ^{∗} be both finite-valued, with φ^{∗} satisfying (13) for g_{0} ∈ ∂φ(z_{0}) and ∥s∥ small enough. Then

∃δ, L > 0 : ∥x − z_{0}∥ ≤ δ ⇒ ∥p_{T} (x) − z_{0}∥ ≤ L∥x − z_{0}∥ ,

or equivalently

∃δ, D > 0 : ∥x − z_{0}∥ ≤ δ ⇒ ∥p_{T} (x) − x∥ ≤ D∥x − z_{0}∥ .  (26)

Proof. The equivalence between both statements is straighforward from the triangular inequality, let us prove (26). Combining (22) from Proposition 4.1 with (25) from Proposition 4.2, there exist δ, D > 0 such that ∥x − z_{0}∥ ≤ δ implies

−g_{0} + {g ∈ ∂φ(p_{T} (x)) : Proj_{T} (g_{0} − g) = p_{T} (x) − x} ⊂ B(0, D∥x − z_{0}∥) .

Take a vector −g_{0} + g as described in the above lefthand side. Since Proj_{T} (·) is nonexpansive and Proj_{T} (0) = 0, we can write

∥p_{T} (x) − x∥ = ∥ Proj_{T} (g_{0} − g)∥ ≤ ∥g_{0} − g∥ ≤ D∥x − z_{0}∥

and (26) follows.

Let us give a simple example showing how these results can be interpreted. Take φ := max(φ_{1}, φ_{2}), with each φ_{i} smooth. Then (2), (7) always hold. Take z_{0} such that φ(z_{0}) = φ_{1}(z_{0}) = φ_{2}(z_{0}) but ∇φ_{1}(z_{0}) ≠ ∇φ_{2}(z_{0}). Then take α ∈]0, 1[ and g_{0} = α∇φ_{1}(z_{0})+(1−α)∇φ_{2}(z_{0}), so that g_{0} ∈ ri ∂φ(z_{0}). We claim that, for x close to z_{0}, p_{T} (x) satisfies φ_{1}(p_{T} (x)) = φ_{2}(p_{T} (x)). In fact, if φ_{1}(p_{T} (x)) > φ_{2}(p_{T} (x)), then ∇φ(p_{T} (x)) = ∇φ_{1}(p_{T} (x)) is far from g_{0} and, from Proposition 4.1, ∇ϕ_{T} (x) = ∇φ(p_{T} (x)) − g_{0} is far from 0 = ∇ϕ_{T} (z_{0}). This contradicts the continuity of ∇ϕ_{T}. Roughly speaking, when x describes a ball around z_{0}, p_{T} (x) describes a portion of the surface S := {z : φ_{1}(z) = φ_{2}(z)} where φ is not differentiable. We show now that, when restricted to this surface, φ is pretty smooth at z_{0}.

Theorem 4.4. Let φ be a (finite-valued) strongly convex function satisfying (2), with r_{u} satisfying (7), and take g_{0} ∈ ri ∂φ(z_{0}). Then there exists D > 0 such that, with p_{T} (x) defined by (23),

φ(p_{T} (x)) ≤ φ(z_{0}) + ⟨g_{0}, p_{T} (x) − z_{0}⟩ + \frac{1}{2}D∥p_{T} (x) − z_{0}∥^{2} ,

for x close enough to z_{0} such that ∥(x − z_{0})_{T} ∥ = O(∥(x − z_{0})_{N} ∥).

Proof. We are in the conditions of Corollary 3.3 and Proposition 4.2 (recall in particular that (4) holds and implies φ^{∗} < +∞); so we can write ϕ_{T} (x) ≤ ϕ_{T} (z_{0}) + \frac{1}{2}∥x − z_{0}∥^{2}. Using (21) we get

φ(p_{T} (x)) − ⟨g_{0}, p_{T} (x)⟩ + \frac{1}{2}∥p_{T} (x) − x∥^{2} ≤ φ(z_{0}) − ⟨g_{0}, z_{0}⟩ + \frac{1}{2}∥x − z_{0}∥^{2} ,

from which we obtain

φ(p_{T} (x)) ≤ φ(z_{0}) + ⟨g_{0}, p_{T} (x) − z_{0}⟩ + \frac{1}{2}∥x − z_{0}∥^{2} .

By assumption, ∥x − z_{0}∥^{2} = O(∥(x − z_{0})_{N} ∥^{2}). Since g_{0} ∈ ri ∂φ(z_{0}), T is a subspace (Proposition 2.2); then (x − z_{0})_{N} = (x − p_{T} (x))_{N} + (p_{T} (x) − z_{0})_{N} = (p_{T} (x) − z_{0})_{N} (remember x − p_{T} (x) ∈ T ). The result follows because ∥(p_{T} (x) − z_{0})_{N} ∥ ≤ ∥p_{T} (x) − z_{0}∥.

When restricted to points of the form p_{T} (·) (and z_{0} is such a point), the function φ is differentiable at z_{0} and locally comparable to a quadratic function. From there, the way is open to obtaining a real second-order development. This is done in [5].

References

[1] J.-P. Crouzeix: A relationship between the second derivative of a convex function and of its conjugate, Mathematical Programming, 13 (1977) 364–365.

[2] J.-B. Hiriart-Urruty: Lipschitz r-continuity of the approximate subdifferential of a convex function, Mathematica Scandinavica, 47 (1980) 123–34.

[3] J.-B. Hiriart-Urruty: The approximate first-order and second-order directional derivatives for a convex function, In J.-P. Cecconi and T. Zolezzi, editors, Mathematical Theories of Optimization, number 979 in Lecture Notes in Mathematics (1983), Springer-Verlag, 154– 166.

[4] J.-B. Hiriart-Urruty and C. Lemaréchal: Convex Analysis and Minimization Algorithms, Springer-Verlag, 1993. (two volumes).

[5] C. Lemaréchal and C. Sagastizábal: Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM Journal on Optimization, 1995. To appear.

[6] J.-P. Penot: Subhessians, superhessians and conjugation, Nonlinear Analysis: Theory, Methods and Applications, 23(6) (1994) 689–702.

[7] R.T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.