1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 """Backtracking line search algorithm.
25
26 This file is part of the U{minfx optimisation library<https://sourceforge.net/projects/minfx>}.
27 """
28
29
30 from numpy import dot
31
32
33 -def backtrack(func, args, x, f, g, p, a_init=1.0, rho=0.5, c=1e-4, max_iter=500):
34 """Backtracking line search.
35
36 Procedure 3.1, page 41, from 'Numerical Optimization' by Jorge Nocedal and Stephen J. Wright, 1999, 2nd ed.
37
38 Requires the gradient vector at point xk.
39
40
41 Internal variables
42 ==================
43
44 ai - The step length at line search iteration i.
45 xai - The parameter vector at step length ai.
46 fai - The function value at step length ai.
47
48
49 @param func: The function to minimise.
50 @type func: func
51 @param args: The tuple of arguments to supply to the functions func.
52 @type args: tuple
53 @param x: The parameter vector.
54 @type x: numpy rank-1 array
55 @param f: The function value at the point x.
56 @type f: float
57 @param g: The gradient vector at the point x.
58 @type g: numpy rank-1 array
59 @param p: The descent direction.
60 @type p: numpy rank-1 array
61 @keyword a_init: Initial step length.
62 @type a_init: float
63 @keyword rho: The step length scaling factor (should be between 0 and 1).
64 @type rho: float
65 @keyword c: Constant between 0 and 1 determining the slope for the sufficient decrease condition.
66 @type c: float
67 @keyword maxiter: The maximum number of iterations.
68 @type maxiter: int
69 @return: The parameter vector, minimised along the direction xk + ak.pk, to be used at k+1.
70 @rtype: numpy rank-1 array
71 """
72
73
74 a = a_init
75 f_count = 0
76 i = 0
77
78 while i <= max_iter:
79 fk = func(*(x + a*p,)+args)
80 f_count = f_count + 1
81
82
83 if fk <= f + c*a*dot(g, p):
84 return a, f_count
85 else:
86 a = rho*a
87
88
89 i = i + 1
90
91
92 return a_init * rho ** 10, f_count
93