Semidefinite program

A semidefinite program (SDP) is an optimization problem of the form

.. math::

   \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 :math:\mathbf{tr} is the trace function, :math:X \in \mathcal{S}^{n} is the optimization variable and :math:C, A_1, \ldots, A_p \in \mathcal{S}^{n}, and :math:b_1, \ldots, b_p \in \mathcal{R} are problem data, and :math:X \succeq 0 is a matrix inequality. Here :math:\mathcal{S}^{n} denotes the set of :math:n-by-:math:n symmetric matrices.

An example of an SDP is to complete a covariance matrix :math:\tilde \Sigma \in \mathcal{S}^{n}_+ with missing entries :math:M \subset \{1,\ldots,n\} \times \{1,\ldots,n\}:

.. math::

   \begin{array}{ll}
   \mbox{minimize}   & 0 \\
   \mbox{subject to} & \Sigma_{ij} = \tilde \Sigma_{ij}, \quad (i,j) \notin M \\
                     & \Sigma \succeq 0,
   \end{array}

Example

In the following code, we solve a SDP with CVXPY.

.. code:: python

# 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)

.. parsed-literal::

The optimal value is 2.654348003008652
A solution X is
[[ 1.6080571  -0.59770202 -0.69575904]
 [-0.59770202  0.22228637  0.24689205]
 [-0.69575904  0.24689205  1.39679396]]