{
  "id": "1512.08370",
  "version": "v1",
  "published": "2015-12-28T10:55:51.000Z",
  "updated": "2015-12-28T10:55:51.000Z",
  "title": "A Simple Parallel Algorithm with $O(1/t)$ Convergence Rate for General Convex Programs",
  "authors": [
    "Hao Yu",
    "Michael J. Neely"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "This paper considers convex programs with a general (possibly non-differentiable) convex object function and Lipschitz continuous convex inequality constraint functions and proposes a simple parallel algorithm with $O(1/t)$ convergence rate. Similar to the classical dual subgradient algorithm or the ADMM algorithm, the new algorithm has a distributed implementation when the object and constraint functions are decomposable. However, the new algorithm has faster $O(1/t)$ convergence rate compared with the best known $O(1/\\sqrt{t})$ convergence rate for the dual subgradient algorithm with averaged primals; and can solve convex programs with nonlinear constraints, which can not be handled by the ADMM algorithm. The new algorithm is applied to multipath network utility maximization problem such that a decentralized flow control algorithm with fast $O(1/t)$ convergence rate is obtained. The $O(1/t)$ convergence rate is further verified by numerical experiments.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-28T10:55:51.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "convergence rate",
      "simple parallel algorithm",
      "general convex programs",
      "network utility maximization problem",
      "convex inequality constraint functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151208370Y"
    }
  }
}