Cours de Francis Clarke

Francis Clarke

Description

Niveau: Supérieur, Master
Chapter 4 Convex analysis Analyse Master 1 Cours de Francis Clarke (2011) Convex analysis refers to a certain calculus that can be developed for convex sets and functions; it has widespread applications. It has also served as progenitor for the subject of nonsmooth analysis, in which generalized calculus is developed much fur- ther. In the convex case, the role of derivative is played by the subdifferential. 4.1 The subdifferential Let f : X ? R∞, where X is a normed space, and let x be a point in dom f . An element ? of X? is a subgradient of f at x (in the sense of convex analysis) if it satisfies the following subgradient inequality : f (y)? f (x) ? , y? x ?y ? X . The geometric content of this condition is clear: the affine function y ? f (x) + ? ,y? x is said to support f from below at y = x (meaning that it lies everywhere below f , with equality at x). The set of all subgradients of f at x is denoted by ∂ f (x), and referred to as the subdifferential of f at x. Thus the map x ? ∂ f (x) is a set-valued (or multi-valued) function whose values are subsets of X?.

• following subgradient


• convex


• rn ?


• now let


• convex analysis


• convex analysis refers


• let ?


• ?y ?


• taking


• there exist

Sujets

• Clarke
• Convex
• Convex analysis
• Eminent domain
• Existential quantification

Informations

• Publié par: cidur
• Nombre de lectures: 30
• Langue: English

Extrait

Chapter 4 Convex analysis

Analyse Master 1

Cours de Francis Clarke (2011)

Convex analysis refers to a certain calculus that can be developed for convex sets and functions; it has widespread applications. It has also served as progenitor for the subject ofnonsmooth analysis, in which generalized calculus is developed much fur- ther. In the convex case, the role of derivative is played by thesubdifferential.

4.1 The subdifferential

∞ Letf:X→R, whereXis a normed space, and letxbe a point in domf. An ∗ elementζofXis asubgradientoffatx(in the sense of convex analysis) if it satisfies the followingsubgradient inequality: ￿  f(y)−f(x)￿ζ,y−x∀y∈X.

The geometric content of this condition is clear: the affine functiony￿→f(x) + ￿  ζ,y−xis said tosupport ffrom below aty=x(meaning that it lies everywhere belowf, with equality atx). The set of all subgradients offatxis denoted by ∂f(x), and referred to as thesubdifferentialoffatx. Thus the mapx￿→∂f(x)is ∗ a set-valued (or multi-valued) function whose values are subsets ofX. We use the ∗ termmultifunctionin such a case:∂fis a multifunction fromXtoX. It follows directly from the definition that the subdifferential∂f(x)is a convex set ∗ which is closed for the weak topology, since, for eachy, the set ofζsatisfying

55

56

Cours de Francis Clarke : Convex analysis

∗ the subgradient inequality is weak closed and convex. It is clear thatfattains a minimum atxif and only if 0∈∂f(x). This is but the first of several ways in which the subdifferential acts like a derivative.

∞ 4.1 Proposition.Letf:X→Rbe a convex function, andx∈domf. Then  ￿   ∗  ∂f(x) =ζ∈X:f(x;v)￿ζ,v∀v∈X.     Iff(x)exists, then∂f(x) =f(x). G G

Proof.The general formula follows directly from Prop. 2.23. It clearly implies the final assertion. In Example 2.24, the reader may check that∂f(−1)and∂f(1)are empty, and that ∂f(x)is a singleton when−1<x<+1.

4.2 Exercise.Letx∈S, whereSis a convex subset ofX. Prove that∂I S (x) =N S (x); that is, the subdifferential of the indicator function is the normal cone.

4.3 Exercise.Letfbe the functionf(x) =x. a) Prove that∂f(0)is the closed unit ball inX. ￿    b) Letζ∈∂f(x), wherex=0. Prove thatζ,x=xandζ=1. ∗



∞ 4.4 Proposition.Letf:X→Rbe a convex function, and letx∈domfbe a point ∗ of continuity off. Then∂f(x)is nonempty and weak compact.

Proof.The continuity atxepiimplies that int f=0/ . epiWe separate int fand the   ∗ pointx,f(x)to deduce the existence ofζ∈Xandλ∈Rsuch that ￿  ￿  ζ,y+λr<ζ,x+λf(x)∀(y,r)∈int epif.

It follows thatλ<0; we may therefore normalize by takingλ=−1. Since epif⊂   cl epif=epicl int f(by Theorem 2.2), the separation inequality implies ￿  ￿  ζ,y−rζ,x−f(x)∀(y,r)∈epif.

We deduce that∂f(x)containsζ, and is therefore nonempty. Theorem 2.34 asserts thatfis Lipschitz of rankKon some neighborhoodVofx. Now letζbe any element of∂f(x). The subgradient inequality yields ￿    ζ,y−xf(y)−f(x)f(y)−f(x)K|y−x|∀y∈V.

∗   It follows thatζK; thus,∂f(x)is bounded. This implies that∂f(x)compactis weak (see Cor. 3.15).

4.1 The subdifferential

57

n n 4.5 Corollary.Letf:R→Rbe a convex function. Then for anyx∈R,∂f(x)is a nonempty convex compact set.

Proof.This follows from Corollary 2.35.

k 4.6 Corollary. (Jensen’s inequality)Letϕ:R→Rbe convex. Then    1  1     1k ϕg(t)dtϕg(t)dt∀g∈L(0,1),R. 0 0



Proof.Observe that, by Cor. 4.5,∂ ϕ(g¯)contains an elementζ, whereg¯ :=  1 g(t)dt. Then, by definition, we have 0 ￿  k ϕ(y)−ϕ(g¯)￿ζ,y−g¯∀y∈R.

Substitutingy=g(t)and integrating over[0,1], we obtain the stated inequality.



4.7 Exercise. a) Modify the statement of Jensen’s inequality appropriately when the underlying interval is[a,b]rather than[0,1]. b) Formulate and prove Jensen’s inequality in several dimensions, when the func-   1k n tiongbelong toLΩ,R,Ωbeing a bounded open subset ofR. 

∞ ∞ 4.8 Theorem. (Subdifferential of the sum)Letf:X→Randg:X→Rbe convex functions which admit a point indomf∩domgat whichfis continuous. Then we have   ∂f+g(x) =∂f(x) +∂g(x)∀x∈domf∩domg.

Proof.The inclusion⊃follows from the definition of subdifferential. Now letζ∈   ∂f+g(x). We may reduce to the casex=0,f(0) =g(0) =0. Letx¯ be a point in domf∩domgat whichfis continuous. The subsets ofX×Rdefined by  ￿   C=int epif,D= (w,t):ζ,w−g(w)￿t

are nonempty as a consequence of the existence ofx¯. They are convex, and disjoint as a result of the subgradient inequality forζ. By Theorem 2.37,CandDcan be ∗ separated: there existξ∈Xandλ∈Rsuch that ￿  ￿  ξ,w+λt<ξ,u+λs∀(w,t)∈D,∀(u,s)∈int epif.

It follows thatλ>0; we can normalize by takingλ=1. Since epif⊂cl epif=   cl int epif(by Theorem 2.2), we deduce ￿  ￿  ξ,w+tξ,u+s∀(w,t)∈D∀(u,s)∈epif.

58

Cours de Francis Clarke : Convex analysis

Taking(w,t) = (0,0), this implies−ξ∈∂f(0). Taking(u,s) = (0,0)leads toξ+ ζ∈∂g(0). Thus,ζ∈∂f(0) +∂g(0).   4.9 Exercise.LetCandDbe convex subsets ofXsuch that intC∩D=Let0/ . x∈C∩D. ThenN C∩D (x) =N C (x) +N D (x).

4.10 Proposition.Letf:X→Rbe a continuous convex function,Ca convex sub- set ofX, andxa point inC. Then the following are equivalent: a)xminimizesfover the setC. b)−∂f(x)∩N C (x)=0/; or equivalently,0∈∂f(x) +N C (x).   Proof.If (a) holds, thenxminimizesu￿→f(u) +I C (u). Thus 0∈∂f+I C (x). The latter equals∂f(x) +∂I C (x) =∂f(x) +N C (x), by Theorem 4.8 and Exer. 4.2; thus,   (b) holds. Conversely, (b) yields 0∈∂f+I C (x), which implies (a).

Adjoint operators.LetXandYbe normed spaces andT∈L(X,Y). It is clear that ∗ ∗ ∗ one defines a unique elementTofL(Y,X)by the formula ￿  ￿  ∗ ∗ ∗ ∗ ∗ T y,x=y,T x∀x∈X,y∈Y.

∗ Tis called theadjointof the operatorT.

∞ 4.11 Theorem.LetYbe a normed space,A∈L(X,Y), andg:Y→Ra convex function. Let there be a pointx 0 inXsuch thatgis continuous atAx 0 . Then the functionf(x) =g(Ax)is convex, and we have

∗ ∂f(x) =A∂g(Ax)∀x∈domf.

∗ Proof.It is easily verified thatfis convex, and that any element ofA∂g(Ax)lies ∞ in∂f(x). We now prove the opposite inclusion. Letϕ:X×Y→Rbe defined by    ϕ(x,y) =g(y) +I grA (x,y), where grAis the graph ofA: the setx,Ax∈X×Y:  x∈X. It follows from the definition of subgradient that     ζ∈∂f(x)⇐⇒ζ,0∈∂ ϕx,Ax.

Because of the existence ofx 0 , we may apply Theorem 4.8 toϕ, for anyζ       as above. There resultsα,β∈N grA x,Axandγ∈∂g(Ax)such thatζ,0=       0,γ+α,β. The normal vectorα,βsatisfies ￿  ￿  α,u−x+β,Au−Ax0∀u∈X,

∗ ∗ ∗ which impliesα=−Aβ. We deduceζ=Aγ∈A∂g(Ax), as required.

n 4.12 Exercise. (Mean Value theorem)Letf:R→Rbe a convex function.



4.1 The subdifferential

59

n a) We fixx,v∈Rand we setg(t) =f(x+tv)fort∈R. Show thatgis convex, and that ￿   ￿   ∂g(t) =∂f(x+tv),v=ξ,v:ξ∈∂f(x+tv).

n b) Prove the following familiar-looking theorem: for allx,y∈R,x=y, there exists z∈(x,y)such that ￿  f(y)−f(x)∈∂f(z),y−x.

n c) LetUbe an open convex subset ofR. Use the above to prove the following subdifferential characterization of the Lipschitz property:

  fis Lipschitz of rankKonU⇐⇒ζK∀ζ∈∂f(x),∀x∈U.



The following result lists some basic facts about the subdifferential of convex func- n tions onR.

n 4.13 Proposition.Letf:R→Rbe convex. Then a)The graph of∂fis closed:ζ i ∈∂f(x i ),ζ i →ζ,x i →x=⇒ζ∈∂f(x).   n b)For any compact subsetSofR, there existsMsuch thatζM∀ζ ∂f(x),x∈S. c)For anyx, for anyε>0, there existsδ>0such that

  y−x<δ=⇒∂f(y)⊂∂f(x) +εB.

∈

d)fis differentiable atxif and only if∂f(x)is a singleton. e)fis continuously differentiable in an open subsetUif and only if∂f(x)reduces to a singleton for everyx∈U.

n Proof.Consider the situation described in (a). For anyy∈R, we have, for eachi, ￿  f(y)−f(x i )￿ζ i ,y−x i . Taking limits, and bearing in mind thatfis continuous ￿  (Cor. 2.35), we obtainf(y)−f(x)￿ζ,y−x; thus,ζ∈∂f(x). We know thatfis locally Lipschitz. A routine argument using compactness shows n thatfis Lipschitz on bounded subsets ofR. Whenfis Lipschitz of rankKnear x, it follows from the definition of subgradient that any element of∂f(x)satisfies   ζK. These facts imply (b). Part (c) follows from a routine argument by contradiction, using parts (a) and (b). We turn now to part (d).    Iffis differentiable atx, then Prop. 4.1 asserts that∂f(x)is the singletonf(x).    Conversely, suppose that∂f(x)is a singletonζ. We proceed to prove thatf(x) = ζ. Letx i be any sequence converging tox(x i =x). Then, by Exer. 4.12, there exist

60 Cours de Francis Clarke : Convex analysis   ￿  z i ∈x i ,xandζ i ∈∂f(z i )such thatf(x i )−f(x) =ζ i ,x i −x.By part (c), the sequenceζ i necessarily converges toζ. Thus we have ￿  ￿     f(x i )−f(x)−ζ,x i −xζ i −ζ,x i −x →0,     x i −x x i −x

 whencef(x)exists and equalsζ. The final assertion follows immediately from (c) and (d).



Strict convexity.LetUbe a convex subset ofX, and letf:U→Rbe given. We say thatfisstrictly convexif the defining inequality of convexity is strict whenever it can be:   x,y∈U,x=y,t∈(0,1) =⇒f(1−t)x+ty<(1−t)f(x) +t f(y).

The role of strict convexity in optimization is partly to assure uniqueness of a min- imum: it is clear that a strictly convex function cannot attain its minimum at two different points.

n 4.14 Exercise.LetUbe an open convex subset ofR, and letf:U→Rbe convex. a) Prove thatfis strictly convex if and only if ￿  x,y∈U,x=y,ζ∈∂f(x) =⇒f(y)−f(x)>ζ,y−x.

b) Deduce that iffis strictly convex, then∂fis injective, in the following sense:

x,y∈U,∂f(x)∩∂f(y)=0/=⇒x=y.

4.2 Conjugate functions



∞ Letf:X→Rbe a proper function (that is, domf=/0).Theconjugate function ∗ ∗∞ f:X→Roffis defined by ￿  ∗ f(ζ) =supζ,x−f(x). x∈X ∗ Note that the properness offrules out the possibility thatfhas the value−∞; we ∗ ∗ ∗∗ say then thatfis well-defined. Whenfis itself proper, thebiconjugate f:X→ ∞ Roffis defined as follows: ￿  ∗∗ ∗ f(x) =supζ,x−f(ζ). ∗ ζ∈X