Sufficiency of the KKT conditions for the barrier problems (points on the central path)
ProvedLinearOptimization.interior_point_kkt_sufficiencycentral-pathconvex-optimizationinterior-pointkkt
(Lemma 9.5, p. 421) If , , and satisfy conditions (9.17) [, , , , for a given ], then they are optimal solutions to problems (9.15) and (9.16), i.e., , , :
for every with (with equality iff , so is the unique minimizer), and symmetrically is optimal for the dual barrier problem (9.16).
Preamble
import Definitions.Def_LinearOptimization_LogBarrier_CentralPath open Matrix /-- **Bertsimas & Tsitsiklis, Lemma 9.5 (p. 421).** KKT sufficiency for the barrier problems: a solution `(x*, p*, s*)` of (9.17) at `μ > 0` has `x*` as the unique minimizer of `B_μ` over the interior primal feasible set, and `(p*, s*)` as a maximizer of the dual barrier objective over the interior dual feasible set. -/
Formal statement
theorem LinearOptimization.interior_point_kkt_sufficiency {m n : ℕ}
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(mu : ℝ) (hmu : 0 < mu)
(xstar : Fin n → ℝ) (pstar : Fin m → ℝ) (sstar : Fin n → ℝ)
(hkkt : IsCentralPathPoint A b c mu xstar pstar sstar) :
(∀ x : Fin n → ℝ, A.mulVec x = b → (∀ j, 0 < x j) →
logBarrier c mu xstar ≤ logBarrier c mu x ∧
(logBarrier c mu x = logBarrier c mu xstar → x = xstar)) ∧
(∀ (p : Fin m → ℝ) (s : Fin n → ℝ), Aᵀ.mulVec p + s = c →
(∀ j, 0 < s j) →
dualLogBarrier b mu p s ≤ dualLogBarrier b mu pstar sstar) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Lemma 9.5, p. 421