Newton and quasi-Newton methods

Expand a twice differentiable objective to second order around the current point. If the Hessian is positive definite, the quadratic model has a unique minimizer in its displacement variable. Setting that model's derivative to zero yields a linear system for the Newton direction. Implementations usually solve this system through a factorization or iterative method; explicitly forming a matrix inverse is unnecessary and can waste work or lose numerical accuracy.

The positive-definiteness assumption is substantive. It guarantees that the gradient's inner product with the Newton direction is negative whenever the gradient is nonzero. An indefinite Hessian can instead point toward increasing objective values, or produce a direction toward a saddle. Regularizing the Hessian, solving a trust-region subproblem, or falling back to a descent direction are ways to handle this situation; none should be silently called an unmodified Newton step.

Near a minimizer with nonsingular positive-definite Hessian, a locally Lipschitz Hessian gives quadratic convergence of full Newton steps when the starting point is sufficiently close. Roughly, the next error is bounded by a constant times the square of the current error. This local statement does not promise convergence from every initialization. Far away, damping through line search or a trust region limits how much of the local quadratic model is trusted.

Newton's direction is also sensitive to how accurately the linear system is solved. In large models, Hessian-vector products can avoid storing the full matrix, but the resulting method needs an explicit linear-solve tolerance. A loose solve may be adequate far from the solution; tighter solves can become necessary for fast local convergence. Computational cost should therefore be compared in gradient evaluations, curvature operations, storage, and elapsed time rather than iteration count alone.

Quasi-Newton methods replace the exact Hessian by a matrix updated from observed displacements and gradient changes. With $s=x_{k+1}-x_k$ and $y=g_{k+1}-g_k$, a Hessian approximation can enforce the secant relation $B_{k+1}s=y$. This is one vector equation, not full knowledge of the true Hessian. BFGS chooses a structured update, and its usual positive-definiteness preservation requires a positive curvature pair $s^{\mathsf T}y>0$ and a positive-definite starting approximation.

Limited-memory variants retain a small history of curvature pairs instead of a dense matrix. They reduce storage but still require sensible line-search rules and numerical safeguards. The lab remains ordinary gradient descent on the unit quadratic: compare its several-step path with the hand-derived Newton step below. It does not compute Hessians, solve Newton systems, update BFGS matrices, or demonstrate the local convergence rate of a general nonlinear Newton iteration.