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

DOI10.1007/S10107-018-1264-6MaRDI QIDQ2316618zbMATH OpenOpenAlexWikidataFDO

Authors Tianxiao Sun, Shu Lu, Quoc Tran Dinh

Publication date 6 August 2019

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.07403

zbMATH Keywords

constrained convex programminggeneralized Newton-type methodsmonotone inclusionpath-following schemessaddle-point problemsself-concordant inclusion

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Large-scale problems in mathematical programming (90C06) Convex programming (90C25)

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 $mathcalOleft(sqrtulog(1/varepsilon)ight)$-worst-case iteration-complexity to achieve an $varepsilon$-solution, where $u$ is the barrier parameter and $varepsilon$ 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.

Recommendations

• Generalized self-concordant functions: a recipe for Newton-type methods
• Inexact proximal Newton methods for self-concordant functions
• scientific article; zbMATH DE number 1594503
• On generalized Newton algorithms: Quadratic convergence, path-following and error analysis
• A Newton Frank-Wolfe method for constrained self-concordant minimization
• An inexact Newton hybrid path-following algorithm for nonlinear programming
• A pathsearch damped Newton method for computing general equilibria
• scientific article; zbMATH DE number 7326968
• Convergence analysis of the Gauss-Newton method for convex inclusion and convex-composite optimization problems
• A general class of penalty/barrier path-following Newton methods for nonlinear programming

Cites work

• A B-differentiable equation-based, globally and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A feasible semismooth asymptotically Newton method for mixed complementarity problems
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator
• A logarithmic-quadratic proximal method for variational inequalities
• A nonsmooth version of Newton's method
• A primal-dual interior point method for nonlinear semidefinite programming
• A semismooth equation approach to the solution of nonlinear complementarity problems
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Alternating Projection-Proximal Methods for Convex Programming and Variational Inequalities
• An inexact perturbed path-following method for Lagrangian decomposition in large-scale separable convex optimization
• An inexact proximal path-following algorithm for constrained convex minimization
• Applications of a Splitting Algorithm to Decomposition in Convex Programming and Variational Inequalities
• Convex Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• Disciplined convex programming
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Dual extrapolation and its applications to solving variational inequalities and related problems
• Efficient evaluation of scaled proximal operators
• Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems
• Finite-Dimensional Variational Inequalities and Complementarity Problems
• Global Convergence of Damped Newton's Method for Nonsmooth Equations via the Path Search
• Gradient methods for minimizing composite functions
• scientific article; zbMATH DE number 4082855 (Why is no real title available?)
• scientific article; zbMATH DE number 3534286 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Implicit Functions and Solution Mappings
• Introductory lectures on convex optimization. A basic course.
• Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Local analysis of Newton-type methods for variational inequalities and nonlinear programming
• Newton's method for a class of nonsmooth functions
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Proximal splitting methods in signal processing
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• Robust Stochastic Approximation Approach to Stochastic Programming
• SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Signal Recovery by Proximal Forward-Backward Splitting
• Smoothing technique and its applications in semidefinite optimization
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Some recent advances in projection-type methods for variational inequalities
• Strongly Regular Generalized Equations
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Variational Analysis

Cited in

(9)

• Composite convex optimization with global and local inexact oracles
• Optimal step length for the Newton method: case of self-concordant functions
• A Newton Frank-Wolfe method for constrained self-concordant minimization
• An inexact interior-point Lagrangian decomposition algorithm with inexact oracles
• Generalized self-concordant functions: a recipe for Newton-type methods
• A new homotopy proximal variable-metric framework for composite convex minimization
• A single-phase, proximal path-following framework
• An inexact proximal path-following algorithm for constrained convex minimization
• Revisiting extragradient-type methods. I: Generalizations and sublinear convergence rates

Describes a project that uses

Uses Software

• SeDuMi
• SDPT3
• YALMIP
• SDPNAL+

This page was built for publication: Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2316618)