Homework 3
Convex Optimization
1. Given symmetric matrices F0,F1,...,Fn,cast the following optimization problem as an
SDP
min (Ax + b)TF(x)−1(Ax + b)
s.t. F(x) ≻ 0
where F(x) = F0 + x1F1 + ··· + xnFn
2. Given symmetric matrices W0 and W1, find the dual of the optimization min
min xTW0X
s.t. xTW1x ≤ 1.
3. Use the duality idea to prove that the set is empty if the set
!λ | λ∈Rm,λ≥ 0,ATλ = 0,bTλ < 0"
is nonempty (where A ∈Rm×n).
4. Separating hyperplane between two polyhedra: formulate the following problem as an
LP (feasibility) problem. Find a separating hyperplane that strictly separates two polyhedra
P1 = {x | Ax ≼ b}, P2 = {x | Cx ≼ d}
then find a vector a ∈Rn and a scalar γ such that
aTx γ ∀x ∈ P1, aTx < γ ∀x ∈ P2
Hence infx∈P2 aTx γ supx∈P2 aTx Use LP duality to simplify the infimum and supremum in these conditions.
1
