A Single-Phase, Proximal Path-Following Framework

• 成果类型: Article
• 署名作者: Quoc Tran-Dinh; Kyrillidis, Anastasios; Cevher, Volkan
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; Rice University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0907
• 发表日期: 2018
• 页码: 1326-1347
• 关键词: interior-point methods; thresholding algorithm; retrieval; approximation; selection; barriers

摘要

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.