Optimization Online


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

Quoc Tran Dinh(quoctd***at***email.unc.edu)
Tianxiao Sun(tianxias***at***live.unc.edu)
Shu Lu(shulu***at***email.unc.edu)

Abstract: 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 a local quadratic convergence of both the 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: convex-concave saddle-point, nonsmooth constrained convex program, and nonsmooth convex program with linear constraints. We also provide three numerical examples to illustrate our theory and compare with existing methods.

Keywords: Self-concordant inclusion; generalized Newton-type methods; path-followingschemes; monotone inclusion; constrained convex programming; saddle-point problems

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 07/22/2017
Entry Accepted: 07/22/2017
Entry Last Modified: 07/22/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society