A projection-free dynamics for nonsmooth composite optimization
Wei Ni, Yangfan Qiu, and Yanyan Xiao · 2025
Read A projection-free dynamics for nonsmooth composite optimization by Wei Ni, Yangfan Qiu, and Yanyan Xiao (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-2510-22173.txt.
Introduction
Wei Ni, Yangfan Qiu, and Yanyan Xiao design a flow for hard optimization problems. The problems mix a nonsmooth term with equality and inequality constraints. The standard trick projects gradients back onto the allowed set. That trick is awkward to analyze and clumsy to simulate. The authors drop projection entirely.
Mirror descent shapes the primal-dual dynamics instead. The variables and their constraint prices move as a pair. An extended proximal augmented Lagrangian handles general convex constraints. The joint dynamics turn strongly convex in one block and strongly concave in the other. That pairing is the recipe for exponential convergence. The error shrinks by a constant factor per unit time. Earlier guarantees were weaker. They ignored constraints, allowed only flat ones, or promised only eventual arrival.
Catalog record
| CREATOR | Wei Ni, Yangfan Qiu, and Yanyan Xiao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 288 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22173
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A projection-free dynamics for nonsmooth composite optimization Wei Ni, Yangfan Qiu, and Yanyan Xiao Abstract This paper proposes a projection-free primal-dual dynamics for the nonsmooth composite optimization problems with equality and inequality constraints. To deal with optimization constraints, this paper departs from the use of gradient projection method, but resorts to the idea of mirror descent to design a continuous-time smooth optimization dynamics which advantageously leads to easier convergence analysis and more efficient numerical simulation. Also, the strategy of proximal augmented Lagrangian (PAL † ) is extended to incorporate general convex equality-inequality constraints and the strong convexity-concavity of the primal-dual variables is achieved, ensuring exponential convergence of the resulting algorithm. Furthermore, the convergence result in this paper extends existing exponential convergence which either takes no account of constraints or considers only affine linear constraints, and it also enhances existing asymptotic convergence under convex constraints which unfortunately depends on the complex gradient projection scheme. \contact WeiNiSchool of Mathematics and Computer Sciences, Nanchang University, Nanchang, China. He is also with Key Laboratory of Intelligent Systems and Human-Machine Interaction of Jiangxi [email protected] \contact YanyanXiaoSchool of Mathematics and Computer Sciences, Nanchang University, Nanchang, China. [email protected] \contact YangfanQiuSchool of Mathematics and Computer Sciences, Nanchang University, Nanchang, [email protected] keywords Composite optimization, proximal augmented Lagrangian, projection-free Classification: 90C25, 90C30, 90C90 † † footnotetext: For convenience, other acronyms defined in this paper are also summarized here: \displaystyle\begin{array}[]{lllllllll}&\text{AL: augmented Lagrangian.}&\text{PAL: proximal augmented Lagrangian.}\\ &\text{IQC: integral quadratic constraints. }&\text{SCQ: Slater's constrained qualification. }\\ &\text{KKT: Karush-Kuhn-Tucker. }&\text{LICQ: linear independence constraint qualification. }\end{array} 1 INTRODUCTION Composite optimization with nonsmooth regularization has been a topic of a large amount of research. This problem consists in minimizing the sum of a differentiable function f(x) and a possibly nonsmooth one \varphi(Tx) , with the latter being a composition of an extended-valued function \varphi with a linear operator T . A prominent example is the empirical risk minimization with nonsmooth regularization as parameter choice rule in deep neural network lecun2015 . As another example, the typical signal processing problem of restoration of a continuous signal from its digital counterparts is tackled by solving an optimization problem known as the lasso tibshirani1996 which is a specific case of the problem considered in this paper. Applications in other fields include inverse problem beck2009 , statistical estimation bickel2008 , and control lin2013 . Due to the presence of the nondifferentiable part \varphi in the objective function, classical gradient based optimization algorithms, such as gradient descent, conjugate gradient, and Newton methods, cannot be directly applied. To tackle non-smoothness, a direct research line is the nonsmooth optimization method, including subgradient method shor2012 , stochastic approximation nemirovski2009 and bundle method makela2002 , but the convergence is very slow. As a parallel, the smooth optimization method nesterov2005 replaces the nonsmooth component with smooth approximations parameterized by a positive parameter and then resorts to smooth optimization routines; however, as the parameter approaches zero, the problem becomes increasingly involved. A breakthrough was made via proximal operator in a series of milestone papers which do not require explicit gradient rockafellar1976b ; beck2009 ; boyd2011 ; tseng2000 . In these methods, the smooth part of the objective function is processed by evaluation of its gradient operator, while a nonsmooth part is handled via its Moreau proximal operator moreau1965 , resulting in iterations of the form x^{+}\in\operatorname{prox}_{\gamma\psi(T(x))}(x-\gamma\nabla f(x)) for some suitable stepsize \gamma . Proximal method can be derived from operator splitting techniques (see Douglas douglas1956 , Passty passty1979 and Bruck bruck1977 ) which find their roots in the works of Browder browder1965 and Minty minty1962 , and now it is developed in the more general setting of maximal monotone operators abbas2015 . The more recent work by Combettes and Wajs combettes2005 provides important insights into the proximal method and has popularized the method for a wide audience. Nowdays the proximal method becomes an important part of convex analysis, optimization, and nonlinear functional analysis. The above proximal method involves the proximal calculation with respect to the composite function \varphi\circ T which is however difficult to evaluate for general case. To overcome this, a frequently used technique is the variable splitting which constructs a new variable y to serve as the argument of \varphi and imposes additional constraint y=Tx . Then this constrained optimization problem can be tackled by using an augmented Lagrangian (AL) method nocedal1999 originally due to Hestenes hestenes1969 and Powell powell1969 and by designing corresponding primal-dual algorithms arrow1958 . The AL here extends the classical Lagrangian by including an extra quadratic term, without changing the optimal solution but facilitating the proximal operator to be used here. The proximal version of this method is earlier developed by Rockafellar rockafellar1976b and its connection to alternating direction of multiplier method is recently explored by Boyd boyd2011 , followed by a burst of research activities in subsequent years. Note that the AL function mentioned above still contains a nondifferentiable term and thus precludes the standard strategy of gradient descent on primal variables and gradient ascent on dual variables. To conquer the nondifferentiablity in the traditional AL, Dhingra et al. dhingra2019 recently propose a new kind of differentiable Lagrangian, called PAL, which is obtained by taking infimum over the AL with respect to the primal variable of the nonsmooth function. Compared with the AL in nocedal1999 , a coming advantage of the PAL is that it is continuously differentiable on both primal and dual variables so that direct primal-dual dynamics can be applied on the PAL. With the help of PAL, the original optimization problem is transformed into the computation of the saddle point of this PAL, and various formulations of primal-dual dynamics have been explored in the literature with focus on investigating asymptotic or exponential convergence under different conditions dhingra2021 ; goldsztajn2021 ; hassan2021 ; ju2022 ; francca2021 ; tang2020 ; eckstein2025 . In a broader view, ever since von Neumann’s celebrated min-max theorem neumann1928 , the problem of finding a saddle point for a convex-concave function has been a major focus of disciplines like machine learning goodfellow2014 , robust optimization ben2009 , robust control hast2013 and game theory bacsar1998 . For the abstract gradient descent-ascent algorithm which performs gradient descent in convex variable and gradient ascent in concave variable, there is a vast literature obtaining asymptotic convergence if either the convexity or concavity are strict sion1958 ; kose1956 ; arrow1958 ; cherukuri2017 ; exponential convergence can be further ensured if strongly convex strongly concave condition is imposed cherukuri2017 . However, when specialized to the case of classical Lagrangian which is only linear on the dual variables, exponential stability can not be obtained directly for the primal-dual dynamics. This has also been highlighted in wang2021 that the combination of general convex constraints and nonsmooth objectives poses a significant challenge to achieving exponential stability. To prove exponential stability under extra conditions, other routines include the contraction analysis cisneros2021 and the technique of spectral bounds of saddle matrices benzi2005 . In this paper, instead of building on the classical Lagrangian but on the PAL, we develop a primal-dual optimization dynamics. Aside from the advantage of variable splitting inherent in the PAL, we will show that the PAL induces strong concavity on dual variable under appropriate conditions and renders the corresponding primal-dual optimization