Finite-Time Convergent Primal-Dual Gradient Dynamics With Applications to Distributed Optimization.

Area of Science:

• Optimization Theory
• Nonsmooth Analysis
• Control Theory

Background:

• Constrained optimization problems are prevalent in various scientific and engineering fields.
• Existing methods often lack finite-time convergence guarantees or require strict convexity.
• Fast primal-dual gradient dynamics (PDGD) offer a promising approach but require further theoretical development for finite-time analysis.

Purpose of the Study:

• To develop and analyze a novel fast primal-dual gradient dynamics (FT-PDGD) algorithm for solving constrained optimization problems in finite time.
• To establish sufficient conditions for finite-time convergence of the proposed FT-PDGD.
• To extend the applicability to general constraints and cost functions, including non-strictly convex cases.

Main Methods:

• Utilizing nonsmooth analysis and augmented Lagrangian functions to derive convergence conditions.
• Defining and analyzing a specific class of nonsmooth sign-preserving functions for stability.
• Employing auxiliary variables to handle general linear inequality constraints and derive reduced conditions.
• Investigating the switching dynamics of primal and dual variables for explicit convergence time bounds.

Main Results:

• Sufficient conditions for finite-time convergence of FT-PDGD are established.
• The method does not require the matrix of linear equations to have full-row rank or the cost function to be strictly convex.
• An explicit upper bound on the convergence time is provided.
• Novel finite-time convergent distributed algorithms are designed as applications.

Conclusions:

• The proposed FT-PDGD effectively achieves finite-time convergence for constrained optimization problems.
• The developed framework offers enhanced stability and broader applicability compared to existing methods.
• The derived distributed algorithms demonstrate the practical utility of FT-PDGD in solving complex optimization tasks.