TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd
Exam (elaborations)
TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd (Solution Manual)
26 views 0 purchase
Course
TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd
Institution
Harvard University
Exam (elaborations) TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd (Solution Manual)
Convex Optimization
Solutions Manual
Stephen Boyd Lieven Vandenberghe
January 4, 2006
Chapter 2
Convex sets
Exercises
Exercises
De nition of convexity
2.1 Let C Rn be a convex set, with ...
TEST BANK FOR Convex Optimization 1st Edition By Stephen Boyd
All documents for this subject (2)
Seller
Follow
Exceldemics
Reviews received
Content preview
,Convex Optimization
Solutions Manual
Stephen Boyd Lieven Vandenberghe
January 4, 2006
,Chapter 2
Convex sets
, Exercises
Exercises
Definition of convexity
2.1 Let C ⊆ Rn be a convex set, with x1 , . . . , xk ∈ C, and let θ1 , . . . , θk ∈ R satisfy θi ≥ 0,
θ1 + · · · + θk = 1. Show that θ1 x1 + · · · + θk xk ∈ C. (The definition 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 definition of convex set. We illus-
trate the idea for k = 3, leaving the general case to the reader. Suppose that x 1 , x2 , x3 ∈ C,
and θ1 + θ2 + θ3 = 1 with θ1 , θ2 , θ3 ≥ 0. We will show that y = θ1 x1 + θ2 x2 + θ3 x3 ∈ 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 = θ1 x1 + (1 − θ1 )(µ2 x2 + µ3 x3 )
where µ2 = θ2 /(1 − θ1 ) and µ2 = θ3 /(1 − θ1 ). Note that µ2 , µ3 ≥ 0 and
θ2 + θ 3 1 − θ1
µ1 + µ 2 = = = 1.
1 − θ1 1 − θ1
Since C is convex and x2 , x3 ∈ C, we conclude that µ2 x2 + µ3 x3 ∈ C. Since this point
and x1 are in C, y ∈ 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 affine if and only if its intersection with any line is affine.
Solution. We prove the first part. The intersection of two convex sets is convex. There-
fore 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 ∈ 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 ∈ C for all θ ∈ [0, 1] and x, y ∈ C. Let
θ(k) be the binary number of length k, i.e., a number of the form
θ(k) = c1 2−1 + c2 2−2 + · · · + ck 2−k
with ci ∈ {0, 1}, closest to θ. By midpoint convexity (applied k times, recursively),
θ(k) x + (1 − θ (k) )y ∈ C. Because C is closed,
lim (θ(k) x + (1 − θ (k) )y) = θx + (1 − θ)y ∈ C.
k→∞
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 affine, or linear hull of a set S
is the intersection of all conic sets, or affine 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= {D | D convex, D ⊇ S}.
We will show that H = D by showing that H ⊆ D and D ⊆ H.
First we show that H ⊆ D. Suppose x ∈ H, i.e., x is a convex combination of some
points x1 , . . . , xn ∈ S. Now let D be any convex set such that D ⊇ S. Evidently, we have
x1 , . . . , xn ∈ D. Since D is convex, and x is a convex combination of x1 , . . . , xn , it follows
that x ∈ D. We have shown that for any convex set D that contains S, we have x ∈ D.
This means that x is in the intersection of all convex sets that contain S, i.e., x ∈ D.
Now let us show that D ⊆ H. Since H is convex (by definition) and contains S, we must
have H = D for some D in the construction of D, proving the claim.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Exceldemics. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $17.49. You're not tied to anything after your purchase.
