CHAPTER 2:

CONVEX SETS

2.1 Let . Then there exists λ ∈ [0,1] and such that x = λx + (1 – λ)x. Since x1 and x2 are both in S1, x must be in conv(S1). Similarly, x must be in conv(S2). Therefore, conv(S2). (Alternatively, since and we have or that An example in which is given below: Here, while in this case. 2.2 Let S be of the form S = {x : Ax ≤ b} in general, where the constraints might include bound restrictions. Since S is a polytope, it is bounded by definition. To show that it is convex, let y and z be any points in S, and let x = λ y + (1 – λ)z , for 0 ≤ λ ≤ 1. Then we have Ay ≤ b and Az ≤ b, which implies that or that x ∈ S. Hence, S is convex. Finally, to show that S is closed, consider any sequence {xn} → x. such that . Then we have or by taking limits as n → ∞, we get as well. Thus S is closed. 2.3 Consider the closed set S shown below along with conv(S), where conv(S ) is not closed: Now, suppose that is closed. Toward this end, consider any sequence {xn} → x , where xn ∈ conv(s), . We must show that x ∈ conv(s). Since xn ∈ conv(s), by definition (using Theorem 2.1.6), we have that we can write where for r = 1,..., 1 p + 1, , and where , with Since the λnr -values as well as the -points belong to compact sets, there exists a subsequence K such that and . From above, we have taking limits as n → ∞, n ∈ K, that where xr ∈ S, = 1,...,p + 1 since S is closed. Thus by definition, x ∈ conv(S) and so conv(S) is closed. 2.7 a. Let y1 and y2 belong to AS. Thus, y1 = Ax1 for some x1 ∈ S and y2 = Ax2 for some x2 ∈ S. Consider y = λy1 + (1 − λ)y2, for any 0 ≤ λ ≤ 1. Then y = A[λx1 + (1 − λ)x2]. Thus, letting x ≡ λ1 + (1 − λ)x2, we have that x ∈ S since S is convex and that y = Ax. Thus y ∈ AS , and so, AS is convex. b. If α ≡ 0, then αS ≡ {0}, which is a convex set. Hence, suppose that α ≠ 0. Let αx1 and αx2 ∈ αS, where x1 ∈ S. Consider αx = λαx1 + (1 − λ)αx2 for any 0 ≤ λ ≤ 1. Then, αx = α[λx1 + (1 − λ)x2]. Since α ≠ 0, we have that x = λx1 + (1 − λ)x2, or that x ∈ S since S is convex. Hence αx ∈ αS for any 0 ≤ λ 1 ≤ 1, and thus αS is a convex set. 2.8 . 2.12 Let S = S1 + S2. Consider any y, z ∈ S, and any λ ∈ (0,1) such that y = y1 + y2 and z = z1 + z2 , with and . Then λy + (1 – λ)z = λy1 + λy2 + (1 – λ)z1 + (1 – λ)z2. Since both sets S1 and S2 are convex, we have λyi + (1 – λ)zi ∈ Si, i = 1, 2. Therefore, λy + (1 – λ)z is still a sum of a vector from S1 and a vector from S2, and so it is in S. Thus S is a convex set. Consider the following example, where S1 and S2 are closed, and convex. Let xn = yn + zn, for the sequences {yn} zn and {zn} shown in the figure, where , and . Then {xn} → 0 where xn ∈ S, , but 0 ∉ S. Thus S is not closed. Next, we show that if S1 is compact and S2 is closed, then S is closed. Consider a convergent sequence {xn} of points from S, and let x denote its limit. By definition, xn = yn + zn , where for each n, yn ∈ S1 and zn ∈ S2. Since {yn} is a sequence of points from a compact set, it must be bounded, and hence it has a convergent subsequence. For notational simplicity and without loss of generality, assume that the sequence {yn} itself is convergent, and let y denote its limit. Hence, y ∈ S1. This result taken together with the convergence of the sequence {xn} implies that {zn} is convergent to z, say. The limit, z, of {zn} must be in S2, since S2 is a closed set. Thus, x = y + z, where y ∈ S1 and z ∈ S2, and therefore, x ∈ S. This completes the proof. 2.15 a. First, we show that . For this purpose, let us begin by showing that S1 and S2 both belong to Ŝ. Consider the case of S1 (the case of S2 is similar). If x∈S1, then A1 x ≤ b1, and so, with y = x, z = 0, λ1 = 1, and λ2 = 0. Thus , and since Ŝ is convex, we have that Next, we show that . Let . Then, there exist vectors y and z such that x = y + z, and A1y ≤ b1 λ1, A2z ≤ b2 λ2 for some (λ1, λ2) ≥ 0 such that λ1 + λ2 = 1. If λ1 = 0 or λ2 = 0 , then we readily obtain y = 0 or z = 0, respectively (by the boundedness of S1 and S2), with x = z ∈ S1 or x = y ∈ S1, respectively, which yields x ∈ S, and so x ∈ conv(S). If λ1 > 0 and λ2 > 0 , then x = λ1y1 + λ2z2, where and . It can be easily verified in this case that y1 ∈ S1 and z2 ∈ S2, which implies that both vectors y1 and z2 are in S. Therefore, x is a convex combination of points in S, and so x ∈ conv(S). This completes the proof b. Now, suppose that S1 and S1 are not necessarily bounded. As above, it follows that and since is closed, we have that . To complete the proof, we need to show that . Let , where x = y + z with A1y ≤ b1 λ1, A2z ≤ b2λ2, for some (λ1, λ2) ≥ 0 such that λ1 + λ1 = 1. If (λ1, λ1) > 0, then as above we have that x ∈ conv(S) x ∈ cℓconv(S). Thus suppose that λ1 = 0 so that λ2 = 1 (the case of λ1 = 1 and λ2 = 0 is similar). Hence, we have A1y ≤ 0 and A2z ≤ b2 , which implies that y is a recession direction of S1 and z ∈ S2 (if S1 is bounded, then y ≡ 0 and then x = z ∈ S2 yields). Let and consider the sequence where 0 < λn ≤ 1 for all n. Note that , z ∈ S2, and so xn ∈ conv(S), . Moreover, letting {λn} → 0+, we get that {xn} → y + z ≡ x, and so x ∈ cℓconv(S) by...