Second-order conditions:Assume that fis twice differentiable(its Hessian or second derivative V2fexists at each point in dom(f),which is open).Then fis convex if and only if dom(f)is convex and its Hessian is positive semidefinite: Vf≥0，for all x∈dom(f) as:f(y)=f(x)+Vf(x)(v-x)+(y-x)V2f(=)(v-x) For a function on R,this reduces to the simple condition f"(x)>0(and dom(f)convex,i.e.,an interval),which means that the derivative is nondecreasing. The condition V2f-0 can be interpreted geometrically as the requirement that the graph of the function have positive (upward)curvature at x. For scalar function,signed curvature is:k=( 25/154
▶ Second-order conditions: Assume that f is twice differentiable (its Hessian or second derivative ∇2 f exists at each point in dom( f ), which is open). Then f is convex if and only if dom( f ) is convex and its Hessian is positive semidefinite: ∇2 f 0, for all x ∈ dom( f ) as: f (y) = f (x) + ∇f (x) T (y − x) + 1 2 (y − x) T∇2 f (z)(y − x) ▶ For a function on R, this reduces to the simple condition f ′′(x) ≥ 0 (and dom( f ) convex, i.e., an interval), which means that the derivative is nondecreasing. ▶ The condition ∇2 f 0 can be interpreted geometrically as the requirement that the graph of the function have positive (upward) curvature at x. For scalar function, signed curvature is: k = f ′′ (1+f ′2) 3/2 25 / 154
函数的上方图epigraph The graph of a function f:R">R is defined as: {(x,f(x)rx∈domf乃 It is a subset of R+1 The epigraph of a functionf:R"R is defined as: epif={(x,t)lx E domf,f(x)st) It is a subset of R"+1.'epi'means'above' Epigraph f) Epigraph Lf) daaf刀 du门 dom(f) 26/154
函数的上方图 epigraph ▶ The graph of a function f : R n 7→ R is defined as: {(x, f (x))|x ∈ dom f} It is a subset of R n+1 . ▶ The epigraph of a function f : R n 7→ R is defined as: epi f = {(x, t)|x ∈ dom f, f (x)≤t} It is a subset of R n+1. ’epi’ means ’above’ 26 / 154
凸函数台epigraph is convex If CE R"is convex and f:CR,then the following are equivalent: (a)epifis convex set (b)For all A1,...,and=1,and points xiEC,i=1,2,...,n,we have: (②立 (c)For any x,y∈Candλ∈0,1g f(Ax+(1-)y)≤入fx)+(1-)fy) 27/154
凸函数 ⇔ epigraph is convex ▶ If C ∈ R n is convex and f : C 7→ R, then the following are equivalent: (a) epi f is convex set (b) For all λ1, . . . , λn and Pn i=1 λi = 1, and points xi ∈ C, i = 1, 2, . . . , n, we have: f Xn i=1 λi xi ! ≤ Xn i=1 λi f (xi) (c) For any x, y ∈ C and λ ∈ [0, 1], f (λ x + (1 − λ)y) ≤ λ f (x) + (1 − λ) f (y) 27 / 154
证明： 1 To see that (a)implies(b),we note that,if for all iE 1,2, ...n,(xif(xi))E epif.As set epifis convex,we have: 立Aa,a-(区，言e which implies that: 店= This establishes(b).It is obvious that(b)implies(c). 28/154
证明： 1 To see that (a) implies (b), we note that, if for all i ∈ 1, 2, . . . , n, (xi , f (xi)) ∈ epi f. As set epi f is convex, we have: Xn i=1 λi(xi , f (xi)) = Xn i=1 λi xi , Xn i=1 λi f (xi) ! ∈ epi f which implies that: f Xn i=1 λi xi ! ≤ Xn i=1 λi f (xi) This establishes (b). It is obvious that (b) implies (c). 28 / 154
2 To to show that(c)implies(a),suppose that (xi,a),(x2,2)∈epifand入∈[0,1.Then: A(x1,3)+(1-A)(x2,2)=(x1+(1-)x2,1+(1-入)2) Sincef(xi)<zi,we have: 入f(x1)+(1-)f(x2)≤入31+(1-入)2 By the assumption(c)that fis convex function,we have: f(x1+(1-入)x2)≤λf(x)+(1-入)f(x2) Then f(入1+(1-X)x2)≤Xz1+(1-)2 This shows that A(x1,z1)+(1-A)(x2,=2)E epif 29/154
2 To to show that (c) implies (a), suppose that (x1,z1),(x2,z2) ∈ epi f and λ ∈ [0, 1]. Then： λ(x1,z1)+(1−λ)(x2,z2) = (λx1+(1−λ)x2, λz1+(1−λ)z2) Since f (xi) ≤ zi , we have: λ f (x1) + (1 − λ) f (x2) ≤ λz1 + (1 − λ)z2 By the assumption (c) that f is convex function, we have: f (λx1 + (1 − λ)x2) ≤ λ f (x1) + (1 − λ) f (x2) Then f (λx1 + (1 − λ)x2) ≤ λz1 + (1 − λ)z2 This shows that λ(x1,z1) + (1 − λ)(x2,z2) ∈ epi f 29 / 154