Unformatted text preview:

103VI. ConvexityConvex setsIn Analysis, convex sets appear as sensible domains from which to single out solutionsof certain problems by extremizing convex fl’s. This chapter deals with the simple aspectsof this problem. Typical examples include the search for a point at which a given blmtakes on its norm, or for a ba from a convex set. In both of these examples, and in general,the convexity of the unit ball in a nls plays an important role. In this chapter, IF = IR.** convexity is local linearity **Let X ls. For any two x, y ∈ X, we call[x . . y] := {(1 − α)x + αy : α ∈ [0 . . 1]}the (closed) interval spanned by x and y. A subset K of X is called convex if it isclosed under interval formation, i.e.,x, y ∈ K =⇒ [x . . y] ⊆ K.Thus convexity is a kind of local linearity. It follows that the intersection of convex setsis convex and that any linear map preserves convexity, i.e., it maps convex sets to convexsets.The unit ball B as well as the closed unit ball B−in a nls X are convex sincek(1 − α)x + αyk ≤ (1 − α)kxk + αkyk whenever α ∈ [0 . . 1].** convex hull **The convex hullconv Mof the set M in the ls X is, by definition, the smallest convex set containing M, hence isthe intersection of all convex sets containing M.For example, conv{x, y} = [x . . y] since the latter is convex and must be contained inevery convex set containing x and y. Also,(1) conv{x, y, z} = [x . . [y . . z]] = [[x . . y] . . z]since both sets must be contained in any convex set containing {x, y, z}, and the first(hence, by symmetry, also the second) equals the 2-simplex{[x, y, z]a : a ∈ IR3+; kak1= 1}.Indeed, if u = xa(1) + ya(2) + za(3) with a nonnegative and a(1) + a(2) + a(3) = 1, theneither a(2) = 0 = a(3), hence u = x, or else u = v := xα + (1− α)(yβ + (1 −β)z) with α :=convex hullc2002 Carl de Boor104 VI. Convexitya(1), β := a(2)/(a(2) + a(3)) ∈ [0 . . 1], hence, either way, u ∈ [x . . [y . . z]], while, conversely,any such v is of the form xa(1) + ya(2)+za(3) with a := (α, (1− α)β, (1− α)(1−β)) ∈ IR3+and kak1= 1. One verifies similarly that the n-simplexconv(x0, . . . , xn) := {[x0, . . . , xn]a : a ∈ IRn+1+; kak1= 1}is the convex hull of {x0, . ., xn}. Its elements are called the convex combinations of thexi’s.For an arbitrary set M with subsets Mi, the convex hull of M contains[M1. . M2] := ∪xi∈Mi[x1. . x2],hence contains, with M(1):= M, the inductively defined setsM(k):= [M(s). . M(k−s)], 0 < s < k; k = 2, 3, . . . ,with the various right-hand sides here indeed equal sinceconv(x1, . . . , xk) = [conv(x1, . . . , xs) . . conv(xs+1, . . . , xk)], 0 < s < k.Each element of M(k)is a convex combination of k elements of M, i.e.,M(k)= ∪F ⊂M;#F =kconv F, with conv F = {[F ]a : a ∈ IRF+; kak1= 1}.The sequence M(1)= M, M(2), . . . is increasing, and its union is convex since [M(r). .M(s)] ⊆ M(r+s). Since this union also lies in every convex set containing M , it followsthat(2) conv M = ∪n∈INM(n).If M is finite, then conv M = M(#M). Whether or not M is finite,conv M = M(dim X+1)this is part of (8)Caratheodory’s Theorem below.H.P.(1) Here is a useful weakening of convexity: The set K is said to be starlike with respect to the set Yif, [Y . . K] ⊂ K. (Thus, a set is convex iff it is starlike wrto itself.) Prove: If K is starlike wrto Y , then K isstarlike wrto conv Y . (Hint: Use (1) to prove [A . . [B . . C]] ⊆ [[A . . B] . . C]; then use (2).)H.P.(2) Here is a useful strengthening of convexity: The set H is said to be a flat (or, an affine set) ifx, y ∈ H implies x + ran[y − x] ⊆ H. Further, [M := the affine hull of M or flat spanned by M, is thesmallest flat containing M . Prove: (i) [M = {[F ]a : F ⊂ M, #F < ∞,Pf ∈Fa(f) = 1}, i.e., [M is the set ofall affine combinations of elements of M. (ii) H is a flat iff H = x + Y for some lss Y (and every x ∈ H).** closure and interior of a convex set **The topological structure of a convex set in a nls is quite simple.(3) Lemma. K convex, x ∈ Ko, y ∈ K−=⇒ [x . . y) ⊆ Ko.Proof: (4)Figure tells the story, but here are the algebraic facts, to be sure. x ∈Ko=⇒ ∃{r > 0} x + Br⊆ K, while y ∈ K−=⇒ ∀{s > 0} ∃{ys∈ K ∩ Bs(y)}. Hence,∀{z ∈ [x . . y)} ∃{t > 0} z + Bt⊆ K, since, with z =: (1 − α)x + αy, we have 0 ≤ α < 1andz + Bt⊆ (1 − α)x + αys+ α(y − ys) + Bt⊆ (1 − α)x + αys+ Bt+αs= (1 − α)(x + Br) + αys⊆ Kif (t + αs)/(1 − α) = r, i.e., t = (1 − α)r − αs, and this is positive for sufficiently small ssince 1 − α > 0.closure and interior of a convex setc2002 Carl de BoorConvex sets 105x yzys(4) Figure. Proof of (3)Lemma(5) Corollary. K convex =⇒ Ko, K−convex.Proof: If x, y ∈ Ko, then [x . . y] ⊂ Koby (3)Lemma, hence Kois convex. Ifx, y ∈ K−, then x = limnxn, y = limnynfor sequences (xn), (yn) in K. Therefore, forevery α ∈ [0 . . 1], (1 − α)x + αy = limn((1 − α)xn+ αyn) ∈ K−, i.e., K−is convex.H.P.(3) Prove: K convex, Ko6= {} =⇒ (i)K−= (Ko)−, hence (ii)∀{λ ∈ X∗} sup λK = sup λ(Ko).Remark. The lemma has an extension to any convex set consisting of more than onepoint, for any such convex set has relative interior, i.e., interior as a subset of its affinehull. It has also an extension to linear topologies more general than the norm topology.For example, the n-simplex, σn:= conv(x0, . . . , xn), is called proper if the flatspanned by it is n-dimensional, i.e., if [x1− x0, . . . , xn− x0] is 1-1. In that case, [σnis the 1-1 affine image of IRnunder the mapf : IRn→ X : a 7→ x0+ [x1− x0, . . . , xn− x0]a,withTn:= conv(ej: j = 0, . . . , n), e0:= 0,the pre-image of σn. Correspondingly, the relative interior of σnis the image under f ofthe interior of Tn. The latter equals(6) Ton= {a ∈ IRn: ∀{j} a(j) > 0;Xja(j) < 1}.Indeed, the right side here is a subset of Tnand is the intersection of n + 1 open sets,hence …


View Full Document

UW-Madison CS 717 - Convexity

Download Convexity
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Convexity and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Convexity 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?