1

Consider a semi-definite program with equality constraints where the variable $X$ is a block matrix. Denoting the different blocks of $X$ by $X_j$ where $j$ is an index, the standard form of the equality constraints is $$\sum_j {\rm tr}(A_{ij} X_j)=b_i,$$ where the $b_i$ are scalars and where the $A_{ij}$ are matrices. In addition one has a constraint that the $X_j$ are psd and one optimizes some linear function of the $X_j$.

Suppose we add a linear constraint of form $$\sum_j D_j X_j=0,$$ where the $D_j$ are matrices, where $D_j X_j$ denotes the product of the given matrices, and where the equality is a matrix equality. Such a linear constraint can be expressed in the standard form in an obvious way: simply find a set of matrices which is a basis (i.e., a basis for the vector space of matrices of given size), and require that the trace of $\sum_j D_j X_j$ with each matrix in that set vanishes. However, expressing this constraint in the standard form in that way can entail a significant memory overhead. For example, if all the $X_j$ and $D_j$ are $n$-by-$n$ matrices, then expressing it in standard form in this way requires $O(n^4)$ memory, while the $D_j$ require only $O(n^2)$ memory to store.

So, my questions: (1) is there a standard name for the kind of linear constraint that I mention? (2) do any currently available solvers support such a constraint?

Matt Hastings
  • 111
  • This constraint is just a linear constraint and most SDP solvers handle such constraints; e.g. SeDuMi. – KBS Aug 10 '22 at 22:25
  • Thanks @KBS. Can you explain the format to handle such a constraint in SeDuMi? I am only familiar with equality constraints with scalars on the r.h.s. – Matt Hastings Aug 11 '22 at 00:03
  • If you have a matrix equality constraint $A^TX=0$, you can write it as $e_i^TAXe_j=0$ for all $i,j$. Otherwise, you can use a parser like Yalmip or CVX if you are using Matlab. There is also CVX for Python. – KBS Aug 11 '22 at 07:14
  • @KBS It seems that what you are saying is exactly what I referred to by saying that such a constraint "can be expressed in the standard form in an obvious way". This indeed brings it to standard form, however it requires $O(n^4)$ memory as there are now $n^2$ independent constraints, and $e_j e_i^T A$ is stored separately for each. Perhaps one can store it with only $O(n)$ memory for each constraint if it uses sparse representation of the matrix, but this still is $O(n^3)$ memory. I am asking if there is a way to do it using only $O(n^2)$ memory. – Matt Hastings Aug 11 '22 at 15:03
  • Then you will have to explain why space is so important to you. Also, use a parser like Yalmip, it will deal with the matrix equality the correct way by correctly pre-processing it and passing the resulting program to SeDuMi. – KBS Aug 11 '22 at 16:08
  • If $n$ is of the order of a few thousand to ten thousand, then $n^2$ is easy to store in memory but $n^3$ is too big to store in memory for most machines. Plus, I would expect that there would be a large speedup in implementing the constraint directly using matrix multplication, though this would depend on the internals of the solver. It sounds like you are saying that you do not know any solver that is capable of using only $O(n^2)$ space in this case, is that correct? Thanks! – Matt Hastings Aug 11 '22 at 18:36

0 Answers0