A Single-Phase, Proximal Path-Following Framework

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.


Published in:
Mathematics Of Operations Research, 43, 4, 1326-1347
Year:
Nov 01 2018
Publisher:
Catonsville, INFORMS
ISSN:
0364-765X
1526-5471
Keywords:
Laboratories:




 Record created 2018-12-13, last modified 2019-02-25


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)