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

Linglingzhi Zhu; Jiajin Li

math.OCJul 9, 2026

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

Authors: Linglingzhi Zhu, Jiajin Li

Organizations: 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.

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.

Explore similar work

Jul 21, 2026math.OC

Online Optimization of Difference-of-Convex Compositions with Smooth Mappings

We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.

Jingwei Ji, Jong-Shi Pang, Renyuan Xu

Convex Optimization Proximal Gradient Descent Regret

Ask PDF

Aug 31, 2026math.OC

Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy

This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points. Leveraging a unified game-theoretic interpretation of eight classical algorithm families--including block coordinate descent, ADMM, generalized Benders decomposition, successive convex approximation, interior-point methods, mirror descent, Frank-Wolfe, and Riemannian gradient descent--we show that the normalized multiplier vector carries an algorithm-independent structural fingerprint. Four scale-free shape features of this vector partition the dual space into five operational regimes: Unconstrained, Resource-Limited, Saturation, Strongly-Coupled, and Hybrid. We establish four structural theorems characterizing the partition: invariance under natural KKT symmetries, local stability under data perturbation with explicit Lipschitz margins from Robinson's strong regularity, codimension-one regime transitions, and the topological identification of the Hybrid regime as the Lebesgue-null boundary of the core regimes. A linear-time classifier is proposed with provable guarantees on correctness, iteration stabilization, sample complexity, and online tracking under data drift. Numerical experiments on 104 mixed-integer nonlinear programs and a downlink beamforming instance validate the theoretical predictions. The framework provides a foundational tool for regime-aware algorithm design and robustness analysis in non-convex optimization.

Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabi

Convex Optimization Norm Game Theory Taxonomy Fingerprint

Ask PDF

Sep 16, 2026math.OC

Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization

We introduce a new single-loop algorithmic framework for smooth nonconvex--concave minimax optimization. The resulting projected damped extragradient method combines projected extragradient updates, dual momentum, and a moving proximal center. Under both the optimization-stationarity and game-stationarity criteria, our method achieves the best-known complexity among single-loop first-order methods. For optimization stationarity, our method achieves a gradient complexity of

O(L^2D_Y\barΔ_0\varepsilon^{-3})

, where

L

is the gradient Lipschitz constant,

D_Y

bounds the diameter of the dual feasible set, and

\barΔ_0

is an initialization quantity involving the value-function gap and the initial gradients. Moreover, by incorporating a fixed-center warm-up phase, the complexity can be improved to

O(L^2D_YΔ_φ\varepsilon^{-3})

, up to an additive lower-order cost, where

Δ_φ:=φ(x_0)-\inf_xφ(x)

. We further establish a lower bound of

Ω(L^2D_YΔ_φ\varepsilon^{-3})

for optimization stationarity over projected zero-respecting first-order methods. This lower bound proves that the warm-started version of our algorithm is optimal up to a constant factor for optimization stationarity within this oracle class. For game stationarity, our method achieves

\mathcal{O}\!(L^{3/2}D_Y^{1/2}Δ_φ\varepsilon^{-5/2})

gradient complexity. This matches the best-known complexity of multi-loop first-order methods, thereby establishing the same complexity with a single-loop algorithmic structure. Under dual strong concavity, the proposed framework achieves

O\!(\sqrtκ\,LΔ_φ\varepsilon^{-2})

leading complexity for both stationarity criteria, where

κ=L/μ

is the dual condition number, up to an additive initialization cost. The

\varepsilon^{-2}

accuracy dependence is optimal under fixed regularity and initialization bounds.

Minghao Zhang, Zi Xu

Convex Optimization Stationarity Gradient Concentration Model Complexity

Ask PDF