On the Convergence Time of Dual Subgradient Methods for Strongly Convex Programs

DOI10.1109/TAC.2017.2738153MaRDI QIDQ4567169zbMATH OpenOpenAlexFDO

Authors

Publication date 27 June 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Convex programming (90C25) Methods of reduced gradient type (90C52)

Abstract: This paper studies the convergence time of dual gradient methods for general (possibly non-differentiable) strongly convex programs. For general convex programs, the convergence time of dual subgradient/gradient methods with simple running averages (running averages started from iteration $0$) is known to be $O(frac1epsilo{n}^2)$. This paper shows that the convergence time for general strongly convex programs is $O(frac1epsilon)$. This paper also considers a variation of the average scheme, called the sliding running averages, and shows that if the dual function of the strongly convex program is locally quadratic (Note that the locally quadratic property is implied by the locally strongly concave property.) then the convergence time of the dual gradient method with sliding running averages is $O(log(frac1epsilon))$. The convergence time analysis is further verified by numerical experiments.

Recommendations

• On the convergence of a dual-primal substructuring method
• Primal convergence from dual subgradient methods for convex optimization
• On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
• Rate of convergence analysis of dual-based variables decomposition methods for strongly convex problems
• Ergodic, primal convergence in dual subgradient schemes for convex programming
• scientific article; zbMATH DE number 3965847
• scientific article; zbMATH DE number 1538165
• Dual convergence for penalty algorithms in convex programming
• On Dual Convergence and the Rate of Primal Convergence of Bregman’s Convex Programming Method
• Convergence of duality bound method in partly convex programming

Cited in

(5)

• Rate of convergence analysis of dual-based variables decomposition methods for strongly convex problems
• Steelmaking-continuous casting scheduling problem with multi-position refining furnaces under time-of-use tariffs
• Note on time bounds of two-phase algorithms for \(L\)-convex function minimization
• On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
• An accelerated decentralized stochastic optimization algorithm with inexact model

This page was built for publication: On the Convergence Time of Dual Subgradient Methods for Strongly Convex Programs

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