1
$\begingroup$

Linear programming subsumed by each of

  1. Semidefinite programming (SDP)
  2. Convex programming (CXP)
  3. SOS programming (SSP)

Is there any relation between each pair in the three?

Are all three equivalent in expressive capability?

$\endgroup$
2
  • 1
    $\begingroup$ $LP\subset SDP\subset SSP\subset CXP$. Also, you can encode SSP as SDP by lifting. These slides are relevant: mit.edu/~parrilo/pubs/talkfiles/Eckman.pdf $\endgroup$ Jul 15, 2020 at 1:32
  • $\begingroup$ So it is rather $LP\subset_{poly} SDP=_{poly}SSP\subset_{poly} CXP$? By subscript $poly$ I mean you are blowing up the program only polynomially. So the inclusions are upto polynomial blowup? $\endgroup$
    – VS.
    Jul 15, 2020 at 1:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.