\[ \begin{array}{rl} {\rm maximize}&\sum_{j=1}^r \langle C_j, X_j\rangle\\ &\sum_{j=1}^r \langle A_{ij}, X_j \rangle \mathrel{\triangle} b_i\quad\text{for $i \in L$},\\ &\sum_{j=1}^r \langle A_{ij}, X_j \rangle = p_i\quad \text{for $i \in P$},\\ &\text{$X_1$, $\ldots$, $X_r$ are positive semidefinite,} \end{array} \]

where:

$X_1, \ldots, X_r$ are the variable matrices, the matrices we wish to find. Here, $X_j$ is an $n_j \times n_j$ real-valued symmetric matrix;
$C_1, \ldots, C_r$ are real-valued matrices specifying the objective function and $C_j$ is $n_j \times n_j$;
$\langle A, B\rangle = \mathop{\rm tr}(A^{\sf T} B)$ denotes the trace inner product of the matrices $A$ and $B$;
Matrix $A_{ij}$, for $i \in L$, is an $n_j \times n_j$ real-valued matrix, and each $b_i$ is a real number. So for each $i \in L$ we have a linear constraint, where $\triangle$ is one of the binary relations ${\leq}$, ${=}$, or ${\geq}$;
Matrix $A_{ij}$, for $i \in P$, is an $n_j \times n_j$ matrix whose entries are (possibly multivariate) Laurent polynomials with real coefficients (in a Laurent polynomial, variables can have negative exponents; this is useful in some applications when dealing, for example, with trigonometric sums-of-squares). Here $p_i$ is a real Laurent polynomial.

The problem above seems more general than a semidefinite programming problem, namely because of the polynomial constraints for $i \in P$. This is not the case, however, since each such polynomial constraint can be expressed as several linear constraints, as we will see below.

Notice moreover that the matrices giving the objective function and the constraints are not required to be symmetric as is usual in the semidefinite programming literature. We could assume that the matrices are symmetric since the variable matrices are symmetric: if $X$ is a symmetric matrix and $A$ is any matrix, then $\langle A, X\rangle = \frac{1}{2}\langle A + A^{\sf T}, X\rangle$. Sometimes however it is useful to allow for nonsymmetric matrices to be given, and the library will make sure to "translate" them so that the solver gets symmetric matrices as input, as it is usually expected.

SDPSL can be used to specify problems as defined above. The variables are specified by giving their sizes, and the matrices and constraints are then given. Numbers can be either double-precision floating-point numbers, or arbitrary-precision floating-point numbers via the GMP library.

Polynomial constraints

As mentioned above, polynomial constraints can be transformed into several linear constraints. This can be easily seen, since given a polynomial constraint

\[ \sum_{j=1}^r \langle A_{ij}, X_j \rangle = p_i \]

for $i \in P$, both the left and right-hand sides are Laurent polynomials. So we have a polynomial identity, that can be checked by verifying that corresponding monomials on each side have the same coefficient. This gives one linear constraint for each monomial occurring in the constraint (both on the left-hand side and on the right-hand side).

Here, it is not necessary to use the standard monomial basis. Suppose all polynomials occurring in the polynomial constraint above (that is, all polynomials that are entries of the matrices $A_{ij}$ and the polynomial $p_i$) belong to a certain linear subspace $U$ of the vector space of Laurent polynomials on the appropriate variables.

Then, given any basis of $U$, we may expand both the left-hand side and the right-hand side of the constraint on this basis. The polynomial identity can then be checked by equating the coefficients of the expansions.

Such basis change operation allows for many possible encodings of the polynomial constraints. In some applications, a change of basis can greatly improve solver performance. SDPSL provides ways in which such basis transformations can be performed.

Design assumptions

SDPSL was developed with some specific applications in mind, and therefore some implicit assumptions are made on the data. Knowning what is assumed of the data can lead to better performance when using the library.

In general, the assumptions made are the following:

There are few (say, less than a hundred) variables. This is usually the case, since many matrix variables might make the problem hard to solve with today's solvers. The exception could be 1-by-1 variables, and a future version of SDPSL might add the possibility of specifying many such variables (maybe in the form of a diagonal matrix variable). Note however that slack variables used to specify linear inequalities are automatically defined by SDPSL.
Variable matrices are of reasonable sizes, say $1000 \times 1000$. Larger matrices can still be specified, but notice that proper support for sparse matrices, what would save on memory, is lacking at the moment. (SDPSL provides matrix masks — see MatrixMask — but these only make the algorithms faster; the whole matrix is still stored.)
Polynomials occurring in the constraints are not too big (say, each one has something like hundreds of nonzero coefficients). Polynomials are implemented at the moment as C++ maps, mapping coefficients to monomials. Moreover, some operations on polynomials might not be very efficient if one considers very large polynomials; in particular, the multiplication algorithm is the standard $O(n^2)$ algorithm.

Next chapter: SDPSL basics

Table of Contents

Polynomial constraints

Design assumptions