First, we need a function that calculates the derivative for the objective function.
The derivative of x^2 is x * 2 and the derivative() function implements this below.
derivative of objective function
def derivative(x):
return x * 2.0
derivative of objective function
def derivative(x):
return x * 2.0
We can define a function that implements the gradient descent optimization algorithm.
The procedure involves starting with a randomly selected point in the search space, then calculating the gradient, updating the position in the search space, evaluating the new position, and reporting the progress. This process is then repeated for a fixed number of iterations. The final point and its evaluation are then returned from the function.
The function gradient_descent() below implements this and takes the name of the objective and gradient functions as well as the bounds on the inputs to the objective function, number of iterations, and step size, then returns the solution and its evaluation at the end of the search.
gradient descent algorithm
def gradient_descent(objective, derivative, bounds, n_iter, step_size):
# generate an initial point
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
# run the gradient descent
for i in range(n_iter):
# calculate gradient
gradient = derivative(solution)
# take a step
solution = solution - step_size * gradient
# evaluate candidate point
solution_eval = objective(solution)
# report progress
print(‘>%d f(%s) = %.5f’ % (i, solution, solution_eval))
return [solution, solution_eval]
gradient descent algorithm
def gradient_descent(objective, derivative, bounds, n_iter, step_size):
# generate an initial point
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
# run the gradient descent
for i in range(n_iter):
# calculate gradient
gradient = derivative(solution)
# take a step
solution = solution - step_size * gradient
# evaluate candidate point
solution_eval = objective(solution)
# report progress
print(‘>%d f(%s) = %.5f’ % (i, solution, solution_eval))
return [solution, solution_eval]
We can then define the bounds of the objective function, the step size, and the number of iterations for the algorithm.
We will use a step size of 0.1 and 30 iterations, both found after a little experimentation.
The seed for the pseudorandom number generator is fixed so that we always get the same sequence of random numbers, and in this case, it ensures that we get the same starting point for the search each time the code is run (e.g. something interesting far from the optima).
…
seed the pseudo random number generator
seed(4)
define range for input
bounds = asarray([[-1.0, 1.0]])
define the total iterations
n_iter = 30
define the maximum step size
step_size = 0.1
perform the gradient descent search
best, score = gradient_descent(objective, derivative, bounds, n_iter, step_size)
…
seed the pseudo random number generator
seed(4)
define range for input
bounds = asarray([[-1.0, 1.0]])
define the total iterations
n_iter = 30
define the maximum step size
step_size = 0.1
perform the gradient descent search
best, score = gradient_descent(objective, derivative, bounds, n_iter, step_size)
Tying this together, the complete example of applying grid search to our one-dimensional test function is listed below.
example of gradient descent for a one-dimensional function
from numpy import asarray
from numpy.random import rand
from numpy.random import seed
objective function
def objective(x):
return x**2.0
derivative of objective function
def derivative(x):
return x * 2.0
gradient descent algorithm
def gradient_descent(objective, derivative, bounds, n_iter, step_size):
# generate an initial point
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
# run the gradient descent
for i in range(n_iter):
# calculate gradient
gradient = derivative(solution)
# take a step
solution = solution - step_size * gradient
# evaluate candidate point
solution_eval = objective(solution)
# report progress
print(‘>%d f(%s) = %.5f’ % (i, solution, solution_eval))
return [solution, solution_eval]
seed the pseudo random number generator
seed(4)
define range for input
bounds = asarray([[-1.0, 1.0]])
define the total iterations
n_iter = 30
define the step size
step_size = 0.1
perform the gradient descent search
best, score = gradient_descent(objective, derivative, bounds, n_iter, step_size)
print(‘Done!’)
print(‘f(%s) = %f’ % (best, score))
example of gradient descent for a one-dimensional function
from numpy import asarray
from numpy.random import rand
from numpy.random import seed
objective function
def objective(x):
return x**2.0
derivative of objective function
def derivative(x):
return x * 2.0
gradient descent algorithm
def gradient_descent(objective, derivative, bounds, n_iter, step_size):
# generate an initial point
solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
# run the gradient descent
for i in range(n_iter):
# calculate gradient
gradient = derivative(solution)
# take a step
solution = solution - step_size * gradient
# evaluate candidate point
solution_eval = objective(solution)
# report progress
print(‘>%d f(%s) = %.5f’ % (i, solution, solution_eval))
return [solution, solution_eval]
seed the pseudo random number generator
seed(4)
define range for input
bounds = asarray([[-1.0, 1.0]])
define the total iterations
n_iter = 30
define the step size
step_size = 0.1
perform the gradient descent search
best, score = gradient_descent(objective, derivative, bounds, n_iter, step_size)
print(‘Done!’)
print(‘f(%s) = %f’ % (best, score))
Running the example starts with a random point in the search space, then applies the gradient descent algorithm, reporting performance along the way.
Note: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.
In this case, we can see that the algorithm finds a good solution after about 27 iterations, with a function evaluation of about 0.0.
Note the optima for this function is at f(0.0) = 0.0.
We would expect that gradient descent with momentum will accelerate the optimization procedure and find a similarly evaluated solution in fewer iterations.
0 f([0.74724774]) = 0.55838
1 f([0.59779819]) = 0.35736
2 f([0.47823856]) = 0.22871
3 f([0.38259084]) = 0.14638
4 f([0.30607268]) = 0.09368
5 f([0.24485814]) = 0.05996
6 f([0.19588651]) = 0.03837
7 f([0.15670921]) = 0.02456
8 f([0.12536737]) = 0.01572
9 f([0.10029389]) = 0.01006
10 f([0.08023512]) = 0.00644
11 f([0.06418809]) = 0.00412
12 f([0.05135047]) = 0.00264
13 f([0.04108038]) = 0.00169
14 f([0.0328643]) = 0.00108
15 f([0.02629144]) = 0.00069
16 f([0.02103315]) = 0.00044
17 f([0.01682652]) = 0.00028
18 f([0.01346122]) = 0.00018
19 f([0.01076897]) = 0.00012
20 f([0.00861518]) = 0.00007
21 f([0.00689214]) = 0.00005
22 f([0.00551372]) = 0.00003
23 f([0.00441097]) = 0.00002
24 f([0.00352878]) = 0.00001
25 f([0.00282302]) = 0.00001
26 f([0.00225842]) = 0.00001
27 f([0.00180673]) = 0.00000
28 f([0.00144539]) = 0.00000
29 f([0.00115631]) = 0.00000
Done!
f([0.00115631]) = 0.000001
0 f([0.74724774]) = 0.55838
1 f([0.59779819]) = 0.35736
2 f([0.47823856]) = 0.22871
3 f([0.38259084]) = 0.14638
4 f([0.30607268]) = 0.09368
5 f([0.24485814]) = 0.05996
6 f([0.19588651]) = 0.03837
7 f([0.15670921]) = 0.02456
8 f([0.12536737]) = 0.01572
9 f([0.10029389]) = 0.01006
10 f([0.08023512]) = 0.00644
11 f([0.06418809]) = 0.00412
12 f([0.05135047]) = 0.00264
13 f([0.04108038]) = 0.00169
14 f([0.0328643]) = 0.00108
15 f([0.02629144]) = 0.00069
16 f([0.02103315]) = 0.00044
17 f([0.01682652]) = 0.00028
18 f([0.01346122]) = 0.00018
19 f([0.01076897]) = 0.00012
20 f([0.00861518]) = 0.00007
21 f([0.00689214]) = 0.00005
22 f([0.00551372]) = 0.00003
23 f([0.00441097]) = 0.00002
24 f([0.00352878]) = 0.00001
25 f([0.00282302]) = 0.00001
26 f([0.00225842]) = 0.00001
27 f([0.00180673]) = 0.00000
28 f([0.00144539]) = 0.00000
29 f([0.00115631]) = 0.00000
Done!
f([0.00115631]) = 0.000001