Description

1. (40%) Consider the optimization problem
(1)
subject to
(a) (10%) Determine if the problem if (1) is a convex problem. Justify your answer.
(b) (10%) If Problem (1) is convex, use CVX to solve the problem. Write down the optimal value p∗ and an optimal point you obtained from CVX.
(c) (10%) Verify that the reported optimal point (x∗,y∗) satisfies the constraint inequality and yields the optimal value.
(d) (10%) Submit your source code as problem1.m or problem1.py.
2. (60%) Consider the optimization problem
minimize f0(x) (2) x∈Rn subject to ||Ax − b||1 ≤ ϵ
where A ∈ Rm×n, b ∈ Rm, and ϵ > 0, and f0(x) = length(x).
(a) (10%) Determine if Problem (2) is a convex problem. Justify your answer.
(b) (10%) Show that Problem (2) is a quasiconvex problem. (Hint: You need to show that f0(x) is a quasiconvex function in x.)
(c) (10%) Construct a family of functions ϕt : Rn → R such that
f(x) ≤ t ⇐⇒ ϕt(x) ≤ 0
and ϕt is convex for all t.
(d) (10%) Let n = 3 and m = 3. Let . Use CVX and the bisection
method your learned in class to solve the problem. Write down the optimal value p∗ and an optimal point x∗ you obtained from your algorithm. Make sure that the reported optimal point x∗ satisfies the constraint inequality and yields the optimal value.
(e) (10%) Repeat (2d) for .
(f) (10%) Submit your source code as problem2.m or problem2.py (along with its subroutines if any).
1
Guidelines of Homework Submission:
• You are allowed to discuss with other students, ask for hints from the TAs. But you have to write your answers and argument solely on your own, without looking at any part of anyone else’s answers. Sharing your written (or typed) answers with others is strongly prohibited. Both parties will get a zero-score penalty for this mis-conduct.
• Submit your answer online as a document file (in *.pdf only) that contains all answers in this problem set.
• Submit your files online onto the NTU Cool system. No paper shall be handed in. If needed, you can choose to write (sketch) your answers on a sheet first and convert the image(s) to a single pdf file.
(3) Homework received between t1 and t2 will be counted with a discount rate

where t is the submission time. Note that t2 − t1 is three hours.
2