PaperlayerView exact revision on arXiv

Source-linked AI summary

SPPID: Saddle-Point PID for Constrained Optimization

Veronica Centorrino, Rawan Hoteit, Efe C. Balta, John Lygeros

arXiv:2609.31086v1math.OCcs.SYeess.SY

TL;DR

Constrained optimization raises the question of how feedback policies on dual variables shape optimization dynamics, and existing work has not established a systematic approach that jointly handles equality and inequality constraints. The paper develops SPPID, a unified PID-based framework for saddle-point flows, and establishes convergence results for convex problems. It also identifies derivative action for inequality constraints as an unresolved design challenge.

  • Problem

    A systematic design for jointly handling equality and inequality constraints, and convergence-guaranteed derivative action in multiplier dynamics, remain lacking or unclear.

    Source: Literature review · p. 2

  • Method

    SPPID uses PID control of dual variables to generate saddle-point dynamics associated with the augmented Lagrangian, with anti-windup PI control for inequality constraints.

    Source: §1 · p. 2, Controller for Inequality Constraints · p. 6

  • Results

    For convex problems, SPPID converges to the KKT set, with conditions for global asymptotic stability.

    Source: §7 · p. 27

  • Takeaways & Limitations

    The framework makes the roles of feedback components explicit and provides a pathway for recovering known algorithms and designing new ones.

    Source: §1 · p. 2

    For inequality constraints, derivative action creates a non-smooth implicit algebraic loop; resolving it and designing a PID scheme remain open problems.

    Source: SPPID Dynamics · p. 7

Abstract

from arXiv · show

This paper studies constrained optimization problems through the lens of feedback control. Building on the interpretation of Lagrange multipliers as feedback controllers, we propose the \emph{saddle-point PID (SPPID) dynamics}: a unified proportional--integral--derivative (PID) framework for continuous-time saddle-point dynamics. The proposed dynamics employ PID control for equality constraints and anti-windup PI control for inequality constraints. We show that SPPID is equivalent to a preconditioned primal--dual gradient flow of the augmented Lagrangian. This equivalence reveals the distinct role of each feedback component: integral action enforces constraint satisfaction, proportional action induces the augmented Lagrangian structure, and derivative action modifies the geometry of the primal dynamics via a state-dependent Riemannian metric. For convex problems, we establish convergence to the KKT set together with conditions for global asymptotic stability. For equality-constrained problems, we establish local exponential convergence for nonlinear equality constraints under standard assumptions, and show that projected gradient flow emerges as the infinite derivative-gain limit. For strongly convex problems with affine equality or inequality constraints, we establish global exponential convergence by leveraging contraction theory. Finally, we provide various numerical examples to illustrate the utility of SPPID.

1 Introduction

The introduction frames constrained optimization as a feedback-design problem and presents SPPID as a unified PID framework for shaping saddle-point dynamics. It previews the framework’s convergence results and its specializations to equality- and inequality-constrained problems.

Literature review

  • The paper identifies an open gap: systematic feedback design for equality and inequality constraints together, and convergence-guaranteed use of derivative action, remain unclear.The introduction situates this gap amid prior work on primal–dual, augmented-penalty, and projected-dynamics approaches.Source: §1 · p. 1, Literature review · p. 2

Contributions

  • SPPID applies PID control to Lagrange multipliers, treating equality and inequality constraints as separate input–output channels in the primal gradient-flow system.The paper proposes anti-windup PI control for inequality constraints and establishes forward invariance of the nonnegative orthant, preserving dual feasibility.Source: Contributions · p. 2
  • SPPID is a preconditioned primal–dual flow of the augmented Lagrangian, with Riemannian primal descent and scaled Euclidean dual ascent.The paper attributes the state-dependent Riemannian metric to derivative feedback arising from the equality controller.Source: Contributions · p. 2
  • For convex problems, the framework establishes convergence to the KKT set, with global asymptotic stability under strict convexity and LICQ and exponential convergence under additional regularity.The paper also states that SPPID equilibria coincide with the original problem’s KKT points.Source: Contributions · pp. 2–3
  • For equality constraints, projected gradient flow arises as the infinite-derivative-gain limit; for affine inequality constraints, SPPID recovers known flows and provides an explicit contraction metric and rate.The paper reports global exponential convergence for affine equality constraints and local exponential stability for non-affine constraints under standard regularity assumptions.Source: Contributions · p. 3
  • Three numerical examples validate the framework: non-convex sequential quadratic programming, multi-period Stackelberg games, and suboptimal nonlinear model predictive control.Source: Contributions · p. 3

2 Mathematical Preliminaries

The preliminaries establish notation and mathematical conditions used to state optimality and convergence results. They define contraction in terms of a log-norm and connect strong contraction to exponential convergence between trajectories.

2 Mathematical Preliminaries

  • The preliminaries fix notation for Euclidean spaces, vector inequalities, ReLU, diagonal matrices, and positive-semidefinite matrix ordering.Source: §2 · p. 3

Norms and Logarithmic Norms

  • The induced log-norm is defined through the small-step growth of a matrix norm, with a corresponding expression for norms weighted by P.The weighted expression uses the symmetric matrix inequality PA + A^⊤P ⪯ 2bP.Source: Norms and Logarithmic Norms · p. 3

Calculus and Function Classes

Optimality Conditions

  • LICQ requires active inequality and equality constraint gradients to be linearly independent; under convexity and the stated conditions, KKT points characterize global optima.When LICQ holds, the Lagrange multipliers are unique; SOSC at a KKT point implies a strict local minimizer.Source: Optimality Conditions · p. 4

Contraction Theory

  • Strong infinitesimal contraction on an open, convex, forward-invariant set implies exponential convergence between any two trajectories in that set.The distance between trajectories converges exponentially at the contraction rate.Source: Contraction Theory · p. 4

3 Unified Framework for Nonlinear Programs

Section 3 develops SPPID as a feedback-control framework for nonlinear constrained optimization, applying PID control to equality constraints and anti-windup PI control to inequality constraints. It also describes convergence rates in convex settings and local stability behavior in nonconvex problems, including the role of proportional feedback in the equality channel.

3.1 PID Control of Nonlinear Optimization Problems

Controller for Equality Constraints

  • For equality constraints, integral action enforces satisfaction, proportional action adds an augmented-Lagrangian term, and derivative action induces a state-dependent metric.The integral gain must be strictly positive to drive accumulated constraint violations to zero.Source: Controller for Equality Constraints · p. 6

Controller for Inequality Constraints

  • For inequality constraints, anti-windup PI control treats dual nonnegativity as saturation, prevents integrator windup, and preserves the nonnegative orthant.When saturated, the output is zero and feedback drives the integrator state back toward zero.Source: Controller for Inequality Constraints · p. 6

SPPID Dynamics

  • SPPID equilibria coincide with KKT points, and its dynamics are a preconditioned primal–dual gradient flow of the augmented Lagrangian.Derivative action in the equality controller induces the primal state-dependent Riemannian metric; designing PID for inequality constraints remains open because derivative action creates a nonsmooth algebraic loop.Source: SPPID Dynamics · p. 7

3.2 Convergence Analysis of SPPID in Convex Settings

  • Under convexity, affine equality constraints, Slater’s condition, and positive integral gain, every SPPID trajectory converges to the KKT set.If the objective is strictly convex and LICQ holds, the KKT point is unique and globally asymptotically stable.Source: §3.2 · p. 8
  • With strict complementarity, LICQ, and SOSC at a KKT point, every trajectory linearly-exponentially converges to that unique point for positive integral gain.This result assumes the convex-setting conditions of Assumption 3.2.Source: §3.2 · p. 10
  • For convex settings, the local exponential convergence rate is cloc = min(cI, cA), combining the inactive-constraint and active-subsystem rates.The inactive multiplier dynamics converge exponentially, while the active subsystem has local rate cA.Source: §3.2 · p. 11

3.3 Relation to Primal–Dual Gradient Dynamics

  • Aug-PDGD coincides with SPPID under specified gain and penalty settings, but its equality channel uses only integral control, which can preclude local stability in nonconvex problems.The stated equivalence uses keq_i = 1 and penalty parameter ρ equal to kin_p.Source: §3.3 · p. 11
  • There are nonconvex programs where Aug-PDGD diverges for every parameter choice, while SPPID is locally asymptotically stable for suitable gain selections.The example's linearized dynamics show instability under Aug-PDGD and stability under SPPID.Source: §3.3 · pp. 11–12
  • Figure 2 illustrates the contrast with exponential divergence under Aug-PDGD and asymptotic stabilization under SPPID in the nonconvex quadratic example.The figure also shows the equality-state and multiplier trajectories, a phase portrait, and primal-norm evolution relative to exponential bounds.Source: Figure 2 · p. 12, §3.3 · p. 12

4 Equality-Constrained Optimization Problems

This section studies SPPID for equality-constrained problems, relating its KKT equilibria to an augmented-Lagrangian saddle flow and examining how derivative feedback affects primal geometry and convergence. It establishes exponential stability results for affine and non-affine constraints and includes a fixed-step Euler experiment on the effect of derivative gain and step size.

4 Equality-Constrained Optimization Problems

  • Equality-constrained SPPID equilibria correspond exactly to KKT points, and its flow is augmented-Lagrangian primal–dual descent/ascent with derivative action inducing a state-dependent Riemannian metric.The primal dynamics descend using the metric induced by M(x), while the dual dynamics ascend in the Euclidean metric.Source: §4 · p. 13
  • A smooth global diffeomorphism relates equality-constrained SPPI to PI-CMO, preserving primal trajectories while smoothly reparameterizing the dual variables.The transformation establishes equivalence between the two dynamics.Source: §4 · p. 13
  • As the derivative gain tends to infinity, the primal dynamics approach projected gradient flow; under LICQ, the constraint manifold is invariant and its equilibria satisfy KKT conditions.On the manifold, primal and dual dynamics decouple and the equilibrium integral state may be arbitrary.Source: §4 · p. 14

4.1 Convergence Analysis for Affine Equality Constraints

  • Under strong convexity, smoothness, and full-row-rank affine constraints, SPPID is globally contracting for any positive integral gain and nonnegative derivative gain, ensuring exponential convergence without extra tuning.The derivative gain affects the certified contraction rate, which decreases monotonically as that gain grows.Source: §4.1 · pp. 15–16

4.2 Convergence Analysis for Non-Affine Constraints

  • For non-affine constraints, SPPID achieves local exponential stability around a KKT point under LICQ and SOSC when the proportional gain is sufficiently large.The theorem considers twice continuously differentiable objective and constraint functions.Source: §4.2 · pp. 16–17

4.1 Convergence Analysis for Affine Equality Constraints

  • In dense coupled quadratic tests, increasing derivative gain compresses frequency spread and raises explicit-Euler stability limits by several orders, enabling convergence where ill-conditioned cases otherwise diverge.The reported effect extends the stiffness-reduction behavior beyond the diagonal example.Source: §4.1 · p. 16, Figure 3 · p. 17, §4.2 · p. 17

4.2 Convergence Analysis for Non-Affine Constraints

  • For p > k̄, the equilibrium z⋆ is locally exponentially stable under SPPID (20).The result applies to non-affine equality constraints.Source: §4.2 · p. 17
  • Larger k_eq^d keeps the fixed-step Euler iteration stable and convergent, while smaller gains diverge when the step exceeds the fastest mode’s stability limit.Figure 4 tests k_eq^d ∈ {0, 10^-1, 1, 10, 10^2} over 5,000 steps with h = 0.02 across condition numbers κ(A) ∈ {1, 10, 100, 1000}.Source: §4.2 · p. 18, Figure 4 · p. 18

5 Inequality-Constrained Problems

For inequality constraints, SPPI uses anti-windup PI feedback to form saddle-point dynamics associated with an augmented Lagrangian. Under convexity assumptions it converges to the KKT set, with stronger stability and contraction guarantees under additional conditions.

5 Inequality-Constrained Problems

  • The SPPI primal dynamics add a constraint-weighted penalty that vanishes for strictly inactive constraints and restores against active or violated constraints, while its integral state drives the projected multiplier toward feasibility.The proportional gain shapes the augmented Lagrangian and penalty strength; the integral gain sets the dual dynamics’ timescale.Source: §5 · p. 19
  • SPPI equilibria correspond exactly to KKT points, and the dynamics coincide with a primal–dual gradient flow of the inequality-constrained augmented Lagrangian.The result applies to continuously differentiable objective and constraint functions with positive proportional and integral gains.Source: §5 · p. 19

5.1 Convergence Analysis of SPPI in Convex Settings

  • Under Assumption 3.2, every SPPI trajectory converges to the KKT set for convex inequality-constrained problems.If the objective is also strictly convex and LICQ holds, the unique KKT point is globally asymptotically stable.Source: §5.1 · p. 20
  • With strict complementarity, LICQ, and SOSC at a KKT point, every trajectory linearly-exponentially converges to that unique point.The convergence claim is for every positive integral gain.Source: §5.1 · p. 21

5.2 Convergence Analysis for Affine Constraints

  • For affine constraints and strongly convex, L-smooth costs, SPPI is strongly infinitesimally contracting with an explicit rate bound under the stated assumptions.The proportional gain affects the rate; excessive proportional gain can saturate the anti-windup mechanism and degrade practical convergence.Source: §5.2 · pp. 22–23

6 Numerical Examples

The examples apply SPPID to SQP, Stackelberg games, and nonlinear MPC, illustrating how controller gains affect convergence. In the SQP test, the SPPID formulation outperforms FL-M across tested proportional gains; the other examples show both benefits and limits of derivative and proportional gains.

6 Numerical Examples

  • Across the examples, larger proportional gains generally speed SPPID, but excessive gain can saturate the anti-windup integrator and degrade convergence.The integral gain sets primal–dual timescale separation, while a nonzero equality derivative gain reduces stiffness and can allow larger integration steps.Source: §6 · p. 23

6.1 Sequential Quadratic Programming

  • The SQP formulation with SPPID outperforms feedback linearization with momentum (FL-M) by several orders of magnitude across the tested proportional gains.Figure 6 reports mean convergence profiles and min–max bounds across initial conditions.Source: §6.1 · p. 24, Figure 6 · p. 24

6.2 Bilevel Optimization of Stackelberg Games

  • In the single-period Stackelberg game, PDGD fails to converge, while higher derivative gain yields faster convergence from feasible starts and oscillatory, constraint-tangential trajectories from infeasible starts.The derivative-gain effects differ by whether the initial point is feasible.Source: §6.2 · p. 25
  • With other gains fixed, increasing proportional gain leads SPPID to converge faster toward the optimum, but increasing it too much saturates the anti-windup PI controller and inhibits convergence.This saturation is reported as proportional gain increases from 45 to 60.Source: §6.2 · p. 25

6.3 Closed-Loop Nonlinear Suboptimal MPC

  • For nonlinear MPC, nonzero equality derivative gain reduces the iterations needed and numerical stiffness, permitting larger integration steps; with zero gain, a 0.0001 step fails to converge within 500 iterations.In the nonconvex problem, more iterations at constant step size do not guarantee convergence; a varying step size is required.Source: §6.3 · p. 27

7 Discussion and Conclusion

The paper presents SPPID as a unified control-theoretic framework for nonlinear constrained optimization, with convergence guarantees and demonstrations in three applications. Its stated future directions include discrete-time analysis, nonconvex convergence analysis, and resolving the loop that currently precludes derivative feedback for inequality constraints.

7 Discussion and Conclusion

  • SPPID generates continuous-time saddle-point flows associated with the augmented Lagrangian, whose equilibria coincide with the original problem’s KKT points.The paper establishes convex-problem convergence and stability results, equality-constrained convergence results, and contractivity for affine constraints with strongly convex, L-smooth costs.Source: §7 · p. 27
  • The applications demonstrate SPPID in nonconvex SQP, a multi-period Stackelberg game, and closed-loop NMPC.The paper identifies discrete-time counterparts and nonconvex convergence analysis as future directions; an unresolved nonsmooth algebraic loop currently precludes derivative feedback for inequality constraints.Source: §7 · p. 27

A Logarithmic Norm of Saddle Matrices

The appendix derives explicit logarithmic-norm bounds for saddle matrices used in the Jacobian analyses of equality- and inequality-constrained SPPID. It states matrix conditions under which the corresponding LMIs hold.

A Logarithmic Norm of Saddle Matrices

  • The equality-constraint analysis bounds the log-norm of scaled saddle matrices under positive-definiteness and spectral bounds on the matrices defining the system.The appendix describes these bounds as extending prior analysis and recovering a prior result for a special scalar metric.Source: A Logarithmic Norm of Saddle Matrices · p. 30
  • For the generalized saddle matrices used in inequality-constraint analysis, the appendix gives an LMI under bounds on B and CC⊤ and 0 ⪯ G ⪯ I.The stated result assumes positive α and β and m ≤ n.Source: A Logarithmic Norm of Saddle Matrices · p. 32

B Review of Dynamics Solving the Affine Inequality-Constrained Problem

This section reviews two primal–dual dynamical systems for affine inequality-constrained optimization and recalls their convergence results.

B Review of Dynamics Solving the Affine Inequality-Constrained Problem

Augmented Primal–Dual Gradient Dynamics [11]

The Augmented Primal–Dual Gradient Dynamics are reviewed with their global exponential stability result and its Lyapunov proof basis.

Augmented Primal–Dual Gradient Dynamics [11]

Proximal Augmented Lagrangian Primal–Dual Dynamics [18]

This section reviews the proximal augmented Lagrangian primal–dual dynamics and states their contraction result under Assumption 3.2.

Proximal Augmented Lagrangian Primal–Dual Dynamics [18]

B.1 Numerical Comparison of Contraction Rates Estimates

The comparison estimates contraction rates for SPPI, Aug-PDGD, and Prox-PDGD under two parameter identifications. Across the tested settings, SPPI’s estimated rate exceeds Aug-PDGD’s by several orders of magnitude, while its advantage over Prox-PDGD varies with conditioning.

B.1 Numerical Comparison of Contraction Rates Estimates

  • Comparing rates on a common axis requires an explicit parameter identification because SPPI and Aug-PDGD have two tunable gains, whereas Prox-PDGD has one scalar parameter.The study uses two identifications; c⋆ is numerically optimized by solving problem (61), approximated by bisection over c and grid search over κ.Source: §B.1 · p. 35
  • Four to seven orders of magnitude: cin exceeds the Aug-PDGD rate across all four tested conditioning regimes.Figure 10 plots the rates against shared γ for the original, well-conditioned, ill-conditioned, and near-isotropic regimes.Source: §B.1 · p. 36, Figure 10 · p. 36
  • cin exceeds c⋆ throughout the original and milder- and harsher-L/ρ regimes, while the curves become comparable at larger γ in the near-isotropic regime.The comparison is against Prox-PDGD; the gap narrows substantially in the near-isotropic case.Source: §B.1 · p. 36
  • Figure 11 varies kin for the cin-versus-cQL comparison, while Figure 10 plots the three rates against shared γ.Source: §B.1 · pp. 35–36, Figure 11 · p. 37
  • Three or more orders of magnitude: cin exceeds the Aug-PDGD rate across all tested kin values, including at each curve’s respective peak.Source: §B.1 · p. 36, Figure 11 · p. 37
Loading 2609.31086v1…