1
$\begingroup$

What is the space complexity of a semidefinite program (SDP)? What is the answer to the same question for convex optimization problems in general?

$\endgroup$
7
  • $\begingroup$ Not a full answer, but since LP, QP, SOCP are all special cases of SDP they give lower bounds on SDP's space complexity. $\endgroup$
    – Richard
    Dec 25, 2022 at 2:00
  • 1
    $\begingroup$ Space and time complexity are attributes of an algorithm for solving a problem, not attributes of the problem itself. What algorithm are you interested in? $\endgroup$ Dec 25, 2022 at 2:40
  • $\begingroup$ If you're interested in the optimal space complexity, ADMM uses space that is a small multiple of the size of the problem data. $\endgroup$ Dec 25, 2022 at 2:43
  • $\begingroup$ Thanks @Brian. So, I am actually interested in the space complexity of a general semidefinite program where we minimize a linear function of an $n\times n$ psd matrix (say, X) and there are a total of $m$ equalities or inequalities linear in X. $\endgroup$ Dec 25, 2022 at 6:52
  • 1
    $\begingroup$ @BrianBorchers , can you provide me a reference where the space complexity of algorithms that are used to solve SDPs are mentioned? (I am sorry I am new to this field so, don't know a lot of references) $\endgroup$ Dec 26, 2022 at 2:02

1 Answer 1

4
$\begingroup$

For a problem with $m$ linear equality constraints and a $n$ by $n$ matrix variable, the problem data $A$, $b$, $C$ requires $O(mn^{2})$ storage for $A$, $O(m)$ storage for $b$, and $O(n^{2})$ storage for $C$. If $A$ is sparse (which it often is in practice), this can considerably reduce the required storage for the problem data. However, the worst case is $O(mn^{2})$ storage for the problem data.

The solution requires $O(n^{2})$ storage for $X$, $O(m)$ storage for $y$, and $O(n^{2})$ storage for the dual slack $Z$.

If you use a primal-dual barrier method (such as those used by CSDP, SDPA, SDPT3, SeDuMi, ...), then the storage required is $O(m^{2}+n^{2})$. See

Borchers, Brian, and Joseph G. Young. "Implementation of a primal–dual method for SDP on a shared memory parallel architecture." Computational Optimization and Applications 37, no. 3 (2007): 355-369.

First order methods can avoid the $O(m^{2})$ storage cost of the Schur complement matrix in the primal-dual method. For example, see the ADMM algorithm for SDP described in

Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2, no. 3 (2010): 203-230.

ADMM requires $O(mn^{2})$ storage for the problem data, $O(n^{2})$ storage for the solution, and $O(n^{2})$ storage for variables used in the algorithm. This assumes that an iterative method is used to solve the linear system of equations for $y$ in each iteration. Thus this algorithm has optimal storage complexity. However, this algorithm does not work very well in practice.

If direct factorization is used to solve the linear system of equations and $AA^{T}$ is fully dense, then $O(m^{2}+n^{2})$ storage is required. If $AA^{T}$ is sparse, then considerable storage savings may be possible.

Recently, there has been interest in methods that can avoid the $O(n^{2})$ storage cost for $X$ in the case where the problem is known to have a low-rank solution. See for example:

Yurtsever, Alp, Joel A. Tropp, Olivier Fercoq, Madeleine Udell, and Volkan Cevher. "Scalable semidefinite programming." SIAM Journal on Mathematics of Data Science 3, no. 1 (2021): 171-200.

Obligatory disclaimer: I'm an author of one of the papers cited above.

$\endgroup$
1
  • $\begingroup$ Thank you so much @Brian for your answer and for the references. They really are very helpful and exactly what I was looking for. :) $\endgroup$ Dec 27, 2022 at 18:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.