Theorem 9.33 — the semidefinite relaxation approximates the range of the quadratic program within
ProvedYeIPA.QPApprox.sdp_range_approximates_qpLet be a symmetric matrix, with rows , , , and assume the quadratic program
is feasible. Let be its semidefinite relaxation, and set , (the maximum of the QP), , . Then 1.
The range of the convex relaxation, computable by interior-point methods, thus approximates the range of the nonconvex QP within constant factors, for quadratic equality constraints and box bounds, and with no sign or definiteness assumption on .
Formalization Note The standing assumptions of §9.5 (p. 325), symmetric and the QP feasible, are the only hypotheses. No positive definite feasible point of the relaxation and no attainment of the dual (9.49) is assumed: the printed proof uses both (finding F3), but the statement holds without them. and are real infima of nonempty compact sets of values, hence attained.
import Mathlib import Definitions.Def_YeIPA_QPApprox_Relaxation open Matrix MeasureTheory
namespace YeIPA.QPApprox
variable {m n : ℕ}
/-- **Theorem 9.33** (Ye, *Interior Point Algorithms*, Wiley 1997, pp. 329–330).
With `q̲ = q̲(Q)`, `q̄ = −q̲(−Q)`, `p̲ = p̲(Q)`, `p̄ = −p̲(−Q)`:
i) `p̄ − q̲ ≥ (2/π)(p̄ − p̲)`;
ii) `q̄ − p̲ ≥ (2/π)(p̄ − p̲)`;
iii) `p̄ − p̲ ≥ q̄ − q̲ ≥ ((4 − π)/π)(p̄ − p̲)`.
Standing assumptions of §9.5 (p. 325): `Q` symmetric, the QP feasible. -/
theorem sdp_range_approximates_qp (Q : Matrix (Fin n) (Fin n) ℝ) (hQ : Q.IsSymm)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (hfeas : ∃ x, IsQPFeasible A b x) :
-- (i)
sdpMax Q A b - qpMin Q A b ≥ (2 / Real.pi) * (sdpMax Q A b - sdpMin Q A b) ∧
-- (ii)
qpMax Q A b - sdpMin Q A b ≥ (2 / Real.pi) * (sdpMax Q A b - sdpMin Q A b) ∧
-- (iii)
sdpMax Q A b - sdpMin Q A b ≥ qpMax Q A b - qpMin Q A b ∧
qpMax Q A b - qpMin Q A b ≥ ((4 - Real.pi) / Real.pi) * (sdpMax Q A b - sdpMin Q A b) := by sorry
end YeIPA.QPApprox
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix a natural number (the number of rows) and a natural number (the number of variables). Both are implicit and may be . The statement takes the following data:
- , an real matrix indexed by , with the hypothesis that is symmetric ();
- , an real matrix;
- ;
- a hypothesis that some vector satisfies .
The statement uses five names that come from the imported module Definitions.Def_YeIPA_QPApprox_Relaxation, whose code is not shown here: , , , and . This read-back therefore cannot expand them. It can only record how the statement uses them. is some predicate on , and a vector , whose type is fixed by that definition. Each of the other four takes and returns a real number, because each is subtracted from the others and multiplied by real constants. Write
Under these hypotheses, the statement asserts that all four of the following inequalities hold together:
Here is the real constant . All inequalities are non-strict, and none of the four is weakened by any other. Apart from symmetry of and existence of one feasible , the statement assumes nothing. In particular it makes no assumption that or makes the feasible set bounded, and no assumption that is nonzero or has any definiteness property.
The statement places no further restriction on and . When , and are empty. Whether then holds for every , or for none, depends on the hidden definition. When , is the empty matrix, which is trivially symmetric, and ranges over whatever type fixes. Every conclusion is then about whatever real values the four functions return on that empty data. If those values are all equal, every difference is and all four inequalities read . The feasibility hypothesis is the only nontrivial hypothesis. If no satisfies , the theorem is vacuous for that . Whether are true extrema depends on the hidden definitions. If they are defined as real infima or suprema, Lean returns the default value for an empty set, a set unbounded in the relevant direction, or an infimum or supremum that is not attained. The other possibility is that they are defined through some other total construction with its own default. In that case the statement asserts the four inequalities about those default numbers, not about genuine optimal values. This can happen, for example, when the quadratic objective is unbounded on an unbounded feasible set.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.