SDP is a sort of cone-LP and optimize linear function over the intersection of an affine space and cone.
It helps solving NP-hard combinatorial optimization including approximation algorithm of max cut problem. Also, if separation problem in LP_C (lp over convex set) could be solved in polynomial time, general optimization problem could be solved in p-time as well by using ellipsoid method.
- Its feasible set is closed convex (= intersection of infinite subspace) Compare this with LP’s feasible set which is intersection of finite subspace and thus polyhedron
- for dual sdp, slater condition implies the closed cone = (A_1Y, …, A_nY) and therefore, to strong duality.
- under slater condition, [separation thm -> ferkas lemma <-> strong duality]
- g(
) – d* –intP – p* – intD – f(x). i.e intP implies strong duality and the existence of dual optimal solution.
The following is a diagram for SDP’s theory, solution, and application from Ryu01.
Comment is the energy for a writer, thanks!