Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 9.33 — the semidefinite relaxation approximates the range of the quadratic program within 2/π2/\pi2/π

Proved
YeIPA.QPApprox.sdp_range_approximates_qp

by Shuze Chen · Oct 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsquadratic-programmingsemidefinite-programming

Let QQQ be a symmetric n×nn\times nn×n matrix, A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n with rows aia_iai​, Ai=diag⁡(ai)A_i=\operatorname{diag}(a_i)Ai​=diag(ai​), b∈Rmb\in\mathbb R^mb∈Rm, and assume the quadratic program

q‾(Q)=min⁡ xTQxs.t.∑j=1naijxj2=bi (i=1,…,m),−e≤x≤e\underline q(Q)=\min\ x^TQx\quad\text{s.t.}\quad \textstyle\sum_{j=1}^na_{ij}x_j^2=b_i\ (i=1,\dots,m),\quad -e\le x\le eq​(Q)=min xTQxs.t.∑j=1n​aij​xj2​=bi​ (i=1,…,m),−e≤x≤e

is feasible. Let p‾(Q)=min⁡{Q∙X: Ai∙X=bi (i=1,…,m), d(X)≤e, X⪰0}\underline p(Q)=\min\{Q\bullet X:\ A_i\bullet X=b_i\ (i=1,\dots,m),\ d(X)\le e,\ X\succeq0\}p​(Q)=min{Q∙X: Ai​∙X=bi​ (i=1,…,m), d(X)≤e, X⪰0} be its semidefinite relaxation, and set q‾=q‾(Q)\underline q=\underline q(Q)q​=q​(Q), qˉ=−q‾(−Q)\bar q=-\underline q(-Q)qˉ​=−q​(−Q) (the maximum of the QP), p‾=p‾(Q)\underline p=\underline p(Q)p​=p​(Q), pˉ=−p‾(−Q)\bar p=-\underline p(-Q)pˉ​=−p​(−Q). Then 1.

pˉ−q‾ ≥ 2π (pˉ−p‾);\bar p-\underline q\ \ge\ \tfrac2\pi\,(\bar p-\underline p);pˉ​−q​ ≥ π2​(pˉ​−p​);
qˉ−p‾ ≥ 2π (pˉ−p‾);\bar q-\underline p\ \ge\ \tfrac2\pi\,(\bar p-\underline p);qˉ​−p​ ≥ π2​(pˉ​−p​);
pˉ−p‾ ≥ qˉ−q‾ ≥ 4−ππ (pˉ−p‾).\bar p-\underline p\ \ge\ \bar q-\underline q\ \ge\ \tfrac{4-\pi}{\pi}\,(\bar p-\underline p).pˉ​−p​ ≥ qˉ​−q​ ≥ π4−π​(pˉ​−p​).

The range [p‾,pˉ][\underline p,\bar p][p​,pˉ​] of the convex relaxation, computable by interior-point methods, thus approximates the range [q‾,qˉ][\underline q,\bar q][q​,qˉ​] of the nonconvex QP within constant factors, for quadratic equality constraints and box bounds, and with no sign or definiteness assumption on QQQ.

Formalization Note The standing assumptions of §9.5 (p. 325), QQQ 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. q‾\underline qq​ and p‾\underline pp​ are real infima of nonempty compact sets of values, hence attained.

Preamble
import Mathlib
import Definitions.Def_YeIPA_QPApprox_Relaxation

open Matrix MeasureTheory
Formal statement
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
Source
Ye, Interior Point Algorithms: Theory and Analysis, Wiley 1997, pp. 329–330, Theorem 9.33
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix a natural number mmm (the number of rows) and a natural number nnn (the number of variables). Both are implicit and may be 000. The statement takes the following data:

  • QQQ, an n×nn \times nn×n real matrix indexed by {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1}, with the hypothesis that QQQ is symmetric (Q⊤=QQ^\top = QQ⊤=Q);
  • AAA, an m×nm \times nm×n real matrix;
  • b∈Rmb \in \mathbb{R}^mb∈Rm;
  • a hypothesis that some vector xxx satisfies IsQPFeasible(A,b,x)\mathrm{IsQPFeasible}(A,b,x)IsQPFeasible(A,b,x).

The statement uses five names that come from the imported module Definitions.Def_YeIPA_QPApprox_Relaxation, whose code is not shown here: IsQPFeasible\mathrm{IsQPFeasible}IsQPFeasible, qpMin\mathrm{qpMin}qpMin, qpMax\mathrm{qpMax}qpMax, sdpMin\mathrm{sdpMin}sdpMin and sdpMax\mathrm{sdpMax}sdpMax. This read-back therefore cannot expand them. It can only record how the statement uses them. IsQPFeasible(A,b,x)\mathrm{IsQPFeasible}(A,b,x)IsQPFeasible(A,b,x) is some predicate on AAA, bbb and a vector xxx, whose type is fixed by that definition. Each of the other four takes (Q,A,b)(Q,A,b)(Q,A,b) and returns a real number, because each is subtracted from the others and multiplied by real constants. Write

q‾=qpMin(Q,A,b),q‾=qpMax(Q,A,b),p‾=sdpMin(Q,A,b),p‾=sdpMax(Q,A,b).\underline{q} = \mathrm{qpMin}(Q,A,b),\quad \overline{q} = \mathrm{qpMax}(Q,A,b),\quad \underline{p} = \mathrm{sdpMin}(Q,A,b),\quad \overline{p} = \mathrm{sdpMax}(Q,A,b).q​=qpMin(Q,A,b),q​=qpMax(Q,A,b),p​=sdpMin(Q,A,b),p​=sdpMax(Q,A,b).

Under these hypotheses, the statement asserts that all four of the following inequalities hold together:

(i)p‾−q‾  ≥  2π (p‾−p‾),\text{(i)}\quad \overline{p} - \underline{q} \;\ge\; \frac{2}{\pi}\,\bigl(\overline{p} - \underline{p}\bigr),(i)p​−q​≥π2​(p​−p​), (ii)q‾−p‾  ≥  2π (p‾−p‾),\text{(ii)}\quad \overline{q} - \underline{p} \;\ge\; \frac{2}{\pi}\,\bigl(\overline{p} - \underline{p}\bigr),(ii)q​−p​≥π2​(p​−p​), (iii-a)p‾−p‾  ≥  q‾−q‾,(iii-b)q‾−q‾  ≥  4−ππ (p‾−p‾).\text{(iii-a)}\quad \overline{p} - \underline{p} \;\ge\; \overline{q} - \underline{q}, \qquad \text{(iii-b)}\quad \overline{q} - \underline{q} \;\ge\; \frac{4-\pi}{\pi}\,\bigl(\overline{p} - \underline{p}\bigr).(iii-a)p​−p​≥q​−q​,(iii-b)q​−q​≥π4−π​(p​−p​).

Here π\piπ is the real constant π\piπ. All inequalities are non-strict, and none of the four is weakened by any other. Apart from symmetry of QQQ and existence of one feasible xxx, the statement assumes nothing. In particular it makes no assumption that AAA or bbb makes the feasible set bounded, and no assumption that QQQ is nonzero or has any definiteness property.

The statement places no further restriction on mmm and nnn. When m=0m = 0m=0, AAA and bbb are empty. Whether IsQPFeasible\mathrm{IsQPFeasible}IsQPFeasible then holds for every xxx, or for none, depends on the hidden definition. When n=0n = 0n=0, QQQ is the empty matrix, which is trivially symmetric, and xxx ranges over whatever type IsQPFeasible\mathrm{IsQPFeasible}IsQPFeasible 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 000 and all four inequalities read 0≥00 \ge 00≥0. The feasibility hypothesis is the only nontrivial hypothesis. If no xxx satisfies IsQPFeasible(A,b,x)\mathrm{IsQPFeasible}(A,b,x)IsQPFeasible(A,b,x), the theorem is vacuous for that (A,b)(A,b)(A,b). Whether q‾,q‾,p‾,p‾\underline{q}, \overline{q}, \underline{p}, \overline{p}q​,q​,p​,p​ are true extrema depends on the hidden definitions. If they are defined as real infima or suprema, Lean returns the default value 000 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.

Human review
  • Endorsed by Community (Bot) · Oct 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 20, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me