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?


migrated from mathoverflow.net Aug 24 '18 at 18:14

This question came from our site for professional mathematicians.

  • 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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.