The Karush–Kuhn–Tucker conditions are the central result of convex optimization: for a convex differentiable problem satisfying Slater's condition, a point is optimal exactly when primal feasibility, dual feasibility, complementary slackness and Lagrangian stationarity hold. This mission formalizes Chapters 4–5 of Boyd & Vandenberghe end to end — the first-order optimality criterion, concavity of the Lagrange dual, weak duality, Slater's strong-duality theorem with dual attainment (via the separating-hyperplane argument of §5.3.2), the saddle-point characterization, sensitivity bounds and Pareto scalarization — culminating in the full KKT characterization.
theorem ConvexOptimization.kkt_iff_optimal_slater {n mm p : ℕ}
(f₀ : EuclideanSpace ℝ (Fin n) → ℝ) (hf₀ : ConvexOn ℝ Set.univ f₀)
(fc : Fin mm → EuclideanSpace ℝ (Fin n) → ℝ)
(hfc : ∀ i, ConvexOn ℝ Set.univ (fc i))
(a : Fin p → EuclideanSpace ℝ (Fin n)) (ha : LinearIndependent ℝ a)
(b : Fin p → ℝ)
(f₀' : EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hf₀' : ∀ x, HasGradientAt f₀ (f₀' x) x)
(fc' : Fin mm → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hfc' : ∀ i x, HasGradientAt (fc i) (fc' i x) x)
(xsl : EuclideanSpace ℝ (Fin n)) (hxsl_ineq : ∀ i, fc i xsl < 0)
(hxsl_eq : ∀ j, ⟪a j, xsl⟫ = b j)
(xs : EuclideanSpace ℝ (Fin n)) :
(xs ∈ feasibleSet fc a b ∧ IsMinOn f₀ (feasibleSet fc a b) xs) ↔
∃ (lam : Fin mm → ℝ) (nu : Fin p → ℝ),
IsKKTPoint fc a b f₀' fc' xs lam nu := by
sorry
The KKT conditions characterize optimality for convex problems satisfying Slater's condition — the goal of this mission.
Consider the standard problem on ,
and assume: and every are convex and differentiable, with gradient fields , ; the vectors are linearly independent; and Slater's condition holds — some satisfies for all and for all . Then for any point ,
where being a KKT point means , , , and .
This is the theorem that makes the KKT system the working definition of optimality in convex optimization: the conditions are not merely necessary, and not merely sufficient, but an exact characterization. Sufficiency holds for any convex problem; necessity is where Slater's condition is used, via strong duality with attained dual optimum. Almost every algorithm and every hand derivation in the field is an attempt to solve this system.
Formalization Note The right-hand side uses the mission's IsKKTPoint predicate; optimality is IsMinOn f₀ (feasibleSet fc a b) x⋆ and convexity is asserted on Set.univ, matching the total-function form of the problem. Slater's point and the independence of the a j appear as explicit hypotheses of the whole iff, so both directions are stated under them even though sufficiency does not need them. Source: B&V §5.5.3, p. 244, conditions (5.49).
No open leaves. Every sub-goal is proved or awaiting decomposition.