Stability and convergence of optimization with sampled constraints
Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints
Machine Learning
Summary
Optimizing problems often involves following certain rules or constraints exactly, but sometimes these rules have to be estimated from imperfect or random samples. The authors find that even unbiased samples can cause a tricky shift in how the method behaves and where it eventually settles. They provide conditions to avoid this shift and propose updating the constraint estimates as part of the process, ensuring the method converges reliably to a correct solution. Their work helps understand and improve optimization methods when constraints can't be known exactly and must be guessed from data.
What this means in practice
- •For optimization engineers: Ensure reliable convergence in real-time optimization when constraint data is sampled or uncertain.
- •For control systems designers: Improve stability of controllers using sampled measurements to enforce constraints in convex systems.
Authors
Kang Liu, Mengxiao Chen, Siqi Xiong, Yi Xia
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.