Description
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 {x | x ∈ Rn, Ax ≤ b} 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
aT x > γ ∀x ∈ P1, aT x < γ ∀x ∈ P2
Hence infx∈P2 aT x > γ > supx∈P2 aT x Use LP duality to simplify the infimum and supremum
in these conditions
