A Single-Phase, Proximal Path-Following Framework

作     者：Quoc Tran-Dinh Kyrillidis, Anastasios Cevher, Volkan 

作者机构：Univ North Carolina Chapel Hill Dept Stat & Operat Res Chapel Hill NC 27599 USA Rice Univ Dept Comp Sci Houston TX 77005 USA Ecole Polytech Fed Lausanne Lab Informat & Inference Syst CH-1015 Lausanne Switzerland 

出 版 物：《MATHEMATICS OF OPERATIONS RESEARCH》 (运筹学数学)

年 卷 期：2018年第43卷第4期

页      面：1326-1347页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：National Science Foundation [DMS-1619884] NAFOSTED [101.01-2017.315] European Research Council [ERC Future Proof] [SNF 200021-146750, SNF CRSII2-147633] European Research Council under the European Union European Research Council (ERC) Funding Source: European Research Council (ERC) 

主　　题：path-following scheme proximal Newton method interior-point method nonsmooth convex optimization self-concordant barrier 

摘      要：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.