Augmented Lagrangian Method

Momentum

2 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 14

Sep 27, 2026math.OC

lapanda: A Matrix-Free Differentiable Solver for Nonconvex Constrained Optimization Layers

Differentiable optimization brings the structural guarantees of mathematical optimization to network pipelines, allowing them to be trained end-to-end. However, its application remains challenging for nonconvex constrained problems, as existing differentiable solvers often suffer from limited modeling expressiveness due to their reliance on specialized problem structures, while also incurring substantial computation time and memory overhead in both the forward and backward passes. To address these challenges, we propose lapanda, a matrix-free differentiable solver for nonconvex optimization with general constraints. It reformulates the problem to a sequence of augmented Lagrangian subproblems, each handled by a first-order inner solver through a proximal averaged quasi-Newton algorithm with adaptive linesearch, thus enabling efficient forward optimization. We establish local well-posedness of the solution map and convergence of the outer iterations, and further derive a sensitivity alignment between the original problem and the final subproblem in the backward pass, demonstrating that the subproblem sensitivity, which can be computed efficiently in a matrix-free manner, provides a principled approximation to the exact optimizer sensitivity. We evaluate lapanda on nonconvex constrained Rosenbrock benchmarks, imitation learning with several representative constrained optimal control problems, and embedded robotic obstacle-avoidance tasks. Compared with state-of-the-art differentiable solvers, lapanda delivers substantial reductions in computation time and memory footprint while maintaining reliable constraint satisfaction and learning performance.

Yuankun Chen, Zifei Nie, Kangyu Lin +2

School of Artificial Intelligence, Jilin University, China · Graduate School of Informatics, Kyoto University, JPN · Department of Civil and Systems Engineering, Johns Hopkins University, USA

Differentiable Programming Nonconvex Optimization Quasi-Newton Methods Augmented Lagrangian Method Differentiable Optimization

Ask PDF

Sep 14, 2026cs.LG

Scaling Laws for Physics-Aware ACOPF Surrogate Learning

Learning-based surrogates for AC optimal power flow (ACOPF) promise large speedups over classical solvers, but their operational value depends on physical feasibility as much as predictive accuracy. Physics-aware objectives such as the augmented Lagrangian (AL) improve constraint satisfaction at additional per-step cost, yet how this trade-off behaves with scale is uncharacterized. We sweep model and dataset sizes under both MSE and AL training, and characterize how constraint violation changes with network size across grids. Both objectives improve as power laws, but at different rates: MSE is governed primarily by model capacity, while AL is balanced across both. Violation grows roughly twice as fast with network size under MSE as under AL. On matched hardware, AL reduces violation by nearly

30\times

for an order of magnitude more training time, with negligible added memory. The training objective determines not only where a surrogate lands but how its quality evolves with scale.

Yijiang Li, Emon Dey, Stefano Fenu +3

Argonne National Laboratory Lemont, USA · Oak Ridge National Laboratory Oak Ridge, USA

Neural Surrogate Modeling Optimal Power Flow Augmented Lagrangian Method Scaling Laws

Ask PDF

Sep 3, 2026cs.LG

Guide, Not Bind: Why Defeasible Priors Fail in Augmented Lagrangian Causal Discovery

Differentiable causal discovery methods increasingly encode expert priors as forbidden-edge constraints enforced by an Augmented Lagrangian (ALM) penalty, on the assumption that a data-adaptive relaxation mechanism will discount and eventually override a rule the data consistently contradicts. We show this design, which we call \emph{guide, not bind}, fails for two independent, precisely characterized reasons, and that directly repairing both restores it only partially. First, sequential penalty-ramping ALM suppresses a wrongly-forbidden true edge before any counterfactual check can detect it: we give three necessary conditions any adaptive relaxation must satisfy to avoid this (Proposition~\ref{prop:conditions}), prove that DADU---the natural relaxation rule this paper introduces as the object of study---violates all three (Corollary~\ref{cor:dadu_failure}), and confirm the failure across 3{,}072 training runs spanning graphs from 4 to 32 nodes, where a single wrong prior suppresses a true edge in 87--97% of trials under DADU. Second, and independent of any fix to the mechanism, we prove in closed form that the standard correlation-matching objective ties a true edge and its reverse to an identical cost of exactly

2r^2

(Lemma~\ref{lem:tie}), not because the underlying equal-variance model is unidentifiable, but because normalizing to correlation discards exactly the variance information that would make it identifiable; covariance matching instead separates the two directions by a provable margin of at least

w_0^4

(Lemma~\ref{lem:separation}).

Sairam Sundararaman, Sara Girdhar, Manit Narasimha Murthy +2

Department of Computer Science (AI & ML) PES University · Department of Computer Science2026 PES University · Department of Computer Science PES University

Causal Discovery Causal Identifiability Augmented Lagrangian Method

Ask PDF

Aug 12, 2026math.OC

A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.

Frank E. Curtis, Lingjun Guo, Daniel P. Robinson

Department of Industrial and Systems Engineering, Lehigh University

Optimization Convergence Analysis Nonconvex Optimization Augmented Lagrangian Method

Ask PDF

Jul 18, 2026cs.NE

Hybrid Augmented Lagrangian Method for General Constrained Optimization via Evolutionary Algorithms

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 Chatzilygeroudis

Laboratory of Automation & Robotics (LAR), Department of Electrical & Computer Engineering, University of Patras, University Campus, Patras, GR-26504, Achaia, Greece

Evolutionary Optimization Augmented Lagrangian Method Constrained Optimization

Ask PDF

Jul 9, 2026math.OC

Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity

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.

Linglingzhi Zhu, Jiajin Li

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.

Primal-Dual Optimization Nonconvex Optimization Augmented Lagrangian Method

Ask PDF

May 30, 2026cs.RO

Infeasible optimization problems and the hierarchical augmented Lagrangian method in imitation learning

Imitation learning (IL) is an effective approach to train complex robotics policies. Recent works have introduced hard constraints into imitation-learning optimization problems to ensure safety, stability, and robustness of the learned policy. However, we argue that these constraints are sometimes infeasible, which can lead to unstable or difficult training dynamics. We study a simple remedy for such situations based on recent theoretical results on the augmented Lagrangian method in infeasible settings. We show that our approach drives the learned policy toward the solution of a closest-feasible constrained IL problem with desirable properties. The method is illustrated on a toy driving example with a total-acceleration constraint and pedestrian-safety constraints, a setting in which infeasibility can naturally arise while still allowing a safe learned policy.

Roland Andrews, Justin Carpentier, Ajay Sathya

Imitation Learning Augmented Lagrangian Method Constrained Optimization

Ask PDF

May 29, 2026cs.LG

Augmented Lagrangian Predictive Coding

Predictive coding (PC) is a local-learning alternative to backpropagation (BP), training deep networks via local energy-minimization dynamics rather than a global backward pass. We introduce Augmented Lagrangian Predictive Coding (PC-ALM), which maintains PC's inference budget but aligns each weight update toward BP by accumulating per-layer constraint errors into a layer-local Lagrange multiplier. In linear PC networks, PC-ALM converges to an equilibrium with exact BP gradients distributed across the network via only layer-local updates. We analyze PC-ALM in nonlinear PC networks up to depth 128 and show that it matches BP performance across all width-depth regimes, notably in deep narrow networks where PC underperforms. PC-ALM introduces recurrent dynamics in each layer's activations. Compared to PC's heat flow on a scalar energy, PC-ALM dynamics are driven by dual ascent on the augmented Lagrangian. We observe "ballistic" credit propagation across very deep networks, with credit signals evenly distributed across layers, compared to PC's slow, diffusive credit propagation. Beyond the algorithm itself, the augmented Lagrangian framework offers a generalization of PC, and may yield insights into how distributed systems could compute and propagate BP-like credit signals through purely local dynamics.

Jeffrey Seely, Julian Gould

Sakana AI

Backpropagation Predictive Coding Augmented Lagrangian Method Neural Network Training Dynamics Local Learning

Ask PDF

May 19, 2026cs.LG

Exploiting Non-Negativity in DAG Structure Learning

This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations generated by a linear structural equation model. DAG learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property. Continuous acyclicity constraints have led to important algorithmic advances by replacing the discrete DAG constraint with smooth equality constraints. However, existing formulations still involve difficult non-convex optimization landscapes and may suffer from degenerate first-order optimality conditions. Here, we restrict attention to DAGs with non-negative edge weights and exploit this additional structure to obtain a simpler characterization of acyclicity. Building on this characterization, we formulate a regularized non-negative DAG learning problem and develop an algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by non-negativity. In the population regime, we show that the true DAG is the unique global minimizer of the proposed augmented-Lagrangian formulation; moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic KKT point. Numerical experiments on synthetic and real-world data show that the proposed method improves over state-of-the-art continuous DAG-learning alternatives.

Samuel Rey, Madeline navarro, Gonzalo Mateos

Dept. of Signal Theory and Communications, Universidad Rey Juan Carlos, Madrid, Spain · Dept. of Electrical and Computer Engineering, Rice University, Houston, TX 77005, USA · Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA

Graph Structure Learning Structural Causal Models Causal Structure Learning Nonconvex Optimization Augmented Lagrangian Method Constrained Optimization

Ask PDF

May 12, 2026cs.LG

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes (CMDPs). While existing theoretical guarantees typically hold for the mixture policy, deploying such a policy is computationally and memory intensive. This leads to a practical mismatch where a single (last-iterate) policy must be deployed. Recent theoretical works have thus focused on proving last-iterate convergence, but are largely limited to the tabular setting or to algorithmic variants that are rarely used in practice. To address this, we use the classic inexact augmented Lagrangian (

\texttt{AL}

) method from constrained optimization, and propose a general framework with provable last-iterate convergence for CMDPs. We first focus on the tabular setting and propose to solve the

\texttt{AL}

sub-problem with projected Q-ascent (

\texttt{PQA}

). Combining the theoretical guarantees of

\texttt{PQA}

and the standard

\texttt{AL}

analysis enables us to establish global last-iterate convergence. We generalize these results to handle log-linear policies, and demonstrate that an efficient, projected variant of

\texttt{PQA}

can achieve last-iterate convergence with comparable guarantees as prior work. Finally, we demonstrate that our framework scales to complex non-linear policies, and evaluate it on continuous control tasks.

Michael Lu, Max Qiushi Lin, Mo Chen +1

Simon Fraser University

Markov Decision Processes Last-Iterate Convergence Policy Optimization Constrained RL Convergence Analysis Augmented Lagrangian Method+1

Ask PDF

May 9, 2026cs.RO

IMPACT: An Implicit Active-Set Augmented Lagrangian for Fast Contact-Implicit Trajectory Optimization

Contact-implicit trajectory optimization (CITO) has attracted growing attention as a unified framework for planning and control in contact-rich robotic tasks. Recent approaches have demonstrated promising results in manipulation and locomotion without requiring a prescribed contact-mode schedule. It is well known that the underlying mathematical programs with complementarity constraints (MPCCs) remain numerically ill-conditioned, and systematic, scalable solution strategies for CITO remain an active area of research. More efficient and principled solvers that can handle contact constraints are therefore essential to broaden the applicability of CITO. In this work, we develop an augmented-Lagrangian approach to CITO for solving MPCC-based CITO with stationarity guarantees. The method can be interpreted as identifying the implicit contact-mode branches on the fly during the trajectory optimization (TO) iterations; we call this approach IMPACT (IMPlicit contact ACtive-set Trajectory optimization). We provide an efficient C++ implementation tailored to trajectory-optimization workloads and evaluate it on the open-source CITO and contact-implicit model predictive control (CI-MPC) benchmarks. On CITO, IMPACT achieves 2.9x-70x speedups over strong baselines (geometric mean 13.8x). On CI-MPC, we show improved control quality for contact-rich trajectories on dexterous manipulation tasks in simulation. Finally, we demonstrate the proposed method on real robotic hardware on a T-shaped object pushing task.

Jiayun Li, Dejian Gong, Georgia Chalvatzaki

1PEARL Lab, Dept. of Computer Science, TU Darmstadt, Germany · 2Hessian.AI, Darmstadt, Germany · 3Robotics Institute Germany (RIG)

Constrained Motion Planning Trajectory Optimization Contact-Rich Robotic Manipulation Augmented Lagrangian Method Constrained Optimization Optimal Control

Ask PDF

May 7, 2026cs.LG

Matrix-Valued Optimism is Matrix-Valued Augmentation: Additive Hybrid Designs for Constrained Optimization

Augmented Lagrangian and optimistic primal--dual methods stabilize equality-constrained optimization through seemingly different mechanisms: the former adds constraint-dependent primal curvature, while the latter adds dual memory. Recent work has shown that these mechanisms are equivalent for scalar parameters. We extend this equivalence to matrix-valued correction. We prove an additivity principle: for symmetric matrix parameters, the ideal primal trajectory depends only on the summed correction matrix, not on how it is split between augmented and optimistic channels. This exposes a design freedom: algebraically equivalent decompositions can have different finite-step feasibility because augmented correction affects primal curvature, whereas optimistic correction affects the scale of the dual memory correction. We formulate the resulting step-size-limited design problem and derive a closed-form hybrid rule that selects a matrix correction, splits it between the two channels, and chooses primal and dual steps using local spectral weights. Experiments on nonlinear equality-constrained problems with controlled constraint-Jacobian conditioning show that the hybrid design improves over pure augmented and pure optimistic endpoints, closely tracks a grid-search hybrid oracle, and is competitive with first-order primal--dual baselines under mild-to-moderate ill-conditioning. The experiments also identify the expected limitation: exact cancellation requires increasingly large matrix corrections as the constraint Jacobian becomes ill-conditioned.

Jiayi Zhao

University of Washington Seattle, WA, USA

Primal-Dual Optimization Augmented Lagrangian Method Constrained Optimization

Ask PDF

May 1, 2026cs.LG

Augmented Lagrangian Multiplier Network for State-wise Safety in Reinforcement Learning

Safety is a primary challenge in real-world reinforcement learning (RL). Formulating safety requirements as state-wise constraints has become a prominent paradigm. Handling state-wise constraints with the Lagrangian method requires a distinct multiplier for every state, necessitating neural networks to approximate them as a multiplier network. However, applying standard dual gradient ascent to multiplier networks induces severe training oscillations. This is because the inherent instability of dual ascent is exacerbated by network generalization -- local overshoots and delayed updates propagate to adjacent states, further amplifying policy fluctuations. Existing stabilization techniques are designed for scalar multipliers, which are inadequate for state-dependent multiplier networks. To address this challenge, we propose an augmented Lagrangian multiplier network (ALaM) framework for stable learning of state-wise multipliers. ALaM consists of two key components. First, a quadratic penalty is introduced into the augmented Lagrangian to compensate for delayed multiplier updates and establish the local convexity near the optimum, thereby mitigating policy oscillations. Second, the multiplier network is trained via supervised regression toward a dual target, which stabilizes training and promotes convergence. Theoretically, we show that ALaM guarantees multiplier convergence and thus recovers the optimal policy of the constrained problem. Building on this framework, we integrate soft actor-critic (SAC) with ALaM to develop the SAC-ALaM algorithm. Experiments demonstrate that SAC-ALaM outperforms state-of-the-art safe RL baselines in both safety and return, while also stabilizing training dynamics and learning well-calibrated multipliers for risk identification.

Jiaming Zhang, Yujie Yang, Yao Lyu +2

Constrained RL Augmented Lagrangian Method Constrained Optimization Safe RL

Ask PDF

Apr 13, 2025math.OC

Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization

In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems with exact constraints and stochastic objective evaluations. To solve this class of problems, we propose a framework of mirror descent linearized augmented Lagrangian methods that employs two-point stochastic zeroth-order gradient estimators and exploits non-Euclidean mirror descent geometry. Under mild assumptions, we establish oracle complexity guarantees for finding an

ε

-KKT point parameterized by

p \geq 2

. Under Rademacher smoothing, our analysis reveals a trade-off between the variance of the zeroth-order gradient estimators and the smoothness of the mirror map. In the high-accuracy regime, the resulting effective oracle complexity is

\mathcal{O}(p d^{2/p}ε^{-3})

for

p \in [2,2\ln d]

and

\mathcal{O}(\ln d\,ε^{-3})

for

p > 2\ln d

. These bounds reduce the dimension dependence in the leading term. When

p=2

, our method recovers the Euclidean setting with an oracle complexity of

\mathcal{O}(dε^{-3})

, improving the

ε

-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an

ε

-KKT point within

\mathcal{O}(1+\log\log(e/ε))

stages while maintaining the leading-order complexity. Numerical tests on QCQPs, black-box adversarial attacks, and fairness-constrained classification demonstrate the effectiveness of our proposed method.

Qiankun Shi, Han Yuan, Xiao Wang +1

Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1

Zeroth-Order Optimization Augmented Lagrangian Method Mirror Descent Constrained Optimization

Ask PDF

Momentum

Related topics

Latest papers 14