pith. sign in

arxiv: 1907.10171 · v1 · pith:GSQNAH4Rnew · submitted 2019-07-23 · 🧮 math.OC

Contraction Analysis on Primal-Dual Gradient Optimization

Yanxu Su , Yang Shi , Changyin Sun This is my paper

Pith reviewed 2026-05-24 16:54 UTC · model grok-4.3

classification 🧮 math.OC
keywords contraction analysisprimal-dual gradientRiemannian metricconvex optimizationdiscrete-time dynamicsequality constraintsinequality constraintsaugmented Lagrangian
0
0 comments X

The pith

A Riemannian metric can be constructed so that primal-dual gradient updates contract inside a region and converge at explicit rates when step sizes are chosen correctly.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper applies contraction theory on Riemannian manifolds to discrete-time primal-dual gradient algorithms for convex optimization. It builds a metric that defines a contraction region where nearby trajectories are pulled together. With step sizes tuned to that region, convergence and rates follow for equality-constrained problems and, separately, for inequality-constrained problems via an augmented Lagrangian that avoids projections. This supplies a geometric certificate of stability and speed.

Core claim

Under reasonable assumptions, a Riemannian metric can be constructed that characterizes a contraction region for the primal-dual updating dynamics. When the step-sizes are properly designed, the convergence rates for both equality and inequality cases follow from the contraction properties inside that region, with the augmented Lagrangian used to handle inequalities in a projection-free manner.

What carries the argument

The Riemannian metric constructed to make the discrete-time primal-dual vector field contracting inside a nonempty region.

If this is right

  • Convergence is guaranteed inside the contraction region for equality-constrained convex problems.
  • Inequality-constrained problems admit projection-free updates via the augmented Lagrangian while retaining the contraction property.
  • Explicit convergence rates are read off directly from the contraction metric once step sizes are fixed.
  • The same construction applies independently to the equality case and the inequality case.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The size of the contraction region may scale with problem conditioning, suggesting metric-based preconditioners.
  • Similar metric constructions could certify contraction for related first-order methods such as ADMM.
  • The metric might be used to derive adaptive step-size rules on the fly.
  • The approach could extend to distributed or stochastic variants if the contraction property survives added noise.

Load-bearing premise

The problem data allow existence of a Riemannian metric under which the discrete-time primal-dual vector field contracts inside some nonempty region.

What would settle it

A specific convex optimization instance satisfying the paper's assumptions in which the iterates diverge for every candidate step-size sequence that the metric would predict to work, or in which no such contracting metric exists.

Figures

Figures reproduced from arXiv: 1907.10171 by Changyin Sun, Yang Shi, Yanxu Su.

Figure 1
Figure 1. Figure 1: Riemannian distance between the actual and optimal s [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Riemannian distance between the actual and optimal s [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
read the original abstract

This paper analyzes the contraction of the primal-dual gradient optimization via contraction theory in the context of discrete-time updating dynamics. The contraction theory based on Riemannian manifolds is first established for convergence analysis of a convex optimization algorithm. The equality and inequality constrained optimization cases are studied, respectively. Under some reasonable assumptions, we construct the Riemannian metric to characterize a contraction region. It is shown that if the step-sizes of the updating dynamics are properly designed, the convergence rates for both cases can be obtained according to the contraction region in which the convergence can be guaranteed. Moreover, the augmented Lagrangian function which is projection free is adopted to tackle the inequality constraints. Some numerical experiments are simulated to demonstrate the effectiveness of the presented contraction analysis results on primal-dual gradient optimization algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper applies Riemannian contraction theory to analyze convergence of discrete-time primal-dual gradient dynamics for convex optimization. For equality-constrained problems and inequality-constrained problems (via augmented Lagrangian), it claims to construct a Riemannian metric under 'reasonable assumptions' that defines a contraction region; with suitably chosen step-sizes, explicit convergence rates are then obtained inside that region. Numerical experiments are included to illustrate the approach.

Significance. If the metric construction is valid and produces a nonempty forward-invariant contraction region for standard convex programs (without requiring strong monotonicity), the work would supply a new, geometrically grounded certificate for global convergence rates of primal-dual methods that applies uniformly to both equality and inequality cases.

major comments (3)
  1. [Abstract] Abstract: the central claim that a Riemannian metric is constructed 'to characterize a contraction region' under reasonable assumptions supplies neither the explicit metric nor a verification that the region is nonempty for any nontrivial convex program; all subsequent rate statements rest on this step.
  2. [Abstract] Abstract and the metric-construction section: when the primal-dual Jacobian is merely monotone (standard convexity) rather than strongly monotone, the paper does not show that the induced norm of the differential can be made strictly less than 1 inside a nonempty set; the existence claim therefore remains unverified.
  3. [Abstract] Abstract: the 'reasonable assumptions' invoked for both the equality and inequality cases are never stated explicitly, so it is impossible to check whether they are non-vacuous or weaker than the usual convexity hypotheses under which primal-dual methods are already known to converge.
minor comments (2)
  1. [Numerical experiments] The numerical experiments should report the observed contraction rates alongside the theoretically predicted rates and compare against standard step-size rules (e.g., diminishing or fixed step-sizes from the literature).
  2. [Theory sections] Notation for the Riemannian metric and the induced norm should be introduced with an explicit definition before being used in the rate derivations.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback. The comments correctly identify that the abstract and metric-construction sections require greater explicitness to support the central claims. We will revise the manuscript to address each point.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that a Riemannian metric is constructed 'to characterize a contraction region' under reasonable assumptions supplies neither the explicit metric nor a verification that the region is nonempty for any nontrivial convex program; all subsequent rate statements rest on this step.

    Authors: We agree the abstract is overly concise. The metric is constructed explicitly in Section 3 via a state-dependent Riemannian metric that renders the primal-dual Jacobian contractive inside a forward-invariant set. In revision we will expand the abstract to state the metric form and add a short verification (e.g., for a quadratic program) confirming the region is nonempty under the paper's assumptions. revision: yes

  2. Referee: [Abstract] Abstract and the metric-construction section: when the primal-dual Jacobian is merely monotone (standard convexity) rather than strongly monotone, the paper does not show that the induced norm of the differential can be made strictly less than 1 inside a nonempty set; the existence claim therefore remains unverified.

    Authors: This observation is accurate. While the construction assumes monotonicity and derives a metric under which the differential norm is bounded below 1 inside the claimed region, an explicit verification that such a nonempty set exists for merely monotone (not strongly monotone) Jacobians is not supplied. We will add a dedicated remark or short appendix providing this verification, either by direct computation on a canonical example or by showing the metric can be chosen so the bound holds on a ball around the equilibrium. revision: yes

  3. Referee: [Abstract] Abstract: the 'reasonable assumptions' invoked for both the equality and inequality cases are never stated explicitly, so it is impossible to check whether they are non-vacuous or weaker than the usual convexity hypotheses under which primal-dual methods are already known to converge.

    Authors: We concur that the assumptions must be stated explicitly. The paper relies on convexity of the objective and constraints together with positive step-size bounds that ensure the discrete map remains inside the contraction region; these are weaker than strong convexity but are not listed in the abstract. In revision we will enumerate them in the abstract and introduction and briefly compare them with standard convexity conditions. revision: yes

Circularity Check

0 steps flagged

No circularity; metric construction is the independent analytical step

full rationale

The paper states it constructs a Riemannian metric under reasonable assumptions to characterize a contraction region for discrete-time primal-dual dynamics, then derives convergence rates from the resulting region when step-sizes are chosen appropriately. No quoted text shows the metric or region being defined in terms of the target rates, no fitted parameters renamed as predictions, and no load-bearing self-citations or uniqueness theorems imported from the authors' prior work. The derivation follows the standard contraction-analysis workflow without reducing any claimed result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the existence of a Riemannian metric that renders the discrete dynamics contracting; this metric is asserted to exist under unspecified 'reasonable assumptions' whose content is not supplied in the abstract.

axioms (1)
  • domain assumption Some reasonable assumptions allow construction of a Riemannian metric characterizing a contraction region for the primal-dual dynamics.
    Invoked in the abstract for both equality and inequality cases.

pith-pipeline@v0.9.0 · 5651 in / 1198 out tokens · 26557 ms · 2026-05-24T16:54:35.615915+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 2 internal anchors

  1. [1]

    EXTRA: An exact first-or der algorithm for decentralized consensus optimization,

    W. Shi, Q. Ling, G. Wu, and W. Yin, “EXTRA: An exact first-or der algorithm for decentralized consensus optimization,” SIAM Journal on Optimization, vol. 25, no. 2, pp. 944–966, 2015

    work page 2015

  2. [2]

    DEXTRA: A fast algorithm for optimiz ation over directed graphs,

    C. Xi and U. A. Khan, “DEXTRA: A fast algorithm for optimiz ation over directed graphs,” IEEE Transactions on Automatic Control , vol. 62, no. 10, pp. 4980–4993, 2017

    work page 2017

  3. [3]

    Distributed gradient algorit hm for con- strained optimization with application to load sharing in p ower systems,

    P . Yi, Y . Hong, and F. Liu, “Distributed gradient algorit hm for con- strained optimization with application to load sharing in p ower systems,” Systems & Control Letters , vol. 83, pp. 45–52, 2015

    work page 2015

  4. [4]

    Connecting automatic genera tion control and economic dispatch from an optimization view,

    N. Li, C. Zhao, and L. Chen, “Connecting automatic genera tion control and economic dispatch from an optimization view,” IEEE Transactions on Control of Network Systems , vol. 3, no. 3, pp. 254–264, 2015

    work page 2015

  5. [5]

    Incremental majorization-minimization op timization with application to large-scale machine learning,

    J. Mairal, “Incremental majorization-minimization op timization with application to large-scale machine learning,” SIAM Journal on Opti- mization, vol. 25, no. 2, pp. 829–855, 2015

    work page 2015

  6. [6]

    Distributed convergenc e to Nash equi- libria in two-network zero-sum games,

    B. Gharesifard and J. Cort´ es, “Distributed convergenc e to Nash equi- libria in two-network zero-sum games,” Automatica, vol. 49, no. 6, pp. 1683–1692, 2013

    work page 2013

  7. [7]

    Distributed subgradient meth ods for multi- agent optimization,

    A. Nedic and A. Ozdaglar, “Distributed subgradient meth ods for multi- agent optimization,” IEEE Transactions on Automatic Control , vol. 54, no. 1, p. 48, 2009

    work page 2009

  8. [8]

    An accelerated dual gradie nt-projection algorithm for embedded linear model predictive control,

    P . Patrinos and A. Bemporad, “An accelerated dual gradie nt-projection algorithm for embedded linear model predictive control,” IEEE Trans- actions on Automatic Control , vol. 59, no. 1, pp. 18–33, 2013

    work page 2013

  9. [9]

    Fenchel dual gradient methods for distri buted convex optimization over time-varying networks,

    X. Wu and J. Lu, “Fenchel dual gradient methods for distri buted convex optimization over time-varying networks,” IEEE Transactions on Automatic Control , 2019

    work page 2019

  10. [10]

    On the linear convergence of the ADMM in decentralized consensus optimiz ation,

    W. Shi, Q. Ling, K. Y uan, G. Wu, and W. Yin, “On the linear convergence of the ADMM in decentralized consensus optimiz ation,” IEEE Transactions on Signal Processing , vol. 62, no. 7, pp. 1750–1761, 2014

    work page 2014

  11. [11]

    Analys is of distributed ADMM algorithm for consensus optimization in presence of no de error,

    L. Majzoobi, F. Lahouti, and V . Shah-Mansouri, “Analys is of distributed ADMM algorithm for consensus optimization in presence of no de error,” IEEE Transactions on Signal Processing , vol. 67, no. 7, pp. 1774–1784, 2019

    work page 2019

  12. [12]

    Asynchronous m ultiagent primal-dual optimization,

    M. T. Hale, A. Nedi´ c, and M. Egerstedt, “Asynchronous m ultiagent primal-dual optimization,” IEEE Transactions on Automatic Control , vol. 62, no. 9, pp. 4421–4435, 2017

    work page 2017

  13. [13]

    Online primal-dual methods with measurement feedback for time-varying convex optimiza- tion,

    A. Bernstein, E. Dall’Anese, and A. Simonetto, “Online primal-dual methods with measurement feedback for time-varying convex optimiza- tion,” IEEE Transactions on Signal Processing , 2019

    work page 2019

  14. [14]

    Asymptotic c onvergence of constrained primal–dual dynamics,

    A. Cherukuri, E. Mallada, and J. Cort´ es, “Asymptotic c onvergence of constrained primal–dual dynamics,” Systems & Control Letters , vol. 87, pp. 10–15, 2016

    work page 2016

  15. [15]

    Saddle-p oint dynamics: Conditions for asymptotic stability of saddle points,

    A. Cherukuri, B. Gharesifard, and J. Cortes, “Saddle-p oint dynamics: Conditions for asymptotic stability of saddle points,” SIAM Journal on Control and Optimization , vol. 55, no. 1, pp. 486–511, 2017

    work page 2017

  16. [16]

    Stability and robustness for saddle-point dynamics through monotone mappings,

    R. Goebel, “Stability and robustness for saddle-point dynamics through monotone mappings,” Systems & Control Letters , vol. 108, pp. 16–22, 2017

    work page 2017

  17. [17]

    C ontraction and robustness of continuous time primal-dual dynamics,

    H. D. Nguyen, T. L. Vu, K. Turitsyn, and J.-J. Slotine, “C ontraction and robustness of continuous time primal-dual dynamics,” IEEE Control Systems Letters , vol. 2, no. 4, pp. 755–760, 2018

    work page 2018

  18. [18]

    On the exponential stability of primal- dual gradient dynamics,

    G. Qu and N. Li, “On the exponential stability of primal- dual gradient dynamics,” IEEE Control Systems Letters, vol. 3, no. 1, pp. 43–48, 2018

    work page 2018

  19. [19]

    Exponential convergen ce of distributed primal–dual convex optimization algorithm wi thout strong convexity,

    S. Liang, L. Y . Wang, and G. Yin, “Exponential convergen ce of distributed primal–dual convex optimization algorithm wi thout strong convexity,” Automatica, vol. 105, pp. 298–306, 2019

    work page 2019

  20. [20]

    On contraction analy sis for non-linear systems,

    W. Lohmiller and J. J. E. Slotine, “On contraction analy sis for non-linear systems,” Automatica, vol. 34, no. 6, pp. 683–696, 1998

    work page 1998

  21. [21]

    Distribute d nonlinear model predictive control based on contraction theory,

    Y . Long, S. Liu, L. Xie, and K. H. Johansson, “Distribute d nonlinear model predictive control based on contraction theory,” International Journal of Robust and Nonlinear Control , vol. 28, no. 2, pp. 492–503, 2018

    work page 2018

  22. [22]

    A contractio n theory approach to stochastic incremental stability,

    Q. C. Pham, N. Tabareau, and J. J. Slotine, “A contractio n theory approach to stochastic incremental stability,” IEEE Transactions on Automatic Control, vol. 54, no. 4, pp. 816–820, 2009

    work page 2009

  23. [23]

    A differential Lyapunov fra mework for contraction analysis

    F. Forni and R. Sepulchre, “A differential Lyapunov fra mework for contraction analysis.” IEEE Transactions on Automatic Control , vol. 59, no. 3, pp. 614–628, 2014

    work page 2014

  24. [24]

    Control Contraction Metrics on Finsler Manifolds

    T. L. Chaffey and I. R. Manchester, “Control contractio n metrics on Finsler manifolds,” arXiv preprint arXiv:1803.01034 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  25. [25]

    Distributed coord ination for non- smooth convex optimization via saddle-point dynamics,

    J. Cort´ es and S. K. Niederl¨ ander, “Distributed coord ination for non- smooth convex optimization via saddle-point dynamics,” Journal of Nonlinear Science , pp. 1–26, 2018

    work page 2018

  26. [26]

    Robust distribu ted model pre- dictive control of constrained dynamically decoupled nonl inear systems: A contraction theory perspective,

    X. Liu, Y . Shi, and D. Constantinescu, “Robust distribu ted model pre- dictive control of constrained dynamically decoupled nonl inear systems: A contraction theory perspective,” Systems & Control Letters , vol. 105, pp. 84–91, 2017

    work page 2017

  27. [27]

    The prox imal augmented Lagrangian method for nonsmooth composite optim ization,

    N. K. Dhingra, S. Z. Khong, and M. R. Jovanovic, “The prox imal augmented Lagrangian method for nonsmooth composite optim ization,” IEEE Transactions on Automatic Control , 2018

    work page 2018

  28. [28]

    Projected primal–dua l gradient flow of augmented Lagrangian with application to distributed ma ximization of the algebraic connectivity of a network,

    H. Zhang, J. Wei, P . Yi, and X. Hu, “Projected primal–dua l gradient flow of augmented Lagrangian with application to distributed ma ximization of the algebraic connectivity of a network,” Automatica, vol. 98, pp. 34–41, 2018

    work page 2018

  29. [29]

    First-order methods for constrained convex programming based on linearized augmented Lagrangian function

    Y . Xu, “First-order methods for constrained convex pro gramming based on linearized augmented Lagrangian function,” arXiv preprint arXiv:1711.08020, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  30. [30]

    Stability of primal–dual gr adient dynamics and applications to network optimization,

    D. Feijer and F. Paganini, “Stability of primal–dual gr adient dynamics and applications to network optimization,” Automatica, vol. 46, no. 12, pp. 1974–1981, 2010

    work page 1974