Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints

Kang Liu; Mengxiao Chen; Siqi Xiong; Yi Xia

math.OCSep 12, 2026

Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints

Authors: Kang Liu, Mengxiao Chen, Siqi Xiong, Yi Xia

Organizations: School of Future Technology, Xi’an Jiaotong University, Xi’an, China · School of Automation Science and Engineering, Xi’an Jiaotong University, Xi’an, China · Department of Rehabilitation Sciences, The Hong Kong Polytechnic University, Hong Kong SAR, China

Abstract

This work studies the stability and convergence of augmented primal-dual dynamics when constraint values are estimated from samples. Unbiased constraint observations can produce a biased augmented multiplier signal, shifting the equilibria of the mean dynamics. For componentwise inequalities, we give a necessary and sufficient condition for preserving the Karush-Kuhn-Tucker (KKT) equilibria and construct a convex example with a locally exponentially stable equilibrium that violates complementarity. To address this bias, constraint values are estimated recursively before forming the augmented multiplier signal. For smooth convex conic problems, a joint energy analysis establishes boundedness of the primal, dual, and estimation states, vanishing estimation error, and almost sure convergence of the primal-dual iterates to a single KKT point under global regularity and bounded conditional second moments. The result allows nonunique solutions and multipliers while keeping the number of samples per iteration fixed. Numerical studies illustrate the predicted equilibrium bias and examine convergence with nonunique KKT points and nonlinear constraints.

Figures & tables

Figure 1: Bias and equilibrium displacement. In panel (a), lines show the formulas in Corollary 4.2 ; markers show antithetic estimates, with error bars of

1.96

estimated standard errors computed across independent pairs. In panel (b), points show final means over 32 paths, with error bars of one sample standard deviation. The dotted line shows the prediction in ( 7.1 ).

Figure 2: REC on the problem in ( 7.2 ). Panel (a) shows means and one sample standard deviation over all 24 paths at the indicated checkpoints. Panel (b) shows the free multiplier coordinate

(2u_{1}-u_{2})/\sqrt{5}

for the first replicate in each initialization group, without smoothing or averaging. This coordinate is unrestricted in the KKT set ( 7.3 ).

Figure 3: Nonlinear study with noise amplitude

\sigma=2

. Curves show mean current residuals over 48 runs on six test instances. Panel (a) uses a common optimization step formula, indexed by update count, to compare constraint estimation strategies. Panel (b) uses the separately calibrated step parameters of each method. The horizontal budget counts observation tuples, each containing one stochastic gradient vector and one stochastic constraint vector; every sample in a batch is counted.

$\sigma$	Method	$10^{4}\mathcal{R}$	$10^{2}E_{f}$	$10^{2}V_{c}$
0.5	RAW ( $B=1$ )	$14.27\pm 6.34$	$1.29\pm 0.53$	$0.29\pm 0.39$
	RAW ( $B=4$ )	$1.11\pm 0.50$	$0.22\pm 0.15$	$0.25\pm 0.20$
	CG	$0.63\pm 0.34$	$0.25\pm 0.16$	$0.55\pm 0.21$
	REC	$0.59\pm 0.33$	$0.23\pm 0.15$	$0.52\pm 0.21$
	PPD	$0.84\pm 0.40$	$0.17\pm 0.13$	$0.45\pm 0.22$
	SLPMM	$12.02\pm 5.09$	$0.35\pm 0.14$	$0.62\pm 0.18$

Table 1: Nonlinear comparison after

20000

observation tuples using separately calibrated step parameters. Entries are means

\pm

sample standard deviations over 48 runs per noise level. The residual

\mathcal{R}

is evaluated at the current primal–dual state. The errors

E_{f}

and

V_{c}

are evaluated at the prescribed averaged primal output for SLPMM and APriD and at the current primal state for the other methods. Column headings indicate the numerical scaling.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

$\sigma$	Method	$10^{2}E_{f}$	$10^{2}V_{c}$
0.5	RAW ( $B=1$ )	$1.17\pm 0.16$	$0.07\pm 0.11$
	RAW ( $B=4$ )	$0.11\pm 0.09$	$0.32\pm 0.16$
	CG	$0.76\pm 0.17$	$1.25\pm 0.24$
	REC	$0.68\pm 0.18$	$1.14\pm 0.24$
	PPD	$0.49\pm 0.20$	$0.95\pm 0.28$
	SLPMM	$0.35\pm 0.14$	$0.62\pm 0.18$

Appendix

Table 2: Averaged primal outputs with separately calibrated step scales. Means

\pm

sample standard deviations cover 48 runs per noise level. APriD uses its prescribed weights; all other averages are arithmetic.

$\sigma$	Estimate	$10^{4}\mathcal{R}$	$10^{2}\\|y-c(x)\\|^{2}$
0.5	RAW ( $B=1$ )	$9.82\pm 2.81$	—
	RAW ( $B=4$ )	$1.41\pm 0.52$	—
	CG	$0.63\pm 0.34$	$1.82\pm 1.29$
	REC	$0.59\pm 0.33$	$0.18\pm 0.12$
2	RAW ( $B=1$ )	$922.41\pm 231.21$	—
	RAW ( $B=4$ )	$143.86\pm 35.12$	—

Appendix

Table 3: Constraint estimation with a common optimization step formula indexed by update count. Each noise level has 48 runs and a budget of

20000

tuples. Batch size four uses

5000

updates; the other configurations use

20000

. A dash indicates that there is no recursive estimate.

Primal-Dual Optimization

Primal-dual optimization jointly updates decision variables and constraint multipliers to solve constrained problems with feasibility and optimality guarantees.

See all 52 papers

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
Jul 9, 2026Linglingzhi Zhu, Jiajin LiPrimal-Dual Optimization Nonconvex Optimization
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.
Matrix-Valued Optimism is Matrix-Valued Augmentation: Additive Hybrid Designs for Constrained Optimization
May 7, 2026Jiayi ZhaoPrimal-Dual Optimization Augmented Lagrangian Method
University of Washington Seattle, WA, USA
A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization
Aug 12, 2026Frank E. Curtis, Lingjun Guo, Daniel P. RobinsonOptimization Convergence Analysis Nonconvex Optimization
Department of Industrial and Systems Engineering, Lehigh University

Jul 9, 2026J/K move · Enter open · S save

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

Linglingzhi Zhu, Jiajin Li

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.

Primal-Dual Optimization Nonconvex Optimization Augmented Lagrangian Method

Open paper AskPDF arXiv

We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems under local multiplier regularity. Both the objective and functional inequality constraints are compositions of convex Lipschitz outer functions with smooth nonlinear mappings. Unlike existing analyses requiring regularity globally or along the entire iterate sequence, we impose multiplier regularity only near the feasible set. Using an auxiliary minimax problem with a compact dual set, we derive Lyapunov estimates that identify nearly feasible iterates under feasible initialization and a sufficiently large penalty, without assuming multiplier boundedness. Local regularity then bounds the associated multipliers and makes dual truncation inactive, yielding approximate KKT certificates for the original problem. The smoothed prox-linear augmented Lagrangian method with dual regularization yields an

O(K^{-1/3})

KKT residual rate. Without regularization, piecewise linear outer functions and additional local structural assumptions yield a local dual error bound and the sharper

O(K^{-1/2})

rate.

Abstract

Primal-Dual Optimization

Explore similar work

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

Matrix-Valued Optimism is Matrix-Valued Augmentation: Additive Hybrid Designs for Constrained Optimization

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization