Cours de Francis Clarke
11
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
11
pages
English
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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?.
Voir
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
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∂IS(x) =NS(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=xandζ=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−xf(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 11 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. ThenNC∩D(x) =NC(x) +ND(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)∩NC(x)=0/; or equivalently,0∈∂f(x) +NC(x). Proof.If (a) holds, thenxminimizesu→f(u) +IC(u). Thus 0∈∂f+IC(x). The latter equals∂f(x) +∂IC(x) =∂f(x) +NC(x), by Theorem 4.8 and Exer. 4.2; thus, (b) holds. Conversely, (b) yields 0∈∂f+IC(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 pointx0inXsuch thatgis continuous atAx0. 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) +IgrA(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 ofx0, we may apply Theorem 4.8 toϕ, for anyζ as above. There resultsα,β∈NgrAx,Axandγ∈∂g(Ax)such thatζ,0= 0,γ+α,β. The normal vectorα,βsatisfies α,u−x+β,Au−Ax0∀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(xi),ζi→ζ,xi→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(xi)ζi,y−xi. 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) = ζ. Letxibe any sequence converging tox(xi=x). Then, by Exer. 4.12, there exist
60 Cours de Francis Clarke : Convex analysis zi∈xi,xandζi∈∂f(zi)such thatf(xi)−f(x) =ζi,xi−x.By part (c), the sequenceζinecessarily converges toζ. Thus we have f(xi)−f(x)−ζ,xi−xζi−ζ,xi−x →0, xi−x xi−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
