Nonconvex line search and inexact newton methods — Examples

1 · Prerequisites

2 · Summary

The examples calculate a unit strong-Wolfe Newton step at the standard Rosenbrock start, show why an indefinite Hessian needs a descent safeguard, and track how a scalar Krylov residual tolerance changes inner work and outer error. The finite-budget search caveat is retained: existence of a Wolfe interval does not guarantee a particular cap reaches it.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

The standard Rosenbrock start accepts a full Newton step

Example

For $f (x, y) = 100 (y - x^{2})^{2} + (1 - x)^{2}$ at $(x_{0}, y_{0}) = (- 6 / 5, 1)$ , use an exact unshifted Newton solve, descent threshold $σ = 1 / 10$ , and strong Wolfe parameters $c_{1} = 1 / 10000$ , $c_{2} = 2 / 5$ . The initial unit trial satisfies both strong Wolfe inequalities, so the bracketing search returns $t = 1$ .

Use the deterministic Krylov procedure which, for a two-dimensional operator $A$ and right-hand side $b$ , forms $V = [b A b]$ when $M \geq 2$ . If $V$ and $V^{T} A V$ are invertible, it returns $p = V (V^{T} A V)^{- 1} V^{T} b$ with iteration count $m = 2$ ; otherwise it returns no-candidate. On other input dimensions or budgets below two it returns no-candidate. Its candidate lies in $K_{2} (A, b)$ by construction. Take $M \geq 2$ , $N \geq 1$ , $E, Z \geq 1$ , $J = 0$ , $η_{k} = \overset{ˉ}{η} = 0$ , $γ = 2$ , and $λ_{0} = λ_{\max} = 1$ .

Facts & Assumptions

Given: The Rosenbrock objective and parameters in the Example.

[F1]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient is the vector of first partial derivatives in Euclidean coordinates.

[F2]

The Hessian matrix and critical points of a scalar field: the Hessian matrix consists of the second partial derivatives.

[F3]

Finite-budget inexact Newton–Krylov with a descent safeguard: with $λ = 0$ , the algorithm accepts a candidate only after it verifies the Newton residual bound and strict descent test.

[F4]

Finite-budget bracketing and zoom for a strong Wolfe step: the expansion phase tests $t = 1$ first and returns a step only after both strong Wolfe inequalities are checked.

[F5]

Wolfe and strong Wolfe line-search conditions: a strong Wolfe step satisfies Armijo decrease and $∣ ϕ^{'} (t) ∣ \leq c_{2} ∣ ϕ^{'} (0) ∣$ .

Verification

Given: The objective, initial point, and parameters of the Example.

1.1givenF1F2algebra

Put $r : = y - x^{2}$ . Direct differentiation using [F1]–[F2] gives $\nabla f = (- 400 x r + 2 (x - 1), 200 r)$ and $H_{f} = [\begin{array}{cc} 1200 x^{2} - 400 y + 2 & - 400 x \\ - 400 x & 200 \end{array}]$ . At $(- 6 / 5, 1)$ , $r = - 11 / 25$ , $g = (- 1078 / 5, - 88)$ , and $H = [\begin{array}{cc} 1330 & 480 \\ 480 & 200 \end{array}]$ .

1.2givenF3algebra

With $b = - g$ , direct calculation gives $\det [b H b] = - 14221856 / 5 \neq 0$ and $\det H = 35600 \neq 0$ . Thus $V$ and $V^{T} H V$ are invertible. The specified solver returns $p \in K_{2} (H, b)$ with $V^{T} (H p - b) = 0$ ; since $V$ is invertible, $H p = b$ . Solving $H p = - g$ gives $p = (11 / 445, 847 / 2225)$ ; substitution into the matrix product verifies the equation exactly. Hence the recomputed unshifted residual is zero and $g^{T} p = - 86394 / 2225 < - 38$ . Also $∥ g ∥_{2} < 234$ and $∥ p ∥_{2} < 41 / 100$ , so $g^{T} p < - 38 < - (1 / 10) (234) (41 / 100) < - σ ∥ g ∥_{2} ∥ p ∥_{2}$ . The descent safeguard accepts this direction.

2.1givenF1F5step 1.2algebra

The full trial is $(x_{1}, y_{1}) = (- 523 / 445, 3072 / 2225)$ , with $y_{1} - x_{1}^{2} = - 121 / 198025$ . Thus $f (x_{0}, y_{0}) = 121 / 5$ , while $f (x_{1}, y_{1}) = (968 / 445)^{2} + 100 (121 / 198025)^{2} < 5$ . Since $ϕ^{'} (0) = g^{T} p > - 39$ , the Armijo right side is greater than $121 / 5 - 39 / 10000 > 24$ ; therefore the full trial satisfies Armijo.

2.2givenF1F5step 1.2algebra

At the trial point, $∣ x_{1} ∣ < 6 / 5$ , $∣ x_{1} - 1 ∣ < 11 / 5$ , and $∣ y_{1} - x_{1}^{2} ∣ < 1 / 1600$ . The gradient formula of step 1.1 gives $∣ (\nabla f (x_{1}, y_{1}))_{1} ∣ < 47 / 10$ and $∣ (\nabla f (x_{1}, y_{1}))_{2} ∣ < 1 / 8$ . Since $∣ p_{1} ∣ < 1 / 40$ and $∣ p_{2} ∣ < 2 / 5$ , it follows that $∣ ϕ^{'} (1) ∣ = ∣ ⟨ \nabla f (x_{1}, y_{1}), p ⟩ ∣ < 1 / 5$ . Meanwhile $c_{2} ∣ ϕ^{'} (0) ∣ > (2 / 5) 38 > 15$ . The strong curvature inequality therefore holds.

3.1F4step 2.1step 2.2∎

Steps 2.1 and 2.2 verify both strong Wolfe tests at the first trial $t = 1$ . By [F4] the search returns this verified full step. This example is a single accepted update and gives no global convergence claim.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

An indefinite Rosenbrock Hessian makes the raw Newton direction ascend

Example

For the Rosenbrock objective $f (x, y) = 100 (y - x^{2})^{2} + (1 - x)^{2}$ at $(x, y) = (0, 1 / 100)$ , the Hessian is indefinite and the unshifted Newton correction is an ascent direction. With shift $λ = 3$ , the linear solve produces a descent direction, and the objective is bounded below on its ray; a strong Wolfe interval therefore exists. A finite search budget may still return failure before finding a step.

Use the deterministic Krylov procedure which, for a two-dimensional operator $A$ and right-hand side $b$ , forms $V = [b A b]$ when $M \geq 2$ . If $V$ and $V^{T} A V$ are invertible, it returns $p = V (V^{T} A V)^{- 1} V^{T} b$ with iteration count $m = 2$ ; otherwise it returns no-candidate. On other input dimensions or budgets below two it returns no-candidate. Its candidate lies in $K_{2} (A, b)$ by construction. Take $M \geq 2$ , $N \geq 1$ , $E, Z \geq 1$ , $η_{k} = \overset{ˉ}{η} = 0$ , $γ = 2$ , $c_{1} = 1 / 10000$ , and $c_{2} = 2 / 5$ , with the shift parameters below.

Facts & Assumptions

Given: The objective and point in the Example, descent threshold $σ = 1 / 10$ , regularization seed $λ_{0} = 3$ , a regularization cap $λ_{\max} \geq 3$ , and attempt budget $J \geq 1$ .

[F1]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient is the vector of first partial derivatives in Euclidean coordinates.

[F2]

The Hessian matrix and critical points of a scalar field: the Hessian matrix consists of the second partial derivatives.

[F3]

Finite-budget inexact Newton–Krylov with a descent safeguard: the first linear system is unshifted; a failed residual or descent check triggers a positive shift, and a regularized candidate is accepted only after recomputing its residual and checking descent.

[F4]

A strong Wolfe step exists on a bounded-below descent ray: for a $C^{1}$ objective bounded below on an entire feasible descent ray, a strong Wolfe interval exists.

Verification

Given: The Rosenbrock objective, the point $(0, 1 / 100)$ , $σ = 1 / 10$ , $λ_{0} = 3$ , $λ_{\max} \geq 3$ , and $J \geq 1$ .

1.1givenF1F2algebra

Put $r : = y - x^{2}$ . Differentiating gives $g = (- 400 x r + 2 (x - 1), 200 r)$ and $H_{f} = [\begin{array}{cc} 1200 x^{2} - 400 y + 2 & - 400 x \\ - 400 x & 200 \end{array}]$ . At the given point, $g = (- 2, 2)$ and $H = diag (- 2, 200)$ . The quadratic form of $H$ is negative on $(1, 0)$ and positive on $(0, 1)$ , so $H$ is indefinite.

2.1givenF3step 1.1algebra

For $b = - g = (2, - 2)$ and either $A = H$ or $A = H + 3 I_{2}$ , $\det [b A b] = - 808 \neq 0$ , and both operators are invertible. Hence the specified projected solver returns the exact solution $A p = b$ in $K_{2} (A, b)$ , using $m = 2 \leq M$ . The unshifted Newton solve $H p = - g$ gives $p = (- 1, - 1 / 100)$ and $g^{T} p = 99 / 50 > 0$ . It is therefore not a descent direction and fails the algorithm's descent check.

2.2givenF3step 1.1algebra

For shift $λ = 3$ , $H + 3 I_{2} = diag (1, 203)$ and the exact shifted solve gives $p = (2, - 2 / 203)$ . Its residual is zero, while $g^{T} p = - 4 - 4 / 203 < - 4$ . Also $∥ g ∥_{2} = 2 \sqrt{2} < 3$ and $∥ p ∥_{2} < 3$ , hence $- (1 / 10) ∥ g ∥_{2} ∥ p ∥_{2} > - 9 / 10$ and $g^{T} p < - (1 / 10) ∥ g ∥_{2} ∥ p ∥_{2}$ . Thus the shifted candidate passes the stated residual and descent tests.

3.1givenF4step 2.2∎

The Rosenbrock objective is nonnegative on $R^{2}$ , and the shifted direction has $g^{T} p < 0$ . The entire ray is feasible because $D = R^{2}$ . Apply [F4] to conclude that a nonempty interval of strong Wolfe steps exists for this direction. This existence result does not guarantee that any specified finite expansion/zoom budget reaches the interval.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A scalar inexact Newton solve trades inner work for outer error

Example

Let $f (x) = x^{2} / 2$ , so $F (x) = f^{'} (x) = x$ and $F^{'} (x) = 1$ . At a nonzero iterate, solve the Newton equation approximately from $p^{(0)} = 0$ by

p^{(j + 1)} = p^{(j)} - (1 - ω) (p^{(j)} + x), 0 < ω < 1.

Stop at the first $j$ with $ω^{j} \leq η$ , where the forcing tolerance satisfies $0 < η \leq c_{2} < 1 / 2$ . With the exact strong Wolfe search from Finite-budget bracketing and zoom for a strong Wolfe step, the unit step is accepted. The number $j$ of inner iterations grows as $η$ is tightened, while the outer error contracts by a factor at most $η$ ; choosing $η_{k} = ∣ x_{k} ∣$ gives a quadratic outer error bound for $0 < ∣ x_{0} ∣ \leq c_{2}$ .

For each finite horizon $N \geq 1$ , let $j_{k}$ be the least integer with $ω^{j_{k}} \leq η_{k}$ on the first $N$ steps of the displayed recurrence, and choose the single inner budget $M_{N} \geq \max_{0 \leq k < N} j_{k}$ . Use $M = M_{N}$ , $\overset{ˉ}{η} = c_{2}$ , $σ = 1 / 2$ , $J = 0$ , $E, Z \geq 1$ , $γ = 2$ , and $λ_{0} = λ_{\max} = 1$ . The deterministic solver on the scalar operator $A = 1$ starts at zero and performs the displayed iteration until $∣ p + x ∣ \leq τ$ , where $τ$ is its absolute requested residual tolerance, or until $M$ iterations are used; it returns that scalar candidate and its iteration count. It returns no-candidate for other operators. For $b = - x \neq 0$ and any $m \geq 1$ , $K_{m} (1, b) = R$ , so every returned candidate meets the Krylov input contract (and $p^{(0)} = 0 \in K_{0}$ ). This realizes every finite prefix. The infinite recurrence and its rate claim do not assert realization by one fixed finite inner budget.

Facts & Assumptions

Given: The scalar objective, the fixed $ω \in (0, 1)$ , and Wolfe parameters $0 < c_{1} < c_{2} < 1 / 2$ .

[F1]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: for a scalar function the gradient is the vector of first partial derivatives.

[F2]

The Hessian matrix and critical points of a scalar field: the Hessian is the matrix of second partial derivatives.

[F3]

Finite-budget inexact Newton–Krylov with a descent safeguard: the unshifted solve is accepted only after recomputing $H (x) p + g (x)$ and checking its forcing residual and descent threshold; the next iterate uses the returned Wolfe step.

[F4]

Finite-budget bracketing and zoom for a strong Wolfe step: the search tests $t = 1$ first and returns it when both strong Wolfe inequalities hold.

[F5]

Forcing residuals determine local inexact-Newton rates: an unshifted full-step sequence with a relative residual bounded by $η_{k} ∥ F (x_{k}) ∥_{2}$ converges quadratically when $η_{k} = O (∥ F (x_{k}) ∥_{2})$ , under the stated local hypotheses.

[F6]

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

[F7]

The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ : $K_{0} (A, b) = {0}$ and $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ for $m \geq 1$ .

Verification

Given: The objective and inner iteration of the Example, with $x \neq 0$ and $0 < η \leq c_{2}$ .

1.1givenF1F2inductionalgebra

The exact scalar identities are $F (x) = x$ , $J (x) = 1$ , and $g (x) = x$ by [F1]–[F2]. Induction on $j$ gives $p^{(j)} = - (1 - ω^{j}) x$ , so the linear residual is $r_{j} = J (x) p^{(j)} + F (x) = ω^{j} x$ .

1.2givenF6F7choosealgebra

Since $0 < ω < 1$ , [F6] gives $ω^{j} \to 0$ , so a least $j$ with $ω^{j} \leq η$ exists. As $η < 1$ , $j \geq 1$ and minimality gives $ω^{j} \leq η < ω^{j - 1}$ . If the requested tolerance is reduced, the set of eligible $j$ can only shrink, so the required inner iteration count cannot decrease. For any finite $N$ , all $j_{k}$ on its first $N$ nonzero iterates are finite, so their finite maximum defines $M_{N}$ . The specified solver therefore reaches its requested residual tolerance before its budget on that prefix, and [F7] verifies its scalar Krylov membership.

2.1givenF3step 1.1step 1.2algebra

At this $j$ , $∣ r_{j} ∣ = ω^{j} ∣ x ∣ \leq η ∣ x ∣$ , while $g (x) p^{(j)} = - (1 - ω^{j}) x^{2}$ and $∣ g (x) ∣ ∣ p^{(j)} ∣ = (1 - ω^{j}) x^{2}$ . Because $0 < σ < 1$ , the descent safeguard passes.

3.1givenF3F4step 2.1algebra

Let $q : = ω^{j} \leq η \leq c_{2}$ . The unit step gives $x_{+} = x + p^{(j)} = q x$ . Its objective satisfies $f (x_{+}) = q^{2} x^{2} / 2 \leq x^{2} (1 - 2 c_{1} (1 - q)) / 2 = f (x) + c_{1} g (x) p^{(j)}$ , because $1 + q \geq 1 > 2 c_{1}$ . Also $∣ ϕ^{'} (1) ∣ = q (1 - q) x^{2} \leq c_{2} (1 - q) x^{2} = c_{2} ∣ ϕ^{'} (0) ∣$ . Thus both strong Wolfe conditions hold, and [F4] accepts $t = 1$ .

4.1givenF5step 1.2step 3.1induction∎

For fixed $η$ , $q = ω^{j}$ is a constant in $(0, 1)$ and $x_{k + 1} = q x_{k}$ , so the outer sequence is linearly convergent. If $0 < ∣ x_{0} ∣ \leq c_{2}$ and $η_{k} = ∣ x_{k} ∣$ , then $η_{k} \leq c_{2}$ at every step and $∣ x_{k + 1} ∣ = ω^{j_{k}} ∣ x_{k} ∣ \leq ∣ x_{k} ∣^{2}$ . Here $η_{k} = ∣ F (x_{k}) ∣$ ; the local tube in [F5] may contain $[- c_{2}, c_{2}]$ because $F (x) = x$ and $J (x) = 1$ everywhere. Thus [F5] supplies the same local quadratic-rate conclusion.