Convex Optimization 2026, 14 - The Lagrange Dual Function

The optimization problem in standard form with nonempty domain 𝔻 = ⋒_i=0^m dom f_i ∩ ⋒_i=1^p dom h_i and optimal value p* is not assumed to be convex beforehand. Lagrangian duality takes the problem's constraints into account by augmenting the objective function with a weighted sum of the constraint functions. Define the Lagrangian as

with dom L = 𝔻 × ℝ^m × ℝ^p. As usual, λ_i is a Lagrange multiplier (5.1.1). The Lagrange dual function is the minimum value of the Lagrangian over x. Given an unbounded Lagrangian, this dual function is -∞. As the dual function is the pointwise infimum of a family of affine functions, it's concave, even if the original problem is not convex (5.1.2). For λ ⪰ 0 and some ν, g(λ, ν) ≤ p^☆ (5.1.3).

The Lagrangian dual function is closely related to the conjugate function. An optimization problem minimizing f₀(x) subject to Ax ⪯ b; Cx = d can express g(λ, ν) through f₀: g(λ, ν) = inf_x (f₀(x) + λ^T(Ax - b) + ν^T(Cx - d)) (Eq. 5.11), so the domain of g can be expressed through that of f₀^*: dom g = {(λ, ν) : - A^Tλ - C^Tν ∈ dom f₀^*} (5.1.6.0).