Consensus optimization ====================== Suppose we have a convex optimization problem with :math:N terms in the objective .. math:: \begin{array}{ll} \mbox{minimize} & \sum_{i=1}^N f_i(x)\\ \end{array} For example, we might be fitting a model to data and :math:f_i is the loss function for the :math:i\ th block of training data. We can convert this problem into consensus form .. math:: \begin{array}{ll} \mbox{minimize} & \sum_{i=1}^N f_i(x_i)\\ \mbox{subject to} & x_i = z \end{array} We interpret the :math:x_i as local variables, since they are particular to a given :math:f_i. The variable :math:z, by contrast, is global. The constraints :math:x_i = z enforce consistency, or consensus. 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: .. math:: \begin{array}{lll} % xbar, u parameters in prox. % called proximal operator. x^{k+1}_i & := & \mathop{\rm argmin}_{x_i}\left(f_i(x_i) + (\rho/2)\left\|x_i - \overline{x}^k + u^k_i \right\|^2_2 \right) \\ % u running sum of errors. u^{k+1}_i & := & u^{k}_i + x^{k+1}_i - \overline{x}^{k+1} \end{array} where :math:\overline{x}^k = (1/N)\sum_{i=1}^N x^k_i. The following code carries out consensus ADMM, using CVXPY to solve the local subproblems. We split the :math:x_i variables across :math:N different worker processes. The workers update the :math:x_i in parallel. A master process then gathers and averages the :math:x_i and broadcasts :math:\overline x back to the workers. The workers update :math:u_i locally. .. code:: from cvxpy import * import numpy as np from multiprocessing import Process, Pipe # Number of terms f_i. N = ... # A list of all the f_i. f_list = ... def run_worker(f, pipe): xbar = Parameter(n, value=np.zeros(n)) u = Parameter(n, value=np.zeros(n)) f += (rho/2)*sum_squares(x - xbar + u) prox = Problem(Minimize(f)) # ADMM loop. while True: prox.solve() pipe.send(x.value) xbar.value = pipe.recv() u.value += x.value - xbar.value # Setup the workers. pipes = [] procs = [] for i in range(N): local, remote = Pipe() pipes += [local] procs += [Process(target=run_process, args=(f_list[i], remote))] procs[-1].start() # ADMM loop. for i in range(MAX_ITER): # Gather and average xi xbar = sum(pipe.recv() for pipe in pipes)/N # Scatter xbar for pipe in pipes: pipe.send(xbar) [p.terminate() for p in procs]