{
  "id": "1504.03087",
  "version": "v1",
  "published": "2015-04-13T07:58:42.000Z",
  "updated": "2015-04-13T07:58:42.000Z",
  "title": "Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity",
  "authors": [
    "Tianyi Lin",
    "Shiqian Ma",
    "Shuzhong Zhang"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in [7] indicating that the multi-block ADMM for minimizing the sum of $N$ $(N\\geq 3)$ convex functions with $N$ block variables linked by linear constraints may diverge. It is therefore of great interest to investigate further sufficient conditions on the input side which can guarantee convergence for the multi-block ADMM. The existing results typically require the strong convexity on parts of the objective. In this paper, we present convergence and convergence rate results for the multi-block ADMM applied to solve certain $N$-block $(N\\geq 3)$ convex minimization problems without requiring strong convexity. Specifically, we prove the following two results: (1) the multi-block ADMM returns an $\\epsilon$-optimal solution within $O(1/\\epsilon^2)$ iterations by solving an associated perturbation to the original problem; (2) the multi-block ADMM returns an $\\epsilon$-optimal solution within $O(1/\\epsilon)$ iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka-Lojasiewicz property, which essentially covers most convex optimization models except for some pathological cases.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-04-13T07:58:42.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "strong convexity",
      "iteration complexity analysis",
      "convex minimization",
      "structured convex optimization problems",
      "multi-block admm returns"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150403087L"
    }
  }
}