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

• 成果类型: Article
• 署名作者: Quoc Tran-Dinh; Sun, Tianxiao; Lu, Shu
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1264-6
• 发表日期: 2019
• 页码: 173-223
• 关键词: proximal point algorithm; variational-inequalities; COMPLEMENTARITY; CONVERGENCE; DECOMPOSITION; extragradient

摘要

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(nu log(1/epsilon))-worst-case iteration-complexity to achieve an epsilon-solution, where nu is the barrier parameter and epsilon 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.