QuasiNewton

Quasi-Newton methods are a class of iterative optimization algorithms that improve upon Newton's method by building an approximation to the Hessian (second-derivative matrix) or its inverse instead of computing it directly at every iteration. They are designed for unconstrained optimization and aim to achieve faster convergence than simple gradient descent without the full computational cost of evaluating and inverting the true Hessian.

At each iteration, the gradient g_k = ∇f(x_k) is computed. The method maintains an approximation B_k of the inverse Hessian (or H_k of the Hessian). The search direction is p_k = -B_k g_k. After taking a step to x_{k+1}, the gradient is updated to g_{k+1}, and the difference vectors s_k = x_{k+1}-x_k and y_k = g_{k+1}-g_k are formed. The inverse Hessian is updated by a rank-two formula:

B_{k+1} = B_k + (y_k y_k^T)/(s_k^T y_k) - (B_k s_k s_k^T B_k)/(s_k^T B_k s_k),

where s_k^T y_k > 0 under appropriate line search. This update preserves symmetry and, with suitable step length choices (for example Wolfe conditions), positive definiteness, yielding reliable descent directions.

Among quasi-Newton methods, BFGS is the most widely used due to robustness and efficiency; DFP is an earlier symmetric update. For large-scale problems, limited-memory variants such as L-BFGS store only a small number of vectors to represent the inverse Hessian, reducing memory usage.

Quasi-Newton methods are valued for their fast, typically superlinear convergence, and their balance of computational cost with robustness. They are applied across fields such as machine learning, engineering, and statistics as practical alternatives to full Newton methods when Hessian evaluation is expensive or impractical.