1©2008-2010 Carlos Guestrin1Convex FunctionsOptimization - 10725Carlos GuestrinCarnegie Mellon UniversityMarch 17th, 20102©2008-2010 Carlos GuestrinConvex Functions Function f:RnR is convex if Domain is convex  Generalization: Jensen’s inequality: Strictly convex function:23©2008-2010 Carlos GuestrinConcave functions Function f is concave if  Strictly concave: We will be able to optimize:4©2008-2010 Carlos GuestrinProving convexity for a very simple example f(x)=x235©2008-2010 Carlos GuestrinFirst order condition If f is differentiable in all dom f  Then f convex if and only if dom f is convex and 6©2008-2010 Carlos GuestrinSecond order condition (1D f) If f is twice differentiable in dom f Then f convex if and only if dom f is convex and Note 1: Strictly convex if: Note 2: dom f must be convex f(x)=1/x2 dom f = {x∈R|x≠0}47©2008-2010 Carlos GuestrinSecond order condition (general case) If f is twice differentiable in dom f Then f convex if and only if dom f is convex and Note 1: Strictly convex if:8©2008-2010 Carlos GuestrinQuadratic programming  f(x) = (1/2) xTAx + bTx + c Convex if: Strictly convex if: Concave if: Strictly concave if:59©2008-2010 Carlos GuestrinSimple examples Exponentiation: eax convex on R, any a∈R Powers: xaon R++ Convex for a≤0 or a≥1 Concave for 0≤a≤1 Logarithm: log x Concave on R++ Entropy: -x log x Concave on R+ (0 log 0 = 0)10©2008-2010 Carlos GuestrinA few important examples for ML Every norm on Rnis convex Log-sum-exp: Convex in Rn Log-det: Concave in Sn++614©2008-2010 Carlos GuestrinRestriction of a convex function to a line f:RnR convex if and only if g(t) (RR) is convex in t For all x0∈dom f, v∈Rn dom g = Can make it much easier to check if f is convex, e.g., f(X) = log det X proof in the book…15©2008-2010 Carlos GuestrinOperations that preserve convexity Many operations preserve convexity Knowing them will make your life much easier when you want to show that something is convex Examples in next few slides Simplest: Non-negative weighted sum: If all fi’s are convex, then f is If all fi’s are concave, then f is Example: integral of f(x,y) Affine mapping: f:RnR, A∈Rnxm, b∈Rm g(x) = f(Ax+b) dom g = If f is convex, then If f is concave, then716©2008-2010 Carlos GuestrinPointwise maximum and supremum If fi’s are convex, then Piecewise linear convex functions: Fundamental for POMDPs For x in a convex set C, sum of the r largest elements: Sort x, pick r largest components, sum them: Maximum eigenvalue of symmetric matrix X∈Rnxn, f:RnxnR f(X) = 17©2008-2010 Carlos GuestrinPointwise maximum of affine functions: general representation We saw: convex set can be written as intersection of (infinitely many) hyperplanes: C convex, then Convex functions can be written as supremum of (infinitely many) lower bounding hyperplanes: f convex function, thenDiscussion on this slide subject to mild conditions on sets and functions, see book818©2008-2010 Carlos GuestrinComposition: scalar differentiable, real domain case How do I prove convexity of log-sum-exp-positive-weighted-sum-monomials? :)  If h:RkR and g:RnRk, when is f(x) = h(g(x)) convex (concave)? dom f = {x ∈ dom g| g(x) ∈ dom h} Simple case: h:RR and g:RnR, dom g = Rndom h = R, g and h differentiable E.g., g(x)=xT∑x, ∑ psd, h(y) = ey Second derivative: f’’(x) = h’’(g(x))g’(x)2+ h’(g(x))g’’(x) When is f’’(x)≥0 (or f’’(x)≤0) for all x? Example of sufficient (but not necessary) conditions: f convex if h is convex and nondecreasing and g is convex f convex if h is convex and nonincreasing and g is concave f concave if h is concave and nondecreasing and g is concave f concave if h is concave and nonincreasing and g is convex19©2008-2010 Carlos GuestrinComposition: scalar, general case If h:RkR and g:RnRk, when is f(x) = h(g(x)) convex (concave)? dom f = {x ∈ dom g| g(x) ∈ dom h} Simple case: h:RR and g:RnR, general domain and non-differentiable Example of sufficient (but not necessary) conditions: f convex if h is convex and h nondecreasing and g is convex f convex if h is convex and h nonincreasing and g is concave f concave if h is concave and h nondecreasing and g is concave f concave if h is concave and h nonincreasing and g is convex nondecreasing or nonincreasing condition on extend value extension of h is fundamental counter example in the book if nondecreasing property holds for h but not for h, the composition no longer convex If h(x)=x3/2with dom h = R+, convex but extension is not nondecreasing If h(x)=x3/2for x≥0, and h(x)=0 for x<0, dom h = R, convex and extension is nondecreasing~~~~~920©2008-2010 Carlos GuestrinVector composition: differentiable If h:RkR and g:RnRk, when is f(x) = h(g(x)) convex (concave)? dom f = {x ∈ dom g| g(x) ∈ dom h} Focus on f(x) = h(g(x)) = h(g1(x), g2(x),…, gk(x)) Second derivative: f’’(x) = g’(x)T ∇2h(g(x))g’(x) + ∇h(g(x)) g’’(x) W hen is f’’(x)≥0 (or f’’(x)≤0) for all x? Example of sufficient (but not necessary) conditions: f convex if h is convex and nondecreasing in each argument, and giare convex f convex if h is convex and nonincreasing in each argument, and giare concave f concave if h is concave and nondecreasing in each argument, and giare concave f concave if h is concave and nonincreasing in each argument, and giare convex Back to log-sum-exp-positive-weighted-sum-monomials dom f = Rn++ , cij>0, aij≥1 log sum exp convex 21©2008-2010 Carlos GuestrinMinimization If f(x,y) is convex in (x,y) and C is a convex set, then: Norm is convex: ||x-y|| minimum distance to a set C is convex:1022©2008-2010 Carlos GuestrinPerspective function If f is convex (concave), then the perspective of f is convex (concave): t>0, g(x,t) = t f(x/t) KL divergence: f(x) = -log x is convex Take the perspective: Sum over many pairs (xi,ti)23©2008-2010 Carlos GuestrinQuasiconvex functions Unimodal functions are not always convex But they are (usually) still easy to optimize: Quasiconvex function: All sublevel sets are convex, for all α∈R: Equivalent definition: max of extremes is higher than function Applications include