Theorem 17.1 — second-order sufficient condition under linear constraints
ProvedVanderbeiLP.CentralPath.second_order_sufficientConsider the equality-constrained problem "maximize subject to , " over , where the constraints are linear: for vectors and scalars , so that . Let be a point at which is twice differentiable. Suppose is a critical point in the sense of (17.3): there are Lagrange multipliers with
Write for the Hessian. If
then is a local maximum of on the feasible set : there is a neighbourhood of with for every feasible .
In the chapter this is the tool that shows the barrier problem has at most one critical point (the barrier Hessian is diagonal with negative entries).
Formalization Note The constraints are for an matrix with rows . "Twice differentiable at " is: is (Fréchet) differentiable at every point of a neighbourhood of , and its derivative is differentiable at ; the quadratic form is . The gradient condition is stated as an identity of linear functionals: for all . The local maximum is relative to the feasible set, not to all of .
import Mathlib open Matrix Filter Topology
namespace VanderbeiLP.CentralPath
/-- Theorem 17.1 (p. 261). Linear constraints `gᵢ(x) = (G x)ᵢ − βᵢ = 0`, `i = 1, …, m`; `f`
twice differentiable at `x*`. A critical point `x*` in the sense of (17.3) (feasible, and
`∇f(x*) = ∑ᵢ yᵢ ∇gᵢ(x*)` for some multipliers `y`) at which `ξᵀ H_f(x*) ξ < 0` (17.4) for every
`ξ ≠ 0` with `ξᵀ ∇gᵢ(x*) = 0` (17.5) is a local maximum of `f` on the feasible set. -/
theorem second_order_sufficient {m n : ℕ} (f : (Fin n → ℝ) → ℝ)
(G : Matrix (Fin m) (Fin n) ℝ) (β : Fin m → ℝ) (xstar : Fin n → ℝ) (y : Fin m → ℝ)
(hf : ∀ᶠ x in 𝓝 xstar, DifferentiableAt ℝ f x)
(hf2 : DifferentiableAt ℝ (fderiv ℝ f) xstar)
(hfeas : G *ᵥ xstar = β)
(hcrit : ∀ v : Fin n → ℝ, fderiv ℝ f xstar v = ∑ i, y i * (G i ⬝ᵥ v))
(hhess : ∀ ξ : Fin n → ℝ, ξ ≠ 0 → (∀ i, ξ ⬝ᵥ G i = 0) →
fderiv ℝ (fderiv ℝ f) xstar ξ ξ < 0) :
IsLocalMaxOn f {x | G *ᵥ x = β} xstar := by sorry
end VanderbeiLP.CentralPath
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.