Remark 3.1 — linear constraints always satisfy RC 0
ProvedKallMayerSLP.KKT.remark_3_1_linearconvex-optimizationkkt-conditionsnonlinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-linear-programming
Let be convex and continuously differentiable, and let all constraints of (3.1) be linear,
with , . Then the program (3.1) satisfies the regularity condition RC 0.
So for linear constraints no further constraint qualification is needed for the KKT conditions.
Differences from the source:
- encoding: ℝⁿ with zᵀv → EuclideanSpace ℝ (Fin n) with the inner product ⟪z, v⟫ and Mathlib's gradient; reason: Lean convention; the same space and the same gradient for differentiable functions
Preamble
import Mathlib import Definitions.Def_KallMayerSLP_KKT_RC0 open scoped RealInnerProductSpace
Formal statement
namespace KallMayerSLP.KKT
/-- **Remark 3.1 (first part): linear constraints satisfy `RC 0`.**
Kall & Mayer, *Stochastic Linear Programming* (2005), Chapter 1, Remark 3.1, p.63 (PDF 74): "Observe that for linear constraints the regularity condition is
always satisfied: Having `gᵢ(x̂) = bᵢ − a⁽ⁱ⁾ᵀx̂ = 0 ∀i ∈ I(x̂)` implies … `RC 0` is satisfied."
Here `f` is convex and continuously differentiable (standing assumptions, pp.61–62) and every
constraint is linear (affine), `gᵢ(x) = bᵢ − a⁽ⁱ⁾ᵀx`.
**Formalization Note.** `a⁽ⁱ⁾ᵀx` is `⟪a i, x⟫`; the linear constraint functions are convex and
smooth, so the standing assumptions on the `gᵢ` hold automatically. -/
theorem remark_3_1_linear {n m : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ)
(hf : ConvexOn ℝ Set.univ f) (hf1 : ContDiff ℝ 1 f)
(a : Fin m → EuclideanSpace ℝ (Fin n)) (b : Fin m → ℝ)
(g : Fin m → EuclideanSpace ℝ (Fin n) → ℝ) (hg : ∀ i x, g i x = b i - ⟪a i, x⟫) :
RC0 f g := by sorry
end KallMayerSLP.KKT
Source
Kall & Mayer, Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer 2005), Chapter 1, §3, Remark 3.1, p.63 (PDF 74)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.