Eliminated Newton solves the constrained KKT system
ProvedConvexOptimization.newton_elimination_equivalenceNewton's method commutes with elimination of equality constraints (B&V §10.2.3): the Newton step of the reduced problem, mapped back, solves the KKT system of the constrained problem.
Consider minimizing a twice differentiable subject to the affine constraints , . Let be linear and parametrize the constraint null space,
let be arbitrary, put , and let solve the reduced Newton system of , stated variationally as for every . Then solves the equality-constrained Newton KKT system (10.12):
where is the vector of dual variables associated with the equality constraints.
The two natural ways of running Newton's method on an equality-constrained problem — eliminate the constraints and run the unconstrained method, or keep them and solve the larger KKT system — therefore produce the same step. That is what allows the convergence theory of the unconstrained case to be transferred verbatim to the constrained one, and it makes the choice between the two implementations a purely numerical matter.
Formalization Note is a continuous linear map EuclideanSpace ℝ (Fin q) →L[ℝ] EuclideanSpace ℝ (Fin n) and the null-space property is an iff between the constraint equations and membership in Set.range F. The reduced Newton system is given in the weak form quantified over test vectors , which is equivalent to without introducing adjoints. The conclusion asserts existence of the multiplier , matching the KKT system rather than a particular formula for it. Source: B&V §10.2.3, pp. 526–527.
import Mathlib open scoped RealInnerProductSpace ENNReal open MeasureTheory
theorem ConvexOptimization.newton_elimination_equivalence {n q p : ℕ}
(f : EuclideanSpace ℝ (Fin n) → ℝ)
(g : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hg : ∀ x, HasGradientAt f (g x) x)
(H : EuclideanSpace ℝ (Fin n) →
EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
(hH : ∀ x, HasFDerivAt g (H x) x)
(a : Fin p → EuclideanSpace ℝ (Fin n))
(F : EuclideanSpace ℝ (Fin q) →L[ℝ] EuclideanSpace ℝ (Fin n))
-- F parametrizes the constraint null space: ran F = {v | Av = 0}
(hF : ∀ v : EuclideanSpace ℝ (Fin n),
(∀ j, ⟪a j, v⟫ = 0) ↔ v ∈ Set.range F)
(xhat : EuclideanSpace ℝ (Fin n)) (z : EuclideanSpace ℝ (Fin q))
(Δz : EuclideanSpace ℝ (Fin q))
-- Δz solves the reduced Newton system Fᵀ H F Δz = −Fᵀ g at x = F z + x̂:
(hΔz : ∀ w : EuclideanSpace ℝ (Fin q),
⟪H (F z + xhat) (F Δz), F w⟫ = -⟪g (F z + xhat), F w⟫) :
-- then Δx = F Δz solves the KKT system (10.12): stationarity with some ν,
-- and primal feasibility of the step direction (A Δx = 0):
(∃ ν : Fin p → ℝ,
g (F z + xhat) + H (F z + xhat) (F Δz) + ∑ j, ν j • a j = 0) ∧
∀ j, ⟪a j, F Δz⟫ = 0 := by
sorry