## Definition

### Lipschitz Continuous

F be an m-vector of functions of x ∈ E n . F is Lipschitz continuous on an open set S⊂En ifthereisaconstant 0<L<∞ such that F(x)−F(y) ≤Lx−y for all x, y ∈ S .

## Newton's Method

Let f be a real-valued function of n variables defined on an open convex set S . Assume that ∇ 2 f is Lipschitz continuous on S, that is, ∇2f (x) − ∇2f (y) ≤ L ∥x − y∥
for all x, y ∈ S and for some constant L < ∞. Consider the sequence { xk } generated by xk+1 =xk −[∇2f(xk)]−1∇f(xk).
Let x∗ be a minimizer of f (x) in S and assume that ∇2f (x∗) is positive definite. If ∥x0 − x∗∥ is sufficiently small, then { xk } converges quadratically to x∗ .

### (Theorm) Superlinear Convergence

Let f be a real-valued function of n variables defined on an open convex set S. Assume that ∇2f is Lipschitz continuous on S, that is,
∇2f (x) − ∇2f (y) ≤ L ∥x − y∥
for all x, y ∈ S and for some constant L < ∞. Consider the sequence { xk } generated by xk+1 =xk +pk.

### (Algorithm) Newton Method with Line Search

1. Specify some initial guess of the solution x0, and specify a convergence tolerance ε.
2. For k = 0,1,…
• If ∥∇f (xk)∥ < ε, stop.
• Compute a modified factorization of the Hessian: ∇2f (xk) + E = LDLT and solve (LDLT)p = −∇f(xk) for the search direction pk . (E will be zero if ∇ 2 f (xk ) is “sufficiently” positive definite.)
• Perform a line search to determine xk+1 =xk +αkpk, the new estimate of the solution.