# Semidefinite program¶

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

$\begin{split}\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}\end{split}$

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{split}\begin{array}{ll} \mbox{minimize} & 0 \\ \mbox{subject to} & \Sigma_{ij} = \tilde \Sigma_{ij}, \quad (i,j) \notin M \\ & \Sigma \succeq 0, \end{array}\end{split}$

## Example¶

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

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

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]]
{"ft_lang_label":"__label__en","ft_lang_prob":0.5407068,"math_prob":0.9999598,"size":1820,"snap":"2020-45-2020-50","text_gpt3_token_len":645,"char_repetition_ratio":0.089207046,"word_repetition_ratio":0.0,"special_character_ratio":0.39175823,"punctuation_ratio":0.17333333,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.0000075,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-10-30T12:58:13Z\",\"WARC-Record-ID\":\"<urn:uuid:3a6fa8ca-571b-4fbd-a2f6-aa4f9c85686a>\",\"Content-Length\":\"13156\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ce5cde90-2998-4f10-a036-a46a5b57e4fc>\",\"WARC-Concurrent-To\":\"<urn:uuid:74f94601-aaa2-4e53-b9b9-42ac8ad4c44b>\",\"WARC-IP-Address\":\"185.199.110.153\",\"WARC-Target-URI\":\"https://www.cvxpy.org/examples/basic/sdp.html\",\"WARC-Payload-Digest\":\"sha1:O3EXIFSZVITIIE5WGI7ODRBV2HOKJ7AP\",\"WARC-Block-Digest\":\"sha1:2T6TM6DFHPEABFHKFT6I6JQJJZKZ7FGB\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-45/CC-MAIN-2020-45_segments_1603107910815.89_warc_CC-MAIN-20201030122851-20201030152851-00159.warc.gz\"}"}