Global Lagrange duality under strict feasibility
ProvedVectorSpaceOpt.lagrange_dualityconvex-programminglagrange-dualityslater-conditionstrong-duality
Let be convex and cone-convex on nonempty in real normed spaces. Let be a convex cone with nonempty interior, and assume a Slater point satisfies . If the finite number is the infimum of over , then some dual-positive attains
If attains the primal value, then and minimizes on . The root adds neither closedness nor pointedness of and retains dual attainment and complementarity. Its conclusion remains useful even when existence of a primal optimizer is not known.
Preamble
import Definitions.Def_VectorSpaceOpt_coneLE import Definitions.Def_VectorSpaceOpt_dualPositive import Definitions.Def_VectorSpaceOpt_coneConvexOn import Definitions.Def_VectorSpaceOpt_lagrangian import Definitions.Def_VectorSpaceOpt_lagrangeDualValue
Formal statement
namespace VectorSpaceOpt
/-- Luenberger, Chapter 8, §8.6, Theorem 1 (Lagrange Duality). -/
theorem lagrange_duality
{X Z : Type*}
[NormedAddCommGroup X] [NormedSpace ℝ X]
[NormedAddCommGroup Z] [NormedSpace ℝ Z]
(P : ConvexCone ℝ Z) (Ω : Set X) (f : X → ℝ) (G : X → Z) (μ : ℝ)
(hΩ : Ω.Nonempty) (hf : ConvexOn ℝ Ω f)
(hG : ConeConvexOn P Ω G)
(hPint : (interior (P : Set Z)).Nonempty)
(hslater : ∃ x ∈ Ω, -G x ∈ interior (P : Set Z))
(hμ : IsGLB
(f '' {x : X | x ∈ Ω ∧ coneLE P (G x) 0}) μ) :
∃ zstar₀ : Z →L[ℝ] ℝ,
dualPositive P zstar₀ ∧
lagrangeDualValue Ω f G zstar₀ = (μ : EReal) ∧
(∀ zstar : Z →L[ℝ] ℝ, dualPositive P zstar →
lagrangeDualValue Ω f G zstar ≤
lagrangeDualValue Ω f G zstar₀) ∧
(∀ x₀ ∈ Ω, coneLE P (G x₀) 0 → f x₀ = μ →
zstar₀ (G x₀) = 0 ∧
∀ x ∈ Ω,
lagrangian f G zstar₀ x₀ ≤ lagrangian f G zstar₀ x) := by sorry
end VectorSpaceOptSource
David G. Luenberger, Optimization by Vector Space Methods, Wiley, 1969, public scan https://sites.science.oregonstate.edu/~show/old/142_Luenberger.pdf, Chapter 8, §8.6, Theorem 1 (Lagrange Duality), printed pp. 224–225; physical PDF pp. 244–245. Equivalent multiplier conclusion also appears in §8.3, Theorem 1, printed pp. 217–218.