+Convex Functions, Convex Sets and Quadratic Programs Sivaraman Balakrishnan+Outline  Convex sets  Definitions  Motivation  Operations that preserve set convexity  Examples  Convex Function  Definition  Derivative tests  Operations that preserve convexity  Examples  Quadratic Programs+Quick definitions  Convex set  For all x,y in C: θx + (1-θ) y is in C for θ \in [0,1]  Affine set  For all x,y in C: θx + (1-θ)y is in C  All affine sets are also convex  Cones  For all x in C: θx is in C θ>= 0  Convex cones: For all x and y in C, θ1x + θ2 y is in C+Why do we care about convex and affine sets?  The basic structure of any convex optimization  min f(x) where x is in some convex set S  This might be more familiar  min f(x) where gi(x) <= 0 and hi(x) = 0  gi is convex function and hi is affine  Cones relate to something called Semi Definite Programming which are an important class of problems+Operations that preserve convexity of sets  Basic proof strategy  Ones we saw in class – lets prove them now  Intersection  Affine  Linear fractional  Others include  Projections onto some of the coordinates  Sums, scaling  Linear perspective+Quick review of examples of convex sets we saw in class  Several linear examples (halfspaces (not affine), lines, points, Rn)  Euclidean ball, ellipsoid  Norm balls (what about p < 1?)  Norm cone – are these actually cones?+Some simple new examples  Linear subspace – convex  Symmetric matrices - affine  Positive semidefinite matrices – convex cone  Lets go over the proofs !!+Convex hull  Definition  Important lower bound property in practice for non-convex problems – the two cases  You’ll see a very interesting other way of finding “optimal” lower bounds (duality)+Convex Functions  Definition  f(θx + (1-θ)y) <= θf(x) + (1-θ) f(y)  Alternate definition in terms of epigraph  Relation to convex sets+Proving a function is convex  It’s often easier than proving sets are convex because there are more tools  First order  Taylor expansion (always underestimates)  Local information gives you global information  Single most beautiful thing about convex functions  Second order condition  Quadratics  Least squares?+Some examples without proofs  In R  Affine (both convex and concave function) unique  Log (concave)  In Rn and Rmxn  Norms  Trace (generalizes affine)  Maximum eigenvalue of a matrix  Many many more examples in the book  log sum exp,powers, fractions+Operations that preserve convexity  Nonnegative multiples, sums  Affine Composition f(Ax + b)  Pointwise sup – equivalent to intersecting epigraphs  Example: sum(max1…r[x])  Pointwise inf of concave functions is concave  Composition  Some more in the book+Quadratic Programs  Basic structure  What is different about QPs?  Lasso