Source Code for Module minfx.line_search.backtrack

 1  ############################################################################### 
 2  #                                                                             # 
 3  # Copyright (C) 2003-2013 Edward d'Auvergne                                   # 
 4  #                                                                             # 
 5  # This file is part of the minfx optimisation library,                        # 
 6  # https://gna.org/projects/minfx                                              # 
 7  #                                                                             # 
 8  # This program is free software: you can redistribute it and/or modify        # 
 9  # it under the terms of the GNU General Public License as published by        # 
10  # the Free Software Foundation, either version 3 of the License, or           # 
11  # (at your option) any later version.                                         # 
12  #                                                                             # 
13  # This program is distributed in the hope that it will be useful,             # 
14  # but WITHOUT ANY WARRANTY; without even the implied warranty of              # 
15  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               # 
16  # GNU General Public License for more details.                                # 
17  #                                                                             # 
18  # You should have received a copy of the GNU General Public License           # 
19  # along with this program.  If not, see <http://www.gnu.org/licenses/>.       # 
20  #                                                                             # 
21  ############################################################################### 
22   
23  # Module docstring. 
24  """Backtracking line search algorithm. 
25   
26  This file is part of the U{minfx optimisation library<https://gna.org/projects/minfx>}. 
27  """ 
28   
29  # Python module imports. 
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      # Initialise values. 
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          # Check if the sufficient decrease condition is met.  If not, scale the step length by rho. 
83          if fk <= f + c*a*dot(g, p): 
84              return a, f_count 
85          else: 
86              a = rho*a 
87   
88          # Increment the counter. 
89          i = i + 1 
90   
91      # Right, couldn't find it before max_iter so return the function count and a step length significantly smaller than the starting length. 
92      return a_init * rho ** 10, f_count 
93