Consensus Optimization

Author

CVXPY Developers and Balasubramanian Narasimhan

Introduction

This example is adapted from the CVXPY documentation on consensus optimization.

Suppose we have a convex optimization problem with $N$ terms in the objective:

$\begin{array}{ll} minimize & \sum_{i = 1}^{N} f_{i} (x) . \end{array}$

For example, we might be fitting a model to data and $f_{i}$ is the loss function for the $i$ th block of training data.

We can convert this problem into consensus form:

$\begin{array}{ll} minimize & \sum_{i = 1}^{N} f_{i} (x_{i}) \\ subject to & x_{i} = z, \end{array}$

where we interpret the $x_{i}$ as local variables (particular to a given $f_{i}$ ) and $z$ as the global variable. The constraints $x_{i} = z$ enforce consistency, or consensus.

ADMM Algorithm

We can solve a problem in consensus form using the Alternating Direction Method of Multipliers (ADMM). Each iteration of ADMM reduces to the following updates:

$\begin{array}{lll} x_{i}^{k + 1} & := & \arg min_{x_{i}} (f_{i} (x_{i}) + \frac{ρ}{2} {‖ x_{i} - {\bar{x}}^{k} + u_{i}^{k} ‖}_{2}^{2}) \\ u_{i}^{k + 1} & := & u_{i}^{k} + x_{i}^{k + 1} - {\bar{x}}^{k + 1} \end{array}$

where ${\bar{x}}^{k} = \frac{1}{N} \sum_{i = 1}^{N} x_{i}^{k}$ .

Example: Consensus Least Squares

We illustrate the consensus ADMM approach on a simple least-squares problem where the data is split across $N$ blocks. The original problem is:

$minimize ∥ A x - b ∥_{2}^{2},$

where $A \in R^{m \times n}$ and $b \in R^{m}$ .

We split $A$ and $b$ into $N$ blocks row-wise, so $f_{i} (x) = ∥ A_{i} x - b_{i} ∥_{2}^{2}$ .

set.seed(1)

## Problem dimensions
n <- 10        # variable dimension
m <- 400       # total measurements
N <- 4         # number of blocks
block_size <- m / N

## Generate problem data
A_full <- matrix(rnorm(m * n), nrow = m, ncol = n)
x_true <- rnorm(n)
b_full <- A_full %*% x_true + 0.1 * rnorm(m)

## Split data into N blocks
A_blocks <- lapply(1:N, function(i) {
    rows <- ((i-1) * block_size + 1):(i * block_size)
    A_full[rows, ]
})
b_blocks <- lapply(1:N, function(i) {
    rows <- ((i-1) * block_size + 1):(i * block_size)
    b_full[rows]
})

Centralized Solution

First, we solve the problem in the standard (non-distributed) way for comparison.

x_central <- Variable(n)
obj_central <- Minimize(sum_squares(A_full %*% x_central - b_full))
prob_central <- Problem(obj_central)
result_central <- psolve(prob_central)

x_central_val <- as.numeric(value(x_central))
cat(sprintf("Centralized solution status: %s\n", status(prob_central)))
cat(sprintf("Centralized objective: %.6f\n", result_central))

Centralized solution status: optimal
Centralized objective: 3.806978

ADMM Consensus Solution

Now we implement the consensus ADMM algorithm. In each iteration, we solve $N$ local subproblems using CVXR and then average to get the global update.

rho <- 1.0
MAX_ITER <- 50

## Initialize
x_vars <- matrix(0, nrow = n, ncol = N)   # local variables
u_vars <- matrix(0, nrow = n, ncol = N)   # dual variables
xbar <- rep(0, n)                          # global average

## Track convergence
obj_history <- numeric(MAX_ITER)

for (iter in seq_len(MAX_ITER)) {
    ## x-update: solve each local subproblem
    for (i in 1:N) {
        x_i <- Variable(n)
        f_i <- sum_squares(A_blocks[[i]] %*% x_i - b_blocks[[i]])
        augmented <- f_i + (rho / 2) * sum_squares(x_i - xbar + u_vars[, i])
        prob_i <- Problem(Minimize(augmented))
        result_i <- psolve(prob_i)
        x_vars[, i] <- as.numeric(value(x_i))
    }

    ## z-update: average the x_i
    xbar <- rowMeans(x_vars)

    ## u-update: update dual variables
    for (i in 1:N) {
        u_vars[, i] <- u_vars[, i] + x_vars[, i] - xbar
    }

    ## Compute objective at current average
    obj_history[iter] <- sum((A_full %*% xbar - b_full)^2)
}

cat(sprintf("ADMM objective after %d iterations: %.6f\n", MAX_ITER, obj_history[MAX_ITER]))
cat(sprintf("Centralized objective: %.6f\n", result_central))

ADMM objective after 50 iterations: 3.815041
Centralized objective: 3.806978

Convergence Plot

df_conv <- data.frame(
    iteration = 1:MAX_ITER,
    objective = obj_history
)

ggplot(df_conv, aes(x = iteration, y = objective)) +
    geom_line(color = "steelblue") +
    geom_hline(yintercept = result_central, linetype = "dashed",
               color = "red") +
    annotate("text", x = MAX_ITER * 0.7, y = result_central * 1.05,
             label = "Centralized optimum", color = "red") +
    labs(x = "Iteration", y = "Objective Value",
         title = "ADMM Consensus Convergence") +
    theme_minimal()

ADMM convergence: objective value over iterations

The ADMM consensus solution converges to match the centralized optimal solution.

Comparison of Solutions

cat("Max absolute difference between ADMM and centralized solution:\n")
cat(sprintf("  %.6e\n", max(abs(xbar - x_central_val))))

Max absolute difference between ADMM and centralized solution:
  2.464990e-03

Session Info

R version 4.5.2 (2025-10-31)
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] ggplot2_4.0.2 CVXR_1.8.1   

loaded via a namespace (and not attached):
 [1] gmp_0.7-5.1        generics_0.1.4     clarabel_0.11.2    slam_0.1-55       
 [5] lattice_0.22-9     digest_0.6.39      magrittr_2.0.4     evaluate_1.0.5    
 [9] grid_4.5.2         RColorBrewer_1.1-3 fastmap_1.2.0      jsonlite_2.0.0    
[13] Matrix_1.7-4       ECOSolveR_0.6.1    backports_1.5.0    scs_3.2.7         
[17] Rmosek_11.1.1      scales_1.4.0       codetools_0.2-20   cli_3.6.5         
[21] rlang_1.1.7        Rglpk_0.6-5.1      withr_3.0.2        yaml_2.3.12       
[25] otel_0.2.0         tools_4.5.2        osqp_1.0.0         Rcplex_0.3-8      
[29] checkmate_2.3.4    dplyr_1.2.0        gurobi_13.0-1      vctrs_0.7.1       
[33] R6_2.6.1           lifecycle_1.0.5    htmlwidgets_1.6.4  pkgconfig_2.0.3   
[37] cccp_0.3-3         pillar_1.11.1      gtable_0.3.6       glue_1.8.0        
[41] Rcpp_1.1.1         xfun_0.56          tibble_3.3.1       tidyselect_1.2.1  
[45] knitr_1.51         dichromat_2.0-0.1  highs_1.12.0-3     farver_2.1.2      
[49] htmltools_0.5.9    rmarkdown_2.30     labeling_0.4.3     piqp_0.6.2        
[53] compiler_4.5.2     S7_0.2.1

References

Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. (2011). “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers.” Foundations and Trends in Machine Learning, 3(1), 1–122.
Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.