6.253 Convex Analysis and Optimization, Lecture 4

LECTURE 4 LECTURE OUTLINE • Relative interior and closure • Algebra of relative interiors and closures • Continuity of convex functions • Closures of functions Reading: Section 1.3 1 RELATIVE INTERIOR • x is a relative interior point of C, if x is an interior point of C relative to aff(C). • ri(C) denotes the relative interior of C, i.e., the set of all relative interior points of C. • Line Segment Principle: If C is a convex set, x ⌘ ri(C) and x ⌘ cl(C), then all points on the line segment connecting x and x, except possibly x, belong to ri(C). x = αx + (1 C α)x x x α⇥ S ⇥ S • Proof of case where x ⌘ C: See the figure. • Proof of case where x ⌘ / C: Take sequence {xk } ⌦ C with xk → x. Argue as in the figure. 2 ADDITIONAL MAJOR RESULTS • Let C be a nonempty convex set. (a) ri(C) is a nonempty convex set, and has the same a⌅ne hull as C. (b) Prolongation Lemma: x ⌘ ri(C) if and only if every line segment in C having x as one endpoint can be prolonged beyond x without leaving C. z1 0 X z1 and z2 are linearly independent, belong to C and span aff(C) C z2 Proof: (a) Assume that 0 ⌘ C . We choose m linearly independent vectors z1 , . . . , zm ⌘ C, where m is the dimension of aff(C), and we let ✏ m ⇣ m ⇧ ⌧ ⇧⌧ X= αi zi ⇧ αi < 1, αi > 0, i = 1, . . . , m i=1 i=1 (b) => is clear by the def. of rel. interior. Reverse: take any x ⌘ ri(C); use Line Segment Principle. 3 OPTIMIZATION APPLICATION • A concave function f : �n ◆→ � that attains its minimum over a convex set X at an x⇤ ⌘ ri(X) must be constant over X. x x x X aff(X) Proof: (By contradiction) Let x ⌘ X be such that f (x) > f (x⇤ ). Prolong beyond x⇤ the line segment x-to-x⇤ to a point x ⌘ X. By concavity of f , we have for some α ⌘ (0, 1) f (x⇤ ) ≥ αf (x) + (1 − α)f (x), and since f (x) > f (x⇤ ), we must have f (x⇤ ) > f (x) - a contradiction. Q.E.D. • Corollary: A nonconstant linear function cannot attain a minimum at an interior point of a convex set. 4 CALCULUS OF REL. INTERIORS: SUMMARY • The ri(C) and cl(C) of a convex set C “differ very little.” − Any set “between” ri(C) and cl(C) has the same relative interior and closure. − The relative interior of a convex set is equal to the relative interior of its closure. − The closure of the relative interior of a convex set is equal to its closure. • Relative interior and closure commute with Cartesian product and inverse image under a linear transformation. • Relative interior commutes with image under a linear transformation and vector sum, but closure does not. • Neither relative interior nor closure commute with set intersection. 5 CLOSURE VS RELATIVE INTERIOR • Proposition: � ⇥ � ⇥ (a) We have cl(C) = cl ri(C) and ri(C) = ri cl(C) . (b) Let C be another nonempty convex set. Then the following three conditions are equivalent: (i) C and C have the same rel. interior. (ii) C and C have the same closure. (iii) ri(C) ⌦ C ⌦ cl(C). � ⇥ Proof: (a) Since ri(C) ⌦ C, we have cl ri(C) ⌦ cl(C). Conversely, let x ⌘ cl(C). Let x ⌘ ri(C). By the Line Segment Principle, we have αx + (1 − α)x ⌘ ri(C),  α ⌘ (0, 1]. Thus, x is� the limit of a sequence that lies in ri(C), ⇥ so x ⌘ cl ri(C) . x x C � ⇥ The proof of ri(C) = ri cl(C) is similar. 6 LINEAR TRANSFORMATIONS • Let C be a nonempty convex subset of �n and let A be an m ⇤ n matrix. (a) We have A · ri(C) = ri(A · C). (b) We have A · cl(C) ⌦ cl(A · C). Furthermore, if C is bounded, then A · cl(C) = cl(A · C). Proof: (a) Intuition: Spheres within C are mapped onto spheres within A · C (relative to the a⌅ne hull). (b) We have A·cl(C) ⌦ cl(A·C), since if a sequence {xk } ⌦ C converges to some x ⌘ cl(C) then the sequence {Axk }, which belongs to A·C, converges to Ax, implying that Ax ⌘ cl(A · C). To show the converse, assuming that C is bounded, choose any z ⌘ cl(A · C). Then, there exists {xk } ⌦ C such that Axk → z. Since C is bounded, {xk } has a subsequence that converges to some x ⌘ cl(C), and we must have Ax = z. It follows that z ⌘ A · cl(C). Q.E.D. Note that in general, we may have A · int(C) ✓= int(A · C), 7 A · cl(C) ✓= cl(A · C) INTERSECTIONS AND VECTOR SUMS • Let C1 and C2 be nonempty convex sets. (a) We have ri(C1 + C2 ) = ri(C1 ) + ri(C2 ), cl(C1 ) + cl(C2 ) ⌦ cl(C1 + C2 ) If one of C1 and C2 is bounded, then cl(C1 ) + cl(C2 ) = cl(C1 + C2 ) (b) We have ri(C1 )⌫ri(C2 ) ⌦ ri(C1 ⌫C2 ), cl(C1 ⌫C2 ) ⌦ cl(C1 )⌫cl(C2 ) If ri(C1 ) ⌫ ri(C2 ) = ✓ Ø, then ri(C1 ⌫C2 ) = ri(C1 )⌫ri(C2 ), cl(C1 ⌫C2 ) = cl(C1 )⌫cl(C2 ) Proof of (a): C1 + C2 is the result of the linear transformation (x1 , x2 ) ◆→ x1 + x2 . • Counterexample for (b): C1 = {x | x ⌥ 0}, C2 = {x | x ≥ 0} C1 = {x | x < 0}, C2 = {x | x > 0} 8 CARTESIAN PRODUCT - GENERALIZATION • Let C be convex set in �n+m . For x ⌘ �n , let Cx = {y | (x, y) ⌘ C}, and let D = {x | Cx ✓= Ø}. Then ⌅ ⇤ ri(C) = (x, y) | x ⌘ ri(D), y ⌘ ri(Cx ) . Proof: Since D is projection of C on x-axis, ⇤ ri(D) = x | there exists y ⌘ so that ⌅ with (x, y) ⌘ ri(C) , �m ⌥ � ri(C) = ∪x⌦ri(D) Mx ⌫ ri(C) , ⇤ where Mx = (x, y) | y ⌘ ri(D), we have �m ⇤ ⌅ . For every x ⌘ ⌅ Mx ⌫ ri(C) = ri(Mx ⌫ C) = (x, y) | y ⌘ ri(Cx ) . Combine the preceding two equations. 9 Q.E.D. CONTINUITY OF CONVEX FUNCTIONS • If f : �n ◆→ � is convex, then it is continuous. e4 = ( 1, 1) yk e1 = (1, 1) xk xk+1 0 e3 = ( 1, 1) zk e2 = (1, 1) Proof: We will show that f is continuous at 0. By convexity, f is bounded within the unit cube by the max value of f over the corners of the cube. Consider sequence xk → 0 and the sequences yk = xk /�xk � , zk = −xk /�xk � . Then ⇥ � f (xk ) ⌥ 1 − �xk � f (0) + �xk � f (yk ) �xk � 1 f (zk ) + f (xk ) f (0) ⌥ �xk � + 1 �xk � + 1 → 0, we have �xk � lim sup �xk � f (yk ) ⌥ 0, lim sup f (zk ) ⌥ 0 �xk � + 1 k⌃ k⌃ Take limit as k → ⇣. Since �xk � so f (xk ) → f (0). Q.E.D. • Extension to continuity over ri(dom(f )). 10 CLOSURES OF FUNCTIONS • The closure of a function f : X ◆→ [−⇣, ⇣] is the function cl f : �n ◆→ [−⇣, ⇣] with � ⇥ epi(cl f ) = cl epi(f ) ˇ f with • The convex closure of f is the function cl � � ⇥⇥ ˇ epi(cl f ) = cl conv epi(f ) • Proposition: For any f : X ◆→ [−⇣, ⇣] ˇ f )(x). inf f (x) = infn (cl f )(x) = infn (cl x⌦X x⌦� x⌦� Also, any vector that attains the infimum of f over ˇ f. X also attains the infimum of cl f and cl • Proposition: For any f : X ◆→ [−⇣, ⇣]: ˇ f ) is the greatest closed (or closed (a) cl f (or cl convex, resp.) function majorized by f . (b) If f is convex, then cl f is convex, and it is proper if and only if f is proper. Also, � ⇥ (cl f )(x) = f (x),  x ⌘ ri dom(f ) , � ⇥ and if x ⌘ ri dom(f ) and y ⌘ dom(cl f ), ⇥ (cl f )(y) = lim f y + α(x − y) . α⌥0 11 �