An Inexact Perturbed Path-Following Method for Lagrangian Decomposition in Large-Scale Separable Convex Optimization

DOI10.1137/11085311XzbMATH Open1284.90049arXiv1109.3323MaRDI QIDQ5300519FDOQ5300519

Carlo Savorgnan, Quoc Tran Dinh, Moritz Diehl, Ion Necoara

Publication date: 27 June 2013

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: In this paper, we propose an inexact perturbed path-following algorithm in the framework of Lagrangian dual decomposition for solving large-scale structured convex optimization problems. Unlike the exact versions considered in literature, we allow one to solve the primal problem inexactly up to a given accuracy. The inexact perturbed algorithm allows to use both approximate Hessian matrices and approximate gradient vectors to compute Newton-type directions for the dual problem. The algorithm is divided into two phases. The first phase computes an initial point which makes use of inexact perturbed damped Newton-type iterations, while the second one performs the path-following algorithm with inexact perturbed full-step Newton-type iterations. We analyze the convergence of both phases and estimate the worst-case complexity. As a special case, an exact path- following algorithm for Lagrangian relaxation is derived and its worst-case complexity is estimated. This variant possesses some differences compared to the previously known methods. Implementation details are discussed and numerical results are reported.

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

zbMATH Keywords

parallel algorithmself-concordant barriersmoothing techniqueseparable convex optimizationLagrangian decompositioninexact perturbed Newton-type method

Mathematics Subject Classification ID

Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Interior-point methods (90C51) Newton-type methods (49M15) Decomposition methods (49M27)

Cited In (19)

• Composite convex optimization with global and local inexact oracles
• An inexact dual fast gradient-projection method for separable convex optimization with linear coupled constraints
• Combining Lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems
• Self-concordant inclusions: a unified framework for path-following generalized Newton-type algorithms
• Generalized self-concordant functions: a recipe for Newton-type methods
• A partially parallel splitting method for multiple-block separable convex programming with applications to robust PCA
• Solving nearly-separable quadratic optimization problems as nonsmooth equations
• Fast inexact decomposition algorithms for large-scale separable convex optimization
• Trajectory-following methods for large-scale degenerate convex quadratic programming
• On the convergence rate of the augmented Lagrangian-based parallel splitting method
• Path-following gradient-based decomposition algorithms for separable convex optimization
• A note on augmented Lagrangian-based parallel splitting method
• An inexact interior-point Lagrangian decomposition algorithm with inexact oracles
• Numerical Structure of the Hessian of the Lagrange Dual Function for a Class of Convex Problems
• An augmented Lagrangian based algorithm for distributed nonconvex optimization
• An exterior point polynomial-time algorithm for convex quadratic programming
• A distributed Douglas-Rachford splitting method for multi-block convex minimization problems
• A proximal partially parallel splitting method for separable convex programs
• Linearized generalized ADMM-based algorithm for multi-block linearly constrained separable convex programming in real-world applications

This page was built for publication: An Inexact Perturbed Path-Following Method for Lagrangian Decomposition in Large-Scale Separable Convex Optimization

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