Constrained optimization stops sampling constraints uniformly: keeping recently violated ones cuts iterate error by two orders of magnitude on synthetic problems
Synopsis
For stochastic-gradient optimization with very many inequality constraints, an adaptive constraint-sampling method stops drawing each step's constraint uniformly from all constraints and instead maintains an "important set" of recently violated constraints, sampling from that set or from all constraints with fixed probabilities. On 100-dimensional synthetic convex problems it lowers the final Euclidean distance of the iterates to the constrained minimizer by about two orders of magnitude on average for ABSGD, Projection-SGD and Huber-penalty SGD, and by one to two orders for APDSG; in Dubins Car control-barrier-function synthesis it lowers maximum constraint violation by half an order to one order of magnitude.
Interpretation
When constraints are numerous, stochastic-gradient methods touch only one constraint per step, but which constraint is drawn strongly affects convergence; the new method biases sampling toward recently violated constraints and pushes iterates closer to the constrained minimizer. Earlier stochastic first-order constrained methods typically use uniform constraint sampling, which in very large problems draws constraints that carry no information for the current update, making updates noisy and performance worse. On a 100-dimensional synthetic problem with five quadratic and five logarithmic components, the method lowers the final Euclidean distance to the constrained minimizer by two orders of magnitude on average for ABSGD, Projection-SGD and Huber-penalty SGD, and by one to two orders for APDSG; the effect holds when constraints rise from 2×105 to 106, and the authors report improvements of up to 100 times relative to uniform sampling.
The mechanism keeps an "important set" of indices of recently violated constraints and, each step, draws a constraint from that set with probability η and from all constraints with probability 1−η, so every constraint retains positive sampling probability. Classical working-set methods evaluate all constraints or solve subproblems to update the working set; the new method uses a history-dependent mechanism over already sampled constraints, needs no full objective information and solves no subproblem per working-set update. On four Dubins Car control-barrier-function synthesis problems, run with Projection-SGD and ABSGD over 100 sample trajectories each, the method lowers maximum constraint violation at the final iteration by half an order to one order of magnitude on average; the authors report under 10% wall-clock increase across all simulations regardless of constraint count.
Perspective
The demonstrated scope is a 100-dimensional synthetic convex problem with a baseline configuration of 2×105 affine constraints, a large-scale configuration of 106 constraints, and a variant adding 103 constraints near the minimizer of the 2×105 baseline, plus four local Dubins Car control-barrier-function synthesis problems, measured by distance of iterates to the minimizer and by maximum constraint violation.
A convergence analysis is not included; the authors say almost-sure convergence and finite-time active-set identification will be presented in an upcoming paper, and nonlinear constraints, neural-network-parameterized control barrier functions, momentum-based and gradient-free methods are listed as future work.