Question

Consider minimizing the function \(\phi(\mathbf{x})=\mathbf{c}^{T} \mathbf{x}+\frac{1}{2} \mathbf{x}^{T} H \mathbf{x}\), where \(\mathbf{c}=(5.04,-59.4,146.4,-96.6)^{T}\) and $$ H=\left(\begin{array}{cccc} .16 & -1.2 & 2.4 & -1.4 \\ -1.2 & 12.0 & -27.0 & 16.8 \\ 2.4 & -27.0 & 64.8 & -42.0 \\ -1.4 & 16.8 & -42.0 & 28.0 \end{array}\right) $$ Try both Newton and BFGS methods, starting from \(\mathbf{x}_{0}=(-1,3,3,0)^{T}\). Explain why the BFGS method requires significantly more iterations than Newton's.

Short answer

In summary, to minimize a quadratic function using Newton's method and BFGS method, we need to derive the gradient and Hessian of the function, and then follow the respective iterative steps of each algorithm until convergence. Newton's method typically converges faster but requires the computation and inversion of the Hessian. On the other hand, BFGS uses an approximation of the Hessian and, while it might require more iterations to converge, it is more efficient for large-scale optimization problems. Compare the number of iterations required for both methods on the given problem and comment on the performance of each method in this specific case. Keep in mind that the performance might differ for other problems or initial conditions.

Step-by-step solution

Derive the gradient of \(\phi(\mathbf{x})\)

We are given the function \(\phi(\mathbf{x})=\mathbf{c}^T\mathbf{x}+\frac{1}{2} \mathbf{x}^T H \mathbf{x}\). To find the gradient, we need to differentiate this function with respect to the vector \(\mathbf{x}\): $$ \nabla \phi(\mathbf{x}) = \frac{d\phi}{d\mathbf{x}} = \mathbf{c} + H\mathbf{x} $$

Derive the Hessian of \(\phi(\mathbf{x})\)

The Hessian matrix is the second derivative of the function with respect to the vector \(\mathbf{x}\): $$ \nabla^2 \phi(\mathbf{x}) = \frac{d^2\phi}{d\mathbf{x}^2} = H $$

Initialize parameters

Let us initialize the given parameters: the vector \(\mathbf{c}\), the matrix \(H\), and the starting point \(\mathbf{x}_0\). We have: $$ \mathbf{c} = \begin{bmatrix} 5.04 \\ -59.4 \\ 146.4 \\ -96.6 \end{bmatrix}, \quad H = \begin{bmatrix} .16 & -1.2 & 2.4 & -1.4 \\ -1.2 & 12.0 & -27.0 & 16.8 \\ 2.4 & -27.0 & 64.8 & -42.0 \\ -1.4 & 16.8 & -42.0 & 28.0 \end{bmatrix}, \quad \mathbf{x}_0 = \begin{bmatrix} -1 \\ 3 \\ 3 \\ 0 \end{bmatrix} $$

Newton's Method

To apply Newton's method, we need to follow the steps below iteratively until convergence: 1. Calculate the gradient: $$\nabla \phi(\mathbf{x}_k) = \mathbf{c} + H\mathbf{x}_k$$ 2. Calculate the search direction: $$\mathbf{d}_k = -(\nabla^2 \phi(\mathbf{x}_k))^{-1}\nabla \phi(\mathbf{x}_k) = -H^{-1}(\mathbf{c} + H\mathbf{x}_k)$$ 3. Update the solution: $$\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_k$$ 4. Check for convergence: If \(\|\nabla \phi(\mathbf{x}_{k+1})\| < \text{tolerance}\) or the maximum number of iterations is reached, stop. Otherwise, go back to step 1. Implement the algorithm and find the solution using Newton's method.

Broyden-Fletcher-Goldfarb-Shanno (BFGS) Method

For the BFGS method, we need to follow these steps iteratively until convergence: 1. Calculate the gradient: $$\nabla \phi(\mathbf{x}_k) = \mathbf{c} + H\mathbf{x}_k$$ 2. Calculate the search direction: $$\mathbf{d}_k = -B_k^{-1}\nabla \phi(\mathbf{x}_k)$$, where \(B_k\) is an approximation of the Hessian. 3. Update the solution: $$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k\mathbf{d}_k$$, where \(\alpha_k\) is the step size determined by a line-search algorithm. 4. Update the Hessian approximation: Use the updated values of \(\mathbf{x}\) and \(\nabla \phi(\mathbf{x})\) to update \(B_k\) with the BFGS formula. 5. Check for convergence: If \(\|\nabla \phi(\mathbf{x}_{k+1})\| < \text{tolerance}\) or the maximum number of iterations is reached, stop. Otherwise, go back to step 1. Implement the algorithm and find the solution using BFGS method.

Comparison of the two methods

Now that we have found the solution using both methods, compare the number of iterations required for each method. Generally, Newton's method converges faster than BFGS because it uses the exact Hessian and applies a true quadratic model for the function. On the other hand, BFGS uses an approximation of the Hessian and might require more iterations to converge. Note that while Newton's method typically converges faster than BFGS, it has the disadvantage of requiring the computation and inversion of the Hessian, which can be expensive for large-scale problems. In contrast, the BFGS method does not require the computation or inversion of the Hessian, making it more efficient for large-scale optimization problems.

Key concepts

Newton's Method

The process of solving optimization problems often involves finding the point where a given function reaches its minimum value. Newton's method is an iterative algorithm that can be used to solve such optimization problems efficiently, especially when dealing with functions that are twice differentiable. It is designed to find the stationary point of a function where its gradient equals zero, which for convex functions, corresponds to its minimum.

The method begins with an initial guess and iteratively refines this estimate to approach the optimal point. Each iteration of Newton's method involves two main computations: the gradient and the Hessian of the objective function. The gradient provides the direction of the steepest increase, while the Hessian, which is the matrix of second derivatives, gives information about the curvature of the function.

To improve upon the current estimate, Newton's method takes a step in the direction opposite to the gradient, scaled by the inverse of the Hessian matrix. The choice of this direction is based on the Taylor series expansion of the function, which implies that taking a step proportional to the negative inverse Hessian should quickly lead to the minimum if the second-order approximation is valid.

While Newton's method can converge very quickly and is particularly effective for quadratic functions, it does come with the caveat that calculating and inverting the Hessian can be computationally demanding as the size of the problem grows. Therefore, Newton's method is often used when the dimensionality of the problem is not excessively large and the exact Hessian can be readily calculated.

BFGS Method

In contrast to Newton's method, the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method provides a way to optimize functions without the direct use of the Hessian matrix. As an iterative optimization algorithm, BFGS fits into the family of quasi-Newton methods, characterized by their approach to approximate the Hessian matrix rather than computing it explicitly.

The BFGS method relies on updating an approximation of the inverse Hessian matrix at each step. This update is calculated using the differences between successive gradient vectors and position vectors, making the approximation more accurate as the iterations progress. One of the pivotal benefits of this method is that it avoids the potentially heavy computational load of calculating and inverting the exact Hessian matrix, which is particularly advantageous for large-scale problems.

Each step of the BFGS method consists of moving in a direction opposite to the product of the approximate inverse Hessian and the gradient, which intuitively resembles the step in Newton's method. However, because the Hessian is approximated, BFGS tends to require more iterations to converge compared to Newton's method. Even though it might be slower in terms of convergence, the reduced computational overhead per iteration often makes it more suitable for complex or high-dimensional problems.

The updating formula of the inverse Hessian approximation in BFGS also ensures that the updated matrix maintains the positive definiteness, which is crucial for the algorithm to provide a descent direction. Moreover, each step size along the search direction is typically determined using a line-search algorithm to ensure that it satisfies the Wolfe conditions, contributing to the stability and convergence of the method.

Gradient and Hessian Calculation

At the core of many optimization algorithms, including Newton's and BFGS methods, lies the calculation of gradients and Hessians. The gradient of a function provides a vector of first-order partial derivatives, which gives the direction of steepest ascent in the function's value. In optimization, we're often interested in the opposite direction to move towards a local minimum.

For a function \( \phi(\mathbf{x}) \) with vector input \( \mathbf{x} \), the gradient \( abla \phi(\mathbf{x}) \) is calculated by differentiating the function with respect to each dimension of \( \mathbf{x} \). With the gradient, we can understand the slope of \( \phi \) at any point and thus predict which way to move to decrease the function's value when performing optimization.

The Hessian matrix, on the other hand, is a square matrix of second-order partial derivatives of the function. It represents the curvature of the function in various directions and is used to predict how the gradient will change as we move away from a point. This prediction is crucial for Newton's method as the inverse of the Hessian directly influences the step size and direction.

In practice, the explicit calculation of the Hessian can be a daunting task for complex functions or higher-dimensional problems, and it is also computationally expensive to invert at each iteration. BFGS addresses this issue by circumventing the explicit calculation, thus making it more practical for sizable optimization problems. To summarize, while gradient and Hessian calculations form the backbone of optimization methods like Newton's and BFGS, the approaches differ substantially in how they leverage these calculations to find the function's minimum.