1 Theory of convex functions - Princeton University

1 ORF 523 Lecture 7 Spring 2015, Princeton UniversityInstructor: AhmadiScribe: G. HallTuesday, March 1, 2016 When in doubt on the accuracy of these notes, please cross check with the instructor s notes,onaaa. Princeton . edu/ orf523. Any typos should be emailed to the previous couple of lectures, we ve been focusing on the Theory of convex sets. In thislecture, we shift our focus to the other important player in convex optimization, namely, convex functions . Here are some of the topics that we will touch upon: convex , concave, strictly convex , and strongly convex functions First and second order characterizations of convex functions Optimality conditions for convex problems1 Theory of convex DefinitionLet s first recall the definition of a convex functionf:Rn Ris convex if its domain is a convex set and for allx,yin its domain, and all [0,1], we havef( x+ (1 )y) f(x) + (1 )f(y).

2 Figure 1: An illustration of the definition of a convex function1 In words, this means that if we take any two pointsx,y, thenfevaluated at any convexcombination of these two points should be no larger than the same convex combinationoff(x) andf(y). Geometrically, the line segment connecting (x,f(x)) to (y,f(y)) must sit above thegraph off. Iffis continuous, then to ensure convexity it is enough to check the definition with =12(or any other fixed (0,1)). This is similar to the notion of midpoint convexsets that we saw earlier. We say thatfisconcaveif fis Examples of univariate convex functionsThis is a selection from [1]; see this reference for more examples. eax log(x) xa(defined onR++),a 1 ora 0 xa(defined onR++), 0 a 1 |x|a,a 1 xlog(x) (defined onR++)Can you formally verify that these functions are convex ?

3 Strict and strong convexityDefinition functionf:Rn Ris Strictly convexif x,y,x6=y, (0,1)f( x+ (1 )y)< f(x) + (1 )f(y). Strongly convex , if >0such thatf(x) ||x||2is convexity Strict convexity Convexity.(But the converse of neither implication is true.)Proof:The fact that strict convexity implies convexity is see that strong convexity implies strict convexity, note that strong convexity offimpliesf( x+ (1 )y) || x+ (1 )y||2 f(x) + (1 )f(y) ||x||2 (1 ) ||y|| ||x||2+ (1 ) ||y||2 || x+ (1 )y||2>0, x,y,x6=y, (0,1),because||x||2is strictly convex (why?). The claim see that the converse statements are not true, observe thatf(x) =xis convex but notstrictly convex andf(x) =x4is strictly convex but not strongly convex (why?)

4 Examples of multivariate convex functions Affine functions :f(x) =aTx+b(for anya Rn,b R). They are convex , but notstrictly convex ; they are also concave: [0,1], f( x+ (1 )y) =aT( x+ (1 )y) +b= aTx+ (1 )aTy+ b+ (1 )b= f(x) + (1 )f(y).In fact, affine functions are the only functions that are both convex and concave. Some quadratic functions :f(x) =xTQx+cTx+d. convex if and only ifQ 0. Strictly convex if and only ifQ 0. Concave if and only ifQ 0; strictly concave if and only ifQ 0. The proofs are easy if we use the second order characterization of convexity (com-ing up). Any norm: Recall that a norm is any functionfthat ( x) =| |f(x), (x+y) f(x) +f(y) (x) 0, x,f(x) = 0 x= 0 Proof: [0,1],f( x+ (1 )y) f( x) +f((1 )y) = f(x) + (1 )f(y).

5 Where the inequality follows from triangle inequality and the equality follows from thehomogeneity property. (We did not even use the positivity property.) (a) An affine function(b) A quadratic function(c) The 1-normFigure 2: Examples of multivariate convex Convexity = convexity along all linesTheorem functionf:Rn Ris convex if and only if the functiong:R Rgivenbyg(t) =f(x+ty)is convex (as a univariate function) for allxin domain offand ally Rn. (The domain ofghere is alltfor whichx+tyis in the domain off.)Proof:This is straightforward from the definition. The theorem simplifies many basic proofs in convex analysis but it does not usuallymake verification of convexity that much easier as the condition needs to hold foralllines (and we have infinitely many).

6 Many algorithms for convex optimization iteratively minimize the function over statement above ensures that each subproblem is also a convex optimization First and second order characterizations of convexfunctionsTheorem :Rn Ris twice differentiable over an open domain. Then, thefollowing are equivalent:(i)fis convex .(ii)f(y) f(x) + f(x)T(y x), for allx,y dom(f).(iii) 2f(x) 0, for allx dom(f).Intepretation:Condition (ii): The first order Taylor expansion at any point is a global under estimator ofthe (iii): The functionfhas nonnegative curvature everywhere. (In one dimensionf (x) 0, x dom(f).)Proof([2],[1]):We prove (i) (ii) then (ii) (iii).5(i) (ii) Iffis convex , by definitionf( y+ (1 )x) f(y) + (1 )f(x), [0,1],x,y dom(f).

7 After rewriting, we havef(x+ (y x)) f(x) + (f(y) f(x)) f(y) f(x) f(x+ (y x)) f(x) , (0,1]As 0, we getf(y) f(x) fT(x)(y x).(1)(ii) (i) Suppose (1) holds x,y dom(f). Take anyx,y dom(f) and letz= x+ (1 ) havef(x) f(z) + fT(z)(x z)(2)f(y) f(z) + fT(z)(y z)(3)Multiplying (2) by , (3) by (1 ) and adding, we get f(x) + (1 )f(y) f(z) + fT(z)( x+ (1 )y z)=f(z)=f( x+ (1 )y). (ii) (iii) We prove both of these claims first in dimension 1 and then generalize.(ii) (iii) (n= 1) Letx,y dom(f), y > havef(y) f(x) +f (x)(y x)(4)andf(x) f(y) +f (y)(x y)(5)6 f (x)(y x) f(y) f(x) f (y)(y x)using (4) then (5). Dividing LHS and RHS by (y x)2givesf (y) f (x)y x 0, x,y, x6= we lety x, we getf (x) 0, x dom(f).(iii) (ii) (n= 1) Supposef (x) 0, x dom(f). By the mean value version of Taylor stheorem we havef(y) =f(x) +f (x)(y x) +12f (z)(y x)2,for somez [x,y].)

8 F(y) f(x) +f (x)(y x).Now to establish (ii) (iii) in general dimension, we recall that convexity is equivalentto convexity along all lines; ,f:Rn Ris convex ifg( ) =f(x0+ v) is convex x0 dom(f) and v Rn. We just proved this happens iffg ( ) =vT 2f(x0+ v)v 0, x0 dom(f), v Rnand + v dom(f).Hence,fis convex iff 2f(x) 0for allx dom(f). Corollary an unconstrained optimization problemminf(x) Rn,wherefis convex and differentiable. Then, any point xthat satisfies f( x) = 0is a :From the first order characterization of convexity, we havef(y) f(x) + fT(x)(y x), x,y7In particular,f(y) f( x) + fT( x)(y x), f( x) = 0, we getf(y) f( x), y. Remarks: Recall that f(x) = 0 is always a necessary condition for local optimality in anunconstrained problem.

9 The theorem states that for convex problems, f(x) = 0 isnot only necessary, but also sufficient for localand globaloptimality. In absence of convexity, f(x) = 0 is not sufficient even for local optimality ( ,think off(x) =x3and x= 0). Another necessary condition for (unconstrained) local optimality of a pointxwas 2f(x) 0. Note that a convex function automatically passes this Strict convexity and uniqueness of optimal Characterization of Strict ConvexityRecall that a fuctionf:Rn Ris strictly convex if x,y,x6=y, (0,1),f( x+ (1 )y)< f(x) + (1 )f(y).Like we mentioned before, iffis strictly convex , thenfis convex (this is obvious from thedefinition) but the converse is not true ( ,f(x) =x, x R).Second order sufficient condition: 2f(x) 0, x fstrictly convex on.

10 The converse is not true though (why?).First order characterization:A functionfis strictly convex on Rnif and only iff(y)> f(x) + fT(x)(y x), x,y ,x6= There are similar characterizations for strongly convex functions . For example,fisstrongly convex if and only if there existsm >0 such thatf(y) f(x) + Tf(x)(y x) +m||y x||2, x,y dom(f),or if and only if there existsm >0 such that 2f(x) mI, x dom(f). One of the main uses of strict convexity is to ensure uniqueness of the optimal see this Strict Convexity and Uniqueness of Optimal SolutionsTheorem an optimization problemminf(x) ,wheref:Rn Risstrictly convexon and is a convex set. Then the optimal solution(assuming it exists) must be :Suppose there were two optimal solutionsx,y Rn. This means thatx,y andf(x) =f(y) f(z), z.