ADMM (version 0.3.4)

admm.sdp: 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 \geq 0 $$ with \(A(X)_i = \textrm{tr}(A_i^\top X) = b_i\) for \(i=1,\ldots,m\) and \(X \geq 0\) stands for positive-definiteness of the matrix \(X\). In the standard form, matrices \(C, A_1,A_2,\ldots,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
)

Value

a named list containing

x

a length-\(n\) solution vector

history

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

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+\sqrt{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.

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.

Author

Kisung You

References

wen_alternating_2010aADMM

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
run = admm.sdp(C,A,b)
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)

if (FALSE) {
## 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[[1]]*X) == b[1],
  sum_entries(A[[2]]*X) == b[2]
)
myp = Problem(myobj, mycon)        # problem

# run and visualize
res  = solve(myp)
Xsol = res$getValue(X)

opar = par(no.readonly=TRUE)
par(mfrow=c(1,2), pty="s")
image(run$X, axes=FALSE, main="ADMM result")
image(Xsol,  axes=FALSE, main="CVXR result")
par(opar)
}