[mycologos]

How useful is reducing to a semidefinite program in reality? A fair amount of stuff seems to conclude with "now that we've reduced to an SDP, it's all polytime from here baby, so we're done modulo boring implementation details that nobody cares about". But I've tried and failed to understand how meaningful that polytime is in a practical sense. Anybody know?

[cevi]

In practice, even storing the matrices that show up in the problem formulation can be prohibitive, let alone running a solver. Often you need to take advantage of sparsity in a nontrivial way (see e.g. COSMO [1]), or take advantage of cases where the solution can be approximated by a low rank matrix, and recently there has been a trend in using first-order methods like ADMM rather than full interior-point algorithms. The review article [2] from 2019 gives a feel for how much work has gone into making large-scale semidefinite programming possible, but has this sentence in their conclusion section:

"Semidefinite programming is still far from being a mature technology like linear or quadratic programming."

[1] https://link.springer.com/article/10.1007/s10957-021-01896-x [2] https://www.annualreviews.org/doi/pdf/10.1146/annurev-contro...

[nihzm]

From my understanding nowadays SDP solvers are becoming well developed, even the open source ones. Also, from my limited experience it is usually the case that the problem being cast into an SDP has no other good ways of solving it, so polytime is better than no solution / NP solutions.