Convex Functions - USM

1 Jim LambersMAT 419/519 Summer Session 2011-12 Lecture 6 NotesThese notes correspond to Section in the FunctionsWe are now prepared describe the usefulness of the Convex sets introduced in the previous certain Functions defined on Convex sets, it can be very easy to determine whether they have aglobal minimizer, and if so, to compute it. A class of Functions that has this property is introducedthrough the following Rnbe a Convex set, and letf:C R. Thenf(x) isconvexonCiff( x+ (1 )y) f(x) + (1 )f(y)for allx,y Cand [0,1].

2 Iff( x+ (1 )y)< f(x) + (1 )f(y)for allx,y C,x6=y, and (0,1), then we say thatf(x) isstrictly also say thatf(x) isconcaveonCiff( x+ (1 )y) f(x) + (1 )f(y)for allx,y Cand [0,1]. Iff( x+ (1 )y)> f(x) + (1 )f(y)for allx,y C,x6=y, and (0,1), then we say thatf(x) isstrictly , the graph of a Convex function lies on or below any chord between two points on thegraph. For a single-variable functionf(x), the following two other characterizations of convexityare helpful:1. The graph of a Convex functionf(x) lies above each of its tangent lines.

3 That is, iff(x) isconvex on an intervalIandx1,x2 I, thenf(x1) +f (x1)(x2 x1) f(x2).12. Iff(x) is twice differentiable on an intervalI, thenf(x) is Convex onIif and only iff (x) 0onI. Furthermore, iff (x)>0 onI, thenf(x) is strictly Convex , though the converse is notnecessarily true. Similarly,f(x) is concave if and only iff (x) 0 onI, and strictly concaveiff (x)<0 (x) =x2. Thenf(x) is strictly Convex onR, asf (x) = 2 Rnbe a fixed vector, and letf:Rn Rbe defined byf(x) = (a x) , by the linearity of the dot product,f( x+ (1 )y) = (a [ x+ (1 )y)2= [ a x+ (1 )a y] the convexity of (t) =t2from the previous example, we have[ t1+ (1 )t2]2 t21+ (1 )t22,witht1=a xandt2=a y.]

4 We conclude thatf( x+ (1 )y) f(x) + (1 )f(y),and thereforef(x) is Convex essential consequence of convexity is given by the following (x) is a Convex function defined on an open Convex setC, thenf(x) is definition of a Convex function can be generalized to apply to Convex combinations of anynumber of Rnbe a Convex set, and letf:C Rbe Convex onC. If 1, 2,.., k [0,1], ki=1 i= 1, andx(1),x(2),..,x(k) C, thenf(k i=1 ix(i)) k i=1 if(x(i)).Iff(x) is strictly Convex onCand i>0 fori= 1,2,..,n, then the above inequality holds, withequality if and only if all of thex(i)are main benefit of knowing whether a function is Convex , as far as optimization is concerned,is provided by the following Rnbe a Convex set, and letf:C Rbe Convex onC.

5 Then any localminimizer off(x) if a global minimizer. Furthermore, iff(x) is strictly Convex onC, then anylocal minimizer off(x) is the unique strict global minimizer off(x) difficulty with applying the preceding theorem is that it can be very difficult to determinewhether a function is Convex using the definition of convexity directly. The following theorem is afirst step toward the development of simpler methods for checking Rnbe Convex , and letf:D Rhave continuous first partial derivatives onD. Thenf(x) is Convex onDif and only iff(x) + f(x) (y x) f(y)for allx,y D.

6 In addition,f(xis strictly Convex onDif and only iff(x) + f(x) (y x)< f(y)for allx,y D,x6= following corollary to the preceding theorem makes it very easy to classify critical points ofconvex Rnbe Convex , and letf:D Rbe Convex and have continuous first partialderivatives onD. Then any critical point off(x) inDis a global minimizer off(x) following theorem is very useful for determining whether a function is Convex or Rnbe open and Convex , and letf:C Rhave continuous second partialderivatives If the HessianHf(x) off(x) is positive semidefinite onC, thenf(x) is Convex IfHf(x) is positive definite onC, thenf(x) is strictly Convex (x,y,z) = 2x2+y2+z2+ function has the HessianHf(x,y,z) = 4 0 00 2 20 2 2 ,which has minors 1= 4, 2= 8, and 3= 0, soHf(x,y,z) is positive semidefinite.)

7 Therefore,f(x,y,z) is Convex onR3. We cannot conclude thatf(x,y,z) is strictly Convex onR3, asHf(x,y,z)is not positive definite, and in fact it is not strictly Convex , asf(x,y,z) can be rewritten asf(x,y,z) = 2x2+ (y+z)2,3which shows thatf(x,y,z) = 0 along the linex= 0,y= z. The graph of a strictly convexfunction must lie strictlybelowthe interior of a chord between any two points on the graph, whichcannot occur if the graph contains any line partial converse of the preceding theorem holds: iff(x) is Convex onC, thenHf(x) is positivesemidefinite onC.

8 However, iff(x) is strictly Convex onC, thenHf(x) is not necessarily positivedefinite; it may be positive (x) =x4. Thenf(x) is strictly Convex onR, but its second derivativef (x) = 12x2is not positive definite, asf (0) = following theorem also is very useful for determining whether a function is Convex , byallowing the problem to be reduced to that of determining convexity for several simpler Iff1(x),f2(x),..,fk(x) are Convex Functions defined on a Convex setC Rn, thenf(x) =f1(x) +f2(x) + +fk(x)is Convex onC.

9 Furthermore, if at least one of the functionsfi(x),i= 1,2,..,k, is strictlyconvex onC, thenf(x) is strictly Convex Iff(x) is Convex on a Convex setC Rn, and if >0, then f(x) is Convex Iff(x) is strictly Convex on a Convex setC Rn, and if >0, then f(x) is strictly Iff(x) is Convex on a Convex setC Rn, and ifg(y) is an increasing Convex function definedon the range off(x, then the compositiong(f(x)) is Convex Iff(x) is strictly Convex on a Convex setC Rn, and ifg(y) is a strictly increasing convexfunction defined on the range off(x, then the compositiong(f(x))))

10 Is strictly Convex (x,y,z) =ex2+y2+z2. This function is strictly Convex onR3, as it is a compositionof a strictly increasing Convex functiong(y) =eywith a functionh(x,y,z) =x2+y2+z2that hasa positive definite HessianHh(x,y,z) = 2I, and is therefore strictly Convex (x) :Rn Rbe defined byf(x) =k i=1ciea(i) x,wherec1,c2,..,ck>0 anda(1),a(2),..,a(k) is becausef(x) is a positive linearcombination of compositions of an increasing functiong(y) =eyand a linear function, which (x,y) =x2 4xy+ 5y2 ln(xy), x,y > (x,y) is strictly Convex on the first quadrantQ1={(x,y) R2|x,y >0},because it is a positive linear combination of the strictly Convex functionf1(x,y) =x2 4xy+ 5y2,for whichHf1(x,y) =[2 4 410]is positive definite, in view of its minors 1= 2 and 2= 4,and the strictly Convex functionf2(x,y) = ln(xy) = lnx lny,for whichHf2(x,y)