Convergence Rates Analysis of The Quadratic Penalty Method and Its Applications to Decentralized Distributed Optimization

2017/11/29 by Huan Li, Li, Huan, Cong Fang +3
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1711.10802

openalex publication_date 2017/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

In this paper, we study a variant of the quadratic penalty method for linearly constrained convex problems, which has already been widely used but actually lacks theoretical justification. Namely, the penalty parameter steadily increases and the penalized objective function is minimized inexactly rather than exactly, e.g., with only one step of the proximal gradient descent. For such a variant of the quadratic penalty method, we give counterexamples to show that it may not give a solution to the original constrained problem. By choosing special penalty parameters, we ensure the convergence and further establish the convergence rates of O((1)/(√(K))) for the generally convex problems and O((1)/(K)) for strongly convex ones, where K is the number of iterations. Furthermore, by adopting Nesterov's extrapolation we show that the convergence rates can be improved to O((1)/(K)) for the generally convex problems and O((1)/(K²)) for strongly convex ones. When applied to the decentralized distributed optimization, the penalty methods studied in this paper become the widely used distributed gradient method and the fast distributed gradient method. However, due to the totally different analysis framework, we can improve their O((log K)/(√(K))) and O((log K)/(K)) convergence rates to O((1)/(√(K))) and O((1)/(K)) with fewer assumptions on the network topology for general convex problems. Using our analysis framework, we also extend the fast distributed gradient method to a communication efficient version, i.e., finding an ε solution in O((1)/(ε)) communications and O(\frac1ε^2+δ) computations for the non-smooth problems, where δ is a small constant.

Citations

• First-order methods of smooth convex optimization with inexact oracle
• Distributed Optimization Over Time-Varying Directed Graphs
• Smooth minimization of non-smooth functions
• Optimal Black-Box Reductions Between Optimization Objectives

Related

• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• EFIX: Exact Fixed Point Methods for Distributed Optimization
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Convergence Rate of a Penalty Method for Strongly Convex Problems with\n Linear Constraints
• Linear Convergence of Primal-Dual Gradient Methods and their Performance\n in Distributed Optimization