Convergence of the Safeguarded Augmented Lagrangian Method under the Polyak-Łojasiewicz constraint qualification for Constrained Composite Optimization

Christian Kanzow, Jannis Krüger · 2026

Read Convergence of the Safeguarded Augmented Lagrangian Method under the Polyak-Łojasiewicz constraint qualification for Constrained Composite Optimization by Christian Kanzow, Jannis Krüger (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25567.txt.

Introduction

Augmented Lagrangian methods are workhorses for constrained optimisation, but the safeguarded variant's convergence theory had a gap where its multipliers might run away. Christian Kanzow and Jannis Krüger close much of that gap in 2026 for composite problems, where the objective splits into a smooth part and a nonsmooth part like a sparsity penalty. Under a new constraint qualification named after Polyak and Łojasiewicz, they prove global convergence to a stationary point of the right generalised kind.

Boundedness of the multipliers does the heavy lifting, and it rests on the nonsmooth part being locally Lipschitz. A counterexample shows that assumption cannot simply be dropped. Numerical trials on sparse portfolio problems confirm the split: with a Lipschitz sparsity term the method behaves far better, while the non Lipschitz term repeatedly produced seemingly unbounded multipliers in practice.

Catalog record

CREATORChristian Kanzow, Jannis Krüger
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25567

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Convergence of the Safeguarded Augmented Lagrangian Method under the Polyak-Łojasiewicz constraint qualification for Constrained Composite Optimization Christian Kanzow, Jannis Krüger Abstract In this work we provide theoretical and practical results of the Safeguarded Augmented Lagrangian Method (SALM) for constrained composite optimization problems whose objective is the sum of a smooth and a nonsmooth function. We obtain global convergence results to an M-stationary point for SALM under the Polyak-Łojasiewicz constraint qualification (PŁCQ). For this result the boundedness of the Lagrange multipliers is crucial, and this is shown under the assumption that the nonsmooth part of the objective function is locally Lipschitz continuous. A counterexample shows that one cannot expect to get bounded multipliers without such an assumption. The performance of the algorithm is evaluated numerically on a set of sparse portfolio optimization problems with two different regularization terms, one being Lipschitz and the other one being non-Lipschitz. The results are significantly better for the Lipschitz sparsity term, whereas the underlying method generates seemingly unbounded multipliers in many instances when using the non-Lipschitz sparsity function. \DeclareSourcemap \maps [datatype=bibtex] \map \step [fieldsource=fjournal, fieldtarget=journaltitle] \map \step [fieldsource=fseries, fieldtarget=series] Keywords. Safeguarded augmented Lagrangian method, global convergence, M-stationarity, Polyak-Łojasiewicz constraint qualification, locally Lipschitz regularization function, composite optimization. Mathematics Subject Classification (2020) 49J53 \cdot 65K05 \cdot 90C30 1 Introduction We consider constrained optimization problems of the form \displaystyle\min_{x\in\mathbb{R}^{n}}f(x)+\varphi(x)\quad\text{s.t.}\quad g(x)\leq 0,\quad h(x)=0 (1.1) under the following assumptions: Assumption 1.1 . (i) The functions f:\mathbb{R}^{n}\to\mathbb{R} , g:\mathbb{R}^{n}\to\mathbb{R}^{m} and h:\mathbb{R}^{n}\to\mathbb{R}^{p} are continuously differentiable. (ii) \varphi is a locally Lipschitz continuous function. Problems of this kind arise in a wide range of topics such as engineering, machine learning, optimal control or signal processing, with tasks like image restoration [ 6 ] , low-rank matrix completion [ 8 ] , compressed sensing [ 41 ] , clustering [ 39 ] , principal component analysis [ 29 ] and model predictive control [ 13 ] . The theoretical difficulty for solving problems of such composite nature is the non-smooth function in the objective, as this requires an extension of differentiability and stationarity concepts that may lack the nice properties of smooth problems. In this paper we consider the Safeguarded Augmented Lagrangian Method (SALM) as a suitable method for numerically solving composite constrained problems. Building on the classical Augmented Lagrangian Method by Powell [ 35 ] , Hestenes [ 22 ] , and Rockafellar [ 36 ] , the safeguarded version introduced for the ALGENCAN solver [ 1 ] is a powerful and versatile choice for smooth constrained optimization due to its algorithmic simplicity and extensive global convergence theory, see also [ 7 ] . As Augmented Lagrangian methods require solving an unconstrained minimization problem in each step, a practically useful extension of SALM to composite problems necessitates the existence of subproblem solvers which can at least find subdifferentially stationary points of unconstrained composite problems satisfying Assumption 1.1 . More recently, suitable results for the Proximal Gradient Method [ 24 ] and Proximal Quasi Newton Methods [ 17 , 12 ] have been established. This gave the opportunity to develop a global convergence theory for SALM and constrained composite problems in [ 16 ] , using even a more general problem setting via geometric constraints, and only requiring \varphi to be proper and lower semicontinuous (lsc). In the latter paper, the authors use AM-regularity as a constraint qualification in order to show subsequential convergence of the SALM sequence to a M-stationary point for the more general problem. We want to follow a different approach here. As we consider a more specialized setting with explicit equality and inequality constraints, we are looking to use the least strict constraint qualification tailored to this constraint setting that also still ensures a global convergence result of the iterates. For this approach, we mainly follow the considerations of Andreani et al. in [ 2 ] . In that paper, the authors introduce a constraint qualification (PŁCQ) using a Polyak-Łojasiewicz inequality, show that it is in fact equivalent to an Error Bound Condition (EB), and also show that this is the least restrictive constraint qualification for smooth problems that still ensures boundedness of the multiplier sequences, which is in return pivotal in establishing convergence of the SALM iterates to an M-stationary point. In view of these results cited above, \varphi being locally Lipschitz continuous may seem like a quite restrictive assumption for the regularization term. However, this restriction is necessary for the required multiplier boundedness, as illustrated in Section 4.1 . The rest of this work is organized as follows: Section 2 summarizes some basic facts from variational analysis. In Section 3 , we extend the global convergence theory of SALM under the PŁCQ from [ 2 ] to our composite optimization setting ( 1.1 ) under Assumption 1.1 . We then provide a counterexample that demonstrates the necessity of the local Lipschitz assumption for \varphi in Section 4 . We present some numerical results of SALM applied to sparse portfolio optimization comparing Lipschitz and non-Lipschitz regularization functions in Section 5 , and conclude the paper with some final remarks in Section 6 . Notation: Let \Omega denote the feasible set of the optimization problem ( 1.1 ). The active set for a feasible point is written as \displaystyle I(x^{*}):=\{i\in\{1,\ldots,m\}:g_{i}(x^{*})=0\}. The sets of non-negative and positive real numbers are denoted by \mathbb{R}_{+} and \mathbb{R}_{++} , respectively. For v\in\mathbb{R}^{n} we write \displaystyle v_{+}:=(\max\{0,v_{1}\},\ldots,\max\{0,v_{n}\})^{T} for the projection of v onto the nonnegative orthant \mathbb{R}^{n}_{+} . The symbol \|\cdot\| always denotes the Euclidean norm, and B_{r}(x) and \overline{B}_{r}(x) the corresponding open and closed balls with radius r centered at x , respectively. Finally, \operatorname{dist}(x,S) denotes the Euclidean distance \inf_{w\in S}\|x-w\| from x\in\mathbb{R}^{n} to S\subseteq\mathbb{R}^{n} . 2 Mathematical Background The set of extended real numbers is denoted by \overline{\mathbb{R}}:=\mathbb{R}\cup\{\pm\infty\} . We write x\to^{f}x^{*} if x\to x^{*} and f(x)\to f(x^{*}) , also called f -attentive convergence . For f:\mathbb{R}^{n}\to\overline{\mathbb{R}} we write \operatorname{dom}(f):=\{x\in\mathbb{R}^{n}\mid f(x)<+\infty\} and say that f is proper, if \operatorname{dom}(f)\neq\emptyset and f(x)>-\infty for all x\in\mathbb{R}^{n} . For our convergence analysis we recall some definitions and classical results from nonsmooth analysis as presented in the standard sources [ 30 ] and [ 37 ] . Definition 2.1 . Let f:\mathbb{R}^{n}\to\overline{\mathbb{R}} be proper, lsc and x\in\operatorname{dom}(f) . (a) The set \displaystyle\hat{\partial}f(x):=\left\{v\in\mathbb{R}^{n}\biggm|\liminf_{x\to\bar{x}}\frac{f(x)-f(\bar{x})-v^{T}(x-\bar{x})}{\|x-\bar{x}\|}\geq 0\right\} is called the Fréchet subdifferential of f at x . (b) The set \displaystyle\partial f(x):=\{v\in\mathbb{R}^{n}\mid\exists\{x^{k}\},\{v^{k}\}\subseteq\mathbb{R}^{n}:x^{k}\to^{f}x,v^{k}\to v,v^{k}\in\hat{\partial}f(x^{k})\,\forall k\in\mathbb{N}\} is called the limiting/Mordukhovich subdifferential of f at x . By the definitions of the subdifferentials it is apparent that \hat{\partial}f(x)\subseteq\partial f(x) (2.1) holds for all x\in\operatorname{dom}(f) . These subdifferentials admit a generalized Fermat rule [ 30 , Proposition 1.30 (i)] , which leads to a natural extension of stationarity for an unconstrained non-smooth setting. Lemma 2.2 (Subdifferential Fermat rule) . Let f be proper and lsc and let f have a local minimum in x^{*} . Then 0\in\hat{\partial}f(x^{*}) (2.2) and 0\in\partial f(x^{*}). (2.3) Points satisfying these conditions are called F- or S-stationary ( 2.2 ) (S for strong) and M-stationary ( 2.3 ) respectively. We can relax the stationarity condition by introducing \varepsilon -stationarity. Here, we only introduce this terminology for the Mordukhovich subdifferential. Definition 2.3 . Let f:\mathbb{R}^{n}\to\overline{\mathbb{R}} be proper and lsc. A vector x^{*}\in\operatorname{dom}(f) is called an \varepsilon -stationary point, if there exists an

Read the complete text