2
$\begingroup$

I am looking for practical applications of semidefinite- programming. So far, I found that the low-rank matrix completion problem (recomendendattion matrices) can be expressed as a semidefinite program. The same goes for the combinatorial problem MAX-CUT.

  1. What is a practical applications of the MAX-CUT problem?
  2. What would be a third practical applications of semidefinite programming?

Would be nice if anyone could recommend any references. Thanks.

$\endgroup$
  • 1
    $\begingroup$ Do they use semidefinite programming in industry? $\endgroup$ – Rodrigo de Azevedo Apr 2 at 6:49
  • 1
    $\begingroup$ One application is determining whether a polynomial can be expressed as a sum of squares. Take a look at this. $\endgroup$ – Rodrigo de Azevedo Apr 2 at 6:51
  • 1
    $\begingroup$ If you haven't already read Boyd and Vandenberghe, it discusses a bunch of applications of SDPs (including in the exercises and the additional exercises). $\endgroup$ – littleO Apr 2 at 9:19
  • $\begingroup$ I've looked into Boyd and Vandenberghe. Problem is, these problems are convex or quasiconvex and since semidef. problems are just a subfield, things dont really fit. Or am I wrong here? $\endgroup$ – P.Müller Apr 3 at 4:12
  • $\begingroup$ @Rodrigo the sum of squares is quite interesting. I read math.stackexchange.com/questions/2410994/… . How would I have to choose A_i if I want to transform min tr(Q) s.t. A(Q)=b,Q⪰O to the standard sdp form min tr(C,Q) s.t. Q⪰O ,tr(A_i,Q)=b_i . $\endgroup$ – P.Müller Apr 3 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.