TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Every Lagrangian dual feasible pair is a lower-bound certificate

Statement

For the convex program and Lagrangian dual of Finite-dimensional convex program, Lagrangian dual, and Slater condition, every primal feasible $x$ and every dual feasible $(λ, ν)$ satisfy $q (λ, ν) \leq f_{0} (x) .$ Consequently, when the primal feasible set is nonempty, $d^{*} \leq p^{*}$ .

Facts & Assumptions

Given: A primal feasible point and a dual feasible multiplier pair.

[F1]

On the common domain, $L (x, λ, ν) = f_{0} (x) + λ^{T} g (x) + ν^{T} (A x - b)$ and $q (λ, ν) = \inf_{x} L (x, λ, ν)$ , with $λ \geq 0$ (Finite-dimensional convex program, Lagrangian dual, and Slater condition).

Proof

1.1givenF1algebra

Since $x$ is feasible, $A x - b = 0$ and $g_{i} (x) \leq 0$ . Since $λ_{i} \geq 0$ , this gives $L (x, λ, ν) = f_{0} (x) + \sum_{i} λ_{i} g_{i} (x) \leq f_{0} (x)$ . The infimum defining $q$ is no larger than this particular Lagrangian value, so $q (λ, ν) \leq f_{0} (x)$ .

2.1step 1.1algebra∎

The bound in step 1.1 holds for every primal feasible $x$ and every dual feasible pair. Taking the infimum over primal feasible $x$ and the supremum over dual feasible pairs gives $d^{*} \leq p^{*}$ when the primal set is nonempty.

Depends on

Finite-dimensional convex program, Lagrangian dual, and Slater condition

Used by

Dependency tree · two levels

3 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Boyd and Vandenberghe, Convex Optimization (standard reference, not scraped)
Zhiyuan Li, Convex Optimization, Lecture 5: Lagrange Multipliers and KKT (standard reference, not scraped)