LemmaStatement: Literature-sourcedProof: 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.

Positive-definite Newton and dogleg steps are well-defined

Statement

Let $B$ be the real symmetric positive-definite model matrix of Quadratic trust-region models and the actual-to-predicted reduction ratio, with $n \geq 1$ , $g \in R^{n}$ , and radius $Δ > 0$ . There is a unique $p_{N} \in R^{n}$ satisfying $B p_{N} = - g$ . The Dogleg steps for positive-definite trust-region models procedure is well-defined on this input and returns a feasible vector. If its boundary-intersection branch is taken, the displayed scalar formula is the unique root $t \in (0, 1)$ of $∥ p_{C} + t (p_{N} - p_{C}) ∥_{2}^{2} = Δ^{2}$ . On a nonstationary input the procedure performs one linear solve and, only on its boundary branch, one scalar-root computation; it has no iteration loop.

Facts & Assumptions

Given: A positive-definite symmetric matrix $B$ , vector $g$ , radius $Δ > 0$ , and the definitions of the Newton and dogleg procedures.

[F1]

Positive definite, negative definite, semidefinite, and indefinite quadratic forms: positive definiteness means $v^{T} B v > 0$ for every nonzero $v$ .

[F2]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix has an orthonormal eigenbasis.

[F3]

Invertible Euclidean linear maps: an invertible Euclidean linear map has a two-sided linear inverse.

[F4]

Dogleg steps for positive-definite trust-region models: after the stationary check, the procedure computes the Cauchy step, solves $B p_{N} = - g$ , returns $p_{N}$ if it is feasible, returns $p_{C}$ if it is on the boundary, and otherwise uses the displayed quadratic-root formula before comparing the two model values.

[F5]

The Cauchy step for a quadratic trust-region model: for $g \neq 0$ , the Cauchy parameter is nonnegative and at most $Δ / ∥ g ∥_{2}$ , so $∥ p_{C} ∥_{2} \leq Δ$ .

[F6]

Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function: every real polynomial is continuous.

[F7]

Intermediate value theorem, by bisection with a canonical left-half rule: a continuous function on $[a, b]$ takes every value between $f (a)$ and $f (b)$ : a continuous real-valued function on a closed interval takes every value between its endpoint values.

Proof

Given: The hypotheses in the Statement.

1.1givenF1F2F3algebra

By [F2], write $B = U diag (μ_{1}, \dots, μ_{n}) U^{T}$ with $U$ orthogonal. Positive definiteness [F1] gives $μ_{i} > 0$ for every unit eigenvector. Thus $C = U diag (1 / μ_{1}, \dots, 1 / μ_{n}) U^{T}$ satisfies $C B = B C = I$ and is a linear inverse by [F3]. Hence $p_{N} = - C g$ solves $B p_{N} = - g$ . If $p$ is another solution, then $B (p - p_{N}) = 0$ , and applying $C$ gives $p = p_{N}$ .

2.1givenF4F5step 1.1cases

If $g = 0$ , [F4] returns $p = 0$ , which is feasible. Suppose $g \neq 0$ . The Cauchy step exists by its explicit formula and is feasible by [F5], and step 1.1 gives the unique Newton step. If $∥ p_{N} ∥_{2} \leq Δ$ , the algorithm returns the feasible $p_{N}$ . If $∥ p_{N} ∥_{2} > Δ$ but $∥ p_{C} ∥_{2} = Δ$ , it returns the feasible $p_{C}$ .

3.1givenF4F6F7step 2.1algebra

In the remaining branch, $∥ p_{N} ∥_{2} > Δ$ and $∥ p_{C} ∥_{2} < Δ$ . Put $d = p_{N} - p_{C}$ and $q (t) = ∥ p_{C} + t d ∥_{2}^{2} - Δ^{2}$ . Then $q$ is a real quadratic polynomial, $q (0) < 0$ , and $q (1) > 0$ . By [F6] it is continuous, and [F7] gives a root $t \in (0, 1)$ . Its coefficients are $a = ∥ d ∥_{2}^{2} > 0$ , $b = 2 ⟨ p_{C}, d ⟩$ , and $c = ∥ p_{C} ∥_{2}^{2} - Δ^{2} < 0$ . Thus its discriminant $b^{2} - 4 a c > b^{2}$ , and the two roots have product $c / a < 0$ . Exactly one root is positive, and the quadratic formula identifies it as $(- b + \sqrt{b^{2} - 4 a c}) / (2 a)$ . The root in $(0, 1)$ is therefore exactly the algorithm's scalar $t$ . The vector $p_{D} = p_{C} + t d$ has norm $Δ$ ; the final comparison returns either $p_{D}$ or $p_{C}$ , both feasible.

4.1step 1.1step 2.1step 3.1F4cases∎

Step 1.1 proves unique Newton-step existence, and steps 2.1 and 3.1 cover every dogleg branch and establish its feasibility and root formula. The Definition calls the Newton solve once on every nonstationary input, calls the scalar-root formula only in branch 3, and has no iteration branch.

Depends on

Used by

A damped least-squares step solves a scaled trust-region model Lemma

Cited to discharge well-definedness by Dogleg steps for positive-definite trust-region models.

Dependency tree · two levels

41 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, second edition (standard reference, not scraped)