{
 "metadata": {
  "name": "",
  "signature": "sha256:24db0c6adba2b929f4959d6a53a8e6801eb92aa1df0d25a160f4d30979c9cd7e"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Consensus optimization"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Suppose we have a convex optimization problem with $N$ terms in the objective\n",
      "\n",
      "\\begin{array}{ll} \\mbox{minimize} & \\sum_{i=1}^N f_i(x)\\\\\n",
      "\\end{array}\n",
      "\n",
      "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.\n",
      "\n",
      "We can convert this problem into consensus form\n",
      "\n",
      "\\begin{array}{ll} \\mbox{minimize} & \\sum_{i=1}^N f_i(x_i)\\\\\n",
      "\\mbox{subject to} & x_i = z\n",
      "\\end{array}\n",
      "\n",
      "We interpret the $x_i$ as local variables, since they are particular to a given $f_i$. The variable $z$, by contrast, is global. The constraints $x_i = z$ enforce consistency, or consensus.\n",
      "\n",
      "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:\n",
      "\n",
      "\\begin{array}{lll}\n",
      "% xbar, u parameters in prox.\n",
      "% called proximal operator.\n",
      "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) \\\\\n",
      "% u running sum of errors.\n",
      "u^{k+1}_i & := & u^{k}_i + x^{k+1}_i - \\overline{x}^{k+1}\n",
      "\\end{array}\n",
      "\n",
      "where $\\overline{x}^k = (1/N)\\sum_{i=1}^N x^k_i$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The following code carries out consensus ADMM, using CVXPY to solve the local subproblems.\n",
      "\n",
      "We split the $x_i$ variables across $N$ different worker processes.\n",
      "The workers update the $x_i$ in parallel.\n",
      "A master process then gathers and averages the $x_i$ and broadcasts $\\overline x$ back to the workers.\n",
      "The workers update $u_i$ locally."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from cvxpy import *\n",
      "import numpy as np\n",
      "from multiprocessing import Process, Pipe\n",
      "\n",
      "# Number of terms f_i.\n",
      "N = ...\n",
      "# A list of all the f_i.\n",
      "f_list = ...\n",
      "\n",
      "def run_worker(f, pipe):\n",
      "    xbar = Parameter(n, value=np.zeros(n))\n",
      "    u = Parameter(n, value=np.zeros(n))\n",
      "    f += (rho/2)*sum_squares(x - xbar + u)\n",
      "    prox = Problem(Minimize(f))\n",
      "    # ADMM loop.\n",
      "    while True:\n",
      "        prox.solve()\n",
      "        pipe.send(x.value)\n",
      "        xbar.value = pipe.recv()\n",
      "        u.value += x.value - xbar.value\n",
      "\n",
      "# Setup the workers.\n",
      "pipes = []\n",
      "procs = []\n",
      "for i in range(N):\n",
      "    local, remote = Pipe()\n",
      "    pipes += [local]\n",
      "    procs += [Process(target=run_process, args=(f_list[i], remote))]\n",
      "    procs[-1].start()\n",
      "\n",
      "# ADMM loop.\n",
      "for i in range(MAX_ITER):\n",
      "    # Gather and average xi\n",
      "    xbar = sum(pipe.recv() for pipe in pipes)/N\n",
      "    # Scatter xbar\n",
      "    for pipe in pipes:\n",
      "        pipe.send(xbar)\n",
      "\n",
      "[p.terminate() for p in procs]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}