Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
2026-07-09 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how fast certain optimization methods work when solving tricky problems that aren't straightforwardly curved (nonconvex) and have constraints made from combining smooth and convex parts. They handle challenges like constraints sometimes being broken and unknown multiplier sizes by limiting the multiplier range and smoothing the problem. Their main result is a way to link progress on a simplified problem to a meaningful solution for the original problem, proving that most steps get close to feasible solutions. They provide clear rates for how quickly their method approaches a solution under different technical conditions.
nonconvex optimizationprimal-dual methodsfunctional inequality constraintsaugmented Lagrangianminimax reformulationKKT conditionsprox-linear methodconvergence ratesdual error boundsconstraint regularity
Authors
Linglingzhi Zhu, Jiajin Li
Abstract
We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems with a convex-composite structure. In this class, both the objective and the functional inequality constraints are given by convex Lipschitz outer functions composed with smooth nonlinear inner mappings. The analysis is complicated by constraint violation in a nonconvex functional inequality system and by the lack of an a priori bound on the multipliers. To address these issues, we restrict the dual variable to an auxiliary compact set and analyze a smoothed prox-linear augmented Lagrangian method through a nonsmooth nonconvex-concave minimax reformulation. The main contribution is a finite-time mechanism for converting stationarity of the truncated minimax problem into a KKT certificate for the original constrained problem. We show that, for a sufficiently large penalty parameter, all but a controlled number of iterates enter a near-feasible region. On this region, a local conic regularity condition uniformly bounds the associated prox-linear multipliers and thereby makes the artificial dual truncation inactive at the selected iterates. Building on this mechanism, we establish explicit convergence rates for the proposed method in terms of the KKT residual. With dual regularization, a global dual error bound together with a bias-balancing argument gives an $O(K^{-1/3})$ rate. In the unregularized case, under additional local structural assumptions including piecewise linearity of the outer functions, a local dual error bound yields the sharper $O(K^{-1/2})$ rate.