Package minfx :: Module coordinate_descent
[hide private]
[frames] | no frames]

Source Code for Module minfx.coordinate_descent

  1  ############################################################################### 
  2  #                                                                             # 
  3  # Copyright (C) 2003-2013 Edward d'Auvergne                                   # 
  4  #                                                                             # 
  5  # This file is part of the minfx optimisation library,                        # 
  6  # https://sourceforge.net/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  """Back-and-forth coordinate descent (CD) optimization. 
 25   
 26  This file is part of the U{minfx optimisation library<https://sourceforge.net/projects/minfx>}. 
 27  """ 
 28   
 29  # Python module imports. 
 30  from numpy import dot, float64, identity 
 31   
 32  # Minfx module imports. 
 33  from minfx.base_classes import Line_search, Min 
 34   
 35   
36 -def coordinate_descent(func=None, dfunc=None, args=(), x0=None, min_options=None, func_tol=1e-25, grad_tol=None, maxiter=1e6, a0=1.0, mu=0.0001, eta=0.1, full_output=0, print_flag=0, print_prefix=""):
37 """Back-and-forth coordinate descent minimisation.""" 38 39 if print_flag: 40 if print_flag >= 2: 41 print(print_prefix) 42 print(print_prefix) 43 print(print_prefix + "Back-and-forth coordinate descent minimisation") 44 print(print_prefix + "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~") 45 min = Coordinate_descent(func, dfunc, args, x0, min_options, func_tol, grad_tol, maxiter, a0, mu, eta, full_output, print_flag, print_prefix) 46 if min.init_failure: 47 print(print_prefix + "Initialisation of minimisation has failed.") 48 return None 49 results = min.minimise() 50 return results
51 52
53 -class Coordinate_descent(Line_search, Min):
54 - def __init__(self, func, dfunc, args, x0, min_options, func_tol, grad_tol, maxiter, a0, mu, eta, full_output, print_flag, print_prefix):
55 """Class for back-and-forth coordinate descent minimisation specific functions. 56 57 Unless you know what you are doing, you should call the function 'coordinate_descent' rather than using this class. 58 """ 59 60 # Function arguments. 61 self.func = func 62 self.dfunc = dfunc 63 self.args = args 64 self.xk = x0 65 self.func_tol = func_tol 66 self.grad_tol = grad_tol 67 self.maxiter = maxiter 68 self.full_output = full_output 69 self.print_flag = print_flag 70 self.print_prefix = print_prefix 71 72 # Set a0. 73 self.a0 = a0 74 75 # Line search constants for the Wolfe conditions. 76 self.mu = mu 77 self.eta = eta 78 79 # Initialisation failure flag. 80 self.init_failure = 0 81 82 # Setup the line search options and algorithm. 83 self.line_search_options(min_options) 84 self.setup_line_search() 85 86 # Initialise the function, gradient, and Hessian evaluation counters. 87 self.f_count = 0 88 self.g_count = 0 89 self.h_count = 0 90 91 # Initialise the warning string. 92 self.warning = None 93 94 # Set the convergence test function. 95 self.setup_conv_tests() 96 97 # The initial function value and gradient vector. 98 self.fk, self.f_count = self.func(*(self.xk,)+self.args), self.f_count + 1 99 self.dfk, self.g_count = self.dfunc(*(self.xk,)+self.args), self.g_count + 1 100 101 # Create the coordinate descent directions, and initialise the coordinate descent iteration number and direction flag. 102 self.cd_dir = identity(len(self.xk), float64) 103 self.n = 0 104 self.back = 0
105 106
107 - def new_param_func(self):
108 """The new parameter function. 109 110 Find the search direction, do a line search, and get xk+1 and fk+1. 111 """ 112 113 # Get the coordinate descent direction (pk is forced to be a descent direction). 114 if dot(self.dfk, self.cd_dir[self.n]) > 0.0: 115 self.pk = -self.cd_dir[self.n] 116 else: 117 self.pk = self.cd_dir[self.n] 118 119 # Line search. 120 self.line_search() 121 122 # Find the new parameter vector and function value at that point. 123 self.xk_new = self.xk + self.alpha * self.pk 124 self.fk_new, self.f_count = self.func(*(self.xk_new,)+self.args), self.f_count + 1 125 self.dfk_new, self.g_count = self.dfunc(*(self.xk_new,)+self.args), self.g_count + 1 126 127 # Scale the coordinate direction to minimise the number of function calls. 128 self.cd_dir[self.n] = self.alpha * self.pk
129 130
131 - def update(self):
132 """Function to update the function value, gradient vector, and Hessian matrix.""" 133 134 # Update the coordinate descent iteration number and direction flag. 135 if not self.back: 136 if self.n < len(self.xk) - 1: 137 self.n = self.n + 1 138 else: 139 self.back = 1 140 self.n = self.n - 1 141 else: 142 if self.n > 0: 143 self.n = self.n - 1 144 else: 145 self.back = 0 146 self.n = self.n + 1 147 if self.print_flag >= 2: 148 print(self.print_prefix + "back_flag: " + repr(self.back)) 149 print(self.print_prefix + "n: " + repr(self.n)) 150 151 # Store old data. 152 self.fk_last = self.fk 153 self.dfk_last = self.dfk * 1.0 154 155 # Shift k+1 data to k. 156 self.xk = self.xk_new * 1.0 157 self.fk = self.fk_new 158 self.dfk = self.dfk_new * 1.0
159