Descent method — Steepest descent and conjugate gradient in Python

Python implementation

Sophia Yang, Ph.D.


Let’s start with this equation and we want to solve for x:

The solution x the minimize the function below when A is symmetric positive definite (otherwise, x could be the maximum). It is because the gradient of f(x), ∇f(x) = Ax- b. And when Ax=b, ∇f(x)=0 and thus x is the minimum of the function.

In this article, I am going to show you two ways to find the solution x — method of Steepest Descent and method of Conjugate Gradient.

Method of Steepest Descent in Python

Now let’s use this steepest_descent function to calculate

With the steepest_descent method, we get a value of (-4,5) and a wall time 2.01ms.

Conjugate gradient method in Python

With the conjugate_gradient function, we got the same value (-4, 5) and wall time 281 μs, which is a lot faster than the steepest descent.

Visualizing steepest descent and conjugate gradient descent