Convex Optimization Fundamentals

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

Outlines 1. Definitions: Convexity, Examples & Views 2. Conditions of Optimality 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 2

Outlines 1. Definitions 1. Convex Function vs Convex Set 2. Examples 1. Norm 2. Entropy 3. Affine 4. Determinant 5. Maximum 3. Views of Functions and Related Hyperplanes 3

1. Definitions: Convex Function vs Convex Set 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 ?(?) ?=> ? 4

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

1. Convex Function Definitions: Examples Example on ??: Affine: ? ? = ??? + ? Norms: ??= ?=1 ? = max 1? ??? ? 1; ? ?? |??| ? Example on ?? ?: Affine: ? ? = ?? ??? = ?=1 Spectral (max singular value): ? ? = ?2= ????? = (??????? ) ? ?=1 ? ?????? 12 6

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

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 ?? ? 8

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. 9

2. Conditions of Optimality: 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 ? ? ? + ?? ? ?(?) ?(?) ? ? ) 10

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. 11

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. 12

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 ?3 2 ?3 ? ? ? ?2? ? = = ? 2? ?2 13

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 + 14

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, ,?} 15

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 ????, ? ?? 16

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

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 18

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. 19

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 20

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 21

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 ? ? ? ? ? ? 22

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. 23

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 24

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?,? ? ? 25

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 26

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

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( ?) 28

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

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

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? ? 31

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, ? ? = ? ??? ? ? ? , ? = ??(? ) 32

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 33

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? ? ?? ? ?? ?? 34

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 ? ? = 35

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

Outlines 1. Definitions: Convexity, Examples & Views 2. Conditions of Optimality 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 37