TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generated

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.

Reduced-BFGS SQP is locally superlinear under reduced Dennis-More and inverse bounds

Statement

Let $F_{A}$ be the active KKT map defined in Full-step exact-Hessian SQP after active-set identification. Let the program be $C^{2}$ , with a correct locally identified active set, LICQ, strict complementarity, and the second-order sufficient condition. Assume the active KKT map $F_{A}$ has a locally Lipschitz Jacobian near the solution. At each nonterminal iterate let $P_{k}$ project onto $\ker A_{k}$ , where $A_{k} = D c_{A} (x_{k})$ is the Jacobian of the identified active constraints. Set $z_{k} = (x_{k}, μ_{k})$ , $F_{k} = F_{A} (z_{k})$ , $J_{k} = D F_{A} (z_{k})$ , and $s_{k} = (p_{k}, δ μ_{k})$ for the computed reduced-BFGS step. Let $H_{k}$ be the exact Lagrangian Hessian and $B_{k}$ the symmetric positive-definite model. Suppose the reduced-BFGS KKT matrices ${\tilde{J}}_{k}$ are nonsingular with $\sup_{k} ∥ {\tilde{J}}_{k}^{- 1} ∥_{2} < \infty$ , and the reduced Dennis–Moré condition holds along the computed primal steps $p_{k}$ : $\frac{∥ P_{k} (B_{k} - H_{k}) P_{k} p_{k} ∥_{2}}{∥ p_{k} ∥_{2}} ⟶ 0 whenever p_{k} \neq 0.$ Also assume the exact Newton residual ratios satisfy $∥ J_{k} s_{k} + F_{k} ∥_{2} \leq \overset{ˉ}{η} ∥ F_{k} ∥_{2}$ for every nonterminal $k$ , for some fixed $\overset{ˉ}{η} < 1$ . Then full steps of Reduced-BFGS SQP KKT step with projected Hessian error started sufficiently near the KKT pair converge superlinearly, unless an exact root is reached first. No globalization or global BFGS convergence claim is made.

Facts & Assumptions

Given: The active KKT regularity hypotheses, symmetric positive definite models, uniform inverse bound, and the reduced Dennis–Moré limit.

[F1]

Inequality constrained programs, tangent cones, constraint qualifications, and KKT defines the active KKT equations and the $g \leq 0$ multiplier convention.

[F2]

The SQP KKT matrix is nonsingular under positive reduced curvature makes the exact KKT Jacobian nonsingular under LICQ and positive reduced curvature.

[F3]

Reduced-BFGS SQP KKT step with projected Hessian error replaces only the tangent Hessian block by $H_{k} + P_{k} (B_{k} - H_{k}) P_{k}$ and solves the resulting KKT system.

[F4]

Forcing residuals determine local inexact-Newton rates gives local superlinear convergence when the Newton residual is $o (∥ F_{k} ∥_{2})$ and the exact root Jacobian is invertible with locally Lipschitz derivative.

[A1]

The program is $C^{2}$ , LICQ and strict complementarity hold at the solution, the reduced Hessian is positive on the tangent space, the active KKT map has a locally Lipschitz Jacobian, the approximate KKT inverse norms are uniformly bounded, the stated reduced Dennis–Moré ratios tend to zero, and all exact Newton residual ratios are bounded by $\overset{ˉ}{η} < 1$ .

Proof

1.1givenF1F3algebra

Set $z_{k} = (x_{k}, μ_{k})$ and $F_{k} = F (z_{k})$ for the active KKT map. The exact Jacobian $J_{k} = D F (z_{k})$ has upper-left block $H_{k}$ . By [F3], the computed step $s_{k} = (p_{k}, δ μ_{k})$ solves ${\tilde{J}}_{k} s_{k} = - F_{k}$ , where ${\tilde{J}}_{k}$ differs from $J_{k}$ only by replacing that block with $H_{k} + P_{k} (B_{k} - H_{k}) P_{k}$ . Hence the exact Newton residual is $r_{k} : = J_{k} s_{k} + F_{k} = (\binom{- P_{k} (B_{k} - H_{k}) P_{k} p_{k}}{0}) .$

2.1givenstep 1.1algebra

The inverse bound gives $∥ s_{k} ∥_{2} \leq C ∥ F_{k} ∥_{2}$ and therefore $∥ p_{k} ∥_{2} \leq C ∥ F_{k} ∥_{2}$ . The Dennis–Moré condition supplies numbers $δ_{k} \to 0$ with $∥ r_{k} ∥_{2} \leq δ_{k} ∥ p_{k} ∥_{2}$ whenever $p_{k} \neq 0$ ; therefore $∥ r_{k} ∥_{2} \leq C δ_{k} ∥ F_{k} ∥_{2}$ . At a zero primal step the displayed residual is zero, so the same conclusion holds.

3.1A1F2F4step 2.1

LICQ and the second-order condition make $J_{*}$ nonsingular by [F2], as in the exact-Hessian result. The Jacobian is locally Lipschitz by [A1]. Thus the steps satisfy the inexact-Newton equation with forcing factor $η_{k} : = ∥ r_{k} ∥_{2} / ∥ F_{k} ∥_{2}$ when $F_{k} \neq 0$ , and $η_{k} : = 0$ when $F_{k} = 0$ . Assumption [A1] gives $η_{k} \leq \overset{ˉ}{η} < 1$ , while step 2.1 gives $η_{k} \leq C δ_{k} \to 0$ .

4.1F3F4step 3.1∎

Apply [F4] to the combined primal-dual variable. Starting sufficiently near the root, the full steps remain local and converge superlinearly. If an exact root is reached, no further convergence assertion is needed; if the algorithm reports a failed solve, its nonsingularity hypotheses have failed and this theorem does not apply.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 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

Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed. (standard reference, not scraped)