Analysis of Convex Sets and Functions

Analysis of Convex Sets and Functions 1 2 1 Convex Sets - Basics A set S ⊂ IRn is defined to be a convex set if for any x1 ∈ S, x2 ∈ S, and any scalar λ satisfying 0 ≤ λ ≤ 1, λx1 + (1 − λ)x2 ∈ S. Points of the form λx1 + (1 − λ)x2 are said to be a convex combination of x1 and x2 , if 0 ≤ λ ≤ 1. A hyperplane H ∈ IRn is a set of the form {x ∈ Rn | pt x = α} for some fixed p ∈ IRn , p =  0, and α ∈ R. A closed halfspace is a set of the form H + = {x | pt x ≥ α} or H − = {x | pt x ≤ α}. An open halfspace is defined analogously, with ≥ and ≤ replaced by < and >. • Any hyperplane or closed or open halfspace is a convex set • The ball {x ∈ IRn | x21 + . . . + x2n ≤ 5} is a convex set. • The intersection of an arbitrary number of convex sets is a convex set. • A polyhedron {x ∈ IRn | Ax ≤ b} is a convex set. • X = {x | x = αx1 + βx2 , where x1 ∈ S1 and x2 ∈ S2 } is a convex set, if S1 and S2 are convex sets. Let S ⊂ IRn . The convex hull of S, denoted H(S), is the collection of all convex combinations of points of S, i.e., x ∈ H(S) if x can be represented as x= k
λj xj j=1 where k
λj = 1, λj ≥ 0, j = 1, . . . , k, j=1 for some positive integer k and vectors x1 , . . . , xk ∈ S. Lemma 1 If S ⊂ IRn , then H(S) is the smallest convex set containing S, and H(S) is the intersection of all convex sets containing S. 3 The convex hull of a finite number of points x1 , . . . , xk+1 ∈ IRn is called a polytope. If the vectors x2 −x1 , x3 −x1 , . . . , xk+1 −x1 , are linearly independent, then H(x1 , . . . , xk+1 ) is called a k-dimensional simplex, with vertices x1 , . . . , xk+1 . Carath´ eodory Theorem. Let S ⊂ IRn , and let x ∈ H(S) be given. Then x ∈ H(x1 , . . . , xn+1 ) for n+1 suitably chosen points xj ∈ S, j = 1, . . . , n+1. In other words, x can be represented as x= n+1
λj xj j=1 where n+1
λj = 1, λj ≥ 0, j = 1, . . . , n, for some xj ∈ S, j = 1, . . . , n + 1 . j=1 Proof: Since x ∈ H(S) , there exist k points x1 , . . . , xk that satisfy k
λj xj = x j=1 and k
λj = 1, λ1 , . . . , λk ≥ 0 . j=1 If k ≤ n + 1, we are done. If not, let us consider the above linear system as a system of n + 1 equations in the nonnegative variable λ ≥ 0, i.e., as a system Aλ = b, λ ≥ 0, where  A= x1 x2 . . . xk 1 1 ... 1   , b= x 1  . Let e = (1, . . . , 1)t . Notice that this system has n + 1 equations in k nonnegative variables. From the theory of linear programming, this system has a basic feasible 4 solution, and we can presume, without loss of generality, that the basis consists of columns 1, . . . , n + 1 of A. Thus, there exists λ ≥ 0, et λ = 1, λn+2 , . . . , λk = 0 such that n+1
j=1 2 λj xj = x, n+1
λj = 1, λ ≥ 0 . j+1 Closure and Interior of Convex Sets Let x ∈ IRn . Define N
(x) = {y ∈ IRn | y − x < }, where  ·  is the Euclidean norm:  
√  n 2 zj = z t z . z :=  j=1 Let S be an arbitrary set in Rn . x ∈ clS, the closure of S, if S∩N
(x) = ∅ for every  > 0. If S = clS, then S is a closed set. x ∈ intS, the interior of S, if there exists  > 0 for which N
(x) ⊂ S. If S = intS, then S is an open set. x ∈ ∂S, the boundary of S, if N
(x) contains a point in S and a point not in S, for all  > 0. Theorem 2 Let S be a convex set in Rn . If x1 ∈ clS and x2 ∈ intS, then λx1 + (1 − λ)x2 ∈ intS for every λ ∈ (0, 1). Proof: Since x2 ∈ intS, there exists  > 0 such that z − x2  <  implies z ∈ S. Also, since x1 ∈ clS, for any δ > 0, there exists a z with z − x1  < δ and z ∈ S. Now let y = λx1 + (1 − λ)x2 be given, with λ ∈ (0, 1). Let r = (1 − λ). I claim that for any z with z − y < r, then z ∈ S. This means that y ∈ intS, proving the theorem. To prove the claim, consider such a z with z − y < r. Let δ = (1 − λ) − z − y. Then δ > 0. Then there exists z 1 with z 1 − x1  < δ and z 1 ∈ S. Let z 2 = (z − λz 1 )/(1 − λ). 5 1 ) (z−λz 2 z 2 − x2  =  (z−λz (1−λ) − x  =  1 )−(y−λx1 )  1−λ   1 1 1 = 1−λ z − y − λ(z − x ) 1 (z − y + λz 1 − x1 ) ≤ 1−λ 1 < 1−λ (z − y + λ ((1 − λ) − z − y)) = z − y + λ < (1 − λ) + λ = . Thus z 2 ∈ S. Also z = λz 1 + (1 − λ)z 2 , and so z ∈ S. The proof construction is illustrated in Figure 1. x1 z1 δ z y r z2 x2 ε S Figure 1: Construction for the proof of Theorem 2 3 Supporting Hyperplanes of Convex Sets Let S be nonempty set in Rn , and let x ¯ ∈ ∂S. A hyperplane H = {x ∈ IRn | pt x = α} (where p = 0) is call a supporting hyperplane of S at x ¯ if 6 either S ⊂ H + or S ⊂ H − , (i.e., if either pt x ≥ α for all x ∈ S or pt x ≤ α for all x ∈ S, and pt x ¯ = α. ¯ i.e., H = {x | pt (x − x) ¯ = Note that we can write H as H = {x | pt x = pt x}, 0}. If S ⊂  H, then H is called a proper supporting hyperplane. ¯ = inf{pt x | x ∈ S} or pt x̄ = sup{pt x | x ∈ S}. Note that either pt x Theorem 3 If S is a nonempty convex set and x ¯ ∈ ∂S, then there exists a supporting hyperplane to S at x; ¯ that is, there exists a nonzero vector p ¯ for all x ∈ S. such that pt x ≤ pt x Proof: Let x̄ ∈ ∂S. Then there exists a sequence of y i , i = 1, . . . , ∞, such that y i → x, / cl(S). Now cl(S) is a closed convex set, and so there ¯ and y i ∈ i exists p = 0 and αi such that (pi )T x ≤ αi for all x ∈ cl(S), and (pi )T y i > αi . We can re-scale the pi values so that pi  = 1. As y i → x, ¯ choose i i T i subsequence of the p that converge, say, to p̄. Then (p ) x ≤ α < (pi )T y i for all x ∈ cl(S), and so p̄T x ≤ p̄T x̄. Thus, as i → ∞, any x ∈ S ⊂ cl(S) satisfies p¯T x ≤ p̄T x. ¯ Theorem 4 If A and B are nonempty convex sets and A ∩ B = ∅, then A and B can be separated by a hyperplane. That is, there exists p =  0, α, such T T that p x ≤ α for any x ∈ A and p x ≥ α for any x ∈ B. Proof: Let S = {x | x = x1 − x2 , x1 ∈ A, x2 ∈ B}. Then S is a convex set, and 0 ∈ / S. Let T = cl(S) = S ∪ (∂S). If 0 ∈ T , then 0 ∈ ∂S, and from Theorem 3, there exists p =  0, such that pT (x1 − x2 ) ≤ 0 for any x1 ∈ A, x2 ∈ B, so that pT x1 ≤ pT x2 for any x1 ∈ A, x2 ∈ B. Let α = inf{pT x2 | x2 ∈ B}. Then pT x1 ≤ α ≤ pT x2 for any x1 ∈ A, x2 ∈ B. If 0 ∈ / T , then since T is a closed set, then we can apply the basic separating hyperplane theorem for convex sets: there exists p = 0 and β for which pT (x1 − x2 ) ≤ β < pT 0 = 0 for any x1 ∈ A, x2 ∈ B, so that pT x1 ≤ pT x2 for any x1 ∈ A, x2 ∈ B. Again let α = inf{pT x2 | x2 ∈ B}. Then pT x1 ≤ α ≤ pT x2 for any x1 ∈ A, x2 ∈ B. 7 Corollary 5 If S1 and S2 are nonempty disjoint closed convex sets, and S1 is bounded, then S1 and S2 can be strongly separated. 4 Polyhedral Convex Sets S is a polyhedral set if S = {x ∈ IRn | Ax ≤ b} for some (A, b). x ¯ is an extreme point of S if whenever x ¯ can be represented as x ¯ = λx1 + (1 − λ)x2 for some x1 , x2 ∈ S and λ ∈ (0, 1), then x1 = x2 = x̄. d ∈ IRn is called a ray of S if whenever x ∈ X, x + αd ∈ S for all α ≥ 0. d is called an extreme ray of S if whenever d = λ1 d1 + λ2 d2 for rays d1 , d2 of S and λ1 , λ2 = 0, then d1 = αd2 for some α ≥ 0 or d2 = αd1 for some α ≥ 0. Theorem 6 The set S = {x ∈ IRn | Ax = b, x ≥ 0} contains an extreme point if S =  ∅. Theorem 7 Let S = {x ∈ IRn | Ax ≤ b} be nonempty. Then S has a finite number of extreme points and extreme rays. Theorem 8 Let S = {x ∈ IRn | Ax ≤ b} be nonempty. Then there exist a finite number of points x1 , . . . , xK and a finite number of directions d1 , . . . , dL with the property that x̄ ∈ S if and only if the following inequality system has a solution in λ1 , . . . , λK , µ1 , . . . , µL : K
xj λj + j=1 L
dj µj = x ¯ j=1 K
λj = 1 j=1 λ1 ≥ 0, . . . , λK ≥ 0, µ1 ≥ 0, . . . , µL ≥ 0 . 8 5 Convex Functions - Basics Let S ⊂ IRn be a nonempty convex set. A function f (·) : S → IR ∪ {−∞, +∞} is a convex function on S if: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) for all λ ∈ [0, 1] and x, y ∈ S. f (·) is strictly convex if the inequality above is strict for all λ ∈ (0, 1) and x=  y. f (·) is concave if −f (·) is convex. f (·) is strictly concave if −f (·) is strictly convex. Examples: 1. f (x) = ax + b 2. f (x) = |x| 3. f (x) = x2 − 2x + 3 √ 4. f (x) = x for x ≥ 0 5. f (x1 , x2 ) = 2x21 + x22 − 2x1 x2 We define Sα := {x ∈ S | f (x) ≤ α}. Sα is called the level set of f (·) at level α. Lemma 9 If f (·) is convex on S, then Sα is a convex set. Proof: Let x, y ∈ Sα . Then f (x) ≤ α and f (y) ≤ α, and so λ ∈ [0, 1] implies f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ≤ λα + (1 − λ)α = α , and so λx + (1 − λ)y ∈ Sα . Therefore Sα is a convex set. Note, the converse Lemma 9 is false. 9 Theorem 10 If S ⊂ IRn is an open convex set and f (·) is a real-valued convex function on S, then f (·) is continuous on S. Proof: We will prove this in three steps. Step 1. If f (·) is convex on S and x1 , . . . , xk ∈ S and λ1 , . . . , λk ≥ 0 and n j=1 λj = 1, then ⎛ f⎝ k
⎞ j⎠ λj x ≤ j=1 k
λj f (xj ) . j=1 Step 2. For each x ∈ S, there exists a β > 0 such that x ± βei ∈ S, for i = 1, . . . , n, where ei is the ith unit vector. Call these vectors z1 , . . . , z2n . Let Mx := max{f (z1 ), . . . , f (z2n )}. Since x lies in the interior of the convex hull of z1 , . . . , z2n , there exists tx > 0 such that B(x, tx ) := {y | y − x ≤ tx } also lies in the convex hull of z1 , . . . , z2n . Then for any y satisfying y − x ≤ tx it holds that 2n y = 2n j=1 λj zj for some appropriate λ1 , . . . , λ2n ≥ 0 and j=1 λj = 1 and so ⎛ ⎞ f (y) = f ⎝ 2n
λj zj ⎠ ≤ j=1 2n
λj f (zj ) ≤ Mx . j=1 Step 3. (The proof of the theorem). Without loss of generality, we assume that f (0) = 0 and we want to prove f (x) is continuous at x = 0. For any  > 0, we must exhibit a δ > 0 such that if y < δ then − ≤ f (y) ≤ . Let t > 0 and M be chosen so that y ≤ t implies f (y) ≤ M (from Step 2). Now let δ = t/M . Let y satisfy y < δ. Also, we can assume that M >  and write:       M  y = 1− y . 0+ M M  Since  ± M
y =  f (y) ≤ 1 − M
y  M   < t, it follows that f ± M
y ≤ M . Therefore:  f (0) +  f M   M  y ≤0+ ×M = .  M 10 We also have: 0=
M 1+ 
M  M 1 − y + y,  1 + M
and so 0 = f (0) ≤
M 1+ 
M  f −
M 1 f (y) M y + f (y) ≤ .
M +
 1+ M 1+ M 1 + M
Therefore f (y) ≥ −, and so − ≤ f (y) ≤ . ¯ in the direction d, denoted by The directional derivative of f (·) at x f (x̄, d) is defined as: � � f (x̄, d) = lim λ→0+ f (¯ x) x + λd) − f (¯ , λ when this limit exists. Lemma 5.1 Suppose that S is convex and f (·) : S → IR is convex, x ¯∈S � and x ¯ + λd ∈ S for all λ > 0 and sufficiently small. Then f (¯ x, d) exists. Proof: Let λ2 > λ1 > 0 be sufficiently small. Then  f (¯ x + λ1 d) = f ≤ λ1 x λ2 (¯ λ1 x λ2 f (¯  + λ2 d) + 1 −  + λ2 d) + 1 − λ1 λ2 λ1 λ2   (¯ x) f (¯ x) Rearranging the above, we have: f (¯ x) f (¯ x) x + λ1 d) − f (¯ x + λ2 d) − f (¯ ≤ . λ2 λ1 Thus the term and is f (¯ x+λd)−f (¯ x) λ is nondecreasing in λ, and so the limit exists,  � f (x̄, d) = inf λ>0 � so long as we allow f (x̄, d) = −∞. f (¯ x + λd) − f (¯ x) λ  , 11 6 Subgradients of Convex Functions Let S ⊂ IRn , and f (·) : S → IR be given. The epigraph of f (·), denoted epi f (·), is a subset of IRn+1 and is defined to be: epi f (·) := {(x, α) ∈ IRn+1 | x ∈ S, α ∈ IR, f (x) ≤ α} . The hypograph of f (·), denoted hyp f (·), is defined analogously as hyp f {(x, α) ∈ IRn+1 | x ∈ S, α ∈ IR, f (x) ≥ α} . Theorem 11 Let S be a nonempty convex set in IRn , and f (·) : S → IR. Then f (·) is a convex function if and only if epi f (·) is a convex set. Proof: Assume f (·) is convex. Let (x1 , α1 ), (x2 , α2 ) ∈ epi f (·). Then if λ ∈ (0, 1), λx1 + (1 − λ)x2 ∈ S, because x1 ∈ S, x2 ∈ S, and S is convex. Also α1 ≥ f (x1 ), α2 ≥ f (x2 ), f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) ≤ λα1 + (1 − λ)α2 . Thus (λx1 + (1 − λ)x2 ), (λα1 + (1 − λ)α2 ) ∈ epi f (·), and so epi f (·) is a convex set. Conversely, assume that epi f (·) is a convex set. Let x1 , x2 ∈ S, and let α1 = f (x1 ), α2 = f (x2 ). Then (x1 , α1 ) ∈ epi f (·) and (x2 , α2 ) ∈ epi f (·). Thus (λx1 + (1 − λ)x2 , λα1 + (1 − λ)α2 ) ∈ epi f (·). This means f (λx1 +(1−λ)x2 ) ≤ λα1 +(1−λ)α2 = λf (x1 )+(1−λ)f (x2 ), and so f (·) is a convex function. If f (·) : S → IR is a convex function, then ξ ∈ IRn is a subgradient of f (·) at x̄ ∈ S if ¯ for all x ∈ S . f (x) ≥ f (¯ x) + ξ t (x − x) Example: f (x) = x2 and let x ¯ = 3 and ξ = 6. Notice that from the basic inequality 0 ≤ (x − 3)2 = x2 − 6x + 9 we obtain for any x: x) + 6(x − x) ¯ , f (x) = x2 ≥ 6x − 9 = 9 + 6(x − 3) = f (¯ 12 which shows that ξ = 6 is a subgradient of f (·) at x = x̄ = 3. Example: f (x) = |x|. Then it is straightforward to show that: • If x ¯ > 0, then ξ = 1 is a subgradient of f (·) at x ¯ • If x ¯ < 0, then ξ = −1 is a subgradient of f (·) at x ¯ • If x ¯ = 0, then ξ ∈ [−1, 1] is a subgradient of f (·) at x. ¯ Theorem 12 Let S ⊂ IRn be a convex set and f (·) : S → IR be a convex ¯ ∈ intS, then there exists a vector ξ ∈ IRn such that the function. If x x) + ξ t (x − x)} ¯ supports epi f (·) at hyperplane H = {(x, y) ∈ IRn+1 | y = f (¯ x, f (¯ x) + ξ t (x − x) (¯ x)). In particular, f (x) ≥ f (¯ ¯ for all x ∈ S, and so ξ is a subgradient of f (·) at x̄. Proof: Because epi f (·) is a convex set, and (¯ x, f (¯ x)) belongs to the boundary of epi f (·), there exists a supporting hyperplane to epi f (·) at (¯ x)). x, f (¯ n+1 such that Thus there exists a nonzero vector (ξ, u) ∈ IR ¯ + uf (¯ x) for all (x, α) ∈ epi f (·) . ξ t x + uα ≤ ξ t x Let α be any scalar larger that f (x). Then as we make α arbitrarily large, the inequality must still hold. Thus u ≤ 0. If u < 0, we can re-scale so that u = −1. Then ξ t x − α ≤ ξ t x ¯ − f (¯ x), which upon rearranging yields: ¯ for all (x, α) ∈ epi f (·) . α ≥ f (¯ x) + ξ t (x − x) ¯ proving the theorem. In particular, with y = f (x), f (x) ≥ f (¯ x) + ξ t (x − x), It remains to show that u = 0 is an impossibility. If u = 0, then ξ t x ≤ ξ t x̄ ¯ ∈ int S, x for all x ∈ S. But since x ¯ + θξ ∈ S for θ > 0 and sufficiently t t x + θξ) ≤ ξ x, ¯ and so θξ t ξ ≤ 0. But this is a contradiction small. Thus ξ (¯ unless ξ = 0, which cannot be true since (ξ, u) =  (0, 0). The collection of subgradients of f (x) at x = x ¯ is denoted by ∂f (¯ x) and is called the subdifferential of f (·). We write ξ ∈ ∂f (x̄) if ξ is a subgradient of f (x) at x = x̄. 13 Theorem 13 Let S ⊂ IRn be a convex set, and let f (·) : S → IR be a ¯ ∈ intS there exists a subfunction defined on S. Suppose that for each x gradient vector ξ. That is, for each x̄ ∈ S there exists a vector ξ such that x) + ξ t (x − x) f (x) ≥ f (¯ ¯ for all x ∈ S. Then f (·) is a convex function on intS. Theorem 14 Let f (·) be convex on IRn , let S be a convex set and consider the problem: P: minx f (x) s.t. x∈S . Then x̄ ∈ S is an optimal solution of P if and only if f (·) has a subgradient ξ at x ¯ such that ξ t (x − x) ¯ ≥ 0 for all x ∈ S. ¯ ≥ 0 for Proof: Suppose f (·) has a subgradient ξ at x ¯ for which ξ t (x − x) t x) + ξ (x − x) all x ∈ S. Then f (x) ≥ f (¯ ¯ ≥ f (¯ x) for all x ∈ S. Hence x ¯ is an optimal solution of P . Conversely, suppose x̄ is an optimal solution of P . Define the following sets: A = {(d, α) ∈ IRn+1 | f (¯ x + d) < α + f (¯ x)} and ¯ + d ∈ S, α ≤ 0} . B = {(d, α) ∈ IRn+1 | x Both A and B are convex sets. Also A ∩ B = ∅. (If not, there is a d and an x + d) < α + f (¯ x), x ¯ + d ∈ S, so x α such that f (¯ x) ≤ f (¯ ¯ is not an optimal solution.) Therefore A and B can be separated by a hyperplane H = {(d, α) ∈ IRn+1 | ξ t d + uα = β} where (ξ, u) = 0, such that: • f (¯ x + d) < α + f (¯ x) ⇒ ξ t d + uα ≤ β • x ¯ + d ∈ S, α ≤ 0 ⇒ ξ t d + uα ≥ β 14 In the first implication α can be made arbitrarily large, so this means u ≤ 0. Also in the first implication setting d = 0 and α =  > 0 implies that β ≥ u. In the second implication setting d = 0 and α = 0 implies that β ≤ 0. Thus β = 0 and u ≤ 0. In the second implication setting α = 0 we have ξ t d ≥ 0 whenever x ¯ + d ∈ S, and so ξ t (¯ x + d − x) ¯ ≥ 0 whenever x ¯ + d ∈ S. Put another way, we have x ∈ S implies that ξ t (x − x) ¯ ≥ 0. It only remains to show that ξ is subgradient. Note that u < 0, for if u = 0 it would follow from the first implication that ξ t d ≤ 0 for any d, a contradiction. Since u < 0, we can re-scale so that u = −1. Now let d be given so that (¯ x + d) ∈ S and let α = f (¯ x + d) − f (¯ x) +  for some  > 0. Then f (¯ x), and it follows from the first x + d) < α + f (¯ x + d) + f (¯ x) −  ≤ 0 for all  > 0. Thus f (¯ x + d) ≥ implication that ξ t d − f (¯ ¯ + d, we have that if x ∈ S, ¯ + d ∈ S. Setting x = x x) + ξ t d for all x f (¯ ¯ f (x) ≥ f (¯ x) + ξ t (x − x), and so ξ is a subgradient of f (·) at x̄. 7 Differentiable Convex Functions Let f (·) : S → IR be given. f (·) is differentiable at x ¯ ∈ intS if there is a x), the gradient vector, such that f (x) = f (¯ x)t (x − x) vector ∇f (¯ x) + ∇f (¯ ¯ + x − xα(¯ ¯ x; x − x), ¯ where limx→¯x α(¯ x; x − x) ¯ = 0. Note that  ∇f (x̄) = ∂f (¯ x) ∂f (¯ x) ,..., ∂x1 ∂xn  . Lemma 7.1 Let f (·) : S → IR be convex. If f (·) is differentiable at x ¯ ∈ ¯ is the singleton set intS, then the collection of subgradients of f (·) at x {∇f (¯ x) = {∇f (¯ x)}, i.e., ∂f (¯ x)}. Proof: The set of subgradients of f (·) at x ¯ is nonempty by Theorem 12. Let ξ be a subgradient of f (·) at x̄. Then for any d and any λ > 0 we have: x + λd − x) ¯ = f (¯ x) + λξ t d . f (¯ x + λd) ≥ f (¯ x) + ξ t (¯ 15 Also f (¯ x) + λ∇f (¯ x + λd) = f (¯ x)t d + λdα(¯ x; λd) . Subtracting, we have 0 ≥ λ(ξ − ∇f (¯ x))t d − λdα(¯ x; λd) which is equivalent to: x; λd) . 0 ≥ (ξ − ∇f (¯ x))t d − dα(¯ As λ → 0 we have α(¯ x; λd) → 0. So (ξ − ∇f (¯ x))t d ≤ 0 for any d. This can only mean that ξ − ∇f (x̄). Theorem 15 If f (·) : S → IR is differentiable, then f (·) is convex if and only if ¯ ∈ int S. ¯ for all x, x f (x) ≥ f (¯ x) + ∇f (¯ x)t (x − x) 8 Exercises on Convex Sets and Functions 1. Let K ∗ denote the dual cone of the closed convex cone K ⊂ IRn , defined by: K ∗ := {y ∈ IRn | y T x ≥ 0 for all x ∈ K} . Prove that (K ∗ )∗ = K, thus demonstrating that the dual of the dual of a closed convex cone is the original cone. n ∈ IR | xj ≥ 2. Let IRn+ denote the nonnegative orthant, namely IRn+ = {x   ∗ n n n , 0, j = 1, . . . , n}. Considering IR+ as a cone, prove that IR+ = IR+ n thus showing that IR+ is self-dual.    n n 2 3. Let Qn = x ∈ IRn | x1 ≥ j=2 xj . Q is called the second-order cone, the Lorentz cone, or the ice-cream cone (I am not making this up). Considering Qn as a cone, prove that (Qn )∗ = Qn , thus showing that Qn is self-dual. 16 4. Prove Lemma 1 of the notes on Analysis of Convex Sets. 5. Let S1 and S2 be two nonempty sets in IRn , and define S1 {x | x = x1 + x2 for some x1 ∈ S1 , x2 ∈ S2 }. (a) Show that S1 sets.   S2 := S2 is a convex set if both S1 and S2 are convex  (b) Show by an example that S1 S2 is not necessarily a closed set, even if both S1 and S2 are closed convex sets. (c) Show that if either S1 or S2 is a bounded convex set, and both  S1 and S2 are closed sets, then S1 S2 is a closed set. 6. Suppose that f (·) is a convex function on IRn . Prove that ξ is a subgradient of f (·) at x̄ if and only if � f (x̄, d) ≥ ξ t d for all directions d ∈ IRn . 7. Prove Theorem 13 of the notes. 8. Consider the function f (·) : IRn → IR∪{−∞}∪{+∞}. Such a function is called an extended real-valued function. The epigraph of f (·) is defined as: epif (·) := {(x, α) | f (x) ≤ α} . We define f (·) to be a convex function if epif (·) is a convex set. Show that if f (·) : IRn → IR, then this definition of a convex function is equivalent to the standard definition of a convex function. 9. In class, we stated the meta result that the study of convex functions reduces to the study of convex functions on the real line. This exercise formalizes this observation and shows how we might use it to obtain results about convex function from results about convex functions on the real line. (a) Let f (x) be a real-valued function defined on an open set X ∈ IRn . Show that f (x) is a convex function if and only if for any two points x, y ∈ X, the function g(θ) := f (θx + (1 − θ)y) of the scalar θ is convex on the open interval θ ∈ (0, 1). 17 (b) Suppose that we have proved that a twice differentiable function g(θ) of the scalar θ is convex on the open interval θ ∈ (0, 1) if and only if its second derivative is nonnegative for every point in this interval. Use this fact, part (a), and the chain rule to show that a twice differentiable real-valued function f (x) defined on an open set X ∈ IRn is convex if and only if its Hessian matrix is positive semi-definite at every point in X. 10. (a) Let f (x) be a real-valued function defined on an open interval I = (l, u) of the real line. For any two points a < b in (l, u) , (a) let S(a, b) := f (b)−f be the secant slope of f (x) between the b−a points a and b. Prove the following result: Three Cord Lemma: f (x) is a convex function on an the interval I = (l, u) of the real line if and only if for any three points a < b < c in I we have S(a, b) ≤ S(a, c) ≤ S(b, c). (b) Use the Three Cord Lemma and the mean value theorem to show that a twice differentiable function f (x) of the scalar x is convex on the open interval I = (l, u) of the real line if and only if its second derivative is nonnegative for every point in this interval. (Hint: What does the Three Cord Lemma in part (a) say about the relationship between the derivative of f (x) at the points a and b ?) 11. Let S be a nonempty bounded convex set in IRn , and define f (·) : IRn → IR as follows: f (y) := sup{y t x | x ∈ S} . x The function f (·) is called the support function of S. (a) Prove that f (·) is a convex function. ¯ ∈ S. Show that x ¯ for some x ¯ ∈ ∂f (¯ y). (b) Suppose that f (¯ y) = y¯t x 12. Let f (·) : IRn → IR be a convex function. Show that if ξ ∈ ∂f (x̄), then the hyperplane ¯ H := {(x, α) | α = f (¯ x) + ξ t (x − x)} is a supporting hyperplane of epif (·) at (¯ x, f (¯ x)). 18 13. Let f (·) : IRn → IR be a convex function, and let x ¯ be given. Show that ∂f (x̄) is a closed convex set. 14. Let f1 (·), . . . , fk (·) : IRn → IR be differentiable convex functions, and define: f (x) := max{f1 (x), . . . , fk (x)} . Let I(x) := {i | f (x) = fi (x)}. Show that ⎧ ⎨ ∂f (¯ x) = ξ|ξ= ⎩
λi ∇fi (¯ x), i∈I(x)
⎫ ⎬ λi = 1, λi ≥ 0 for i ∈ I(x) ⎭ i∈I(x) . 15. Consider the function L∗ (u) defined by the following optimization problem, where X is a compact polyhedral set: L∗ (u) := minx ct x + ut (Ax − b) s.t. x∈X . (a) Show that L∗ (·) is a concave function. (b) Characterize the set of subgradients of L∗ (·) at any given u = ū.