Used in

ALADIN theory

Augmented Lagrangian Alternating Direction Inexact Newton method

Foundation

Definition

ALADIN (Augmented Lagrangian Alternating Direction Inexact Newton) is a distributed optimization algorithm developed by Houska, Frasch, and Diehl in 2016 as an evolution of ADMM specifically designed for non-convex problems. It combines ADMM’s decomposability — local subproblems solved in parallel by each agent — with a centralized coordination step that exploits local Hessian and gradient information through an inexact Newton update. The result is fast convergence on non-convex problems like AC OPF, where ADMM alone offers no theoretical guarantees and often stalls in practice. ALADIN is the next-generation distributed solver scheduled for inclusion in Lirion.

Why a successor to ADMM was needed

ADMM has well-established convergence guarantees for convex problems: any ρ > 0 leads to convergence in primal residuals, dual residuals, and objective value. For non-convex problems — AC OPF being the canonical example in power systems — these guarantees evaporate. ADMM may converge to a local minimum, oscillate indefinitely, or get stuck at a saddle point of the augmented Lagrangian.

Three practical issues with ADMM on non-convex problems:

  1. Sensitivity to ρ: the penalty parameter that controls convergence speed for convex problems can completely determine which local optimum ADMM finds on non-convex ones. Different ρ values yield different “solutions.”
  2. Slow asymptotic convergence: even when ADMM converges, the O(1/k) rate makes high-accuracy solutions impractical. AC OPF often requires 10−5 or tighter to certify physical feasibility.
  3. No use of curvature: ADMM is a first-order method. It ignores the Hessian information that interior-point methods exploit to achieve quadratic convergence near the optimum.

ALADIN addresses all three by introducing a centralized quadratic program at each iteration that aggregates local Hessian and gradient information from the agents. The result is a method with ADMM’s decomposability and — under mild conditions — Newton-like convergence.

The problem ALADIN solves

ALADIN targets the same separable structure as ADMM, but allows non-convex objectives and constraint sets. Each agent i has its own variable, its own objective fi (possibly non-convex), and its own local constraint set (also possibly non-convex). Agents are coupled through a shared affine constraint.

$$\begin{aligned} \min_{x_1, \ldots, x_N} \quad & \sum_{i=1}^{N} f_i(x_i) \\ \text{s.t.} \quad & \sum_{i=1}^{N} A_i x_i = b \\ & x_i \in \mathcal{X}_i, \quad i = 1, \ldots, N \end{aligned}$$

For OPF, each agent represents a geographic zone of the power network. Its fi is the local generation cost, đť’łi is the local AC power-flow feasible region (non-convex), and the coupling constraint expresses tie-line consistency between adjacent zones. The coupling constraint Σ Ai xi = b typically represents consensus on shared variables, network flow conservation, or budget constraints.

The ALADIN updates

Each ALADIN iteration has three phases: parallel local solves, centralized coordination, and a coordinated step.

Phase 1 — Parallel local steps

Each agent i solves its local augmented Lagrangian problem independently. The objective combines the local cost fi, a dual penalty for tie-line consistency, and a proximal term keeping xi close to the previous coordinated value zik. This phase is embarrassingly parallel: agents communicate nothing during their local solves.

$$x_i^{k+1} = \arg\min_{x_i \in \mathcal{X}_i}\; f_i(x_i) + \lambda^{k\,T} A_i x_i + \tfrac{1}{2} \|x_i - z_i^k\|_{\Sigma_i}^2.$$

The norm ‖·‖Σi is weighted by an agent-specific positive-definite matrix Σi. The subproblem can be solved exactly with an interior-point NLP solver (Ipopt) or inexactly with a few Newton iterations from a warm start — hence “Inexact Newton” in the algorithm’s name.

Phase 2 — Information exchange

Each agent communicates to a coordinator:

  • Its local solution xik+1
  • Its local gradient gik+1 = ∇fi(xik+1)
  • Its local Hessian Hik+1 = ∇²fi(xik+1) (or an approximation)
  • Active constraint Jacobians at xik+1

This communication is the price of faster convergence: ALADIN exchanges richer information than ADMM (which only exchanges primal values and dual prices). For OPF with moderate-sized zones, the Hessian Hi has dimension equal to the number of local variables — typically manageable.

Phase 3 — Coordinated quadratic program

The coordinator solves a centralized convex quadratic program (QP) that aggregates the agents’ information. The variables Δxi are corrections to each agent’s local solution, and s is a slack on the coupling constraint penalized by μ. The QP minimizes a second-order model of the global objective subject to a softened coupling constraint.

$$\begin{aligned} \min_{\Delta x,\, s} \quad & \sum_{i} \left( \tfrac{1}{2} \Delta x_i^T H_i^{k+1} \Delta x_i + g_i^{k+1\,T} \Delta x_i \right) + \tfrac{\mu}{2} \|s\|_2^2 \\ \text{s.t.} \quad & \sum_{i} A_i (x_i^{k+1} + \Delta x_i) = b + s \end{aligned}$$

The coordinator broadcasts Δxi back to each agent, who steps to zik+1 = xik+1 + αΔxi with a step size α chosen by line search or a fixed strategy. The dual variable λ is updated from the QP’s multiplier on the coupling constraint.

Convergence properties

ALADIN’s convergence guarantees are stronger than ADMM’s for non-convex problems:

  • Local quadratic convergence: near a KKT point satisfying second-order sufficiency, ALADIN converges at the rate of Newton’s method. The number of correct digits doubles each iteration in the asymptotic regime.
  • Global convergence: with appropriate line search and updates of the proximal weights Σi, ALADIN converges to a KKT point from any starting iterate satisfying local feasibility conditions.
  • Robustness to non-convexity: unlike ADMM, ALADIN’s coordinated QP step is always convex (the QP itself is convex by construction), making the algorithm’s behavior predictable even on highly non-convex problems.

The price for these guarantees is computational: each ALADIN iteration is more expensive than an ADMM iteration. The centralized QP grows with the network’s coupling structure, and the Hessian communication consumes bandwidth. For OPF, the breakeven point is typically around 100–1000 buses per zone: smaller zones favor ADMM, larger zones favor ALADIN.

When to choose ALADIN over ADMM

A practical heuristic for distributed OPF:

  • Use ADMM when the problem is convex (DC OPF, SOCWR, SOCBF) or near-convex (LPAC), when zones are small and numerous (hundreds of agents), or when communication bandwidth is limited.
  • Use ALADIN when the problem is non-convex (AC OPF, ACR, IVR), when zones are large and few (a handful of TSOs coordinating across borders), or when high-accuracy solutions are required.
  • Hybrid approaches exist: warm-start ALADIN from an ADMM solution to combine ADMM’s robust early progress with ALADIN’s fast asymptotic convergence.

Key comparison axes between ADMM and ALADIN:

  • Convergence rate (convex): ADMM O(1/k) vs. ALADIN locally superlinear
  • Convergence rate (non-convex): ADMM no guarantee vs. ALADIN locally quadratic
  • Per-iteration cost: ADMM low (local solves only) vs. ALADIN higher (QP + local solves)
  • Communication per iteration: ADMM primal + dual vs. ALADIN primal + dual + gradient + Hessian
  • Sensitivity to penalty parameter: ADMM high vs. ALADIN lower (replaced by line search)

Implementation in Lirion

ALADIN is on Lirion’s roadmap but not yet implemented. The current distributed module supports ADMM for DC, AC, and SOCWR formulations; ALADIN will be added with a similar interface, allowing direct comparison on the same problem with the same partitioning. The implementation will use Ipopt for local non-convex subproblems and OSQP for the centralized QP, with Hessian information extracted from Ipopt’s KKT system at the local solution.

Research questions Lirion’s ALADIN implementation aims to address:

  • How does the choice of proximal weight Σi affect convergence on heterogeneous networks (mixing transmission and distribution zones)?
  • Can the Hessian communication be compressed without sacrificing convergence — for example, by transmitting only the dominant eigenmodes?
  • Does warm-starting ALADIN from an ADMM convergence path yield reliably better solutions than either method alone?

These are open questions, and ALADIN’s flexible mathematical structure makes Lirion a natural testbed for exploring them.

Further reading

  1. Houska, B., Frasch, J., & Diehl, M. (2016). An augmented Lagrangian based algorithm for distributed non-convex optimization. SIAM Journal on Optimization, 26(2), 1101–1127. — The original ALADIN paper.
  2. Engelmann, A., Jiang, Y., Mühlpfordt, T., Houska, B., & Faulwasser, T. (2019). Toward distributed OPF using ALADIN. IEEE Transactions on Power Systems, 34(1), 584–594. — Application to AC OPF.
  3. Engelmann, A., Jiang, Y., Houska, B., & Faulwasser, T. (2020). Decomposition of non-convex optimization via bi-level distributed ALADIN. IEEE Transactions on Control of Network Systems, 7(4), 1848–1858. — Hierarchical extensions for very large networks.
  4. Murray, A., Engelmann, A., Hagenmeyer, V., & Faulwasser, T. (2018). Hierarchical distributed mixed-integer optimization for reactive power dispatch. IFAC-PapersOnLine, 51(28), 368–373. — Discrete variables in ALADIN.
  5. Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 1–122. — Comparison baseline (ADMM).
← ADMM theory Foundations overview →