I am interested in solving the following semidefinite optimization problem: \begin{equation} \begin{split} \underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\ &-\mathbb{I} \le X \le \mathbb{I} \\ &X - \sum_{k=1}^m \lambda_k A_k \ge 0, \end{split} \end{equation} where $\lambda,c \in \mathbb{R}^m$ and $X,A_k$, for $k = 1,\ldots,m$, are symmetric $n\times n$ matrices, where $c$ and the $A_k$'s are fixed. Further, $\mathbb{I}$ denotes the $n \times n$ identity matrix. I would like to solve such optimizations for $n$ large ($\mathcal{O}(10^3)$ and larger) and $m \sim 100$.

Are there any algorithms that perform better than alternating projection for those dimensions? What is the state of the art algorithm for such a problem?

  • 2
    $\begingroup$ Are the inequalities $ - \mathbb{I} \leq X \leq \mathbb{I}$ meant entrywise, implying that $X$ is diagonal with diagonal entries in $[-1,1]$, or in the psd sense, meaning that $X + \mathbb{I}$ is psd and $\mathbb{I} - X$ is psd? I suspect the latter, because the last inequality surely is meant as a psd inequality, right? $\endgroup$ – Jonas Frede Aug 24 '18 at 9:02
  • $\begingroup$ Yes, indeed, all three inequality conditions are meant to be semidefinite constraints. $\endgroup$ – Marc Aug 24 '18 at 12:49
  • 2
    $\begingroup$ Your problems appear to be well within the range of problems that are commonly solved primal-dual interior point methods. Depending on your accuracy requirements, using a primal-dual solver might be faster than solving by a first order method. Probably the best available first order solver code available is scs. github.com/cvxgrp/scs $\endgroup$ – Brian Borchers Aug 24 '18 at 21:42
  • $\begingroup$ Using available toolboxes for matlab that rely on primal-dual interior point methods I run out of memory for $n$ clearly less than 500 but I would like to go as large as possible. How to solve the optimization with interior point methods for larger system would also be a possibility to solve this problem. The accuracy requirements are not very high, though. I assumed that memory is the limiting factor and not time. Thanks a lot for the reference. $\endgroup$ – Marc Aug 25 '18 at 15:54
  • $\begingroup$ After the clarification of your constraints $-I \succeq X \succeq I$, it's clear that putting the problem in standard SDP form would require a lot of constraints, so I'm not surprised that you ran out of storage. I'd recommend scs, as long as you can get good enough solutions. $\endgroup$ – Brian Borchers Aug 25 '18 at 15:58

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.