Nonlinear-Optimization-Methods

The idea behind Quasi-Newton methods is to approximate the Hessian matrix at each iteration by incorporating gradient information into the Newton method, thereby avoiding the need for direct computation of the Hessian.

1. Overview

We implement two classical quasi-Newton methods for unconstrained optimization:

• BFGS: Broyden–Fletcher–Goldfarb–Shanno method
• DFP: Davidon–Fletcher–Powell method

Both methods minimize a differentiable objective function

$$ \min_{x\in\mathbb{R}^n} f(x), $$

The exact Hessian matrix

$$ \nabla^2 f(x) $$

is not explicitly computed during the optimization. Instead, BFGS and DFP construct an approximation of the inverse Hessian matrix. This approximation is updated using information obtained from successive iterates and gradients.

2. Newton's Method and the Quasi-Newton Idea

For a twice-differentiable function, Newton's method determines the search direction by solving

$$ \nabla^2 f(x_k)p_k=-\nabla f(x_k). $$

Equivalently,

$$ p_k=-\left[\nabla^2 f(x_k)\right]^{-1}\nabla f(x_k). $$

Newton's method can converge very rapidly near a minimizer, but it has two important disadvantages:

1. The Hessian must be computed.
2. A linear system involving the Hessian must be solved at every iteration.

Quasi-Newton methods avoid direct Hessian computation. They maintain a matrix $$(H_k)$$ satisfying approximately

$$ H_k\approx \left[\nabla^2 f(x_k)\right]^{-1}. $$

The search direction is then calculated as

$$ p_k=-H_k g_k, $$

where

$$ g_k=\nabla f(x_k). $$

After choosing a step length $$\alpha_k$$, the next point is

$$ x_{k+1}=x_k+\alpha_kp_k. $$

The corresponding displacement and gradient change are defined by

$$ s_k=x_{k+1}-x_k, $$

and

$$ y_k=g_{k+1}-g_k. $$

The vectors $$(s_k)$$ and $$(y_k)$$ provide an approximation to the curvature information of the objective function.

3. The Secant Condition

The exact inverse Hessian satisfies approximately

$$ \left[\nabla^2 f(x_k)\right]^{-1}y_k\approx s_k. $$

Therefore, a new inverse Hessian approximation $$(H_{k+1})$$ is expected to satisfy the secant condition

$$ H_{k+1}y_k=s_k. $$

Both BFGS and DFP construct matrix updates that satisfy this condition while changing the previous approximation as little as possible.

The curvature quantity

$$ s_k^Ty_k $$

plays a central role. For a positive-definite Hessian approximation, it is desirable that

$$ s_k^Ty_k>0. $$

When this condition is not satisfied, the update may destroy the positive definiteness of $$(H_k)$$. Therefore, the implementation only performs the update when the curvature conditions are numerically acceptable.

4. BFGS Method

4.1 Hessian update

The BFGS update for the inverse Hessian approximation is

$$ H_{k+1}=\left(I-\rho_k s_ky_k^T\right)H_k\left(I-\rho_k y_ks_k^T\right)+\rho_k s_ks_k^T, $$

where

$$ \rho_k=\frac{1}{y_k^Ts_k}. $$

An equivalent expanded form is

$$ H_{k+1}=H_k+\frac{s_ks_k^T}{y_k^Ts_k}-\frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}. $$

The BFGS direction is

$$ p_k=-H_kg_k. $$

If $$(H_k)$$ is positive definite and

$$ s_k^Ty_k>0, $$

then the updated matrix $$(H_{k+1})$$ is also positive definite. Consequently,

$$ g_k^Tp_k=-g_k^TH_kg_k<0, $$

so $$(p_k)$$ is a descent direction.

4.2 Characteristics

BFGS is widely used because it generally has good numerical stability and strong practical performance. It is especially effective for problems where the objective function has curved or narrow valleys, such as the Rosenbrock function.

BFGS usually provides a reliable compromise between:

• computational cost;
• numerical stability;
• convergence speed;
• preservation of positive definiteness.

5. DFP Method

5.1 Hessian update

The DFP update is

$$ H_{k+1}=H_k+ \frac{s_ks_k^T}{y_k^Ts_k}- \frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k}. $$

Using

$$ H_ky_k $$

as an intermediate vector, the second correction term can also be written as

$$ \frac{(H_ky_k)(H_ky_k)^T}{y_k^TH_ky_k}. $$

The DFP search direction is also

$$ p_k=-H_kg_k. $$

The DFP update satisfies the secant condition

$$ H_{k+1}y_k=s_k. $$

If $$(H_k)$$ is positive definite and the denominators are positive, the update can preserve positive definiteness.

5.2 Characteristics

DFP was one of the earliest quasi-Newton methods. It has a similar mathematical structure to BFGS, but the correction terms are arranged differently.

In many practical optimization problems, BFGS is more robust than DFP. DFP may be more sensitive to:

• inaccurate line searches;
• round-off errors;
• poor curvature information;
• nearly singular update denominators.

Nevertheless, DFP is important because it provides a useful comparison with BFGS and illustrates the symmetry between Hessian and inverse-Hessian approximation methods.

6. Line Search

The search direction alone does not determine the next iterate. A step length $$(\alpha_k)$$ must also be selected:

$$ x_{k+1}=x_k+\alpha_kp_k. $$

The implementation considers two line-search strategies:

1. Armijo backtracking;
2. weak Wolfe line search.

6.1 Armijo sufficient-decrease condition

The Armijo condition requires

$$ f(x_k+\alpha_kp_k) \leq f(x_k)+c_1\alpha_k g_k^Tp_k, $$

where

$$ 0\lt c_1\lt 1. $$

Since $$(p_k)$$ is a descent direction,

$$ g_k^Tp_k\lt 0. $$

Therefore, the right-hand side is smaller than $$(f(x_k))$$, and the condition requires a sufficient reduction in the objective function.

A typical backtracking procedure starts with

$$ \alpha=1 $$

and repeatedly reduces the step length according to

$$ \alpha\leftarrow\beta\alpha, $$

where

$$ 0<\beta<1. $$

Armijo backtracking is simple and inexpensive, but it only examines the function value. It does not directly control the gradient behavior at the new point.

6.2 Weak Wolfe conditions

The weak Wolfe line search requires both sufficient decrease and a curvature condition.

• Sufficient decrease

$$ f(x_k+\alpha_kp_k) \leq f(x_k)+c_1\alpha_k g_k^Tp_k. $$

• Curvature condition

$$ \nabla f(x_k+\alpha_kp_k)^Tp_k \geq c_2g_k^Tp_k, $$

where

$$ 0\lt c_1\lt c_2\lt 1. $$

The first condition prevents the step from being too large. The second condition prevents the step from being excessively small and ensures that the directional derivative has been reduced sufficiently.

Because

$$ g_k^Tp_k<0, $$

the curvature condition requires the new directional derivative to be less negative than the initial one.

The weak Wolfe conditions are particularly useful for quasi-Newton methods because they are more closely related to maintaining the curvature condition

$$ s_k^Ty_k>0. $$

6.3 Bracketing and zooming

A Wolfe line search generally consists of two stages:

1. Bracketing phase: increase the trial step length until a suitable interval containing an acceptable step is found.
2. Zoom phase: repeatedly reduce the interval and search for a step satisfying both Wolfe conditions.

The implementation uses a safeguarded bisection strategy during the zoom phase. This is simpler than interpolation-based methods, although it may require more function and gradient evaluations.

References

• Broyden, C. G., Fletcher, R., Goldfarb, D., and Shanno, D. F. Quasi-Newton methods for unconstrained optimization.
• Nocedal, J. and Wright, S. J. Numerical Optimization.
• Fletcher, R. Practical Methods of Optimization.