Ordinary convex programs and Lagrange multipliers #
An ordinary convex program minimises f₀ over C = dom f₀ subject to finitely many convex
inequalities fᵢ x ≤ 0 and finitely many affine constraints. The main result is the existence of
Kuhn–Tucker vectors under Slater's condition: if the optimal value is not -∞ and some point of
ri C satisfies every non-affine constraint strictly, then non-negative multipliers exist for
which the infimum of the Lagrangian equals the optimal value.
The two families of constraints are kept apart by role. Those indexed by ι are the ones Slater's
condition asks a strict inequality of — the indices where fᵢ is not affine — and are
EReal-valued convex functions; those indexed by κ are affine maps E →ᵃ[ℝ] ℝ asked only for a
weak inequality. That is the split the theorem of the alternative is stated against, so the
existence theorem applies it directly and the affine-only case is ι = Empty.
Main definitions #
feasibleSet,programLagrangian,optimalValue,IsKuhnTuckerVector— the vocabulary.
Main results #
exists_isKuhnTuckerVector_of_slater— the existence theorem (Theorem 28.2 in [^1]).exists_isKuhnTuckerVector_of_mem_dom— when every constraint holds strictly somewhere inC, the Slater point need not lie inri C.exists_isKuhnTuckerVector_of_affine— with only affine constraints, a feasible point inri Csuffices.exists_multipliers_of_slater_eq— the same for affine equality constraints, whose multipliers are then of unrestricted sign.
Implementation notes #
The standing hypothesis hsub : dom f₀ ⊆ dom (f i) makes every fᵢ finite on C; that is what
turns the multiplier inequality into one between real numbers, which may be divided by the
multiplier of the objective.
References #
[^1]: R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970, §28.
The Lagrangian of an ordinary convex program at the multipliers (l, μ), namely
f₀ + λ₁f₁ + ⋯ + λ_m f_m. The perturbational Lagrangian of a bifunction is lagrangian.
Equations
Instances For
The optimal value of the program: the infimum of the objective over the feasible set.
Equations
- Tdaf.ConvexAnalysis.optimalValue f₀ f b = ⨅ x ∈ Tdaf.ConvexAnalysis.feasibleSet f b, f₀ x
Instances For
(l, μ) is a vector of Kuhn–Tucker coefficients: the multipliers are non-negative, and the
infimum of the Lagrangian is finite and equal to the optimal value. This is the direct definition,
not the equivalent perturbational inequality p u + ⟨λ, u⟩ ≥ p 0.
The multipliers of the convex constraints are non-negative.
The multipliers of the affine inequality constraints are non-negative.
The infimum of the Lagrangian is not
-∞.The infimum of the Lagrangian is not
+∞.The infimum of the Lagrangian is the optimal value in the program.
Instances For
A non-negatively weighted sum of strictly negative values with one non-zero weight is strictly negative; this rules out a vanishing multiplier on the objective.
On the feasible set every constraint term is non-positive, so L ≤ f₀.
Off dom f₀ the Lagrangian is +∞: no constraint term can be -∞, since the fᵢ never take
-∞ and the multipliers are non-negative.
The Lagrangian where objective and constraints are all finite, as a single real number.
Existence of Kuhn–Tucker coefficients under Slater's condition. If the optimal value is
not -∞ and the program has a feasible solution in ri C, C = dom f₀, satisfying strictly
every constraint of the first family, then a vector of Kuhn–Tucker coefficients exists.
With only affine constraints a feasible solution in ri C suffices: the existence theorem
with an empty family of strict constraints.
When every constraint holds strictly at some point of C, that point need not lie in
ri C: prolonging it towards a relative interior point produces a Slater point.
The book states this for a program with no affine constraints; affine constraints are allowed here,
at the price of asking strict inequality of them too, which is what survives the prolongation. The
hypothesis hri is what following fᵢ along the segment needs.
The same for a program whose affine constraints are equations. Their multipliers are then of
unrestricted sign, obtained as μ' - μ'' from the two inequalities each equation splits into.