Semidefinite Programming
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.
admm.sdp( C, A, b, mu = 1, rho = 1, abstol = 1e-10, maxiter = 496, print.progress = FALSE )
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; |
a named list containing
a length-n solution vector
dataframe recording iteration numerics. See the section for more details.
When you run the algorithm, output returns not only the solution, but also the iteration history recording following fields over iterates,
object (cost) function value
feasibility tolerance for primal feasibility condition
feasibility tolerance for dual feasibility condition
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
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.
## 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) ## 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[[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) ## End(Not run)
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.