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$
7
  • 1
    $\begingroup$ Do they use semidefinite programming in industry? $\endgroup$
    – Rodrigo de Azevedo
    Commented Apr 2, 2019 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
    Commented Apr 2, 2019 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
    Commented Apr 2, 2019 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
    Commented Apr 3, 2019 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
    Commented Apr 3, 2019 at 4:49

0

Reset to default

You must log in to answer this question.