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.

Damped Newton reaches its local quadratic phase in finitely many continued updates

Statement

Let $d \geq 1$ and $U \subseteq R^{d}$ be open and convex, let $f \in C^{2} (U, R)$ have an attained global minimum $f^{*} = f (x^{*})$ at $x^{*} \in U$ , and fix $x_{0} \in U$ . Suppose $K : = {y \in U : f (y) \leq f (x_{0})}$ is compact and is contained in a convex open $V \subseteq U$ that contains every Newton backtracking trial segment under consideration. For constants $0 < m \leq M$ , assume

$m ∥ v ∥_{2}^{2} \leq v^{T} H_{f} (y) v \leq M ∥ v ∥_{2}^{2} (y \in V, v \in R^{d}) .$

Assume also that there are $R > 0$ and $L_{H} \geq 0$ with $B (x^{*}, R) \subseteq V$ and $∥ H_{f} (y) - H_{f} (z) ∥_{o p} \leq L_{H} ∥ y - z ∥_{2}$ for $y, z \in B (x^{*}, R)$ , where $∥ A ∥_{o p} : = \sup_{∥ v ∥_{2} = 1} ∥ A v ∥_{2}$ . Run Damped Newton method with $a \in (0, 1 / 2)$ , $b \in (0, 1)$ , and positive decrement tolerance $ε$ . Let $ρ > 0$ and $C < \infty$ be constants furnished by Newton's method has local quadratic convergence under a Lipschitz Hessian for these data, and set

$τ_{N} : = \min {1, \frac{2 b (1 - a) m}{M}}, q_{N} : = 1 - \frac{2 a m τ_{N}}{M} .$

For every accepted update before entry into $B (x^{*}, ρ)$ ,

$f (x_{k + 1}) - f^{*} \leq q_{N} (f (x_{k}) - f^{*}), 0 < q_{N} < 1.$

Thus, after finitely many such updates the method either has stopped at its positive decrement test or has entered $B (x^{*}, ρ)$ . More explicitly, if $ε < m^{2} ρ^{2} / (2 M)$ , the decrement test cannot stop outside that ball, so the method reaches it after finitely many accepted updates. Once in this ball, every later attempted update has step $t_{k} = 1$ and satisfies

$∥ x_{k + 1} - x^{*} ∥_{2} \leq C ∥ x_{k} - x^{*} ∥_{2}^{2} .$

The last assertion is conditional on the decrement test not stopping first. No post-stop iterate or update is asserted. This is a strongly convex objective result; it does not apply to arbitrary vector roots or indefinite Hessians.

Facts & Assumptions

Given: The hypotheses of the Statement, a generated iterate $x \in K$ , and the canonical damped-Newton line-search parameters and decrement test.

[F1]

Damped Newton method: when $H_{f} (x)$ is positive definite it computes $p = - H_{f} (x)^{- 1} \nabla f (x)$ and $λ^{2} = \nabla f (x)^{T} H_{f} (x)^{- 1} \nabla f (x)$ ; if $λ^{2} / 2 \leq ε$ it stops before line search, and otherwise it backtracks from $t = 1$ using the Armijo condition with parameter $a$ and factor $b$ .

[F2]

Newton's method has local quadratic convergence under a Lipschitz Hessian: for a $C^{2}$ objective with a positive-definite critical Hessian and a Lipschitz Hessian on a ball, every generated iterate from a sufficiently small ball remains there; each attempted update whose decrement test does not stop has unit step and a quadratic error bound.

[F3]

A Hessian lower bound gives strong convexity and gradient-gap bounds: the Hessian lower bound gives $f (x) - f^{*} \geq m ∥ x - x^{*} ∥_{2}^{2} / 2$ and $∥ \nabla f (x) ∥_{2}^{2} \geq 2 m (f (x) - f^{*})$ .

[F4]

Multivariable Taylor formula with a Lagrange remainder along a line segment: on a segment in the convex domain, the second-order remainder is a Hessian quadratic form at an interior point.

[F5]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric Hessian has an orthonormal eigenbasis, so $m I ⪯ H ⪯ M I$ implies $M^{- 1} I ⪯ H^{- 1} ⪯ m^{- 1} I$ .

[F6]

The Hessian of a $C^{2}$ scalar field is symmetric and The Hessian matrix and critical points of a scalar field: the Hessian of a $C^{2}$ real scalar objective is symmetric and uses the second-partial convention.

[F7]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: $\nabla f$ is the vector of first partial derivatives.

[F8]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : if $0 < q_{N} < 1$ , then $q_{N}^{k} \to 0$ .

Proof

1.1F1F5F6F7givenalgebra

At a nonstationary iterate, $H : = H_{f} (x)$ is symmetric positive definite by [F6] and the lower bound. Put $g : = \nabla f (x)$ and $p : = - H^{- 1} g$ . The Newton decrement is $λ^{2} = g^{T} H^{- 1} g = p^{T} H p$ , and [F5] gives $λ^{2} \geq ∥ g ∥_{2}^{2} / M$ and $λ^{2} \geq m ∥ p ∥_{2}^{2}$ .

2.1F1F4F8step 1.1algebrachoose

Set $T_{N} : = 2 m (1 - a) / M$ . For any trial $0 < t \leq T_{N}$ , [F4] and $H_{f} ⪯ M I$ on its segment give $f (x + t p) \leq f (x) - t λ^{2} + (M / 2) t^{2} ∥ p ∥_{2}^{2} \leq f (x) - a t λ^{2}$ , where the last inequality uses $λ^{2} \geq m ∥ p ∥_{2}^{2}$ . If $T_{N} \geq 1$ , trial $t = 1$ passes. If $T_{N} < 1$ , [F8] gives a least $j$ with $b^{j} \leq T_{N}$ ; then $b^{j} > b T_{N}$ and that candidate passes, so the first accepted step is at least $τ_{N}$ .

3.1F1F3step 1.1step 2.1algebra

For any accepted update before the local ball, $λ^{2} \geq ∥ g ∥_{2}^{2} / M$ by step 1.1 and $t \geq τ_{N}$ by step 2.1. Armijo acceptance and [F3] therefore give $f (x_{+}) - f^{*} \leq f (x) - f^{*} - (a τ_{N} / M) ∥ g ∥_{2}^{2} \leq (1 - 2 a m τ_{N} / M) (f (x) - f^{*})$ . The coefficient is positive because $τ_{N} \leq 2 b (1 - a) m / M$ implies $2 a m τ_{N} / M \leq 4 a b (1 - a) (m / M)^{2} < 1$ ; it is less than one because all factors in the subtracted term are positive.

4.1F1F3F5F8step 1.1step 3.1givenchoose

If $x$ lies outside $B (x^{*}, ρ)$ , [F3] gives $f (x) - f^{*} \geq m ρ^{2} / 2$ . Step 1.1 then gives $λ^{2} / 2 \geq ∥ g ∥_{2}^{2} / (2 M) \geq (m / M) (f (x) - f^{*}) \geq m^{2} ρ^{2} / (2 M)$ . Thus if $ε < m^{2} ρ^{2} / (2 M)$ the decrement test cannot stop outside the ball. Repeating step 3.1 gives a gap bounded by $q_{N}^{k} (f (x_{0}) - f^{*})$ ; choose $N$ with $q_{N}^{N} (f (x_{0}) - f^{*}) < m ρ^{2} / 2$ , which exists by [F8]. If no earlier stop occurs, [F3] places the $N$ th generated iterate inside $B (x^{*}, ρ)$ . For larger tolerances the method may stop before this finite entry, and no post-stop sequence is asserted.

5.1F1F2step 4.1∎

Starting the canonical local theorem [F2] at the first generated iterate in $B (x^{*}, ρ)$ shows that every later generated iterate remains in that ball. Whenever its decrement test does not stop, [F2] gives $t_{k} = 1$ and $∥ x_{k + 1} - x^{*} ∥_{2} \leq C ∥ x_{k} - x^{*} ∥_{2}^{2}$ . If the decrement test stops, the algorithm returns there and no later update is asserted.

Depends on

Used by

A damped Newton step precedes the local quadratic phase Example

Dependency tree · two levels

49 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

Stephen Boyd and Lieven Vandenberghe, Convex Optimization (standard reference, not scraped)
Philip E. Gill and Margaret H. Wright, Math 171B Numerical Optimization Class Notes (standard reference, not scraped)