Aug-PDG: Linear Convergence of Convex Optimization with Inequality Constraints

2020/11/17 by Min Meng, Xiuxian Li, Meng, Min +1 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.2011.08569

arxiv created 2020/11/17 · arxiv updated 2020/11/18

Abstract

This paper investigates the convex optimization problem with general convex inequality constraints. To cope with this problem, a discrete-time algorithm, called augmented primal-dual gradient algorithm (Aug-PDG), is studied and analyzed. It is shown that Aug-PDG can converge semi-globally to the optimizer at a linear rate under some mild assumptions, such as the quadratic gradient growth condition for the objective function, which is strictly weaker than strong convexity. To our best knowledge, this paper is the first to establish a linear convergence for the studied problem in the discrete-time setting, where an explicit bound is provided for the stepsize. Finally, a numerical example is presented to illustrate the efficacy of the theoretical finding.

Citations

• Stability of primal–dual gradient dynamics and applications to network optimization

Cited by

• Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• On Faster Convergence of Scaled Sign Gradient Descent
• Sparse Sensor Allocation for Inverse Problems of Detecting Sparse Leaking Emission Sources

Related

• Exponential Convergence of Augmented Primal-dual Gradient Algorithms for Partially Strongly Convex Functions
• Fast Primal-Dual Gradient Method for Strongly Convex Minimization Problems with Linear Constraints
• A Unified Primal-Dual Algorithm Framework for Inequality Constrained Problems
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization
• A new insight on augmented Lagrangian method with applications in machine learning