AlgorithmAlgorithm: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pending

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 KKT step with projected Hessian error

Definition

Let $c_{A} (x)$ stack the equality and identified active constraints, and let $A = D c_{A} (x)$ have full row rank. Set $P = I - A^{T} (A A^{T})^{- 1} A$ when $A$ has positive row count and $P = I$ when it has zero rows. Given the exact Lagrangian Hessian $H$ and a symmetric positive-definite full-memory BFGS matrix $B$ , define $H_{r e d} = H + P (B - H) P .$ Solve the active KKT system with $H_{r e d}$ in its upper-left block and right-hand side $- F_{A} (x, μ)$ as in Full-step exact-Hessian SQP after active-set identification. If the rows are dependent or the solve fails, return kkt-solve-failure.

For a curvature pair $(s, y)$ with $s^{T} y > 0$ , the optional next-model update is $B^{+} = B - \frac{(B s) (B s)^{T}}{s^{T} B s} + \frac{y y^{T}}{s^{T} y};$ if $s^{T} y \leq 0$ , skip the update and retain $B$ . The curvature pair is defined as in Bfgs curvature pairs and Hessian/inverse updates.

Facts & Assumptions

Given: An identified active set with independent rows, its SQP KKT residual $F_{A}$ , exact Lagrangian Hessian $H$ , and $B ≻ 0$ .

[F1]

The linearized quadratic subproblem in sequential quadratic programming fixes the active-row KKT block convention.

[F2]

The SQP KKT matrix is nonsingular under positive reduced curvature states that reduced positive curvature and independent rows imply nonsingularity.

[F3]

Bfgs curvature pairs and Hessian/inverse updates defines the BFGS curvature pair and update.

[F4]

Bfgs updates preserve the secant equations, symmetry, and positive definiteness: if $B ≻ 0$ and $s^{T} y > 0$ , the BFGS update is symmetric positive definite.

[F5]

Inequality constrained programs, tangent cones, constraint qualifications, and KKT fixes the active set and the Lagrangian multiplier convention used in $F_{A}$ .

[A1]

The current active rows are independent, and the supplied BFGS model is symmetric positive definite.

Proof

1.1givenF1F2F5algebra

Full row rank gives $A P = 0$ , $P^{T} = P$ , and $P z = z$ for $z \in \ker A$ ; these follow by multiplying out the displayed projector. Hence for every $z \in \ker A$ , $z^{T} H_{r e d} z = z^{T} B z > 0$ . Applying [F2] to $H_{r e d}$ shows that the KKT solve is nonsingular.

2.1givenF3F4step 1.1∎

If $s^{T} y > 0$ , the update in [F3] is symmetric and remains positive definite by [F4]. If $s^{T} y \leq 0$ , the algorithm retains the already positive-definite $B$ . Thus every successful model update preserves the stated $B ≻ 0$ invariant.

Depends on

Used by

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

Dependency tree · two levels

10 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)