Convex Optimization Lecture: Sets, Functions, and Problems
Explore the fundamentals of convex optimization, including sets, functions, and problem statements. Learn about convexity, basic convex sets, separating hyperplanes, and dual cones. Understand how to define convex functions and sets, and examine the specifications and properties of convex sets in optimization problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE203B Convex Optimization Lecture 2 Convex Set CK Cheng Dept. of Computer Science and Engineering University of California, San Diego 1
Chapter 2 Convex Set 1. Set Convexity and Specification i. Convexity Definition ii. Set Specification: Qualification vs. Enumeration Oriented Description 2. Basic Convex Sets 3. Separating Hyperplanes 4. Dual Cones 2
Convex Optimization Problem: Problem Statement ?0? , ? ?? min ? Subject to ??? ?? ,? = 1, ,? The conditions of convex optimization problem 1. ?0? is a convex function 2. For ??? ??, ? = 1, ,? ?|??(?) ??,? = 1, ,? is a convex set 3
Convex Optimization Problem: A. Convex Function Definition: ???? + ?? ???? + ???? , ? + ? = 1,?,? 0 4
Convex Optimization Problem: A. Convex Function Definition: ???? + ?? ???? + ???? , ? + ? = 1,?,? 0 B. Convex Set Definition: ?,? ? We have ?? + ?? ?, ? + ? = 1,?,? 0 5
1. Set Convexity and Specification: Convexity A set ? is convex if we have ?? + ?? ?, ? + ? = 1,?,? 0, ?,? ? Examples: 6
1. Set Convexity and Specification: Convexity A set ? is convex if we have ?? + ?? ?, ? + ? = 1,?,? 0, ?,? ? Remark: 1. Most used sets in the class 1. Scalar set: ? ? 2. Vector set: ? ?? 3. Matrix set: ? ?? ? 2. Set S is convex if every two points in S has the connected straight segment in the set. 3. For convex sets ?1 and ?2: ?1 ?2 is also convex Proof: 7
1. Set Convexity and Specification: Convexity A set ? is convex if we have ?? + ?? ?, ? + ? = 1,?,? 0, ?,? ? Remark: 3. For convex sets ?1 and ?2: ?1 ?2 is also convex Proof: 8
1. Set Specification via Qualification or Enumeration ??= {?|?? ?,? ??} ??= {?? | ? ?+ Qualification Oriented Expression Enumeration Oriented Expression ?} Qualification Oriented Expression: Constraints Min ??? Subject to ?? ?,? ?? Enumeration Oriented Expression: Obj function Min ???? ,? ?+ ? 9
1. Qualification vs Enumeration Oriented Description Qualification Oriented Expression Example: {?|?? ?} Remark: Simultaneous linear constraints imply AND, Intersection of the constraints ?1 2?1 +2?2 ?2 ?2 +3?3 4 3 5 10 +?3 ?3 4 3 5 10 1 2 0 0 2 3 0 1 1 ?1 ?2 ?3 1 1 0 , ? = , ? = ? = 10
1. Qualification vs. Enumeration Oriented Description ?1= {?|?? ?,? ??} is a convex set Proof: Given two vectors ?,? ?1, ?.?. ?? ?, ?? ? For ? = ?1? + ?2?, ?1+ ?2= 1,?1,?2 0 we have ?? ?. (?? = ?1?? + ?2?? ?1? + ?2? = ?) The inequality implies ? ?1 By definition, set ?1is convex. Remark: 1. Simultaneous linear constraints imply AND, Intersection of the constraints 2. Linear constraints constitute a convex set. 11
1. Qualification vs. Enumeration Oriented Description Example: ?2= ? ?? ?,? ??} ?3= ? ?? = ?,? ??} 12
1. Qualification Oriented Expression ??(?) 1 for ? ? Example: ? = ? ?? 3} ? ??? ??? = ?1cos? + ?2cos2? + + ??cos?? 13
1. Enumeration Oriented Expression Expression Conversion ?} Example: {?|?? ?,? ??} ?? {??| 1?? = 1, ? ?+ ?1 ?2 ?3 ?4 1 1 1 0 0 2 1 1 1 ?1 ?2 1 1 1 1 1 1 3 1 0 1 1 14
1. Qualification vs. Enumeration Oriented Description Remark: Qualification Oriented Expression: Constraints of the problem Enumeration Oriented Enumeration: The objective function The interchange may not be trivial. min?0(??) ?.?. ??? 1 ? ???,? ?+ min?0(?) ?.?.?? ? ? ?? ? Every vector ?? in matrix ? is a solution of n equations in constraint ?? ? ? ????????? ? ????????? ???? ?,? ???????? ?????? ??????. 15
1. Qualification vs. Enumeration Oriented Description Mixed Description ?4= ?? + ? ??? + ? > 0,? ?4} (Projective Function) ??? + ? ? ?? ??,? > 0, ?,? ?5} (Perspective Function) ?5= ?4 is convex if ?4 is convex ?5 is convex if ?5 is convex 16
1. Qualification vs. Enumeration Oriented Description Statement: ?5 ?? ?????? if ?5 ?? ??????. Proof: Given ?1 ?2 ?1 ?2 ?5, let us set ?5, ?3= ??1+ ?2,?3= ??1+ ??2, ? + ? = 1,?,? 0 We have ?3 ?3 =??1+ ?2 ??1+ ?2 ??1 ?1 ?1 ??2 ?2 ?2 = + ??1+ ?2 ??1+ ?2 ??1 ??2 Let ? = ,? = ??1+ ?2 ??1+ ?2 (Note that ? + ? = 1,? ,? 0), we have?3 = ? ?1 + ? ?2 ?5 ?3 ?1 ?2 Therefore, by definition ?5 is convex. 17
2. Basic Convex Sets: Terms and Definitions Definitions: I. Affine Set, II. Cone, and III. Convex Hull Given ?1,?2, ,?? ??, function ? ?,? = ?1?1+ ?2?2+ + ???? and two conditions 1. ?1+?2+ + ??= 1 2. ?? 0 ? I. f u, condition 1}: Affine set II. f u, condition 2}: Cone III. f u, conditions 1 and 2}: Convex hull ??1:?1?1+ ?2?2= ?1+ ?2(?2 ?1) ??2:?1?1+ ?2?2+ ?3?3 18
2. Basic Sets and Definitions: VI. Hyperplanes and Half Spaces Hyperplane ? ??? = ?},? ??,? ? or ? ??(? ?0) = 0},for any ?0 ??,? ??,? ? Half Space ? ??? ?} ? ??,? ? or ? ??(? ?0) 0} ?1 ?2 0.5 ??: ? ?1+ ?2= 1} ?? ? [1,1] = 0} 0.5 or ? ??? ?0 = 0}, ??= [1,1],? = 1,?0= [2, 1] For many applications,we standardize the expression: normalize the expression: ?? ?2?= ? ?2 19
2. Basic Sets and Definitions: VI. Hyperplanes Ex : 3 variables ?|??? = ? , ??= 1,1,1 , ? = 6 Ex : 4 variables ?|??? = ? , ??= 1,1,1,1 , ? = 6 (1) degrees of freedom : ? 1 ??. (2) all vectors (? ?) are orthogonal to direction ?, i.e. ??? ? = 0, ?,? in the hyperplane Proof: Exercise: Conceptually (visually) construct hyperplane. 20
2. Basic Sets and Definitions: VI. Hyperplanes Hyperplane : as an Equal potential of cost function min?0? = ??? ?1 ?2 ??0? ??1 ?.?. 1,2 = 1 ??0? ??2 = 2 ?1 ?2 Vector ? is the sensitivity or cost of vector 21
2. Basic Sets and Definitions VI. Hyperplane : as a linearized constraint ??? ?,? ?? ?1 ?2 Remark : Hyperplane is one key building block of convex optimization. (theory, algorithms, applications for machine learning, deep learning, ) Each hyperplane separates the space into two half spaces. If ? ?,? hyperplanes can separate the space into 2? disjoint regions. ?.?. 1,2 10 22
2. Basic Sets and Definitions . Polyhedra (plural) : Poly (many) Hedron (face) ? = ? ?? ?,?? = ?} ? ? ?1 ?2 ?? ?1 ?2 ?? ? ? ? = C = ? ? 23
2. Basic Sets and Definitions I. Matrix Space : Positive Semidefinite Cone ??= ? ?? ?? = ??} Symmetric Matrix ?+ ?++ ? ? ? ? ?+ [? ?]?? ?= ?2? + ?2? + 2??? 0, ?,? ?= ? ??? 0}?.?. ???? 0, ? ?= ? ??? 0}?.?. ???? > 0, ? 0 2 ? 0,? 0,?? ?2 Ex: ? = 24
2. Basic Sets and Definitions ? ? ? ? ?+ 2 ? 0,? 0,?? ?2 Ex: ? = [? ?]?? ?= ?2? + ?2? + 2??? 0, ?,? Proof : Let ? =1 0 = ? ? ? ?? ? 1? 1 We have ? ? ?? ?= [? ?]? ?????? 1? 0 0 ? ? ? ? 1?2 ? 1? ? ? ? ? 1 0 1 ? 0 0 ? 1? 1 1 0 = ? 1? ? ? 1?2 25
3. Separating Hyperplane ? ??? = ?} (Classification, Optimization, Duality) Theorem : Given two convex sets ? ? = in ?? ? ??,? ?, ?.?. ??? ?, ? ? ??? ?, ? ? 2 ?2 2 2 ?2 Actually, ? = ? ?,? = i.e. ? ? = ??? ? = ? ??(? ?+? 2) For ???? ?,? = inf ? ?2? ?,? ?} 26
3. Separating Hyperplane Proof : ? ?,??? ??? should be true By contradiction, suppose that ??? < ??? Then we can show that ? + ?(? ?) is close to ? for ? > 0 Because ? 2= 2 ? ??? ? < 0 ??? + ? ? ? ?2 We have ? + ? ? ? ?2< ? ?2 for tiny ? > 0 27
3. Supporting Hyperplane Given set ? ??, and a point ?0 on the boundary of ?,the hyperplan ? ??? = ???0} is called supporting hyperplane of C if ??? ???0, ? ?. Supporting Hyperplane Theorem: For any nonempty convex set ?, and a point ?0 on the boundary of ?, There exists a support hyperplane to ? at ?0. Proof: A separating hyperplane that separates interior ? and {?0} is a supporting hyperplane. 28
4. Dual Cones ? ????|??> 0,?? ??, ?}) Given Cone ? (i.e. ? = { ?=1 ? = ? ??? 0, ? ?} Ex: 1. ? = ?+ 2. ? = ?+ 3. ? = ?,? 4. ? = ?,? ? ? = ?+ ? ? = ?+ ? ? ?2 ? ? = {(?,?)| ?2 ?} ?1 ? ? = {(?,?)| ? ?} 29
4. Dual Cones Show that cone ? = ?,? ?1 ? has its dual ?,? ? ? ? = Proof : Statement ??? + ?? 0, ?1 ? L=>R By contradiction, suppose that ? > ? We can find ? ?.? ?1 1,??? > ? Setting t=1, then we have ?? ? + ? < 0. R=>L Given ?1 ?, ? ? ?? ?/?1 ? ? Thus, ?? ? ?? ? ? 30
4. Dual Cones Definition: ? ?? if ? ? ? Theorem: ? ?? iff ??? ???, ? ? Examples 31
4. Dual Cones The polyhedral cone ? = {?|?? 0} has its dual cone ? = {???|? 0} Proof : By definition ? = {?|??? 0, ? ?} Thus ? = {?|??? 0, ?? 0} Let ? = ???, we have ??? = ????? > 0 if ? 0 Ex: ? =1 2 1 i.e. ?1+ 2?2 0,?1 ?2 0 1 1 i.e. {?1 1 ??=1 1 2+ ?2 1 1|?1,?2 0} 2 32
4. Dual Cones Remark: ?0+ ? ? ? (1) ? cone can be translated to ?0 (2) If ? ? , then ??? 0, ? ?, i.e. ?? is a supporting hyperplane of cone ? (3) Suppose that the current feasible search region is at corner ?0 and ?0+ ? ? ?,|| ?|| < ? is a local feasible region of a convex set If ??0?0 ? , i.e. ??0?0 Then ?0 is an optimal solution ? ? 0, ? ?, 33
