It is proved that the Error Bound Constraint Qualification is the weakest constraint qualification that guarantees boundedness of the computed multiplier sequences generated by the augmented Lagrangian method, and the feasibility of accumulation points of primal sequences generated by the augmented Lagrangian method under a Polyak-Łojasiewicz inequality for the quadratic infeasibility measure.
We consider convex optimization with nonlinear inequality constraints and develop a primal--dual multiplier framework that is consistent in continuous and discrete time. We first propose continuous-time dynamics with Nesterov-type vanishing damping $\alpha/t$, together with suitable extrapolations of the dual variable and the nonlinear constraint mapping. Under convexity assumptions and $\alpha\geq3$, we establish $\mathcal O(t^{-2})$ convergence rates for both nonlinear feasibility and the objective residual. We then derive an inexact accelerated primal--dual algorithm through a compatible discretization of a perturbed version of the dynamics. For composite convex objectives, a weighted summability condition on the primal inexactness yields the $\mathcal O(k^{-2})$ rates for feasibility and the objective residual, thereby matching the accelerated rates of their continuous-time counterparts. To the best of our knowledge, this is the first Nesterov-type primal--dual multiplier framework for convex optimization with nonlinear inequality constraints.
It is shown that strict complementarity, together with a quadratic facial-violation property of the associated complementary faces, implies uniform quadratic growth of both the primal and dual augmented Lagrangians near a strictly complementary solution, and the local equivalence of three regularity conditions is proved.
It is shown that any first-order method guaranteeing a bound on the primal objective gap f(x_N)-f(x_\star) assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate.
In this paper, we study a Tikhonov-regularized mixed-order primal--dual dynamical system with implicit Hessian damping for linearly constrained convex optimization problems in finite-dimensional Euclidean spaces, where the primal equation is second order and incorporates the viscous damping term \(\delta\sqrt{\varepsilon(t)}\,\dot x(t)\), whereas the multiplier equation remains first order. By constructing a new class of energy functions, for a general Tikhonov regularization coefficient \(\varepsilon(t)\), we prove the strong convergence of the primal trajectory and derive fast convergence rates under the same parameter assumptions, without imposing any eventual inside/outside-ball condition. More precisely, the primal trajectory converges to the minimum-norm solution, and the multiplier converges to a compatible KKT multiplier, while the convergence rates of the Lagrangian gap, feasibility violation, and objective residual are \(o(\varepsilon(t))\), and the convergence rate of the velocity norm is \(o(\sqrt{\varepsilon(t)})\). For the critical case \(\varepsilon(t)=c/t^2\), in which the damping coefficient \(\delta\sqrt{\varepsilon(t)}\) reduces to \(\delta\sqrt{c}/t\), we establish the sharper convergence rates \(o(t^{-2})\) for the Lagrangian gap, feasibility violation, and objective residual, together with \(o(t^{-1})\) for the velocity norm, which improve the corresponding \(O(t^{-2})\) and \(O(t^{-1})\) decay estimates obtained in the related literature. Most importantly, when the proposed dynamical system is specialized to the finite-dimensional unconstrained setting, our analysis answers the open question on strong convergence in this critical regime posed by Attouch and L\'aszl\'o [Math. Methods Oper. Res., 99 (2024), pp.~307--347].
This work proposes a nonlinear-residual linearized augmented Lagrangian method (NR-LALM) that replaces this subproblem by a regularized Gauss-Newton-type step while retaining the classical multiplier update based on the nonlinear constraint residual.
Benqi Liu, Kangkang Deng, Zichen Wang et al.· 0 citations
In this paper, we propose a balanced augmented Lagrangian method based on accelerated stochastic ADMM (b-ASADMM) to efficiently solve structured separable nonconvex optimization problems subject to linear constraints. The objective function in this problem comprises potentially nonsmooth and smooth functions, where the smooth function is an average of multiple nonconvex smooth functions. The involved smooth subproblem is tackled by an accelerated stochastic gradient method based on weighting of stochastic item and pre-variable. The involved nonsmooth subproblem is solved under incorporation of Bregman distance to avoid the case that subproblem does not have a closed-form solution due to the complicated quadratic term or other hindering. The involved balanced augmented Lagrangian method advances the original ALM by balancing its subproblems and improving its implementation. In contrast to most deterministic and stochastic ADMMs, our dual variable allows a more flexible and larger step-size region. By standard smoothness assumption, we establish the global convergence and iteration complexity of the generated sequence. Furthermore, we provide a linear convergence rate of b-ASADMM under a local error bound condition and the weakly convex property of the nonsmooth component. Numerical experiments on the graph-guided fused Lasso problem and the smooth clipped absolute deviation penalty problem are conducted to verify the effectiveness of b-ASADMM.
