Theorem 6.11, p. 345 — Goemans–Williamson: E ζ⊤Lζ ≥ 0.878 max over {−1,1}ⁿ of x⊤Lx for ζ = sign(ξ), ξ ∼ N(0, Σ)
ProvedConvexOptAlg.GoemansWilliamson.theorem_6_11Let be a symmetric matrix of non-negative weights and its graph Laplacian, being diagonal with entries . Let be a solution of the SDP relaxation of MAXCUT,
Let and . Then is integrable and
This is the Goemans–Williamson guarantee: rounding the solution of a semidefinite program by a random Gaussian hyperplane produces, in expectation, a cut within a factor of the maximum cut, whereas a uniformly random cut only guarantees the factor .
Formalization Note "The solution" is any maximizer of the relaxation (IsSDPRelaxationOptimum); maximizers exist because the feasible set is nonempty and compact. is Mathlib's multivariateGaussian 0 Σ, defined also for singular (e.g. ). The sign is -valued with . The maximum over the hypercube is a finite maximum over the sign vectors. Integrability of the bounded integrand is part of the conclusion. The constant is the book's.
import Mathlib import Definitions.Def_ConvexOptAlg_GoemansWilliamson_Defs
namespace ConvexOptAlg.GoemansWilliamson
open MeasureTheory ProbabilityTheory Matrix
/-- **Theorem 6.11** (Goemans–Williamson; Bubeck, arXiv:1405.4980v2, §6.6, p. 345). Let
`A ∈ ℝ₊ⁿˣⁿ` be a symmetric matrix of non-negative weights and `L = D − A` its graph Laplacian.
Let `Σ` be the solution to the SDP relaxation of MAXCUT. Let `ξ ∼ N(0, Σ)` and
`ζ = sign(ξ) ∈ {−1, 1}ⁿ`. Then `E ζ⊤Lζ ≥ 0.878 max_{x ∈ {−1,1}ⁿ} x⊤Lx`.
`Σ` is any maximizer of `⟨L, X⟩` over `X ∈ S₊ⁿ` with unit diagonal; `N(0, Σ)` is Mathlib's
`multivariateGaussian 0 Σ` (well defined for singular `Σ`). The integrand is bounded and
measurable; its integrability is asserted as part of the conclusion. -/
theorem theorem_6_11 {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hsymm : A.IsSymm)
(hnonneg : ∀ i j, 0 ≤ A i j) (Sig : Matrix (Fin n) (Fin n) ℝ)
(hopt : IsSDPRelaxationOptimum (laplacian A) Sig) :
Integrable (fun ξ : EuclideanSpace ℝ (Fin n) => sgnVec ξ ⬝ᵥ laplacian A *ᵥ sgnVec ξ)
(multivariateGaussian 0 Sig) ∧
∫ ξ, sgnVec ξ ⬝ᵥ laplacian A *ᵥ sgnVec ξ ∂(multivariateGaussian 0 Sig) ≥
(0.878 : ℝ) * hypercubeMax (laplacian A) := by sorry
end ConvexOptAlg.GoemansWilliamson
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.