Skip to content

Add subgradient (augmented-Lagrangian) penalty update strategy #233

Description

@bernalde

Motivation

The iterative penalty-refinement engine (JuliaQUBO/QUBO.jl#67, design record in this comment) ships with multiplicative escalation for MQT QAO parity. Multiplicative escalation needs ρ→∞ for feasibility and collides with sampler coefficient dynamic-range limits within a few ×10 steps (Ohzeki, Sci. Rep. 10:3126, 2020, names this explicitly). The method of multipliers converges with bounded ρ (Powell's shifted-penalty view; Bertsekas 1982: linear rate at fixed finite ρ), and Yonaga–Miyama–Ohzeki (arXiv:2012.06119) run exactly this iteration on a D-Wave annealer with fixed ρ = 0.1, tracking best-feasible and best-energy samples separately.

Proposed change

Building on the engine from #67's PR A:

  • Attributes.AugmentedLagrangianPenalty{T} <: ConstraintPenaltyMethod with multiplier::T (λ, any sign, default 0) and rho::T (> 0): emits λ·ℓ + ρ·ℓ² for equalities and the sign-oriented composite for LessThan/GreaterThan, reusing _unbalanced_penalty's emission (src/compiler/constraints.jl:61-71) but lifting UnbalancedPenalty's strictly-positive-coefficients and inequality-only restrictions. Document as iterated unbalanced penalization for inequalities (the Rockafellar one-sided AL term is not QUBO-expressible slack-free).
  • SubgradientUpdate strategy for Attributes.PenaltyUpdateStrategy: per iteration, from the best sample's signed residuals (_constraint_measurements; EqualTo residual is signed, inequalities positive-when-violated): equality λ ← λ + η·r; inequality λ ← max(0, λ + η·r); default step η = ρ (classical MoM). Safeguard: escalate ρ ×τ only when ‖r_k‖ > γ·‖r_{k−1}‖ (Bertsekas γ ≈ 0.25, BCL-style), so escalations stay rare and coefficients bounded.
  • MAX-sense handling via the compiler's σ convention (multipliers live in the minimization frame; tests must cover a MAX model).
  • Interval constraints: the measured residual loses violation direction (feasibility.jl:357-367) — either split handling or document exclusion.

Acceptance criteria

  • An under-penalized equality-constrained model reaches feasibility via multiplier updates with ρ held fixed (no escalation), within the iteration budget.
  • An inequality model converges with one-sided updates; multipliers never go negative.
  • A MAX-sense model converges with correct signs.
  • Safeguarded ρ escalation triggers only on stalled residuals (unit test on the trigger condition).
  • Multipliers and iteration count queryable post-solve; docs section with the references above.

Part of the MQT QAO parity epic: JuliaQUBO/QUBO.jl#69 (extends beyond parity — this strategy has no MQT equivalent).

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions