1
$\begingroup$

I have the following semidefinite program with $N$ semidefinite constraints,

\begin{equation*} \begin{aligned} \min_{\theta \in \mathbb{R},\; 0 \leq w \leq 1}&\quad \theta\\ \text{st:}&\quad \left[ \begin{array}{cc} \theta & x^{\top}_i \\ x_i & X^{\top} \text{diag(w)} X \end{array} \right] \succeq 0, \quad i = 1,\ldots, N \end{aligned} \end{equation*}

I want to ask if it is possible to reformulate the constraints to something simpler. A single SDP constraint, or something simpler that an SDP constraint. As $N$ grows, and the dimension of $X$ grows, the problem becomes very large and slow to solve.

$\endgroup$
1
  • $\begingroup$ Can you state precisely the shape of your variables / constants as it is quite ambiguous at the moment? As I read the problem now, the size of the SDP grows with $N$ but I don't see why the dimension of $X$ grows with $N$. Also, if you want to trivially convert a collection of $Y_i \succeq 0$ constraints into a single SDP constraint then you can just convert it to a block diagonal matrix, i.e., $\bigoplus_i Y_i \succeq 0$. This won't reduce the size of your problem though. $\endgroup$
    – Rammus
    Commented Sep 23, 2021 at 8:46

1 Answer 1

2
$\begingroup$

You can make a block-diagonal matrix with all these matrices as its blocks. The newly made matrix is PDS iff all these blocks are SDP. Of course the size of the matrix is so large, but number of PSD conditions decreases to 1.

$\endgroup$

You must log in to answer this question.

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