Semidefinite Program

Author

Anqi Fu and Balasubramanian Narasimhan

Introduction

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} \]

Example

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

## Problem dimensions
set.seed(4)
n <- 3   # matrix size
p <- 3   # number of equality constraints

## Generate random problem data
C <- matrix(rnorm(n^2), nrow = n)
sdp_data <- lapply(1:p, function(i) {
    list(A = matrix(rnorm(n^2), nrow = n), b = rnorm(1))
})

## Define and solve the CVXR problem
X <- Variable(c(n, n), symmetric = TRUE)
## Trace constraints: tr(A_i X) = b_i
trace_constraints <- lapply(sdp_data, function(s) {
    matrix_trace(s$A %*% X) == s$b
})
prob <- Problem(Minimize(matrix_trace(C %*% X)),
                constraints = c(list(PSD(X)), trace_constraints))
result <- psolve(prob)
check_solver_status(prob)

## Print result
cat(sprintf("The optimal value is %f\n", result))
cat("A solution X is\n")
print(value(X))

The optimal value is 1.395479
A solution X is
           [,1]       [,2]        [,3]
[1,]  0.3771715 -0.5692175  0.11666375
[2,] -0.5692175  0.8590482 -0.17606590
[3,]  0.1166638 -0.1760659  0.03608552

Session Info

R version 4.5.3 (2026-03-11)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3.1

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] CVXR_1.8.1

loaded via a namespace (and not attached):
 [1] slam_0.1-55       cli_3.6.5         knitr_1.51        ECOSolveR_0.6.1  
 [5] rlang_1.1.7       xfun_0.56         clarabel_0.11.2   otel_0.2.0       
 [9] gurobi_13.0-1     Rglpk_0.6-5.1     highs_1.12.0-3    cccp_0.3-3       
[13] scs_3.2.7         S7_0.2.1          jsonlite_2.0.0    backports_1.5.0  
[17] rprojroot_2.1.1   htmltools_0.5.9   Rmosek_11.1.1     gmp_0.7-5.1      
[21] piqp_0.6.2        rmarkdown_2.30    grid_4.5.3        evaluate_1.0.5   
[25] fastmap_1.2.0     yaml_2.3.12       compiler_4.5.3    codetools_0.2-20 
[29] htmlwidgets_1.6.4 Rcpp_1.1.1        here_1.0.2        osqp_1.0.0       
[33] lattice_0.22-9    digest_0.6.39     checkmate_2.3.4   Matrix_1.7-4     
[37] tools_4.5.3

Introduction

Example

Session Info

References