Optimization Online


Generalized Self-Concordant Functions: A Recipe for Newton-type Methods

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

Abstract: We study the smooth structure of convex functions by generalizing a powerful concept so-called \textit{self-concordance} introduced by Nesterov and Nemirovskii in the early 1990s to a broader class of convex functions, which we call \textit{generalized self-concordant functions}. This notion allows us to develop a unified framework for designing Newton-type methods to solve convex optimization problems. The proposed theory provides a mathematical tool to analyze both local and global convergence of Newton-type methods without imposing unverifiable assumptions as long as the underlying functionals fall into our generalized self-concordant function class. First, we introduce the class of generalized self-concordant functions, which covers standard self-concordant functions as a special case. Next, we establish several properties and key estimates of this function class, which can be used to design numerical methods. Then, we apply this theory to develop several Newton-type methods for solving a class of smooth convex optimization problems involving the generalized self-concordant functions. We provide an explicit step-size for the damped-step Newton-type scheme which can guarantee a global convergence without performing any globalization strategy. We also prove a local quadratic convergence of this method and its full-step variant without requiring the Lipschitz continuity of the objective Hessian. Then, we extend our result to develop proximal Newton-type methods for a class of composite convex minimization problems involving generalized self-concordant functions. We also achieve both global and local convergence without additional assumption. Finally, we verify our theoretical results via several numerical examples, and compare them with existing methods.

Keywords: Generalized self-concordance; Newton-type method; proximal Newton method; quadratic convergence; local and global convergence; convex optimization

Category 1: Convex and Nonsmooth Optimization

Citation: STOR-UNC-2017-b

Download: [PDF]

Entry Submitted: 04/11/2017
Entry Accepted: 04/12/2017
Entry Last Modified: 01/30/2018

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