Iteration complexity analysis of dual first-order methods for conic convex programming
From MaRDI portal
Abstract: In this paper we provide a detailed analysis of the iteration complexity of dual first order methods for solving conic convex problems. When it is difficult to project on the primal feasible set described by convex constraints, we use the Lagrangian relaxation to handle the complicated constraints and then, we apply dual first order algorithms for solving the corresponding dual problem. We give convergence analysis for dual first order algorithms (dual gradient and fast gradient algorithms): we provide sublinear or linear estimates on the primal suboptimality and feasibility violation of the generated approximate primal solutions. Our analysis relies on the Lipschitz property of the gradient of the dual function or an error bound property of the dual. Furthermore, the iteration complexity analysis is based on two types of approximate primal solutions: the last primal iterate or an average primal sequence.
Recommendations
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- Iteration-complexity of first-order penalty methods for convex programming
- Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Iteration-complexity of first-order augmented Lagrangian methods for convex programming
- Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
- On complexity analysis of the primal-dual interior-point method for second-order cone optimization problem
- scientific article; zbMATH DE number 3892945
- Convergence analysis of approximate primal solutions in dual first-order methods
- Primal-dual first-order methods for a class of cone programming
Cites work
- A Distributed Newton Method for Network Utility Maximization–I: Algorithm
- A fast dual proximal gradient algorithm for convex minimization and applications
- An <formula formulatype="inline"><tex Notation="TeX">$O(1/k)$</tex> </formula> Gradient Method for Network Resource Allocation Problems
- Application of a Smoothing Technique to Decomposition in Convex Optimization
- Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Computational complexity certification for dual gradient method: application to embedded MPC
- Computational complexity of inexact gradient augmented Lagrangian methods: application to constrained MPC
- Ergodic convergence in subgradient optimization
- Gradient methods for minimizing composite functions
- Interior-point Lagrangian decomposition method for separable convex optimization
- Lagrangian Relaxation via Ballstep Subgradient Methods
- On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
- On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
- Optimal scaling of a gradient method for distributed resource allocation
- Primal convergence from dual subgradient methods for convex optimization
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- Smooth minimization of non-smooth functions
- Variational Analysis
Cited in
(19)- A smooth primal-dual optimization framework for nonsmooth composite convex minimization
- Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Conic Programming
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Solving nearly-separable quadratic optimization problems as nonsmooth equations
- Complexity certifications of first-order inexact Lagrangian methods for general convex programming: application to real-time MPC
- Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)
- Generalizing the optimized gradient method for smooth convex minimization
- Augmented Lagrangian optimization under fixed-point arithmetic
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- Iteration-complexity of first-order penalty methods for convex programming
- On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
- Computational complexity certification for dual gradient method: application to embedded MPC
- Convergence analysis of approximate primal solutions in dual first-order methods
- On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent
- Primal-dual first-order methods for a class of cone programming
- On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems
- Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization
This page was built for publication: Iteration complexity analysis of dual first-order methods for conic convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2815553)
