Description
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 “Ax − b”4 =
!
“m
i=1
(at
ix − bi)
4
#1/4
where A ∈ Rm×n and b ∈ Rm. Formulate this problem as a QCQP.
3. Consider the LP problem:
min eT x + f
s.t. aT
i x + bi = 0, i = 1, · · · , m
cT
i x + di ≤ 0, i = 1, cdots, k
Find A0, · · · , An to formulate this problem as a SDP:
min eT x + 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
x∗ ≥ 0, ∇f(x∗
) ≥ 0, [∇f(x∗
)]
i x∗
i = 0, i = 1, · · · , n
Prove that x∗ is a solution of the optimization problem.
