math.OCNov 15, 2026

First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization

Authors: Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu

Organizations: Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY · Tippie College of Business, University of Iowa, Iowa City, IA · IMAI, Wuhan University; Department of Applied Mathematics, Hong Kong Polytechnic University, China

Abstract

We consider regularized nonconvex optimization over a closed convex set X⊆Rd\mathcal{X} \subseteq \mathbb{R}^d, which involves a convex nonsmooth regularizer rr in the objective and nn smooth equality constraints. To find a near-KKT point of the problem, we propose a prox-linear first-order method, named as SEPi-Prox, based on a smoothed exact-penalty formulation. At each outer iteration of SEPi-Prox, a strongly convex prox-linear subproblem is formed and solved inexactly to a sufficient accuracy. Under a local non-singularity condition that is weaker than some other commonly used regularity conditions or constraint qualifications, SEPi-Prox finds an εε-KKT point within O(ε−2)O(ε^{-2}) first-order oracle calls, matching the lower bound for unconstrained smooth nonconvex optimization. We employ Nesterov's accelerated proximal-gradient method (APG) and a dual cutting-plane method (DCP) for the prox-linear subproblems. Let CFO\mathcal{C}_{\mathrm{FO}} and Cr\mathcal{C}_r denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of rr over X\mathcal{X}, respectively. Then SEPi-Prox requires O~(CFOε−2+(dn+Cr)ε−5/2)\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2}) and O~((CFO+dn2+nCr+n3.373)ε−2)\widetilde{O}((\mathcal{C}_{\mathrm{FO}} + dn^2 + n\mathcal{C}_r + n^{3.373})ε^{-2}) total arithmetic operations to produce an εε-KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when nn is small and nearly matches the optimal dependence on εε. Numerical experiments on instances of the multi-class Neyman-Pearson classification demonstrate the efficiency of SEPi-Prox with both subsolvers.

Figures & tables

Explore similar work

Jan 31, 2025

A SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization

Many real-world problems, such as those with fairness constraints, involve complex expectation constraints and large datasets, necessitating the design of efficient stochastic methods to solve them. Most existing research focuses on cases with no {constraint} or easy-to-project constraints or deterministic constraints. In this paper, we consider nonconvex nonsmooth stochastic optimization problems with expectation constraints, for which we build a novel exact penalty model. We first show the relationship between the penalty model and the original problem. Then on solving the penalty problem, we present a single-loop SPIDER-type stochastic subgradient method, which utilizes the subgradients of both the objective and constraint functions, as well as the constraint function value at each iteration. Under certain regularity conditions (weaker than Slater-type constraint qualification or strong feasibility assumed in existing works), we establish an iteration complexity result of O(ε−4)O(ε^{-4}) to reach a near-εε stationary point of the penalized problem in expectation, matching the lower bound for such tasks. Building on the exact penalization, an (ε,ε)(ε,ε)-KKT point of the original problem is obtained. For a few scenarios, our complexity of either the {objective} sample subgradient or the constraint sample function values can be lower than the state-of-the-art results by a factor of ε−2ε^{-2}. Moreover, on solving two fairness-constrained problems and a multi-class Neyman-Pearson classification problem, our method is significantly (up to 466 times) faster than the state-of-the-art algorithms, including switching subgradient method and inexact proximal point methods.
Jul 9, 2026

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

We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems under local multiplier regularity. Both the objective and functional inequality constraints are compositions of convex Lipschitz outer functions with smooth nonlinear mappings. Unlike existing analyses requiring regularity globally or along the entire iterate sequence, we impose multiplier regularity only near the feasible set. Using an auxiliary minimax problem with a compact dual set, we derive Lyapunov estimates that identify nearly feasible iterates under feasible initialization and a sufficiently large penalty, without assuming multiplier boundedness. Local regularity then bounds the associated multipliers and makes dual truncation inactive, yielding approximate KKT certificates for the original problem. The smoothed prox-linear augmented Lagrangian method with dual regularization yields an O(K−1/3)O(K^{-1/3}) KKT residual rate. Without regularization, piecewise linear outer functions and additional local structural assumptions yield a local dual error bound and the sharper O(K−1/2)O(K^{-1/2}) rate.
Aug 31, 2026

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.