SDP basics#

A semidefinite program is an optimization problem whose unknown is a matrix. SDPLab uses the following primal form:

\[\min_X \quad \langle C, X\rangle \quad \text{s.t.} \quad \mathcal{A}X = b,\quad X \succeq 0.\]

Each symbol has a direct coding meaning:

  • \(X \in \mathrm{dom}\) is the unknown primal element – a Hermitian matrix here, but dom may be any Euclidean Jordan algebra space, so a nonnegative vector or a tree of blocks works the same way.

  • \(C \in \mathrm{dom}\) is the symmetric or Hermitian cost matrix.

  • \(\langle C, X\rangle\) is the scalar objective value.

  • \(\mathcal{A}: \mathrm{dom} \to \mathrm{cod}\) is a linear constraint operator.

  • \(b \in \mathrm{cod}\) is the desired constraint value.

  • \(X \succeq 0\) means that \(X\) is positive semidefinite.

Why the trace appears#

For dense real or complex matrices, the expression \(\langle C, X\rangle\) is the matrix analogue of a dot product. If \(C\) is the cost matrix, then entries of \(X\) aligned with large positive entries of \(C\) make the objective larger; entries aligned with negative directions make it smaller.

Linear constraints#

The equation \(\mathcal{A}X = b\) should be read as “apply the constraint operator to the matrix.” In the common dense-vector case, this means a list of trace equations:

\[(\mathcal{A}X)_i = \langle A_i, X\rangle = b_i, \qquad i = 0,\ldots,m-1.\]

The matrices \(A_i\) are not stored by sdplab.problem.SDPProblem itself. They live inside the SpaceCore linear operator that represents \(\mathcal{A}\), which may materialize them or stay matrix-free.

Dual variables#

The dual variable \(y\) lives in the same space as \(b\). The adjoint operator

\[\mathcal{A}^\dagger: \mathrm{cod} \to \mathrm{dom}\]

moves \(y\) back into matrix space. SDPLab solvers often use the dual slack expression

\[\mathcal{A}^\dagger y - C.\]

Its eigenvalues are important because semidefinite constraints are spectral: they are constraints on eigenvalues.