BFGS Optimization Algorithm

It is a quasi-Newton family of optimization algorithms that uses a finite amount of memory to mimic the Broyden-Fletcher-Goldfarb-Shanno algorithm (BFGS algorithm). It is a well-liked machine learning approach for parameter estimation.

In this article, we will understand more about the BFGS algorithm, the working example of BFGS, the L-BFGS algorithm, and the algorithm steps involved in BFGS. 

BFGS Algorithm

An algorithm for second-order optimization is called BFGS. It is an abbreviation that honors the algorithm’s four co-discoverers, Fletcher, Broyden, Goldfarb, and Shanno. This local search algorithm is designed for a convex optimization problem with a single optimum.

You must explore: What are Algorithms?

The best way to understand the Broyden-Fletcher-Goldfarb-Shanno algorithm is to think of it as a member of the Quasi-Newton Methods algorithmic family, an extension of Newton’s Method optimization algorithm. The Hessian matrix is used by Newton’s technique, a second-order optimization process.

The fact that the inversion of the Hessian matrix must be calculated is a drawback of Newton’s approach. Depending on the characteristics of the objective function, this is a relatively expensive procedure that might need to be more stable.

The inverse Hessian can be modified, as opposed to being re-computed after each iteration, using the Broyden-Fletcher-Goldfarb-Shanno algorithm. It may be one of the most widely used second-order or quasi-Newton optimization techniques for numerical optimization or one of its extensions.

You can also explore: What is Rabin Karp Algorithm?

L-BFGS Algorithm

It is an improvement to the Broyden-Fletcher-Goldfarb-Shanno algorithm taking into account the expense of having numerous parameters. By assuming that the inverse Hessian was simplified in the last iteration of that method, it avoids the need for storing the whole estimate of the inverse matrix (usually used for approximation).

You can also explore: Introduction to Greedy Algorithm

BFGS Algorithm in Python

Using the SciPy function minimize(), a user is able to build the BFGS algorithm in Python to optimize any function.

In particular, we can specify the objective function’s name as the first parameter, the search’s starting point as the 2nd arg, and the “method” argument as “BFGS” when calling the function. The “jac” parameter allows the user to specify the function name that is further used to calculate the objective function’s derivative.

Step 1: Performing searching in Broyden-Fletcher-Goldfarb-Shanno algorithm

result = minimize(objective, pt, method=’BFGS’, jac=derivative)

Step 2: The following is the objective function. A straightforward bowl function in 2-D might be defined, for instance, as x2. It is only the squared sum of the input variables, with f(0, 0) = 0.0 serving as its optimal value.

def objective(x):return x[0]**2.0 + x[1]**2.0

Step 3: This step will include the derivative of the previous objective function. Let’s create a function to represent the function’s derivative, which is [x*2, y*2].

def derivative(x):return [x[0] * 2, x[1] * 2]

Step 4: This step will define the range for the output. The box that contains the function’s boundaries will have a range of -5 and 5

r_min, r_max = -5.0, 5.0

Step 5: The search will begin at a randomly chosen location within the search domain.

pt = r_min + rand(2) * (r_max – r_min)

Step 6: By providing the objective name for the function along with the detail of the starting point, the methodology BFGS, along with the derivative name, we can then apply the BFGS algorithm to identify the minima of the objective function.

result = minimize(objective, pt, method=’BFGS’, jac=derivative)

Complete BFGS algorithm code in python is given below:

The output of the above code will be:

Status: Optimization terminated successfully. Total Evaluations: 4 Solution: f([0.00000000e+00 1.11022302e-16]) = 0.00000

Must explore: All About Floyd-Warshall Algorithm

Conclusion

In this article, we have discussed the Broyden-Fletcher-Goldfarb-Shanno algorithm in detail. It is a quasi-Newton family of optimization algorithms that uses a finite amount of memory to mimic the Broyden-Fletcher-Goldfarb-Shanno algorithm (BFGS). It is a well-liked machine learning approach for parameter estimation. We have also talked about the working example of BFGS, the L-BFGS algorithm, and the algorithm involved in BFGS. 

Author: Megha Garg