The main contribution is a finite-time mechanism for converting stationarity of the truncated minimax problem into a KKT certificate for the original constrained problem and establishing explicit convergence rates for the proposed method in terms of the KKT residual.
Abstract
We study nonasymptotic convergence of primal-dual methods for a class of nonconvex constrained optimization problems with a convex-composite structure. In this class, both the objective and the functional inequality constraints are given by convex Lipschitz outer functions composed with smooth nonlinear inner mappings. The analysis is complicated by constraint violation in a nonconvex functional inequality system and by the lack of an a priori bound on the multipliers. To address these issues, we restrict the dual variable to an auxiliary compact set and analyze a smoothed prox-linear augmented Lagrangian method through a nonsmooth nonconvex-concave minimax reformulation. The main contribution is a finite-time mechanism for converting stationarity of the truncated minimax problem into a KKT certificate for the original constrained problem. We show that, for a sufficiently large penalty parameter, all but a controlled number of iterates enter a near-feasible region. On this region, a local conic regularity condition uniformly bounds the associated prox-linear multipliers and thereby makes the artificial dual truncation inactive at the selected iterates. Building on this mechanism, we establish explicit convergence rates for the proposed method in terms of the KKT residual. With dual regularization, a global dual error bound together with a bias-balancing argument gives an $O(K^{-1/3})$ rate. In the unregularized case, under additional local structural assumptions including piecewise linearity of the outer functions, a local dual error bound yields the sharper $O(K^{-1/2})$ rate.
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.
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
This paper studies a new class of nonlocal optimal control problems where the constraints involve approximations of minimizers of quasiconvex energies. These problems are parameterized by a fractional parameter $s \in (0, 1)$ and a horizon parameter $\delta>0$, and the energy density depends on a nonlocal fractional gradient. Here, the constraint consists of finding quasi-minimizers with respect to the quasiconvex energy. Despite the fact that the energies of interest may not have unique minimizers, we may prove the existence of solutions to this class of control problems. The constraint in Cueto-Siktar 2026 was finding global minimizers of the energy, and this problem's main limitation was an inability to prove convergence of solutions for the nonlocal control problems to those of a corresponding local, PDE-constrained optimal control problem. While this issue arises from the lack of uniqueness of minimizers for the constraining energy, we get stronger convergence results with our new choice of constraints. Namely, we obtain convergence of minimizers for nonlocal optimal control problems that have a general cost functional depending on the nonlocal gradient.
It is well-known that duality theory is a fundamental tool in various areas of mathematics. There are great advantages to including or using the dual problem and duality statements. Especially, solving the dual problem can be done using other methods of analysis or numerical mathematics. We consider a primal vector optimization problem with an objective function acting between a linear topological space
X
and a linear topological space
Y
equipped with a pointed closed convex cone
$$D\subset Y$$
D
⊂
Y
with nonempty interior. The feasible set is supposed to be a closed convex cone. The aim of this paper is to construct a simple and easy-to-handle dual problem by exploiting the special structure of the primal problem and using a suitable nonlinear scalarization. The computation of the dual image set involves the minimization of a nonlinear scalarization of the primal vector-valued objective function subject to only one linear inequality constraint. We introduce a new concept of upper semicontinuity for a vector-valued function and prove (weak and strong) duality statements under the assumption that the vector-valued objective function is
D
-quasiconvex and
D
-upper semicontinuous. Furthermore, we study special cases.
J. Martínez-Legaz, C. Tammer· TOP - An Official Journal of...· 0 citations
This work considers the design of first-order convex optimization algorithms and convergence proofs. In particular, we consider nonsmooth Lipschitz and smooth problems accessed through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance Estimation Problems (PEPs) has shown that structured, tight convergence proofs typically exist. Under mild conditions, we further show 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. These implicit optimal dual certificates, which take the form of affine lower bounds, also provide insight into the role of auxiliary sequences in momentum methods.