## Semidefinite Programming

### Description

We solve the following standard semidefinite programming (SDP) problem

\textrm{min}_X ~ \textrm{tr}(CX)

\textrm{s.t.} A(X)=b, ~ X ≥q 0

with A(X)_i = \textrm{tr}(A_i^\top X) = b_i for i=1,…,m and X ≥q 0 stands for positive-definiteness of the matrix X. In the standard form, matrices C, A_1,A_2,…,A_m are symmetric and solution X would be symmetric and positive semidefinite. This function implements alternating direction augmented Lagrangian methods.

### Usage

admm.sdp(
C,
A,
b,
mu = 1,
rho = 1,
abstol = 1e-10,
maxiter = 496,
print.progress = FALSE
)


### Arguments

 C an (n\times n) symmetric matrix for cost. A a length-m list of (n\times n) symmetric matrices for constraint. b a length-m vector for equality condition. mu penalty parameter; positive real number. rho step size for updating in (0, \frac{1+√{5}}{2}). abstol absolute tolerance stopping criterion. maxiter maximum number of iterations. print.progress a logical; TRUE to show the progress, FALSE to go silent.

### Value

a named list containing

x

a length-n solution vector

history

dataframe recording iteration numerics. See the section for more details.

### Iteration History

When you run the algorithm, output returns not only the solution, but also the iteration history recording following fields over iterates,

objval

object (cost) function value

eps_pri

feasibility tolerance for primal feasibility condition

eps_dual

feasibility tolerance for dual feasibility condition

gap

gap between primal and dual cost function.

We use the stopping criterion which breaks the iteration when all eps_pri,eps_dual, and gap become smaller than abstol.

Kisung You

### References

Wen Z, Goldfarb D, Yin W (2010). “Alternating direction augmented Lagrangian methods for semidefinite programming.” Mathematical Programming Computation, 2(3-4), 203–230. ISSN 1867-2949, 1867-2957, doi: 10.1007/s12532-010-0017-1.

### Examples

## a toy example
#  generate parameters
C  = matrix(c(1,2,3,2,9,0,3,0,7),nrow=3,byrow=TRUE)
A1 = matrix(c(1,0,1,0,3,7,1,7,5),nrow=3,byrow=TRUE)
A2 = matrix(c(0,2,8,2,6,0,8,0,4),nrow=3,byrow=TRUE)

A  = list(A1, A2)
b  = c(11, 19)

# run the algorithm
hst = run$history # visualize opar <- par(no.readonly=TRUE) par(mfrow=c(2,2)) plot(hst$objval,   type="b", cex=0.25, main="objective value")
plot(hst$eps_pri, type="b", cex=0.25, main="primal feasibility") plot(hst$eps_dual, type="b", cex=0.25, main="dual feasibility")
plot(hst$gap, type="b", cex=0.25, main="primal-dual gap") par(opar) ## Not run: ## comparison with CVXR's result require(CVXR) # problems definition X = Variable(3,3,PSD=TRUE) myobj = Minimize(sum_entries(C*X)) # objective mycon = list( # constraint sum_entries(A[]*X) == b, sum_entries(A[]*X) == b ) myp = Problem(myobj, mycon) # problem # run and visualize res = solve(myp) Xsol = res$getValue(X)