he search is not guaranteed to find the optima of the function.
This can happen if a direction is specified that is not large enough to encompass the optima.
For example, if we use a direction of three, then the search will fail to find the optima. We can demonstrate this with a complete example, listed 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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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)))
Running the example, the search reaches a limit of an alpha of 1.0 which gives an end point of -2 evaluating to 49. A long way from the optima at f(5) = 0.0.
start=-5.0, direction=3.0
Alpha: 1.000
f(end) = f(-2.000) = 49.000
1
2
3
start=-5.0, direction=3.0
Alpha: 1.000
f(end) = f(-2.000) = 49.000
Additionally, we can choose the wrong direction that only results in worse evaluations than the starting point.
In this case, the wrong direction would be negative away from the optima, e.g. all uphill from the starting point.
…
define the starting point
point = -5.0
define the direction to move
direction = -3.0
1
2
3
4
5
…
define the starting point
point = -5.0
define the direction to move
direction = -3.0
The expectation is that the search would not converge as it is unable to locate any points better than the starting point.
The complete example of the search that fails to converge is listed 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])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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])
Running the example results in a LineSearchWarning indicating that the search could not 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
1
2
3
4
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