1 Fundamentals of optimization

Quasi-Newton methods belong to the broader field of numerical optimization, where the goal is to locate a minimum of a function by using iterative improvement. They are especially useful when the function is smooth enough to admit derivative information, but the exact second derivative is too costly to compute directly.

1.1 Objective functions and minimization goals

An objective function assigns a numerical value to each candidate solution, and optimization seeks the input that makes this value as small as possible. In many problems, the function may represent error, loss, energy, or cost. The algorithm repeatedly generates new trial points, each intended to improve upon the previous one.

1.2 Gradients and stationarity conditions

The gradient measures the direction of steepest increase, so moving opposite to it tends to reduce the objective. At a stationary point, the gradient vanishes, although that point may be a minimum, maximum, or saddle point. Optimization methods often stop when the gradient norm becomes small enough to indicate near-stationarity.

1.3 Convexity and local versus global behavior

Convex functions have a single global minimum, which makes optimization comparatively straightforward. Many real problems are nonconvex, meaning several stationary points may exist and the method may converge to a local minimum or saddle point. Quasi-Newton methods are designed to perform well in both convex and moderately nonconvex settings, though guarantees are strongest under convexity and smoothness assumptions.

2 Newton’s method as a foundation

Quasi-Newton methods are best understood as approximate versions of Newton’s method. Newton’s method uses second-order information to choose steps that account for local curvature, often leading to rapid convergence near a solution.

2.1 Newton iteration and its assumptions

Newton’s method updates the current point by solving a linear system involving the Hessian and the gradient. This approach assumes the function is twice differentiable and that the Hessian is sufficiently well behaved near the solution. When these conditions hold, the method can converge very quickly once it is close enough to the optimum.

2.2 Hessian usage and computational burden

The Hessian matrix contains all second partial derivatives and encodes curvature information in multiple directions. For large problems, forming, storing, and factorizing this matrix can be expensive in both time and memory. This cost is a major reason why approximate methods became important in applied optimization.

2.3 Line search and step size selection

Even a direction suggested by Newton’s method may be too aggressive if taken in full. Line search chooses how far to move along a proposed direction, often by seeking sufficient decrease in the objective. This extra step improves stability and helps prevent overshooting in regions where the local quadratic model is only approximate.

3 Core idea of quasi-Newton updates

Quasi-Newton methods replace the exact Hessian with an evolving approximation that is updated from observed behavior of the objective. The approximation is refined using gradient differences, so each iteration contributes new curvature information without requiring second derivatives.

3.1 Hessian and inverse-Hessian approximations

Some formulations update an approximation to the Hessian itself, while others maintain an approximation to its inverse. The inverse form is especially convenient because it directly maps gradients into search directions. Both viewpoints aim to capture curvature efficiently enough to emulate Newton-like progress.

3.2 Secant condition and curvature information

A key principle is the secant condition, which requires the updated approximation to reproduce the most recent observed change in gradient along the most recent step. This condition uses differences between consecutive iterates and gradients to infer local curvature. By fitting this information, the method improves its model of the objective without full second derivatives.

3.3 Low-rank matrix updates

Rather than rebuilding the approximation from scratch, quasi-Newton methods modify it using a structured low-rank correction. This keeps the update inexpensive and preserves useful properties such as symmetry. The rank of the correction is typically one or two, which is enough to incorporate new curvature information while maintaining computational efficiency.

Several update formulas are widely used in practice, each with its own strengths. Among these, BFGS is often regarded as the most broadly effective, while DFP and SR1 offer alternative tradeoffs between robustness, curvature modeling, and numerical behavior.

4.1 BFGS (Broyden–Fletcher–Goldfarb–Shanno)

BFGS is one of the most influential quasi-Newton methods and is commonly used as a default choice for smooth optimization. It maintains a positive-definite inverse-Hessian approximation under suitable conditions, which helps ensure descent directions.

4.1.1 Update formulas and intuition

The BFGS update modifies the current approximation using the latest step and gradient change. Intuitively, it adjusts curvature in the direction just explored while leaving much of the previous model intact. This balance between correction and preservation often produces reliable progress across a wide range of problems.

4.1.2 Positive definiteness and safeguards

If the curvature condition is satisfied, BFGS can preserve positive definiteness, which is important because it helps the search direction remain a descent direction. In practice, line search rules and damping strategies may be used to avoid unstable updates. These safeguards make the method more robust when the objective is noisy or poorly scaled.

4.2 DFP (Davidon–Fletcher–Powell)

DFP is an earlier quasi-Newton formula that also uses gradient differences to update curvature information. It is historically significant and closely related to BFGS, though it is used less often in modern implementations.

4.2.1 Alternative secant-based update

Like BFGS, DFP satisfies the secant condition and seeks to improve the inverse-Hessian estimate after each step. The update formula differs in how it redistributes curvature across directions. This can make DFP behave differently in finite-precision arithmetic and in challenging optimization landscapes.

4.2.2 Practical differences versus BFGS

In many applications, BFGS is preferred because it is often more numerically stable and tends to perform better in practice. DFP may still be of interest in theoretical discussions or specialized settings. The two methods are closely connected and can be viewed as dual formulations of quasi-Newton updating.

4.3 SR1 (Symmetric Rank One)

SR1 uses a simpler rank-one correction and is capable of representing indefinite curvature. This makes it useful in some nonconvex settings, where strict positive definiteness is not always desirable.

4.3.1 When non-positive curvature may help

When the objective has saddle-like regions or curved valleys, allowing indefinite approximations can capture the local geometry more faithfully. SR1 may therefore produce directions that better reflect the actual shape of the function. This can be advantageous for escaping shallow regions or modeling complex curvature patterns.

4.3.2 Stability considerations

SR1 is more delicate than BFGS because its update may fail or become unstable if the denominator in the formula is too small. Implementations often skip the update when the curvature information is insufficient. This selective use improves numerical reliability while retaining the method’s flexibility.

5 Convergence analysis

The convergence behavior of quasi-Newton methods depends on assumptions about smoothness, curvature, and step selection. Under favorable conditions, they can approach the solution rapidly, often faster than first-order methods.

5.1 Conditions for superlinear convergence

Superlinear convergence means the error decreases faster than any fixed linear rate near the solution. For quasi-Newton methods, this typically requires a smooth objective, a suitable line search, and accurate curvature accumulation over time. When these conditions hold, the approximation becomes increasingly faithful and the iterates accelerate toward the minimizer.

5.2 Role of line search and Wolfe conditions

Line search is often paired with Wolfe conditions, which balance sufficient decrease with acceptable directional behavior. These criteria help guarantee progress while preserving the information needed for good quasi-Newton updates. Proper step selection is central to both stability and convergence speed.

5.3 Inexact evaluations and robustness

Real computations often involve rounding error, approximate gradients, or noisy objective values. Quasi-Newton methods are usually fairly robust to moderate inexactness, especially when safeguards are present. However, excessive noise can distort curvature estimates and weaken the quality of the updates.

6 Implementation details

Practical performance depends heavily on numerical details, not just on the formal update rule. Good implementations make careful choices about initialization, scaling, and stopping criteria.

6.1 Choosing initial approximations

The initial inverse-Hessian approximation is often chosen as a scaled identity matrix. This provides a neutral starting point that can be adapted through successive updates. A reasonable scale can improve early progress by matching the typical magnitude of the problem variables.

6.2 Scaling, regularization, and damping

Scaling helps align the algorithm with the geometry of the variables, reducing imbalance between coordinates. Regularization can stabilize the approximation when the update becomes unreliable or nearly singular. Damping modifies the curvature update to avoid abrupt changes, especially when the secant information is weak.

6.3 Handling ill-conditioning

Ill-conditioned problems have directions with very different curvature magnitudes, which can slow convergence and amplify numerical error. Quasi-Newton methods often cope better than simple gradient descent because they learn curvature information over time. Still, preconditioning, rescaling, or safeguarded updates may be necessary in difficult cases.

6.4 Termination criteria and tolerance settings

Stopping rules commonly monitor the gradient norm, the change in objective value, or the size of the step. Tolerance thresholds should be chosen according to the desired accuracy and the noise level in the problem data. If tolerances are too strict, the method may spend many iterations chasing negligible improvement.

7 Practical variants for large-scale problems

For very high-dimensional problems, storing full matrix approximations may be impractical. Large-scale variants preserve the main advantages of quasi-Newton ideas while reducing memory and computation.

7.1 Limited-memory quasi-Newton (L-BFGS)

L-BFGS stores only a small number of recent correction pairs instead of a full matrix. This makes it suitable for large problems in machine learning and scientific computing. Despite its compact representation, it often retains much of the practical effectiveness of full BFGS.

7.1.1 Storing curvature pairs efficiently

The method keeps recent step vectors and gradient-difference vectors, known as curvature pairs. These pairs summarize the most useful local information without requiring matrix storage. As older pairs are discarded, memory usage stays bounded.

7.1.2 Two-loop recursion for search direction

The two-loop recursion is an efficient procedure for applying the implicit inverse-Hessian approximation to a gradient vector. It reconstructs the search direction using the stored curvature pairs in two passes. This algorithm is central to the practicality of L-BFGS.

7.2 Coordinate and stochastic adaptations

Some variants adapt quasi-Newton ideas to coordinate updates or noisy gradient estimates. These methods are useful when data arrive in batches or when only partial information is available at each step. Their performance depends strongly on how well curvature memory is preserved despite randomness.

8 Algorithm workflow

A quasi-Newton solver typically follows a repeated sequence of evaluation, direction computation, step selection, and update. This structure is simple in outline but requires careful coordination between its components.

8.1 Iteration loop: gradients, update, direction

Each iteration begins by evaluating the gradient at the current point. The algorithm then uses its current curvature approximation to compute a search direction. After moving to a new point, it updates the approximation using the observed step and gradient change.

8.2 Line search subroutine integration

The line search is often embedded directly within the iteration loop. It selects a step length that improves the objective while maintaining conditions needed for a reliable update. This integration helps the method remain stable across a wide variety of problems.

8.3 Logging and diagnosing optimization progress

Practical implementations often record objective values, gradient norms, step sizes, and update quality. These logs help identify slow convergence, poor scaling, or numerical difficulties. Diagnostic information is especially useful when tuning parameters or comparing algorithm variants.

9 Applications

Quasi-Newton methods are widely used because they provide a strong compromise between speed and computational cost. They are especially attractive when exact second derivatives are unavailable or unnecessarily expensive.

9.1 Unconstrained smooth optimization

In unconstrained smooth problems, quasi-Newton methods are a standard tool for finding minima efficiently. They are common in engineering design, parameter estimation, and model fitting. Their ability to adapt to curvature makes them effective on many classical benchmark problems.

9.2 Regularized empirical risk minimization

In machine learning, quasi-Newton methods are often applied to objective functions formed by averaging losses over data and adding regularization terms. Their fast convergence can reduce training time when gradients are moderately expensive. L-BFGS is particularly popular in this setting because it scales well to many variables.

9.3 Numerical problems requiring derivative efficiency

Some scientific and engineering tasks require repeated optimization with expensive simulation-based objectives. Quasi-Newton methods are valuable there because they extract curvature information from gradient history rather than from costly second-derivative calculations. This makes them a practical choice when function evaluations dominate the budget.

Quasi-Newton methods sit between first-order and full second-order approaches. They share ideas with several other optimization families, including methods based on linear algebra, memory of past gradients, and region-based step control.

10.1 Truncated Newton and conjugate-gradient methods

Truncated Newton methods approximate the Newton step by solving the associated linear system only partially, often with conjugate-gradient iterations. Like quasi-Newton methods, they aim to gain second-order advantages without full Hessian factorization. The main difference is that truncated Newton methods work more directly with Hessian-vector products, while quasi-Newton methods build an explicit or implicit curvature approximation.

10.2 Gradient descent with curvature memory

Quasi-Newton methods can be viewed as an enhanced form of gradient descent that remembers past curvature information. Instead of using a fixed step rule, they adjust the search direction based on accumulated local geometry. This memory is what gives them much of their superior convergence behavior.

Trust-region methods choose steps by optimizing within a region where the model is considered reliable, rather than by moving along a single direction with line search. Both frameworks aim to control step quality and improve robustness. Quasi-Newton updates can be combined with either approach, although line search is more common in standard implementations.