A semidefinite program (SDP) is an optimization problem of the form $$ \begin{array}{ll} \mbox{minimize} & \mathbf{tr}(CX) \\ \mbox{subject to} & \mathbf{tr}(A_iX) = b_i, \quad i=1,\ldots,p \\ & X \succeq 0, \end{array} $$ where $\mathbf{tr}$ is the trace function, $X \in \mathcal{S}^{n}$ is the optimization variable and $C, A_1, \ldots, A_p \in \mathcal{S}^{n}$, and $b_1, \ldots, b_p \in \mathcal{R}$ are problem data, and $X \succeq 0$ is a matrix inequality. Here $\mathcal{S}^{n}$ denotes the set of $n$-by-$n$ symmetric matrices.
An example of an SDP is to complete a covariance matrix $\tilde \Sigma \in \mathcal{S}^{n}_+$ with missing entries $M \subset \{1,\ldots,n\} \times \{1,\ldots,n\}$: $$ \begin{array}{ll} \mbox{minimize} & 0 \\ \mbox{subject to} & \Sigma_{ij} = \tilde \Sigma_{ij}, \quad (i,j) \notin M \\ & \Sigma \succeq 0, \end{array} $$
In the following code, we solve a SDP with CVXPY.
In [9]:
# Import packages.
import cvxpy as cp
import numpy as np
# Generate a random SDP.
n = 3
p = 3
np.random.seed(1)
C = np.random.randn(n, n)
A = []
b = []
for i in range(p):
A.append(np.random.randn(n, n))
b.append(np.random.randn())
# Define and solve the CVXPY problem.
# Create a symmetric matrix variable.
X = cp.Variable((n,n), symmetric=True)
# The operator >> denotes matrix inequality.
constraints = [X >> 0]
constraints += [
cp.trace(A[i]@X) == b[i] for i in range(p)
]
prob = cp.Problem(cp.Minimize(cp.trace(C@X)),
constraints)
prob.solve()
# Print result.
print("The optimal value is", prob.value)
print("A solution X is")
print(X.value)