PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Exponential Stability of Primal-Dual Gradient Dynamics

Guannan Qu, Na Li

arXiv:1803.01825v3math.OC

TL;DR

The paper addresses the limited study of global exponential stability for primal-dual gradient dynamics in constrained optimization. It analyzes strongly convex and smooth objectives with affine equality or inequality constraints, proves global exponential stability, and provides decaying-rate bounds, while identifying scope for tighter bounds and weaker assumptions.

  • Problem

    The paper asks whether constrained primal-dual gradient dynamics can be globally exponentially stable, beyond the better-studied global asymptotic stability setting.

  • Method

    The paper studies PDGD for strongly convex and smooth objectives with affine equality or inequality constraints, using separate analyses for the two constraint types.

  • Results

    The paper proves global exponential stability for the considered PDGD and gives explicit bounds on the decaying rates.

  • Takeaways & Limitations

    The results provide stability guarantees and decay-rate bounds for continuous-time primal-dual dynamics in the stated constrained optimization setting.

  • Takeaways & Limitations

    Future work includes tighter decaying-rate bounds, especially for inequality constraints, and relaxing Assumption 2 in the inequality-constrained case.

Abstract

from arXiv · show

Continuous time primal-dual gradient dynamics that find a saddle point of a Lagrangian of an optimization problem have been widely used in systems and control. While the global asymptotic stability of such dynamics has been well-studied, it is less studied whether they are globally exponentially stable. In this paper, we study the primal-dual gradient dynamics for convex optimization with strongly-convex and smooth objectives and affine equality or inequality constraints, and prove global exponential stability for such dynamics. Bounds on decaying rates are provided.

I. INTRODUCTION

The paper asks whether primal-dual gradient dynamics can achieve global exponential stability for constrained optimization, extending beyond the predominantly asymptotic stability literature. It proves this property under regularity conditions and introduces a projection-free treatment for affine inequality constraints.

  • PDGD has been widely used in engineering, control, power grids, wireless communication, distributed optimization, and game theory.
  • Prior studies have mostly focused on asymptotic stability, leaving global exponential stability in the constrained case as an open question.
  • Global exponential stability is desirable for strong guarantees in critical infrastructure and geometric convergence after sufficiently small-step explicit Euler discretization.
  • The paper proves global exponential stability of PDGD under regularity conditions and provides bounds on the decaying rates.
  • The proof uses a quadratic Lyapunov function with non-zero off-diagonal terms rather than the commonly used block-diagonal form.
  • For inequality constraints, the proposed augmented-Lagrangian PDGD is projection-free, preserves nonnegative multipliers, and avoids projection-induced discontinuities.

II. ALGORITHMS AND MAIN RESULTS

The paper analyzes equality- and inequality-constrained primal-dual dynamics for strongly convex, smooth objectives, combining separate cases to establish global exponential stability. Its main results characterize stability and decaying-rate bounds under stated assumptions.

  • Assumptions: The analysis assumes that f is twice differentiable, µ-strongly convex, and ℓ-smooth.
  • Main results: The paper treats equality- and inequality-constrained cases separately and integrates them to obtain global exponential stability for the full problem.
  • Equality Constrained Case: For equality constraints, A is assumed full row rank with κ1I ⪯ AAT ⪯ κ2I, ensuring a unique saddle point under the stated assumptions.
  • Equality Constrained Case: Theorem 1 establishes global exponential stability of the equality-constrained PDGD and defines a decaying-rate bound τeq.
  • Equality Constrained Case: The equality-constrained result is related to prior exponential-stability work but uses a different Lagrangian setting and serves as a complementary result.

B. Inequality Constrained Case

For affine inequality constraints, the paper uses a projection-free Augmented Lagrangian PDGD, avoiding discontinuities associated with projected dynamics and proving global exponential stability under stated assumptions.

  • Augmented Lagrangian PDGD: The inequality-constrained dynamics use an Augmented Lagrangian rather than the standard Lagrangian used in prior projected formulations.The augmented Lagrangian is built with a penalty function Hρ for constraint violations, with ρ > 0.
  • Augmented Lagrangian PDGD: The resulting Aug-PDGD is projection free, avoiding discontinuity issues caused by the projection step.The paper motivates this choice by reported theoretical and numerical difficulties with discontinuous projection-based PDGD.
  • Augmented Lagrangian PDGD: Nonnegative initial multipliers remain nonnegative along the dynamics without using projection.This invariance follows from the multiplier dynamics in (9b).
  • Equilibrium and stability: Under Assumptions 1 and 2, Aug-PDGD has a unique equilibrium point satisfying the KKT conditions of the inequality-constrained problem.The saddle point of the augmented Lagrangian coincides with that of the standard Lagrangian.

III. STABILITY ANALYSIS

The stability analysis proves exponential convergence by constructing a quadratic Lyapunov function for stacked primal-dual states and establishing a decay inequality under strong convexity and smoothness.

  • Rate bound: Global exponential stability also ensures geometric convergence for the explicit Euler discretization.This links the continuous-time stability result to a discrete-time numerical implementation.
  • Lyapunov analysis: The analysis stacks the primal and dual variables into z = [x^T, λ^T]^T and compares them with the equilibrium z*.This converts the coupled primal-dual dynamics into a single state-space representation.
  • Lyapunov analysis: A quadratic Lyapunov function V(z) = (z − z*)^T P(z − z*) is used, with P ≻ 0 chosen to support exponential decay.The proof differentiates V along trajectories and reduces stability to an auxiliary lemma.
  • Rate bound: The decay rate is bounded using a parameter choice summarized by τ = ηκ1c, with c selected from bounds involving η, κ1, κ2, µ, and ℓ.The proof concludes after combining the auxiliary lemma with the derivative estimate.
  • Lyapunov analysis: Strong convexity and smoothness yield a symmetric matrix B(x) satisfying µI ⪯ B(x) ⪯ ℓI and ∇f(x) − ∇f(x*) = B(x)(x − x*).This mean-value-theorem representation supplies the bounds used in the Lyapunov argument.

B. The Inequality Constrained Case, Proof of Theorem 2

The inequality-constrained proof rewrites Aug-PDGD using state-dependent matrices and establishes exponential stability through a quadratic Lyapunov function. The analysis also transfers continuous-time stability to geometric convergence of Euler discretizations for sufficiently small steps.

  • Lyapunov construction: The proof stacks primal and dual variables into z and uses a positive-definite quadratic Lyapunov function V(z)=(z−z*)^T P(z−z*).The matrix P is selected so that the Lyapunov function captures the coupled primal-dual dynamics.
  • Stability inequality: The derivative of V is bounded by a negative quadratic form after proving the required matrix inequality, completing the exponential-stability argument.The proof establishes the inequality through auxiliary lemmas and Schur-complement bounds.
  • Discretization: The discrete-time bound includes a factor involving e^−τδ and the condition number κP of the Lyapunov matrix.The resulting constant also depends on the vector field, decay rate, Lyapunov matrix, and initial distance from equilibrium.
  • Discretization: Euler discretizations of both PDGD and Aug-PDGD converge geometrically fast when the discretization step size δ is sufficiently small.The continuous-time Lyapunov decay condition supplies the basis for the discrete-time convergence result.

IV. ILLUSTRATIVE EXAMPLES

The illustrative examples numerically examine decay rates for equality- and inequality-constrained dynamics. In both cases, increasing η beyond a sufficiently large value does not increase the observed decay rate.

  • Equality constrained case: For equality constraints, quadratic costs turn PDGD into an LTI system whose decay rate is estimated from its eigenvalues.The experiment uses n=5 and m=2 with randomly generated problem data.
  • Equality constrained case: The equality-constrained simulation plots decay rate versus η and distance to equilibrium versus time.The upper plot varies η, while the lower plot shows trajectories for selected η values.
  • Equality constrained case: Beyond a certain threshold, increasing η does not produce a faster PDGD decay rate.The same behavior appears in both the decay-rate plot and the distance-to-equilibrium simulations.
  • Inequality constrained case: For affine inequality constraints, Aug-PDGD is tested on synthetic logistic-regression data with n=50, m=40, and ρ=1.The entries of A and b are independently sampled from a standard normal distribution, while η is varied.
  • Inequality constrained case: For inequality constraints, sufficiently large η likewise does not increase the observed decay rate.The results are shown in the Aug-PDGD simulations under different η values.
  • Conclusions: The paper studies strongly convex and smooth objectives with affine equality or inequality constraints and proves global exponential stability with explicit decay-rate bounds.The stated future work includes tightening the bounds and relaxing an assumption for the inequality-constrained case.

APPENDIX

The appendix verifies the matrix inequalities underlying the stability proof. It handles state-dependent matrices by bounding their blocks and reducing diagonal interpolation cases to finitely many endpoint matrices.

  • Equality constrained case: The proof treats G(z) and B(x) through uniform bounds µI⪯B⪯ℓI and establishes a Lyapunov matrix inequality for every admissible symmetric B.The argument uses bounds involving A^TA and AA^T before applying a Schur complement.
  • Equality constrained case: The resulting matrix bound is Q−τP⪰0, which is equivalent to the required negative Lyapunov derivative inequality.The proof concludes the corresponding inequality after summing componentwise bounds.
  • Inequality constrained case: For inequality constraints, G(z) depends on B(x) and a diagonal Γ(z) whose entries lie in [0,1].The proof seeks Q⪰τP under these uniform admissibility conditions.
  • Inequality constrained case: The Schur-complement proof lower-bounds Q2 and controls Q3Q2^-1Q3^T before combining the bounds for Q1.This decomposition reduces the target positive-semidefiniteness condition to blockwise inequalities.
  • Inequality constrained case: The matrix M(γ1,…,γm) is a convex combination of 2^m endpoint matrices, so bounding every endpoint suffices.The endpoint matrices are indexed by binary choices for the diagonal entries of Γ.
  • Inequality constrained case: The endpoint analysis writes AAT in block form and verifies the required inequality across k=0,…,m active entries.The proof covers the all-zero, all-one, and intermediate block cases.

D. Proof of Lemma 1

The appendix connects the dynamics' equilibria to KKT conditions and derives exponential decay using Lipschitz continuity and Lyapunov estimates. It also extends the formulation to two-sided inequality constraints.

  • Lyapunov estimates: Strong convexity and smoothness imply that the mean Hessian matrix B(x) satisfies µI⪯B(x)⪯ℓI.This bound supports the state-dependent linearization used in the stability proof.
  • Fixed points and KKT conditions: The fixed-point equations of Aug-PDGD coincide with the KKT conditions of the inequality-constrained problem.The dual stationarity equation is rewritten componentwise to obtain the complementarity relations.
  • Two-sided constraints: For two-sided constraints, Aug-PDGD-TS has a unique fixed point, and its fixed points correspond one-to-one with the KKT solutions.The correspondence uses the mapping from an unrestricted multiplier to its positive and negative parts.
  • Two-sided constraints: Under Assumptions 1 and 2, Aug-PDGD-TS is exponentially stable for any η>0 and ρ>0.The theorem states exponential stability for the two-sided augmented dynamics within the specified assumptions.

there exists constant

The proof rewrites the augmented primal-dual dynamics in a state-dependent linear form and establishes exponential decay using a quadratic Lyapunov function. A matrix inequality valid for all states yields the decay bound.

  • there exists constant: The resulting state error obeys ∥z − z∗∥ = O(e^−τt).The theorem also provides constants and an explicit decay-rate expression for the inequality-constrained dynamics.
  • there exists constant: The dynamics are written as d/dt z = G(z)(z − z∗), with state dependence captured through Γ(z).Γ(z) is diagonal, with entries in [0, 1].
  • there exists constant: The proof uses V(z) = (z − z∗)^T P(z − z∗) as a quadratic Lyapunov function.The matrix P is chosen as in the corresponding one-sided-constraint case.
  • there exists constant: Lemma 8 establishes −G(z)^T P − PG(z) ⪰ τP for every state z, with τ = ηκ1.The result remains valid because the proof only requires Γ(z) to be diagonal with entries in [0, 1].
  • there exists constant: The Lyapunov derivative satisfies dV(z)/dt ≤ −τV(z), proving exponential decay of the Lyapunov function.This differential inequality completes the proof of Theorem 4.

I. Relaxing the Rank Constraint

The paper relaxes the rank constraint for affine inequality-constrained optimization by introducing an augmented Lagrangian and proving exponential stability under strong convexity, smoothness, and constraint qualification assumptions. The proof uses state-dependent linearization and a Lyapunov argument.

  • I. Relaxing the Rank Constraint: The relaxed setting considers a twice-differentiable, µ-strongly convex, and ℓ-smooth objective with a unique minimizer.The optimization problem also satisfies a linear independent constraint qualification.
  • I. Relaxing the Rank Constraint: The constraints are partitioned into active constraints at x∗ and inactive constraints with strict slack.The first m1 constraints are active, while the remaining m2 = m − m1 constraints are inactive.
  • I. Relaxing the Rank Constraint: An augmented Lagrangian with penalty parameter ρ is used to define the primal-dual gradient dynamics.The penalty function Hρ acts on constraint violation, and the resulting dynamics are given in (43).
  • I. Relaxing the Rank Constraint: Under Assumptions 3 and 4, dynamics (43) are exponentially stable.The proof defines z = [x^T, λ^T]^T, constructs a positive-definite matrix P, and uses V(z) as a Lyapunov function.
  • I. Relaxing the Rank Constraint: The proof obtains V(z) ≤ e^−τtV(z(0)), completing the exponential-stability result.The decay rate uses τ = ηκ1, with the theorem's constant c chosen to make P positive definite and satisfy the required matrix bounds.

J. Proof of Lemma 10

The proof of Lemma 10 reduces the stability condition to matrix inequalities involving the Hessian surrogate B and the constraint matrix Γ. Bounds on inactive constraints and a sufficiently large penalty constant establish the required positive semidefiniteness.

  • J. Proof of Lemma 10: For inactive constraints, γj(z) ≤ γ̄ < 1, where γ̄ depends on the initial state and penalty parameters.This bound follows from strict inactivity at x∗ and is used to lower-bound I − Γ2.
  • J. Proof of Lemma 10: The proof allows B to satisfy µI ⪯ B ⪯ ℓI and Γ to be diagonal with entries in [0, 1].For inactive constraints, the additional bound γj ≤ γ̄ is imposed.
  • J. Proof of Lemma 10: A sufficiently large c makes Q2 positive semidefinite under the stated matrix inequality conditions.Lemma 12 provides conditions involving η, κ1, κ2, ρ, and γ̄.
  • J. Proof of Lemma 10: The active-constraint bound is established by exploiting convexity over the diagonal entries of Γ1 and checking the relevant endpoint cases.This yields the lower bound used for Q2.
  • J. Proof of Lemma 10: Combining the lower bounds with a Schur-complement argument proves the remaining matrix inequality and hence −G(z)^T P − PG(z) ⪰ τP.The saddle-point property supplies one of the inequalities needed to show the final matrix is positive semidefinite.
Loading 1803.01825v3…