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

Jul 16, 2026

Upload by Rowan

Study of first-order primal-dual methods for nonconvex constrained optimization with convex-composite structure: both the objective and functional inequality constraints are formed by convex Lipschitz outer functions composed with smooth nonlinear inner mappings. The analysis tackles constraint violation and the absence of an a priori multiplier bound by truncating dual variables to an auxiliary compact set and applying a smoothed prox-linear augmented Lagrangian through a nonsmooth nonconvex-concave minimax reformulation. Finite-time conversion from truncated stationarity to a KKT certificate is established, yielding explicit KKT-residual rates, including O(K^{-1/3}) with dual regularization and O(K^{-1/2}) in the unregularized piecewise-linear setting.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages30

Reading Time1 h 16 min

Introduction

Problem Formulation and Convex-Composite Structure

Background on ALM and Multiplier Control

Related Primal-Only Methods and Motivation

arXiv :2607 .08954v1 [math .OC] 9 Jul 2026 Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity Linglingzhi Zhu∗ Jiajin Li† July 2026 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. Mathematics Subject Classification (2020) . Primary 90C26, 90C30; Secondary 90C46, 49J52 . 1 Introduction We consider nonsmooth nonconvex constrained optimization problems whose objective and functional inequality constraints have the convex-composite form min x∈X s.t. h0 (c0 (x)) hi(ci(x)) ≤ 0, i = 1 ,..., d. (P) Here, X ⊆ Rn is a nonempty compact convex set, each outer function hi is convex and Lipschitz continuous, and each inner mapping ci is smooth and possibly nonlinear. This convex-composite structure is classical in nonsmooth optimization and model-based first-order methods [12 , 14 , 19] . It ∗ H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. ([llzzhu@gatech.edu](llzzhu@gatech.edu)) †Sauder School of Business, University of British Columbia, Vancouver, BC, Canada. ([jiajin.li@sauder.ubc.ca](jiajin.li@sauder.ubc.ca)) naturally covers empirical conditional value-at-risk constraints after introducing an auxiliary quantile variable [31], as well as maximum-type and finite robust constraints represented by convex nonsmooth outer functions applied to smooth scenario losses [4 , 5] . Together, these examples illustrate that the convex-composite formulation provides a natural framework for constrained problems in which both the objective and the functional constraints may be nonsmooth and nonconvex. A growing body of work has developed convergence and complexity analyses for penalty- and Lagrangian-based methods in constrained nonconvex optimization. For problems with smooth nonlinear constraints, inexact and proximal augmented Lagrangian methods (ALMs), quadratic-penalty schemes, and primal–dual methods based on the augmented Lagrangian have been studied under various regularity assumptions [1 , 6 , 15 , 22 , 23 , 32 , 36] . A common technical issue in these analyses is the control of multiplier sequences. Existing approaches typically obtain multiplier boundedness through a global error-bound or a PŁ-type regularity condition for the feasibility violation, a uniform constraint qualification, or an explicit bounded-multiplier assumption. For nonconvex problems

FAQs

What problem class is studied in this document?

It studies nonconvex constrained optimization problems where the objective and functional inequality constraints have a convex-composite form: convex Lipschitz outer functions composed with smooth (possibly nonlinear) inner mappings.

How does the paper address the lack of an a priori bound on multipliers?

It restricts the dual variable to an auxiliary compact set and analyzes a smoothed prox-linear augmented Lagrangian using a nonsmooth nonconvex-concave minimax reformulation.

What convergence guarantees are provided for the proposed method?

For sufficiently large penalty parameters, iterates enter a near-feasible region where local conic regularity bounds prox-linear multipliers and allows the truncation to be inactive. Explicit convergence rates are given in terms of the KKT residual, including O(K^{-1/3}) with dual regularization and O(K^{-1/2}) under additional unregularized local structural assumptions such as piecewise linear outer functions.

Jul 16, 2026

Upload by Rowan