{
  "id": "1603.01681",
  "version": "v1",
  "published": "2016-03-05T05:18:06.000Z",
  "updated": "2016-03-05T05:18:06.000Z",
  "title": "A single-phase, proximal path-following framework",
  "authors": [
    "Quoc Tran-Dinh",
    "Anastasios Kyrillidis",
    "Volkan Cevher"
  ],
  "comment": "23 pages, 2 figures, 4 tables",
  "categories": [
    "math.OC"
  ],
  "abstract": "We propose a new proximal, path-following framework for a class of---possibly non-smooth---constrained convex problems. We consider settings where the non-smooth part is endowed with a proximity operator, and the constraint set is equipped with a self-concordant barrier. Our main contribution is a new re-parametrization of the optimality condition of the barrier problem, that allows us to process the objective function with its proximal operator within a new path following scheme. In particular, our approach relies on the following two main ideas. First, we re-parameterize the optimality condition as an auxiliary problem, such that a \"good\" initial point is available. Second, we combine the proximal operator of the objective and path-following ideas to design a single phase, proximal, path-following algorithm. Our method has several advantages. First, it allows handling non-smooth objectives via proximal operators, this avoids lifting the problem dimension via slack variables and additional constraints. Second, it consists of only a \\emph{single phase} as compared to a two-phase algorithm in [43] In this work, we show how to overcome this difficulty in the proximal setting and prove that our scheme has the same $\\mathcal{O}(\\sqrt{\\nu}\\log(1/\\varepsilon))$ worst-case iteration-complexity with standard approaches [30, 33], but our method can handle nonsmooth objectives, where $\\nu$ is the barrier parameter and $\\varepsilon$ is a desired accuracy. Finally, our framework allows errors in the calculation of proximal-Newton search directions, without sacrificing the worst-case iteration complexity. We demonstrate the merits of our algorithm via three numerical examples, where proximal operators play a key role to improve the performance over off-the-shelf interior-point solvers.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-05T05:18:06.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C06",
      "90C25",
      "90-08"
    ],
    "keywords": [
      "proximal path-following framework",
      "single-phase",
      "optimality condition",
      "class of-possibly non-smooth-constrained convex problems",
      "proximal-newton search directions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160301681T"
    }
  }
}