Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms

• Published in: Mathematical programming 2019-09, Vol.177 (1-2), p.173-223
• Main Authors: Tran-Dinh, Quoc, Sun, Tianxiao, Lu, Shu
• Format: Article
• Language: English
• Subjects: Algorithms; Calculus of Variations and Optimal Control; Optimization; Combinatorics; Computational geometry; Constraints; Convexity; Formulations; Full Length Paper; Inclusions; Iterative methods; Mathematical and Computational Physics; Mathematical Methods in Physics; Mathematics; Mathematics and Statistics; Mathematics of Computing; Numerical Analysis; Optimization; Saddle points; Theoretical
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-018-1264-6

We study a class of monotone inclusions called “self-concordant inclusion” which covers three fundamental convex optimization formulations as special cases. We develop a new generalized Newton-type framework to solve this inclusion. Our framework subsumes three schemes: full-step, damped-step, and path-following methods as specific instances, while allows one to use inexact computation to form generalized Newton directions. We prove the local quadratic convergence of both full-step and damped-step algorithms. Then, we propose a new two-phase inexact path-following scheme for solving this monotone inclusion which possesses an O ( ν log ( 1 / ε ) ) -worst-case iteration-complexity to achieve an ε -solution, where ν is the barrier parameter and ε is a desired accuracy. As byproducts, we customize our scheme to solve three convex problems: the convex–concave saddle-point problem, the nonsmooth constrained convex program, and the nonsmooth convex program with linear constraints. We also provide three numerical examples to illustrate our theory and compare with existing methods.