Understanding Convex Optimization Functions and Sets

CSE203B Convex Optimization: Lecture 3: Convex Function CK Cheng Dept. of Computer Science and Engineering University of California, San Diego 1

Convex Problems and Convex Functions ?0? , ? ?? min ? Subject to ??? 0,? = 1, ,? ?? = 0,? = 1, ,? We use functions to define the objective function and qualify the constraints. For a convex problem, the desired features: Objectives ?0(?): Convex function Constraints: Convex functions, ??(?): Convexity is a sufficient condition for a convex set ?(?): Linear equation 2

Outlines Examples: Softmax and Mutual Entropy 1. Definition 1. Convex Function 2. Examples 3. Views 2. Conditions of Convexity 1. First Order Condition 2. Second Order Condition 3. Operations that Preserve the Convexity 1. Pointwise Maximum 2. Partial Minimization 4. Conjugate Function 5. Log-Concave, Log-Convex Functions 3

Examples: Softmax Given a set of numbers, ?? ?,? = 1, ,?, calculate functions ?1?1,?2, ,?? = ?????? ?2?1,?2, ,?? = log ????/? ?3?1,?2, ,?? = ??????/?/ ????/? 4

Examples: Entropy and Kullback-Leibler Divergence Negative Entropy: ?(?) = ?????,? ?+ Kullback-Leibler: ?? ?? ??+ ??, ????,? = ???log ?. where ?,? ?++ 5

Outlines 1. Definition 1. Convex Function Definition and Relation to Convex Set 2. Examples 1. Norms 2. Entropy 3. Linear functions 4. Determinant of matrices 5. Maximum of functions 3. Views of Functions and Related Hyperplanes 6

1.1. Convex Function Definition ?:?? ? is convex if ??? ? is a convex set and ? ?? + 1 ? ? ?? ? + 1 ? ?(?) ?,? ??? ?,0 ? 1 7

1.1. Definition: Convex Functions vs Convex Sets Theorem: Given ? = ? ? ? ? If function ? ? is convex,then ? is a convex set. Proof: We prove by the definition of convex set. For every ?,? ?,i.e.? ? ?,? ? ?, We want to show that ? + ?? ?, + ? = 1,?,? 0. We have ? ?? + ?? ?? ? + ?? ? (? ?? ??????) ?? + ?? = ? + ? ? = ? (? + ? = 1) (?,? 0) Thus ? + ?? ? Remark: Convex function => Convex Set ?(?) ?=> Convex Set ?(?) ?=> ? 8

1.2. Convex Function Examples ?:?? ? is convex if ??? ? is a convex set and ? ?? + 1 ? ? ?? ? + 1 ? ?(?) ?,? ??? ?,0 ? 1 Example on R: Convex Functions Linear: ?? + ? ?? ? for any ?,? ? Exponential: ??? Power: ?? ?? ?++ for ? 1 or ? 0 ?? ?? ? Concave Functions Affine: ?? + ? ?? ? for any ?,? ? Power: ?? ?? ?++ Logarithm: ???? ?? ?++ for any ? ? for ? 1 for 0 ? 1 9

1.2. Convex Function Examples Concave Functions: Log Determinant: ? ? = logdet?,??? ? = S++ Proof: Let ? ? = ? ? + ?? ? ?? ? ? = ?????? (? + ??) = ??????? + ??????(? + ?? 1 = ??????? + ?=1 ???(1 + ???) ??:?????????? ?? ? 1 ? is concave in ? ? is concave ? 2?? 1 2) ? 2?? 1 2 10

1.2. Convex Function Examples Example on ??: Linear function: ? ? = ??? + ? Norms: ??= ?=1 ? = max 1? ??? ? 1; ? ?? |??| ? Example on ?? ?: Linear function: ? ? = ?? ??? = ?=1 Spectral (max singular value): ? ? = ?2= ????? = (??????? ) ? ?=1 ? ?????? 12 11

1.2. Convex function examples: norm, max, expectation Norm: If ?:?? ? is a norm and 0 ? 1 ? ?? + 1 ? ? ? ?? + ? 1 ? ? = ??(?) + (1 ?)?(?) Max function: ? ? = max ? ? ?? + 1 ? ? = max ? ?max ? = ?? ? + 1 ? ? ? for 0 ? 1 Probability: (Expectation) If ? ? is convex with ? ? a probability at ?, i.e.? ? 0, ? and ?(?)?? = 1 Then ? ?? ?? ? , where ?? = ?? ? ?? ??(?) = ?(?)? ? ?? triangle inequality scalability ? ??,? = ?1,?2, ,?? ???+ 1 ? ?? ??+ 1 ? max ?? ? 12

1.3 Views of Functions and Related Hyperplanes Given ? ? ,? ??, we plot the function in ?? and ??+1 spaces. 1. Draw function in ?? space Equipotential surface: tangent plane?? ??? ? = 0 at ? 2. Draw function in ??+1 space 2.1 Graph of function: {(?, )|? ??? ?, = ? ? } ?????????? (h = ?? ??? ? + ?( ?)) ? ? ?? ?? 1 = 0 ? ? Example: ? ? = ?2.We show the hyperplane with ?? ? 2.2. Epigraph: epi ?: {(x,?)|? ??? ?,? ? ?} A function is convex iff its epigraph is a convex set. Example: ? ? = max ??? | ? = 1 ? ,??? ??? ??????. Since epi ? is the intersect of epi ??, epi ? is convex. Thus, function ? is convex. 13

1.3 Views of Functions: Example ??.? ?1,?2 = ??1 1. Equipotential surface 2,?,? > 0. 2+ ??2 ?2 ?1 2. {(?, )|? ??? ?, = ? ? } ? ?2 ?1 3. Epigraph 14

2. Conditions of Convexity: First Order Condition Defintion: ? is differentiable if ???? is open and ??(?) (?? ? ??1,?? ? ??2, ,?? ? ???)? exists at each ? ???? Theorem:Differentiable ? with convex domain is convex iff ? ? ? ? + ?? ?T? ? , ?,? ???? Proof => If ? is convex ? ?? 1 ? ? ? + ?? ? ? 1 ? ? + ?? , 0 ? 1 ? ? ? ? ? ? ? + ? ? ? ? ? ? ? 1 ?(? ? + ? ? ? = ?? ? ? ? ? ?? ? 0 <= ????? ? ? ? ? + ?? ?T? ? , ?,? ???? ??? ? = 1 ? ? + ?? where ? ? ? ? + ?? ?T? ? ? ? ? ? + ?? ?T? ? Thus 1 ? ? ? + ?? ? ?(?) ?(?) ? ? ) 15

2. Conditions: Second Order Condition Definition: ? is twice differentiable if ???? is open and the Hessian ?2? ? ?? ?2? ??? ?2? ? ??????, ?,? = 1, ,? exists at each ? ???? Theorem:Twice Differentiable ? with convex domain is convex iff ?2? ? 0, ? ???? Proof: Using Lagrange remainder, we can find a z ? ? + ?(? ?) = ? ? + ?? ??? ? ? +1 2?2? ???2? ? ? ? , 0 ? 1,? is between ? and ? + ?(? ?) Since the last term is always positive by assumption, the first order condition is satisfied. 16

2. Conditions: Second Order Condition Example: Negative Entropy: ? ? = ?log?,? ?++ ? ? =? Since ? ?++,? ? > 0 ? ? is convex ?+ log? = 1 + log?,? ? =1 ? Show the plot of ?log? Remark: 1st order condition can be used to design and prove the property of opt. algorithms. 2nd order condition implies the 1st order condition 2nd order condition can be used to prove the convexity of the functions. 17

2. Conditions: Examples Quadratic Function: ? ? =1 ?? ? = ?? + ?, ?2? ? = ? Least Square: ? ? = ?? ?2 ?? ? = 2???? ? , ?2? ? = ??? Quadratic over linear: ? ?,? =?2 2???? + ??? + ?,? ?? 2 ?, ? > 0 ? 2? ?, ?2 2 ? 2? ?2 ?? ?,? = , ?2 2? ?2 2?2 ?3 2 ?3 ? ? ? ?2? ? = = ? 18

2. Conditions: Examples ? ??? (Smooth max of softmax Log-sum-exp: ? ? = log ?=1 function) ?2? ? = 1?????? ? ???2? ? ? = 1 1 (1??)2 ???,??= ??? ? ?? ?=1 for all ? ?? (Cauchy-Schwarz inequality) 1 ? 2?? ?=1 ? 2] 0, 1??2[ ?=1 ?? ???? Thus, ?(?) is a convex function Cauchy-Schwarz inequality: ??? ??? ???2, ??= Proof 1: Let ? = ? ?? ? We have ???2 ???2??? Proof 2: By induction ??,??= ?? ?? ?? ??, or ? = ? +??? ???? ???2 ???2??? = ???2 ??? a?a = zTz + 19

3. Operations that preserve convexity Nonnegative multiple: ??, where ? 0, ? is convex Sum: ?1+ ?2, where ?1,??? ?2 are convex Composition with affine function: ? ?? + ? , where ? is convex Proof: ??2? ?? + ? = ????2? ?|? = ?? + ? ? E.g. ? ? = ?=1 ??? ? = {?|?? ? ? = ?? + ? (if ? is twice differentiable) ?log ?? ?? ???, ?? < ??,? = 1, ,?} 20

3. Operations that preserve convexity Pointwise maximum: ? ? = max{?1? , ,??(?)},??are convex Pointwise supremum: ? ? = sup ? ? ?(?,?), where ? ?,? is convex in ? and ? is an arbitrary set Examples ??? = sup ? ? ???, for an arbitrary set ? ? ? = sup ? ? ????? = sup ? ? ,for an arbitrary set ? ?2=1 ????, ? ?? 21

3. Operations that preserve convexity: Dual norm Example: ? ? = max ?2 1??? ? ? = max ?1 1??? ?? 1??? ? ? = max 22

3. Operations that preserve convexity: max function Theorem: Pointwise maximum of convex functions is convex Given ? ? = max ?1? ,?2? and ??? ? = ??? ?1 ??? ?2 is convex, then ? ? is convex. Proof: For 0 ? 1, ?,? ??? ? ? ?? + 1 ? ? = max{?1?? + 1 ? ? ,?2?? + 1 ? ? } max{??1?) + 1 ? ?1(? , ??2?) + 1 ? ?2(? } ?max{?1?), ?2(?)} + 1 ? max {?1(? ,?2(?)} = ?? ? + 1 ? ? ? i.e. ? ?? + 1 ? ? ?? ? + 1 ? ? ? Thus, function ? ? is convex. , where ?1 and ?2 are convex 23

3. Operations that preserve convexity: minimization Theorem: Partial minimization If? ?,?is convex in ? and ?, and a set ?is convex Then? ? = min ? ?? ?,?is convex. ? ??(?1,?)} and ?2 {?|min Proof:Let?1 {?|min we can write ?? ?1 + 1 ? ? ?2 = ?? ?1,?1 + 1 ? ?(?2,?2) ?(??1+ 1 ? ?2,??1+ 1 ? ?2) ? ?? ?????? min ? ?? ??1+ 1 ? ?2,? = ?(??1+ 1 ? ?2) i.e. we have ?? ?1 + 1 ? ? ?2 ? ??1+ 1 ? ?2 Therefore, ? ? = min ? ?(?(?2,?)}, ? ?? ?????? ? ?? ?,?is convex. 24

3. Operations that preserve convexity Examples for Partial Minimization ? ? ? ?? ? ? Given ? ?,? = ?? ?? ? ?? ? ? ?,? ?+ ?, ?+? ? ??,? ??,? ?+ ?+ ?(?,?) = ??? ??+???, Let ? ? = min ? ?+:?????? ???????of matrix ?. (Drazin inverse, or generalized inverse) We can claim that function ? ? is convex. Proof: (1) ? ?,? is convex (2) ? ?? where ?? is a convex non-empty set (3) Therefore, ?(?) is convex, i.e. ? ??+?? 0 25

3. Operations that preserve convexity Composition: Given ?:?? ? ??? :? ?,we set ? ? = (? ? ) f is convex if g convex, h convex, nondecreasing g concave, h convex, nonincreasing f is concave if g convex, h concave, nonincreasing g concave, h concave, nondecreasing Proof : for ?=1 ? ? = ? ? ? ?2+ ? ? ? ? Ex1: exp?(?) is convex if g is convex Ex2: 1/? ? is convex if g is concave and positive Note that we set ? = if ? ??? , h is convex ? = if ? ??? , h is concave 26

3. Operations that preserve convexity Show that ? ?? + 1 ? ? for the case that g, h are convex, and is nondecreasing (1) g is convex ? ?? + 1 ? ? ?? ? + 1 ? ?(?) (2) h is nondecreasing: From (1), we have ? ? ? + 1 ? (? ? ) ? ?? + 1 ? ? (3) h is convex ?? ? + 1 ? ? ? ?? ? + 1 ? ? ? (4) From (2) & (3) ? ? ? + 1 ? ? ? ? ?? + 1 ? ? + 1 ? ? ? ? ? ? 27

4. Conjugate Functions The setting of conjugate functions starts from the following problem (which may not be convex) ??? subject to ?(?) ? 0 We convert to a function of ? ? ? ??? ??? ? The conjugate function is ? ? = sup ??? ?(?) ? In the class, we interchange min and inf; max and sup to simplify the notation. 28

4. Conjugate Functions Given ?:?? ?, we have ? :?? ? ? ? = ? ??? ???? ? ? ; ( ? ? = Constraint: ? ?? for which the supremum is finite (bounded) ? ? is called the conjugate of function f Theorem : ? (?) is convex (pointwise maximum) ? ??? ? ??? + ?(?)) sup min Proof : ? ??1+ 1 ? ?2 = sup ?? ?(?) ??1+ 1 ? ?2 ? ?? ?? ? ?? 1 ? ?(?)) sup ??1 + sup ( 1 ? ?2 ? ? = ?? ?1 + 1 ? ? ?2 Remark: ? (?) is convex even if ?(?) is not convex 29

4. Conjugate Functions Suppose we have a pair ?, ?, such that ? ? = ?? ? ? ? (exercise 3.40) And the supporting hyperplane : ??? = ? ? ? , we can show that ? = ?? ? = ? ( ?) ?? 1 Ex. ? ? = ?2 2?, ? ? ? ? = sup ?? ?2+ 2?,? ? ? 30

4. Conjugate Functions One way to view conjugate function ? ? = ? ??? ???? ?(?) x : negative slack y : shadow price (loss) to accommodate the slack f*(y): balance between price slack product (???) and objective function ? ? . Remark: When ? ? is unbounded, the shadow price ? is not reasonable. sup 31

4. Conjugate Functions: Examples (single variable) Ex: ? ? = ?? + ?, ? ? ? ? = sup (?? ?? ?) ? (1) If ? ?,? ? = (2) If ? = ?,? ? = ? ??? ? = ?,? ? = ? 32

4. Conjugate Functions: Examples (single variable) Ex: ? ? = ????, ? R++ ? ? = sup ? ?++ (1) If ? 0, ? ? = (2) If ? < 0, ? ? = max ?? + ???? ? ?++?? + ???? Let ? ? = ?? + ????, ? ? = ? +1 ? If ? ? = 0,? = 1 ? Thus, ? ? = 1 + log 1 = 1 log ? ? ??? ? = ?++, ? ? = 1 log( ?) 33

4. Conjugate Functions Ex: ? ? = ??, ? ? ? ? = ??? ?? ?? ? (1)? < 0 ? ? = (2)? > 0 Let ? ? = ?? ?? ? ? = ? ?? If ? ? = 0, then ? = ???? Thus ? ? = ????? ? (3) ? = 0 ? ? = 0 ??? ? = ?+, ? ? = ????? ? Therefore, we have ? ? = ????? ?, where ? 0. 34

4. Conjugate Functions Ex: ? ? = ?????, ? ?+, ? 0 = 0 ? ? = ??? ? Let ? ? = ?? ????? ? ? = ? ???? 1 Suppose ? ? = 0, we have ? = 1 + ???? or ? = ?? 1 Thus ? ? = ??? 1 ?? 1(? 1) = ?? 1 where ? ? ?? ????? 35

4. Conjugate Functions Ex: ? ? =1 ? 2????, ? ??,? ?++ ? ? = ??? ? Let ? ? = ??? 1 ??? 1 2???? 2???? ?? ? = ? ?? If ?? ? = 0, we have ? = ? 1? Thus, ? ? =1 2??? 1? Remark: Suppose that ? ? = ?? ? ? ? and 2? ? 0 1 (exercise 3.40) We have ? ? = ? and 2? ? = 2? ? 36

4. Conjugate Functions Basic Properties (1) ? ? + ? ? ??? Fenchel s inequality. Thus, in the above example ??? 1 2???? +1 ? 2??? 1?, ?,? ??,? ?++ (2) ? = ?, if f is convex & f is closed (i.e. epi f is a closed set) (3) If f is convex & differentiable, ??? ? = ?? For max??? ?(?), we have ? = ??(? ) Thus, ? ? = ? ??? ? ? ? , ? = ??(? ) 37

4. Conjugate Functions ? ? ??? ? ? = ?=1 Ex : ? ? = ??? ?=1 ? ? = ??? ??????? ? ??? ? ? = ??? ??? ??? ?=1 ??? ? ? ? Let ? ? = ??? ??? ?=1 ??? ??? ? ?? ? ??? = ?? ???= 0 ?=1 ??? ? ???, i.e. 1?? = 1 Thus, ??= ?=1 (1) 1?? 1 unbounded (2) ??< 0 unbounded (3) ? ? = ?=1 ? ???????, ? 0,1?? = 1 38

5. Log-Concave, Log-Convex Functions Log function : ???? ? , ?:?? ?,? ? > 0, ? ??? ? Suppose f is twice differentiable, ??? ? is convex. 1 1 ?2???? ? = ? ??2? ? ? ?2?? ? ?? ?? Then f is log-convex iff ? ??? ? ? ? ?2? ? ?? ? ?? ?? f is log-concave iff ? ??? ? ? ? ?2? ? ?? ? ?? ?? 39

5. Log-Concave, Log-Convex Functions ? ?? ?, Definition: If log? is concave, f is log-concave. Definition: If log? is convex, f is log-convex. Ex : ? ? = ??? + ?,??? ? = ? ??? + ? : log-concave ? ? = ??, ? ?++, ? 0 : log-convex ? > 0 log-concave ? ? = ??? : log convex & log-concave ? ? > 0, ? ??? ? ? ?2 ? 1 2? ? ? = Gaussian density log-concave 2?? : cumulative distribution function of 2????? ? 1 2? ?? 1? ? : log-concave 1 ? ? = 40

5. Log-Concave, Log-Convex Functions Properties 1 1 ?2???? ? = ?2? ? ? ?2?? ? ?f xT ? ? ? ? ?2? ? ?? ? ?? ??, ? ??? ? : log-convex ? ? ?2? ? ?? ? ?? ??, ? ??? ? : log-concave 41

Outlines 1. Definition: Convexity, Examples & Views 2. Conditions of Convexity 1. First Order Condition 2. Second Order Condition 3. Operations that Preserve the Convexity 1. Pointwise Maximum 2. Partial Minimization 4. Conjugate Function 5. Log-Concave, Log-Convex Functions 42