Necessary optimality condition: no strictly descent-feasible direction at an optimum of (3.1)
ProvedKallMayerSLP.KKT.necessary_condition_strictconvex-optimizationkkt-conditionsnonlinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-linear-programming
Throughout, and are convex and continuously differentiable, the book's standing assumptions for the program
with feasible set .
Let be an optimal solution of (3.1) and its active set. Then for every ,
This is the condition from which the regularity condition RC 0 is obtained by relaxing the strict inequalities.
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
- reading: zᵀ∇gᵢ(x̂) < 0, i ∈ I(x̂) → ∀ i ∈ activeSet g x̂, ⟪z, ∇gᵢ(x̂)⟫ < 0; reason: the sentence before it writes the same hypothesis as ∀i ∈ I(x̂)
Preamble
import Mathlib import Definitions.Def_KallMayerSLP_KKT_IsOptimal import Definitions.Def_KallMayerSLP_KKT_activeSet open scoped RealInnerProductSpace
Formal statement
namespace KallMayerSLP.KKT
/-- **Necessary condition for an optimum of (3.1), strict form.**
Kall & Mayer, *Stochastic Linear Programming* (2005), Chapter 1, §3, pp.62–63 (PDF 73–74): "For `x̂` to be a solution of (3.1) we have therefore the
(necessary) condition `zᵀ∇gᵢ(x̂) < 0, i ∈ I(x̂)` implies that `zᵀ∇f(x̂) ≥ 0`."
Here `f` and every `gᵢ` are convex on `ℝⁿ` and continuously differentiable (`ContDiff ℝ 1`), the
book's standing assumptions for (3.1) (p.61 and p.62); `x̂` is an optimal solution of (3.1) and `I(x̂)` its active set.
**Formalization Note.** "`zᵀ∇gᵢ(x̂) < 0, i ∈ I(x̂)`" is read as "for all `i ∈ I(x̂)`", as in the
sentence before it ("`z̃ᵀ∇gᵢ(x̂) < 0 ∀i ∈ I(x̂)`"); `z` ranges over all of `ℝⁿ`. -/
theorem necessary_condition_strict {n m : ℕ} (f : EuclideanSpace ℝ (Fin n) → ℝ) (g : Fin m → EuclideanSpace ℝ (Fin n) → ℝ)
(hf : ConvexOn ℝ Set.univ f) (hg : ∀ i, ConvexOn ℝ Set.univ (g i))
(hf1 : ContDiff ℝ 1 f) (hg1 : ∀ i, ContDiff ℝ 1 (g i))
(xh : EuclideanSpace ℝ (Fin n)) (hxh : IsOptimal f g xh) :
∀ z : EuclideanSpace ℝ (Fin n),
(∀ i ∈ activeSet g xh, ⟪z, gradient (g i) xh⟫ < 0) → 0 ≤ ⟪z, gradient f xh⟫ := by sorry
end KallMayerSLP.KKT
Source
Kall & Mayer, Stochastic Linear Programming: Models, Theory, and Computation (Kluwer/Springer 2005), Chapter 1, §3, pp.62–63 (PDF 73–74)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.