A unified and comprehensive perspective on constructing augmented Lagrangian functions (based on the Hestenes–Powell–Rockafellar augmented Lagrangian) for various optimization problems, including nonlinear programming and convex and nonconvex composite programming.
Abstract
Abstract.
Large-scale constrained optimization is pivotal in modern scientific, engineering, and industrial computation, often involving complex systems with numerous variables and constraints. This paper provides a unified and comprehensive perspective on constructing augmented Lagrangian functions (based on the Hestenes–Powell–Rockafellar augmented Lagrangian) for various optimization problems, including nonlinear programming and convex and nonconvex composite programming. We present the augmented Lagrangian method (ALM), covering its theoretical foundations in both convex and nonconvex cases, and discuss several successful examples and applications. Recent advancements have extended the ALM’s capabilities to handle nonconvex constraints and ensure global convergence to first- and second-order stationary points. For nonsmooth convex problems, the ALM utilizes proximal operations, preserving desirable properties such as locally linear convergence rates. Furthermore, recent progress has refined the complexity analysis of the ALM and tackled challenging integer programming instances. This review aims to offer a thorough understanding of the ALM’s benefits and limitations, exploring different ALM variants designed to enhance convergence and computational performance. We also illustrate effective algorithms for ALM subproblems across different types of optimization problems and highlight practical implementations in several fields.
This work proposes a Hybrid Augmented Lagrangian (HyAL) method that combines the constraint-handling capabilities of the AL framework with the exploratory power of population-based search, and demonstrates that HyAL effectively solves constrained optimization problems, including high-dimensional cases where population-based methods struggle.
Lampros Printzios, Konstantinos I. Chatzilygeroudis· Proceedings of the Genetic a...· 0 citations
Constrained Optimization Problems are crucial in fields such as engineering, economics, and robotics, where high-dimensional search spaces and complex objectives and constraints are common. Numerical optimization methods, including Feasible Direction, Interior Point, and Sequential Quadratic Programming, have shown strong performance in finding feasible local optima, but require accurate analytical gradients and effective initialization, which can be challenging in real-world settings. Evolutionary Algorithms, on the other hand, offer gradient-free search and robustness to noisy landscapes, managing to detect global optima more often than numerical methods, but they often suffer from high computational costs and slow convergence. In this work, we propose a Hybrid Augmented Lagrangian (HyAL) method that integrates the AL framework's constraint-handling strengths with the exploratory power of population-based search. Our approach employs evolutionary techniques to solve subproblems within the AL iterations, promoting exploration and aiding in the escape from local optima. We conduct extensive experiments on benchmark optimization problems, comparing our method against state-of-the-art optimizers, including IPOPT and CMA-ES, and a standalone evolutionary optimization baseline (with constraint enforcement via penalties). In addition, we evaluate four population-based methods integrated within the AL framework to study the effect of different evolutionary solvers. Our results show that HyAL consistently produces high-quality solutions across the benchmark suite. It outperforms purely evolutionary approaches and scales more effectively to high-dimensional constrained problems, where evolutionary-only methods often struggle. HyAL also surpasses state-of-the-art numerical optimization algorithms on complex landscapes containing numerous local minima and saddle points.
Lampros Printzios, Konstantinos I. Chatzilygeroudis· 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.
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.
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
Two novel augmented Lagrangian algorithms with exact multipliers are developed, designed respectively for the full row-rank case and the general matrix case, where all subproblems are globally optimized via closed-form solutions.