Fact 8.7.1 — first-order optimality criterion for a convex function on a convex set
ProvedMatousekLP.SmallestBall.first_order_optimalityconvex-programmingoptimality-conditionsp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a convex set and a differentiable convex function, and let . Write for the gradient of at , viewed as a row vector, so that is its scalar product with . Then minimizes over , that is, for all , if and only if
This is the variational inequality characterizing minimizers of a convex differentiable function over a convex set. It is the bridge from convex programming to linear programming used in the proof of the Karush–Kuhn–Tucker conditions (Proposition 8.7.2).
Formalization Note is the Fréchet derivative of at applied to . The book's phrase "a vector minimizes over " includes ; this membership is a hypothesis.
Preamble
import Mathlib
Formal statement
namespace MatousekLP.SmallestBall
/-- Fact 8.7.1 (Matoušek & Gärtner, p. 186). Let `C ⊆ ℝⁿ` be convex and `f : ℝⁿ → ℝ`
differentiable and convex, and let `x* ∈ C`. Then `x*` minimizes `f` over `C` if and only if
`∇f(x*)(x − x*) ≥ 0` for all `x ∈ C`; here `∇f(x*)(x − x*)` is the derivative of `f` at `x*`
applied to `x − x*`. -/
theorem first_order_optimality {n : ℕ} (C : Set (Fin n → ℝ)) (hC : Convex ℝ C)
(f : (Fin n → ℝ) → ℝ) (hf : Differentiable ℝ f) (hfc : ConvexOn ℝ Set.univ f)
(xstar : Fin n → ℝ) (hxstar : xstar ∈ C) :
IsMinOn f C xstar ↔ ∀ x ∈ C, 0 ≤ fderiv ℝ f xstar (x - xstar) := by sorry
end MatousekLP.SmallestBall
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 186, Fact 8.7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.