A Single-Phase, Proximal Path-Following Framework

Quoc Tran-Dinh (), Anastasios Kyrillidis () and Volkan Cevher ()
Additional contact information
Quoc Tran-Dinh: Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599
Anastasios Kyrillidis: Department of Computer Science, Rice University, Houston, Texas 77005
Volkan Cevher: Laboratory for Information and Inference Systems, École Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland

Mathematics of Operations Research, 2018, vol. 43, issue 4, 1326-1347

Abstract: We propose a new proximal path-following framework for a class of constrained convex problems. We consider settings where the nonlinear—and possibly nonsmooth—objective part is endowed with a proximity operator, and the constraint set is equipped with a self-concordant barrier. Our approach relies on the following two main ideas. First, we reparameterize the optimality condition as an auxiliary problem, such that a good initial point is available; by doing so, a family of alternative paths toward the optimum is generated. Second, we combine the proximal operator with path-following ideas to design a single-phase, proximal path-following algorithm. We prove that our algorithm has the same worst-case iteration complexity bounds as in standard path-following methods from the literature but does not require an initial phase. Our framework also allows inexactness in the evaluation of proximal Newton 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.

Keywords: path-following scheme; proximal Newton method; interior-point method; nonsmooth convex optimization; self-concordant barrier (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0907 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:4:p:1326-1347

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().