Convergence rates for an inexact linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints

Lahcen El Bourkhissi, Ion Necoara · 2025

Read Convergence rates for an inexact linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints by Lahcen El Bourkhissi, Ion Necoara (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-2503-01060.txt.

Introduction

Lahcen El Bourkhissi and Ion Necoara design an optimization algorithm for hard problems that mix nonsmooth objectives with nonlinear equality constraints. Their paper came out in 2025. Such problems appear in control engineering and in data fitting, where exact methods often stall.

Their method extends a classic splitting scheme that alternates between two blocks of variables. At each step it linearizes the smooth parts, adds a changing quadratic penalty, and solves one block only approximately. Despite the approximations, they prove the iterates reach an approximate stationary point within a predictable number of steps. Under extra structure on the data, the whole sequence converges, with rates they also derive. Tests on control problems and matrix factorization support the theory.

Catalog record

CREATORLahcen El Bourkhissi, Ion Necoara
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE98 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-01060

Browse the full library · About the Tower of Babel

Full text

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

Convergence rates for an inexact linearized ADMM for nonsmooth nonconvex optimization with nonlinear equality constraints Lahcen El Bourkhissi, Ion Necoara Abstract In this paper, we consider nonconvex optimization problems with nonsmooth nonconvex objective function and nonlinear equality constraints. We assume that both the objective function and the functional constraints can be separated into 2 blocks. To solve this problem, we introduce a new inexact linearized alternating direction method of multipliers (ADMM) algorithm. Specifically, at each iteration, we linearize the smooth part of the objective function and the nonlinear part of the functional constraints within the augmented Lagrangian and add a dynamic quadratic regularization. We then compute the new iterate of the block associated with nonlinear constraints inexactly. This strategy yields subproblems that are easily solvable and their (inexact) solutions become the next iterates. Using Lyapunov arguments, we establish convergence guarantees for the iterates of our method toward an ϵ \epsilon -first-order solution within 𝒪 ⁡ ( ϵ − 2 ) \mathcal{O}(\epsilon^{-2}) iterations. Moreover, we demonstrate that in cases where the problem data exhibit e.g., semi-algebraic properties or more general the KL condition, the entire sequence generated by our algorithm converges, and we provide convergence rates. To validate both the theory and the performance of our algorithm, we conduct numerical simulations for several nonlinear model predictive control and matrix factorization problems. keywords Nonconvex optimization, linearized augmented Lagrangian method, alternating direction method of multipliers, convergence analysis. † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: The authors contributed equally to this work. 1 Introduction Many applications such as nonlinear model predictive control, state and parameter estimation of dynamical systems, training shallow neural networks, classification and signal processing can be formulated as the following structured nonsmooth nonconvex optimization problem with nonlinear equality constraints of the form (see for example [ 12 , 23 , 14 , 27 , 8 ] ): \displaystyle \displaystyle\underset{x\in\mathbb{R}^{n},y\in{\mathcal{Y}}\subseteq\mathbb{R}^{p}}{\min} \displaystyle f(x)+g(x)+h(y) (1) \displaystyle\textrm{s.t.:} \displaystyle F(x)+Gy=0, where \mathcal{Y} is a nonempty, closed subset of \mathbb{R}^{p} which admits an easy projection, the matrix G\in\mathbb{R}^{m\times p} , the functions f:\mathbb{R}^{n}\to{\mathbb{R}},g:\mathbb{R}^{n}\to\bar{\mathbb{R}},h:\mathbb{R}^{p}\to{\mathbb{R}}, and F\triangleq{(f_{1},...,f_{m})}^{T} , with f_{i}:\mathbb{R}^{n}\to{\mathbb{R}} for all i\in\{1,...,m\} , are nonlinear functions. We consider that f,h,f_{i} , for all i=1,...,m , are continuously differentiable functions, f,h are possibly nonconvex and g is a proper lower semi-continuous and prox-bounded function relative to its domain \text{dom}g (possibly nonconvex) . Moreover, we assume that the problem is well-posed, i.e., the feasible set is nonempty and the optimal value is finite. Note that problem ( 1 ) is more general than the one considered e.g., in [ 8 ] ; specifically, [ 8 ] can have constraints only on the block variables x , while we can impose constraints on both block variables x and y , respectively. Moreover, inequality constraints on x can be included in the function g using the indicator function. For example, any constrained composite optimization problem frequently appearing in optimal control [ 27 ] : \displaystyle\min_{x\in\mathcal{X}}f(x)+h(F(x))\quad\text{s.t. }\;F(x)\in\mathcal{Y}, can be easily recast in the form of optimization problem ( 1 ) by defining F(x)=y , then G=-I_{m} and g the indicator function of the set \mathcal{X} . Related work. In this paper, we propose an augmented Lagrangian approach to address problem ( 1 ). The augmented Lagrangian method, or method of multipliers, was introduced in [ 17 , 22 ] to minimize an objective function under equality constraints. It provides many theoretical advantages, even for non-convex problems (e.g., no duality gap and exact penalty representation), see [ 33 ] . In constrained optimization, the augmented Lagrangian approach has attracted considerable attention and has been widely studied for convex problems, for example in [ 1 , 6 , 28 , 30 , 21 ] and related references. More recently, researchers have extended this approach to non-convex problems, encompassing both smooth and non-smooth objectives with linear constraints, see for example [ 36 , 40 , 31 , 24 , 41 , 23 , 19 ] . However, there are very few studies on the use of the augmented Lagrangian framework for nonconvex optimization, where nonconvexity comes from constraints, e.g., [ 39 , 8 , 25 , 2 ] . In particular, in [ 39 ] , a proximal augmented Lagrangian (Proximal AL) algorithm is proposed to solve the problem ( 1 ); in this method, a static proximal term is added to the original augmented Lagrangian function. It is proved that when an approximate first- (second-) order solution of the subproblem is found, then an \epsilon first- (second-) order solution of the original problem ( 1 ) is obtained within \mathcal{O}(\epsilon^{\eta-2}) outer iterations, for some parameter \eta\in[0,2] . Note that when \eta is close to 2 , the efficiency is reduced to \mathcal{O}(1) outer iterations, but the subproblem, which is already non-convex, becomes very ill-conditioned as the penalty parameter of the augmented Lagrangian is inversely proportional to \epsilon^{\eta} . On the other hand, when the optimization problem at hand possesses a specific structure, such as the separability discussed in this paper, it becomes feasible to leverage this inherent structure within the augmented Lagrangian framework. This approach leads to the well-known Alternating Direction Method of Multipliers (ADMM) (refer to [ 6 , 13 , 15 , 8 , 40 , 3 , 5 , 18 ] ). In particular, in [ 6 ] , an ADMM method was introduced for solving a separable convex problem with linear constraints, and its asymptotic convergence was demonstrated. In [ 18 ] , the authors established the convergence rate of an inexact ADMM, designed for solving a nonsmooth convex problem with linear constraints. It was proven that when the objective function is convex their method has complexity \mathcal{O}(\epsilon^{-1}) and \mathcal{O}(\epsilon^{-0.5}) in the strongly convex setting. Furthermore, [ 40 ] proposed a Proximal Linearized ADMM (PL-ADMM) to address nonsmooth nonconvex problems with linear equality constraints for two blocks. In this scenario, one block of the problem is smooth, and the other is nonsmooth. The PL-ADMM algorithm linearizes the smooth parts during each block update, incorporates a dynamic metric proximal term in the primal update, and includes an overrelaxation step in the dual update. Paper [ 40 ] demonstrated that each limit point of the sequence generated by this algorithm is a stationary point of the original problem. Additionally, it was shown that under the Kurdyka-Lojasiewicz (KL) property, the method converges either in a finite number of iterations, sublinearly, or linearly, depending on the exponent associated with the KL condition. However, for nonconvex problems with nonlinear equality constraints, limited research has been conducted, specifically in [ 8 , 3 , 9 ] . In [ 3 ] , the authors addressed a special case of problem ( 1 ) ( g=0 , \mathcal{Y}=\mathbb{R}^{n} and G=-I , where I denotes the identity matrix of appropriate dimension), proving that when the primal iterates are approximate stationary points of the augmented Lagrangian function, each limit point is a first-order solution of the problem. Furthermore, it was demonstrated that, under KL, the entire sequence generated by their method converges to a first-order solution of the problem. Further, in [ 8 ] , the authors proposed an augmented Lagrangian-based method to tackle the problem considered in this paper (with \mathcal{Y}=\mathbb{R}^{n} ) and

Read the complete text