Optimizing with Linear Search in Python

Linear search is an optimization algorithm that can be used for objective functions with one or more variables. It provides the ability to use a one-dimensional optimization algorithm such as bisection search for a multidimensional objective function, working with a linear search to determine the optimal step size in each dimension from a known point to the optimum. We’ve already shared Jason Brownlee’s translations, such as an article on mixed ensembles, and in this tutorial, which we translated at the start of the course on machine and deep learning, explains the basics: you will learn how to optimize using linear search in Python.


By reading this guide, you will learn:

  • that linear search is an optimization algorithm for one-dimensional and multidimensional optimization problems;

  • that the SciPy library provides a linear search API that requires knowledge of how the first derivative of your objective function is calculated;

  • how to perform a linear search for an objective function and work with the result.

Let’s start.

Overview

This tutorial is divided into three parts:

  1. What is Linear Search?

  2. Linear search in Python.

  3. How is linear search done? It consists of:

a) definition of the objective function;

b) performing a linear search;

c) work with algorithm failures.

What is Linear Search?

Linear search Is an optimization algorithm for one-dimensional or multi-dimensional optimization. It requires a starting position in the search space as well as an indication of the direction of the search. Then, from the initial one, he selects the next position in the search space, which will lead to the value better or to the best value of the objective function.

The direction has a plus or minus sign along the line and the maximum length of the search, therefore it is better to consider it as a search area for candidates, it must be large enough to cover the optima or a point better than the initial one.

Linear search will automatically select a scale factor, called alpha, for the step size (direction) based on the current target minimizing position. To find the optimal point in the selected direction and select the appropriate alpha, another one-dimensional optimization algorithm is used

One approach is to apply a linear search that selects a step factor that minimizes the one-dimensional function […]… We can apply the one-dimensional optimization method of our choice.

Optimization algorithms, 2019 .– P. 54.

Alpha is the scale factor for the direction, so only values ​​in the range 0.0 to 1.0 are considered in the search. One step of the linear search solves the minimization problem, which minimizes the objective function for the current position in the sum with the scalable direction, that is:

  • Minimizes objective (position + alpha * direction).

Thus, linear search works one dimension at a time and returns the distance to move in the selected direction.

Each iteration of the linear search method calculates the search direction pk and then decides how far to go in that direction.

Numerical optimization, 2006 .– S. 30.

To move the search space to the solution, the linear search can be called again and may fail if the selected direction does not contain points with a lower objective function value, for example, when the algorithm is directed to search up a slope.

The solution is approximate or imprecise, and depending on the shape of the search space, it may not be a general solution. The conditions under which this algorithm is suitable are called Wolf conditions… Now that we are familiar with linear search, let’s see how to do it in Python.

Linear search in Python

You can do a linear search in Python manually using the function line_search ()… It supports one-dimensional optimization as well as multi-dimensional optimization problems. This function takes the name of the objective function and the name of the gradient for the objective function, as well as the current position in the search space and the direction of movement.

Thus, you must know the first derivative of your objective function. You should also have some idea of ​​where to start your search and how broadly to do it. Recall that a search can be performed several times with different directions (sign and length).

...
result = line_search(objective, gradient, point, direction)

The function returns a tuple of six elements, including a scale factor for the direction, called alpha, and the number of function evaluations performed, and other values. The first element in the resulting tuple contains alpha. If the search fails, alpha will matter None

...
# retrieve the alpha value found as part of the line search
alpha = result[0]

Alpha, starting point and direction can be used to construct the endpoint of a linear search.

...
# construct the end point of a line search
end = point + alpha * direction

For optimization problems with more than one input variable, such as multivariate optimization, the function line_search () will return one alpha value for all dimensions. This means that the function assumes that the optimum is equidistant from the starting point in all dimensions, such a limitation is significant. Now that we have seen how to perform linear search in Python, let’s look at a working example.

How is linear search done?

We can demonstrate how to use linear search with a simple one-dimensional objective function and its derivative. This section, in turn, is divided into several parts, including defining a test function, performing a linear search, and handling failures when the optimum is not found.

Objective function definition

First, we can define an objective function. Here we will work with a one-dimensional objective function, namely, with a function x ^ 2 shifted by a small amount from zero. It is a convex function and was chosen because it is easy to understand and also easy to calculate the first derivative.

  • objective (x) = (-5 + x) ^ 2.

Please note that linear search is not limited to one-dimensional or convex functions. The implementation of this function is shown below.

# objective function
def objective(x):
	return (-5.0 + x)**2.0

The first derivative of this function can be calculated analytically as follows:

  • gradient (x) = 2 * (-5 + x).

The gradient for each input simply indicates the slope to the optima at each point. The implementation of the gradient function is shown below:

# gradient for the objective function
def gradient(x):
	return 2.0 * (-5.0 + x)

You can define the input range for x from -10 to 20 and calculate the target value for each input:

...
# define range
r_min, r_max = -10.0, 20.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]

Then, to get an idea of ​​the shape of the function, we can plot the input values ​​against the target values:

...
# plot inputs vs objective
pyplot.plot(inputs, targets, '-', label="objective")
pyplot.legend()
pyplot.show()

Putting it all together, we get the following code:

# plot a convex objective function
from numpy import arange
from matplotlib import pyplot
 
# objective function
def objective(x):
	return (-5.0 + x)**2.0
 
# gradient for the objective function
def gradient(x):
	return 2.0 * (-5.0 + x)
 
# define range
r_min, r_max = -10.0, 20.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs objective
pyplot.plot(inputs, targets, '-', label="objective")
pyplot.legend()
pyplot.show()

The program calculates input (x) values ​​in the range -10 to 20 and creates a graph showing the familiar U-shape of a parabola. The optimum of the function, apparently, is at the point x = 5.0, the target value is 0.0.

Linear Plot of Convex Objective Function
Linear Plot of Convex Objective Function

Performing a Linear Search

You can then perform a linear search on this function. First, we must define the starting point of the search and its direction. Here we will use the starting point x = -5, the distance from which to the optimum is about 10 units. Let’s take a big step to the right, in this case 100 units (which is significantly higher than the optimum), for example, in a positive direction. Recall that the direction is similar to the stride size and search scales the stride size to find the optimum:

...
# define the starting point
point = -5.0
# define the direction to move
direction = 100.0
# print the initial conditions
print('start=%.1f, direction=%.1f' % (point, direction))
# perform the line search
result = line_search(objective, gradient, point, direction)

The search then looks for optima and returns alpha or distance to change direction. From the result, we can get the alpha value, as well as the number of function calculations performed:

...
# summarize the result
alpha = result[0]
print('Alpha: %.3f' % alpha)
print('Function evaluations: %d' % result[1])

We can use alpha, along with our starting point and step size, to compute the location of the optima and calculate the objective function at that point (which we expect to be 0.0):

...
# define objective function minima 
end = point + alpha * direction
# evaluate objective function minima
print('f(end) = %.3f' % objective(end))

Then, for fun, we can plot the function again and show the start point as a green square and the end point as a red square.

...
# define range
r_min, r_max = -10.0, 20.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs objective
pyplot.plot(inputs, targets, '--', label="objective")
# plot start and end of the search
pyplot.plot([point], [objective(point)], 's', color="g")
pyplot.plot([end], [objective(end)], 's', color="r")
pyplot.legend()
pyplot.show()

The following is a complete example of performing a linear search for a convex objective function:

# perform a line search on a convex objective function
from numpy import arange
from scipy.optimize import line_search
from matplotlib import pyplot
 
# objective function
def objective(x):
	return (-5.0 + x)**2.0
 
# gradient for the objective function
def gradient(x):
	return 2.0 * (-5.0 + x)
 
# define the starting point
point = -5.0
# define the direction to move
direction = 100.0
# print the initial conditions
print('start=%.1f, direction=%.1f' % (point, direction))
# perform the line search
result = line_search(objective, gradient, point, direction)
# summarize the result
alpha = result[0]
print('Alpha: %.3f' % alpha)
print('Function evaluations: %d' % result[1])
# define objective function minima
end = point + alpha * direction
# evaluate objective function minima
print('f(end) = f(%.3f) = %.3f' % (end, objective(end)))
# define range
r_min, r_max = -10.0, 20.0
# prepare inputs
inputs = arange(r_min, r_max, 0.1)
# compute targets
targets = [objective(x) for x in inputs]
# plot inputs vs objective
pyplot.plot(inputs, targets, '--', label="objective")
# plot start and end of the search
pyplot.plot([point], [objective(point)], 's', color="g")
pyplot.plot([end], [objective(end)], 's', color="r")
pyplot.legend()
pyplot.show()

The sample program first reports the starting point and direction. The search is performed, and the alpha value that changes direction for finding the optimum is found, in this case, the value found after three calculations of the function 0.1. The optimum point is at 5.0, the y-value, as expected, is 0.0:

start=-5.0, direction=100.0
Alpha: 0.100
Function evaluations: 3
f(end) = f(5.000) = 0.000

Finally, a function graph is generated showing a green starting point and a red target.

Linear graph of the objective function with optima and the starting point of the search
Linear graph of the objective function with optima and the starting point of the search

Dealing with algorithm failures

Linear search does not guarantee finding the optima of the function. It may not find the optima if the direction value is not large enough to cover them. For example, it will be impossible to find the optima when the direction is 3. This can be demonstrated with the full example below:

# perform a line search on a convex objective function with a direction that is too small
from numpy import arange
from scipy.optimize import line_search
from matplotlib import pyplot
 
# objective function
def objective(x):
	return (-5.0 + x)**2.0
 
# gradient for the objective function
def gradient(x):
	return 2.0 * (-5.0 + x)
 
# define the starting point
point = -5.0
# define the direction to move
direction = 3.0
# print the initial conditions
print('start=%.1f, direction=%.1f' % (point, direction))
# perform the line search
result = line_search(objective, gradient, point, direction)
# summarize the result
alpha = result[0]
print('Alpha: %.3f' % alpha)
# define objective function minima
end = point + alpha * direction
# evaluate objective function minima
print('f(end) = f(%.3f) = %.3f' % (end, objective(end)))

When running the example, the search reaches the alpha limit of 1.0, which gives an endpoint between -2 and 49. With f (5) = 0.0, the optima is very far away:

start=-5.0, direction=3.0
Alpha: 1.000
f(end) = f(-2.000) = 49.000

In addition, we may choose the wrong direction, leading only to calculations worse than the starting point. Here it will be negative towards the optimum, for example, up the slope from the starting point:

...
# define the starting point
point = -5.0
# define the direction to move
direction = -3.0

The search is expected to fail because it cannot find any better than the starting point. A complete example of a search that does not converge is shown below:

# perform a line search on a convex objective function that does not converge
from numpy import arange
from scipy.optimize import line_search
from matplotlib import pyplot
 
# objective function
def objective(x):
	return (-5.0 + x)**2.0
 
# gradient for the objective function
def gradient(x):
	return 2.0 * (-5.0 + x)
 
# define the starting point
point = -5.0
# define the direction to move
direction = -3.0
# print the initial conditions
print('start=%.1f, direction=%.1f' % (point, direction))
# perform the line search
result = line_search(objective, gradient, point, direction)
# summarize the result
print('Alpha: %s' % result[0])

Program execution results in a LineSearchWarning warning indicating that the search cannot converge as expected. The alpha value returned from the search is None:

start=-5.0, direction=-3.0
LineSearchWarning: The line search algorithm did not converge
warn('The line search algorithm did not converge', LineSearchWarning)
Alpha: None

Further reading

If you want to dive deeper into the topic, see this section.

Books

API

Articles

Summary

In this tutorial, you learned how to perform linear search optimization in Python. In particular, you learned:

  • that linear search is an optimization algorithm for one-dimensional and multidimensional optimization problems;

  • that the SciPy library provides a linear search API that requires knowledge of how the first derivative of your objective function is calculated;

  • how to perform a linear search for an objective function and work with its result.

Optimization techniques used in machine learning are of course not limited to linear search, they are numerous, varied, and each has its own disadvantages and advantages. If you want to dive into machine learning, study optimization deeper, but do not want to limit yourself to the ML field, you can pay attention to our course “Machine Learning and Deep Learning”, whose partner, NVIDIA, needs no introduction.

find outhow to level up in other specialties or master them from scratch:

Other professions and courses

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *