DefinitionDefinition: 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.

L1 exact-penalty merit and predicted decrease for SQP

Definition

Use the nonlinear program and SQP subproblem conventions of The linearized quadratic subproblem in sequential quadratic programming. For $ρ > 0$ , define the nondifferentiable L1 merit function $ψ_{ρ} (x) = f (x) + ρ (∥ h (x) ∥_{1} + ∥ [g (x)]_{+} ∥_{1}) .$ For a subproblem step $p$ at $x$ , its linearized predicted decrease is $D_{ρ} (x, p) = - [\nabla f (x)^{T} p + ρ (∥ h (x) + D h (x) p ∥_{1} - ∥ h (x) ∥_{1} + ∥ [g (x) + D g (x) p]_{+} ∥_{1} - ∥ [g (x)]_{+} ∥_{1})] .$ A trial fraction $t \in (0, 1]$ satisfies the Armijo test with coefficient $σ \in (0, 1)$ when $ψ_{ρ} (x + t p) \leq ψ_{ρ} (x) - σ t D_{ρ} (x, p) .$ The definition alone does not assert $D_{ρ} (x, p) > 0$ , existence of an accepted fraction, or convergence of a sequence of accepted SQP steps.

Facts & Assumptions

Given: The $C^{2}$ program and a subproblem displacement $p$ , with penalty parameter $ρ > 0$ .

[F1]

The linearized quadratic subproblem in sequential quadratic programming defines the affine linearized equality and inequality residuals and uses $g \leq 0$ .

[A1]

The penalty is $ρ > 0$ , the point $x$ belongs to $U$ , and the trial point belongs to $U$ whenever its nonlinear merit is evaluated.

Proof

1.1givenA1F1algebra

The norm and positive-part terms in $ψ_{ρ}$ are finite for every $x \in U$ , since the constraint maps are real-valued and the dimensions are finite. The displayed $D_{ρ} (x, p)$ is therefore the negative of the change in the linear objective-plus-penalty model from displacement $0$ to $p$ .

2.1givenA1step 1.1algebra∎

Let $m_{ρ} (s)$ denote the linear objective-plus-penalty model from step 1.1, including the constant $f (x)$ . Then $m_{ρ} (0) = ψ_{ρ} (x)$ and $m_{ρ} (p) - m_{ρ} (0) = - D_{ρ} (x, p)$ , so the Armijo reference is $m_{ρ} (0) + σ t (m_{ρ} (p) - m_{ρ} (0))$ . The test compares this finite scalar with the actual merit $ψ_{ρ} (x + t p)$ ; the reference need not equal $m_{ρ} (t p)$ . No positivity or acceptance claim follows from the definition.

Depends on

The linearized quadratic subproblem in sequential quadratic programming

Used by

Dependency tree · two levels

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