ECE 273: Convex Optimization and Applications
Spring 2021
Homework # 2
Due: Friday, April 23, 11:59pm,
via Gradescope
Collaboration Policy: This homework set will be graded for effort. Students who are able to (i)
provide correct and complete solutions to certain selected problems, and/or (ii) demonstrate
creative approaches towards problem solving, will receive Bonus points. This homework set
allows limited collaboration. You are expected to try to solve the problems on your own. You
may discuss a problem with other students to clarify any doubts, but you must fully understand
the solution that you turn in and write it up entirely on your own. Blindly copying results from
any resource (such as your friend, or the internet) will be considered a violation of academic
integrity. ∗
Suggested Readings. Review Lecture Notes 1− 6, video lectures, and Boyd Book Sec. 2.1.1, 2.1.2,
2.1.4, 2.2, 2.3.1, 2.3.2. Boyd’s book can be found online here.
1. Problem 1: Convex Combination and Convex Hull.
In this problem, you will provide a formal proof of properties of convex sets and convex
hull.
(a) Prove that a set C ⊂ Rn is convex if and only if it contains all possible convex
combinations of all its points, i.e., if and only if C contains all points of the form
m
∑
i=1
θixi, 0 ≤ θi ≤ 1,
m
∑
i=1
θi = 1, xi ∈ C, ∀i = 1, 2, · · · ,m, ∀m ≥ 2
[Hint: Use induction on m.]
(b) Prove that the following statements are equivalent:
i. Given a set A ⊂ Rn, the convex hull of A is the intersection of all convex sets
containing A.
ii. Given a set A ⊂ Rn, the convex hull of A is the set of all possible convex combi-
nations of points from A.
2. Problem 2: Polyhedral Sets. Solve Problem 2.8 from Boyd’s Book.
3. Problem 3: Solution of Quadratic Inequalities. Solve Problem 2.10 from Boyd’s Book.
∗
(
Œ|¶+`åŽ )
(
Œ|¶+`å Ž )
4. Problem 4: Operations Preserving Convexity.
(a) Suppose A ⊂ Rm and B ⊂ Rn are convex sets. Show that the following set C ⊂ Rm+n
is a convex set:
C = {[xT, yT]T, x ∈ A, y ∈ B}
(b) Suppose C ⊂ Rn is a convex set and S be a subspace in Rn. Show that the orthogonal
projection of C onto S is a convex set.
5. Problem 5: Norm Balls and Ellipsoids. Let ‖ · ‖ : Rn → R be a norm. Given, x0 ∈ Rn
and r > 0, recall the definition of a norm ball B‖·‖(x0, r):
B‖·‖(x0, r) := {x ∈ Rn, ‖x− x0‖ ≤ r}
Given a positive definite matrix P ∈ Sn++, define an ellipsoid E (with center xc ∈ Rn) as
E = {x ∈ Rn, (x− xc)TP−1(x− xc) ≤ 1}
(a) Show that B‖·‖(x0, r) is a convex set.
(b) Show that E is the image under an affine map of a suitable norm ball. Specify the
map and the norm ball.























































学霸联盟