Homework 2
Convex Optimization
1. Given A ∈Rm×n and b ∈Rm, cast each of the following problems as LP
• min "Ax − b"1 s.t. "x"∞ ≤ 1
• min "x"1 s.t. "Ax − b"∞ ≤ 1
• min "Ax − b"1 + "x"∞
2. Consider the L4-norm approximation problem:
min
where A ∈Rm×n and b ∈Rm. Formulate this problem as a QCQP.
3. Consider the LP problem:
min eTx + f
s.
Find A0,··· ,An to formulate this problem as a SDP:
min eTx + f
s.t. A0 + A1x1 + ··· + Anxn ≼ 0
4. Consider the optimization problem
min f(x) s.t. x ≥ 0
where f is convex. Let x∗ be a point such that
Prove that x∗ is a solution of the optimization problem.
1
