Cours de Francis Clarke
11 Pages

Cours de Francis Clarke


Downloading requires you to have access to the YouScribe library
Learn all about the services we offer


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



Published by
Reads 30
Language English
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:XR, 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)￿ζ,yxyX.
The geometric content of this condition is clear: the affine functiony￿→f(x) + ￿  ζ,yxis 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 subdifferentialf(x)is a convex set which is closed for the weak topology, since, for eachy, the set ofζsatisfying
Cours de Francis Clarke : Convex analysis
the subgradient inequality is weak closed and convex. It is clear thatfattains a minimum atxif and only if 0f(x). This is but the first of several ways in which the subdifferential acts like a derivative.
4.1 Proposition.Letf:XRbe a convex function, andxdomf. Then  ￿   ∗  f(x) =ζX:f(x;v)￿ζ,vvX.     Iff(x)exists, thenf(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 thatf(1)andf(1)are empty, and that f(x)is a singleton when1<x<+1.
4.2 Exercise.LetxS, whereSis a convex subset ofX. Prove thatIS(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 thatf(0)is the closed unit ball inX. ￿    b) Letζf(x), wherex=0. Prove thatζ,x=xandζ=1.
4.4 Proposition.Letf:XRbe a convex function, and letxdomfbe a point of continuity off. Thenf(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 ￿  ￿  ζ,yrζ,xf(x)(y,r)epif.
We deduce thatf(x)containsζ, and is therefore nonempty. Theorem 2.34 asserts thatfis Lipschitz of rankKon some neighborhoodVofx. Now letζbe any element off(x). The subgradient inequality yields ￿    ζ,yxf(y)f(x)f(y)f(x)K|yx|yV.
  It follows thatζK; thus,f(x)is bounded. This implies thatf(x)compactis weak (see Cor. 3.15).
4.1 The subdifferential
n n 4.5 Corollary.Letf:RRbe a convex function. Then for anyxR,f(x)is a nonempty convex compact set.
Proof.This follows from Corollary 2.35.
k 4.6 Corollary. (Jensen’s inequality)Letϕ:RRbe convex. Then   11     1k ϕg(t)dtϕg(t)dtgL(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¯)￿ζ,yg¯yR.
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:XRandg:XRbe convex functions which admit a point indomfdomgat whichfis continuous. Then we have   f+g(x) =f(x) +g(x)xdomfdomg.
Proof.The inclusionfollows 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 domfdomgat whichfis continuous. The subsets ofX×Rdefined by  ￿   C=int epif,D= (w,t):ζ,wg(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 epifcl epif=   cl int epif(by Theorem 2.2), we deduce ￿  ￿  ξ,w+tξ,u+s(w,t)D(u,s)epif.
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 intCD=Let0/ . xCD. ThenNCD(x) =NC(x) +ND(x).
4.10 Proposition.Letf:XRbe 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,0f(x) +NC(x).   Proof.If (a) holds, thenxminimizesu￿→f(u) +IC(u). Thus 0f+IC(x). The latter equalsf(x) +IC(x) =f(x) +NC(x), by Theorem 4.8 and Exer. 4.2; thus,   (b) holds. Conversely, (b) yields 0f+IC(x), which implies (a).
Adjoint operators.LetXandYbe normed spaces andTL(X,Y). It is clear that ∗ ∗ one defines a unique elementTofL(Y,X)by the formula ￿  ￿  ∗ ∗ ∗ ∗ T y,x=y,T xxX,yY.
Tis called theadjointof the operatorT.
4.11 Theorem.LetYbe a normed space,AL(X,Y), andg:YRa convex function. Let there be a pointx0inXsuch thatgis continuous atAx0. Then the functionf(x) =g(Ax)is convex, and we have
f(x) =Ag(Ax)xdomf.
Proof.It is easily verified thatfis convex, and that any element ofAg(Ax)lies inf(x). We now prove the opposite inclusion. Letϕ:X×YRbe defined by   ϕ(x,y) =g(y) +IgrA(x,y), where grAis the graph ofA: the setx,AxX×Y: xX. 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 ￿  ￿  α,ux+β,AuAx0uX,
∗ ∗ which impliesα=Aβ. We deduceζ=AγAg(Ax), as required.
n 4.12 Exercise. (Mean Value theorem)Letf:RRbe a convex function.
4.1 The subdifferential
n a) We fixx,vRand we setg(t) =f(x+tv)fortR. 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,yR,x=y, there exists z(x,y)such that ￿  f(y)f(x)f(z),yx.
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),xU.
The following result lists some basic facts about the subdifferential of convex func-n tions onR.
n 4.13 Proposition.Letf:RRbe convex. Then a)The graph offis closed:ζif(xi),ζiζ,xix=ζf(x).   n b)For any compact subsetSofR, there existsMsuch thatζMζ f(x),xS. c)For anyx, for anyε>0, there existsδ>0such that
  yx<δ=f(y)f(x) +εB.
d)fis differentiable atxif and only iff(x)is a singleton. e)fis continuously differentiable in an open subsetUif and only iff(x)reduces to a singleton for everyxU.
n Proof.Consider the situation described in (a). For anyyR, we have, for eachi, ￿  f(y)f(xi)￿ζi,yxi. Taking limits, and bearing in mind thatfis continuous ￿  (Cor. 2.35), we obtainf(y)f(x)￿ζ,yx; 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 off(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 thatf(x)is the singletonf(x).   Conversely, suppose thatf(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   ￿  zixi,xandζif(zi)such thatf(xi)f(x) =ζi,xix.By part (c), the sequenceζinecessarily converges toζ. Thus we have ￿  ￿     f(xi)f(x)ζ,xixζiζ,xix 0,     xix xix
whencef(x)exists and equalsζ. The final assertion follows immediately from (c) and (d).
Strict convexity.LetUbe a convex subset ofX, and letf:URbe given. We say thatfisstrictly convexif the defining inequality of convexity is strict whenever it can be:   x,yU,x=y,t(0,1) =f(1t)x+ty<(1t)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:URbe convex. a) Prove thatfis strictly convex if and only if ￿  x,yU,x=y,ζf(x) =f(y)f(x)>ζ,yx.
b) Deduce that iffis strictly convex, thenfis injective, in the following sense:
4.2 Conjugate functions
Letf:XRbe a proper function (that is, domf=/0).Theconjugate function ∗ ∗f:XRoffis defined by ￿  f(ζ) =supζ,xf(x). xX Note that the properness offrules out the possibility thatfhas the value; we ∗ ∗ ∗∗ say then thatfis well-defined. Whenfis itself proper, thebiconjugate f:XRoffis defined as follows: ￿  ∗∗ ∗ f(x) =supζ,xf(ζ). ζX