An adaptive proximal safeguarded augmented Lagrangian method for nonsmooth DC problems with convex constraints
Christian Kanzow, Tanja Neder · 2025
Read An adaptive proximal safeguarded augmented Lagrangian method for nonsmooth DC problems with convex constraints by Christian Kanzow, Tanja Neder (2025) 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-2505-15369.txt.
Introduction
Christian Kanzow and Tanja Neder present a solver method for rough tuning problems in 2025. Their target problems minimize a difference of two convex functions. Limits include staying inside a convex set plus linear and convex side rules. All parts may have kinks, which blocks smooth methods.
Their method wraps a safeguarded penalty scheme around local linear stand ins for the concave part. Each step solves a convex sub problem for the main variable. Under a mild rule on the constraints, the path is proven to reach a point that meets the classic optimality tests. Tests compare the method with known solvers.
Catalog record
| CREATOR | Christian Kanzow, Tanja Neder |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 145 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-15369
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An adaptive proximal safeguarded augmented Lagrangian method for nonsmooth DC problems with convex constraints Christian Kanzow, Tanja Neder Abstract A proximal safeguarded augmented Lagrangian method for minimizing the difference of convex (DC) functions over a nonempty, closed and convex set with additional linear equality as well as convex inequality constraints is presented. Thereby, all functions involved may be nonsmooth. Iterates (of the primal variable) are obtained by solving convex optimization problems as the concave part of the objective function gets approximated by an affine linearization. Under the assumption of a modified Slater constraint qualification, both convergence of the primal and dual variables to a generalized Karush-Kuhn-Tucker (KKT) point is proven, at least on a subsequence. Numerical experiments and comparison with existing solution methods are presented using some classes of constrained and nonsmooth DC problems. An ALM for constrained DC problems \manuscriptlicense CC-BY 4.0 \manuscriptsubmitted 2025-05-23 \manuscriptaccepted 2026-03-23 \manuscriptvolume 6 \manuscriptnumber 15731 \manuscriptyear 2026 \manuscriptdoi 10.46298/jnsao-2026-15731 1 Introduction We consider a class of nonsmooth DC problems with convex constraints of the following type: \min_{x\in\mathbb{R}^{n}}f(x):=g(x)-h(x)\quad\text{s.t.}\quad Ax=b,\ c(x)\leq 0,\ x\in C (P) with g,h:\mathbb{R}^{n}\rightarrow\mathbb{R} convex, A\in\mathbb{R}^{p\times n} (with p\leq n ), b\in\mathbb{R}^{p} , c_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R} convex for i=1,\dots,m and \emptyset\neq C\subseteq\mathbb{R}^{n} closed and convex, where for a vector y\in\mathbb{R}^{m} the relation y\leq 0 here as well as in what follows is meant componentwise, that is y\leq 0\quad:\Longleftrightarrow\quad y_{i}\leq 0\ \forall i=1,\dots,m. As the objective function f has a representation as the difference of two convex functions, it is called a DC function , whereas g and h are referred to as DC~components . (These DC components are, of course, not unique.) The increasing interest in DC optimization is due to the broad field of real world applications (see e.g. [ 35 , 23 ] and references therein for exemplary overviews). To put the focus on problems matching the above setting, let us mention questions emerging in logistics, in particular location planning [ 35 , 6 ] as well as production-transportation problems [ 15 ] , in chance-constrained management problems [ 9 ] , in designing communication systems with physical layer based security [ 28 ] , in compressed sensing [ 41 ] , in the packaging industry [ 16 ] and in machine learning, for example within feature selection in the context of support vector machines [ 20 ] . Many methods for the solution of constrained DC programs impose additional assumptions on the DC objective function. In particular, it is frequently assumed that one of the DC components has to be continuously differentiable (see e.g. [ 1 ] or DCA2 in [ 21 ] ) or even Lipschitz-differentiable (see e.g. LCDC-ALM in [ 17 ] ), or that the second DC component has to be the pointwise maximum of finitely many continuously differentiable functions [ 28 , 29 , 26 ] . Extension of these approaches to general nonsmooth DC objective functions seems to be difficult. Hence, we focus on constrained DC problems where the objective function is given as the difference of two arbitrary nonsmooth convex functions. To the best of our knowledge, there are only a few other approaches dealing with this general setting. [ 9 ] presents a proximal bundle method for minimizing a nonsmooth DC function over a general closed and convex set. Thereby, the key idea is not only to approximate the second DC component by a linearization, but also the first one by a cutting-plane model. No penalization of the constraints is carried out. An approach for minimizing nonsmooth DC functions under linear equality constraints can be found in [ 17 ] by neglecting the smooth part of the first DC component while considering Composite LCDC-ALM. Then, further restrictions are implicitly embedded as the first DC component of the objective function is assumed to be proper, lower semicontinuous and convex with compact domain over which it is itself supposed to be Lipschitz-continuous. The crucial point of the method is, to replace once more in each iteration the concave part by a linearization before then considering the Moreau envelope of the resulting augmented Lagrangian function. In [ 36 , 37 ] the authors introduce a method for minimizing a nonsmooth DC function over a closed and convex set which gets further restricted by (without loss of generality one single) DC-type inequality. Adopting the idea of the classical DC Algorithm (DCA, [ 22 ] ), one linearizes in each iteration the second DC component in both, the objective function and the constraint. The resulting subproblems though need not to be solved exactly. Instead, computing a point of the modified feasible set which provides a sufficient decrease in the model function is adequate. However, a feasible point is required for initialization in order to avoid infeasibility of the subproblems which might otherwise occur due to relaxing the DC type constraint. In case one omits the latter constraint, the method boils down to (a proximal version of) DCA [ 22 ] but with the modification of allowing for inexact solutions of the subproblems. Also in [ 21 ] , DC programs with DC constraints that get complemented by a closed and convex set are considered. Referring to DCA1, penalizing the DC constraints suitably carries over the DC structure to the resulting penalty problems. This again allows to apply the strategy of the classical DCA, that is to approximate within each subproblem the concave part of the objective function by an affine majorization. In addition, the penalty parameter gets updated in each iteration. Although the problem setting at the beginning is kept of a general nature, the convergence theory of DCA1 requires, in particular, differentiability of one of the DC components of the penalized objective function. Dealing with constrained DC problems, one can, of course, always apply the classical DCA [ 22 ] itself by formally rewriting the problem as an unconstrained one, which, however, is equivalent to carrying over the constraints into the subproblems. Notwithstanding the method, keeping the constraints in the subproblems might make them hard to solve, depending on the application. Hence, our aim has been to develop an algorithm for constrained DC optimization which first, is able to handle a general nonsmooth DC objective function and second, allows for augmentation of the probably most considered convex constraints, namely linear equality as well as convex inequality restrictions. For the last mentioned ones, also no smoothness assumptions are imposed. In addition, we wanted to provide the possibility of keeping somewhat easy constraints, for example box constraints, in the subproblems. Thus, we add an abstract constraint to our problem formulation. Moreover, we adopt the idea of the classical DCA [ 22 ] to approximate the concave part of the objective function in each iteration by an affine majorization. Combining this approach with the basic concept of safeguarded augmented Lagrangian methods, which has some advantages against the classical augmented Lagrangian method (see [ 18 ] for a discussion), we yield convex subproblems, being, in general, simpler to solve than DC problems. Note that quite many applications (with convex feasible region) involve only linear equality and convex inequality constraints but no further abstract ones. In that case we even may obtain unconstrained convex subproblems. (Though, there is still the possibility of keeping such