1
$\begingroup$

Given a symmetric $n\times n$ matrix $A$, I'm interested in the class of SDP problems that can be written canonically as: $$ \begin{align} \text{minimize} \quad &-\text{tr}(AX) \\ \text{subject to} \quad &\forall i, \, X_{ii} = 1 \\ & X \succeq 0. \end{align} $$ I understand that this is a convex problem so an efficeint algorithm exists, but I want to write my own code to solve this problem for pedagogical sake, and also to better interface with the current code I have.

Therefore, I'm wondering what is the best known algorithm for solving this class of SDP problem, and is there a documentation containing some form of pseudocode that I can refer to.

$\endgroup$
1
  • 2
    $\begingroup$ if you want an efficient and robust algorithm, use a mature well-supported solver, such as Mosek. If you want to write your own code, you will give up efficiency and robustness - your choice. $\endgroup$ Jul 18, 2020 at 16:37

1 Answer 1

2
$\begingroup$

Primal-dual interior point methods can solve this formulation efficiently and there are multiple open source codes available to do so. CSDP can solve it well and is documented here. If you use that paper, I'd ignore the operator $B$ to make things simpler. Alternatively, SDPT3 is also an excellent code and is documented here. That said, from a pedagogical point of view, these papers are a terrible place to start. In my opinion, a much better path is to start from Wright's book Primal-Dual Interior-Point Methods, which covers the algorithm for linear, not semidefinite, cones. Really, most of the algorithm is the same, but the primal and dual variables are no longer vectors, but matrices. In Wright's book, this means that $X$ and $S$ are matrices and no longer $Diag(x)$ and $Diag(s)$ respectively. This also adds the complication of symmetrization because the optimization steps will in general not be symmetric, but the CSDP and SDPT3 papers will cover what to do in this situation.

To be sure, I am aware that there is continued research on SDP max-cut relaxations and most likely algorithms, so it's possible that there is better than what I've suggested above. That said, those algorithms are really good and are a reasonable place to start.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .