Convergence analysis of approximate primal solutions in dual first-order methods
From MaRDI portal
Abstract: Dual first-order methods are powerful techniques for large-scale convex optimization. Although an extensive research effort has been devoted to studying their convergence properties, explicit convergence rates for the primal iterates have only been established under global Lipschitz continuity of the dual gradient. This is a rather restrictive assumption that does not hold for several important classes of problems. In this paper, we demonstrate that primal convergence rate guarantees can also be obtained when the dual gradient is only locally Lipschitz. The class of problems that we analyze admits general convex constraints including nonlinear inequality, linear equality, and set constraints. As an approximate primal solution, we take the minimizer of the Lagrangian, computed when evaluating the dual gradient. We derive error bounds for this approximate primal solution in terms of the errors of the dual variables, and establish convergence rates of the dual variables when the dual problem is solved using a projected gradient or fast gradient method. By combining these results, we show that the suboptimality and infeasibility of the approximate primal solution at iteration are no worse than when the dual problem is solved using a projected gradient method, and when a fast dual gradient method is used.
Recommendations
- On the linear convergence of the general first order primal-dual algorithm
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- On the convergence of a dual-primal substructuring method
- Acceleration and global convergence of a first-order primal-dual method for nonconvex problems
- Convergence analysis of primal-dual based methods for total variation minimization with finite element approximation
- Iteration complexity analysis of dual first-order methods for conic convex programming
- Convergence of the primal-dual Newton method for linear programming problems
- scientific article; zbMATH DE number 1054749
- Primal convergence from dual subgradient methods for convex optimization
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Accelerated gradient methods and dual decomposition in distributed model predictive control
- An <formula formulatype="inline"><tex Notation="TeX">$O(1/k)$</tex> </formula> Gradient Method for Network Resource Allocation Problems
- An Accelerated Dual Gradient-Projection Algorithm for Embedded Linear Model Predictive Control
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
- Cooperative distributed multi-agent optimization
- Double smoothing technique for large-scale linearly constrained convex optimization
- Ergodic, primal convergence in dual subgradient schemes for convex programming
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- scientific article; zbMATH DE number 3293978 (Why is no real title available?)
- scientific article; zbMATH DE number 3356467 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Multiuser optimization: distributed algorithms and error analysis
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
Cited in
(13)- Convergence of the dual variables for the primal affine scaling method with unit steps in the homogeneous case
- On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems
- Primal recovery from consensus-based dual decomposition for distributed convex optimization
- Iteration complexity analysis of dual first-order methods for conic convex programming
- Convergence Rate Analysis of Primal-Dual Splitting Schemes
- Duality between subgradient and conditional gradient methods
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- The approximate duality gap technique: a unified theory of first-order methods
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Optimal inexactness schedules for tunable oracle-based methods
- Primal and dual predicted decrease approximation methods
- Computational complexity certification for dual gradient method: application to embedded MPC
This page was built for publication: Convergence analysis of approximate primal solutions in dual first-order methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2834559)
