**$ 20.00**

# TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd (Solution Manual)

- A-Grades
- Rating : 0
- Grade :
**No Rating** - Questions : 0
- Solutions : 275
- Blog : 0
- Earned : $35.00

Convex Optimization

Solutions Manual

Stephen Boyd Lieven Vandenberghe

January 4, 2006

Chapter 2

Convex sets

Exercises

Exercises

Denition of convexity

2.1 Let C Rn be a convex set, with x1; : : : ; xk 2 C, and let 1; : : : ; k 2 R satisfy i 0,

1 + + k = 1. Show that 1x1 + + kxk 2 C. (The denition of convexity is that

this holds for k = 2; you must show it for arbitrary k.) Hint. Use induction on k.

Solution. This is readily shown by induction from the denition of convex set. We illustrate

the idea for k = 3, leaving the general case to the reader. Suppose that x1; x2; x3 2 C,

and 1 + 2 + 3 = 1 with 1; 2; 3 0. We will show that y = 1x1 + 2x2 + 3x3 2 C.

At least one of the i is not equal to one; without loss of generality we can assume that

1 6= 1. Then we can write

y = 1x1 + (1 1)(2x2 + 3x3)

where 2 = 2=(1 1) and 2 = 3=(1 1). Note that 2; 3 0 and

1 + 2 =

2 + 3

1 1

=

1 1

1 1

= 1:

Since C is convex and x2; x3 2 C, we conclude that 2x2 + 3x3 2 C. Since this point

and x1 are in C, y 2 C.

2.2 Show that a set is convex if and only if its intersection with any line is convex. Show that

a set is ane if and only if its intersection with any line is ane.

Solution. We prove the rst part. The intersection of two convex sets is convex. Therefore

if S is a convex set, the intersection of S with a line is convex.

Conversely, suppose the intersection of S with any line is convex. Take any two distinct

points x1 and x2 2 S. The intersection of S with the line through x1 and x2 is convex.

Therefore convex combinations of x1 and x2 belong to the intersection, hence also to S.

2.3 Midpoint convexity. A set C is midpoint convex if whenever two points a; b are in C, the

average or midpoint (a + b)=2 is in C. Obviously a convex set is midpoint convex. It can

be proved that under mild conditions midpoint convexity implies convexity. As a simple

case, prove that if C is closed and midpoint convex, then C is convex.

Solution. We have to show that x + (1 )y 2 C for all 2 [0; 1] and x; y 2 C. Let

(k) be the binary number of length k, i.e., a number of the form

(k) = c121 + c222 + + ck2k

with ci 2 f0; 1g, closest to . By midpoint convexity (applied k times, recursively),

(k)x + (1 (k))y 2 C. Because C is closed,

lim

k!1

((k)x + (1 (k))y) = x + (1 )y 2 C:

2.4 Show that the convex hull of a set S is the intersection of all convex sets that contain S.

(The same method can be used to show that the conic, or ane, or linear hull of a set S

is the intersection of all conic sets, or ane sets, or subspaces that contain S.)

Solution. Let H be the convex hull of S and let D be the intersection of all convex sets

that contain S, i.e.,

D =

\

fD j D convex; D Sg:

We will show that H = D by showing that H D and D H.

First we show that H D. Suppose x 2 H, i.e., x is a convex combination of some

points x1; : : : ; xn 2 S. Now let D be any convex set such that D S. Evidently, we have

x1; : : : ; xn 2 D. Since D is convex, and x is a convex combination of x1; : : : ; xn, it follows

that x 2 D. We have shown that for any convex set D that contains S, we have x 2 D.

This means that x is in the intersection of all convex sets that contain S, i.e., x 2 D.

Now let us show that D H. Since H is convex (by denition) and contains S, we must

have H = D for some D in the construction of D, proving the claim.

## [Solved] TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd (Solution Manual)

- This solution is not purchased yet.
- Submitted On 10 Feb, 2022 12:44:32

- A-Grades
- Rating : 0
- Grade :
**No Rating** - Questions : 0
- Solutions : 275
- Blog : 0
- Earned : $35.00