descent_minimizer.py 7.12 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# NIFTy
# Copyright (C) 2017  Theo Steininger
#
# Author: Theo Steininger
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.
18
19

import abc
20
from nifty.nifty_meta import NiftyMeta
21
22
23
24
25
26
27
28

import numpy as np

from keepers import Loggable

from .line_searching import LineSearchStrongWolfe


29
class DescentMinimizer(Loggable, object):
30
31
32
33
34
35
36
    """ A base class used by gradient methods to find a local minimum.

    Descent minimization methods are used to find a local minimum of a scalar
    function by following a descent direction. This class implements the
    minimization procedure once a descent direction is known. The descent
    direction has to be implemented separately.

37
38
    Parameters
    ----------
39
40
41
42
43
44
45
46
47
48
49
50
    line_searcher : callable *optional*
        Function which infers the step size in the descent direction
        (default : LineSearchStrongWolfe()).
    callback : callable *optional*
        Function f(energy, iteration_number) supplied by the user to perform
        in-situ analysis at every iteration step. When being called the
        current energy and iteration_number are passed. (default: None)
    convergence_tolerance : float *optional*
        Tolerance specifying the case of convergence. (default: 1E-4)
    convergence_level : integer *optional*
        Number of times the tolerance must be undershot before convergence
        is reached. (default: 3)
51
    iteration_limit : integer *optional*
52
53
        Maximum number of iterations performed (default: None).

54
55
56
    Attributes
    ----------
    convergence_tolerance : float
57
58
59
60
        Tolerance specifying the case of convergence.
    convergence_level : integer
        Number of times the tolerance must be undershot before convergence
        is reached. (default: 3)
61
62
    iteration_limit : integer
        Maximum number of iterations performed.
63
64
65
    line_searcher : LineSearch
        Function which infers the optimal step size for functional minization
        given a descent direction.
66
    callback : function
67
68
69
70
71
        Function f(energy, iteration_number) supplied by the user to perform
        in-situ analysis at every iteration step. When being called the
        current energy and iteration_number are passed.

    Notes
72
    ------
73
74
75
76
77
78
    The callback function can be used to externally stop the minimization by
    raising a `StopIteration` exception.
    Check `get_descent_direction` of a derived class for information on the
    concrete minization scheme.

    """
79

80
    __metaclass__ = NiftyMeta
81
82
83
84
85
86

    def __init__(self, line_searcher=LineSearchStrongWolfe(), callback=None,
                 convergence_tolerance=1E-4, convergence_level=3,
                 iteration_limit=None):

        self.convergence_tolerance = np.float(convergence_tolerance)
87
        self.convergence_level = np.int(convergence_level)
88
89
90
91
92
93
94
95

        if iteration_limit is not None:
            iteration_limit = int(iteration_limit)
        self.iteration_limit = iteration_limit

        self.line_searcher = line_searcher
        self.callback = callback

96
    def __call__(self, energy):
97
        """ Performs the minimization of the provided Energy functional.
98
99
100
101

        Parameters
        ----------
        energy : Energy object
102
103
           Energy object which provides value, gradient and curvature at a
           specific position in parameter space.
104
105
106

        Returns
        -------
107
        energy : Energy object
108
109
110
111
            Latest `energy` of the minimization.
        convergence : integer
            Latest convergence level indicating whether the minimization
            has converged or not.
112

113
114
        Note
        ----
115
116
117
118
119
120
121
        The minimization is stopped if
            * the callback function raises a `StopIteration` exception,
            * a perfectly flat point is reached,
            * according to the line-search the minimum is found,
            * the target convergence level is reached,
            * the iteration limit is reached.

122
123
124
125
126
127
128
129
130
131
        """

        convergence = 0
        f_k_minus_1 = None
        step_length = 0
        iteration_number = 1

        while True:
            if self.callback is not None:
                try:
132
                    self.callback(energy, iteration_number)
133
134
135
136
137
                except StopIteration:
                    self.logger.info("Minimization was stopped by callback "
                                     "function.")
                    break

138
139
            # compute the the gradient for the current location
            gradient = energy.gradient
140
141
            gradient_norm = gradient.dot(gradient)

142
            # check if position is at a flat point
143
144
145
146
147
            if gradient_norm == 0:
                self.logger.info("Reached perfectly flat point. Stopping.")
                convergence = self.convergence_level+2
                break

148
            # current position is encoded in energy object
149
            descend_direction = self.get_descend_direction(energy)
150

151
152
            # compute the step length, which minimizes energy.value along the
            # search direction
153
154
            step_length, f_k, new_energy = \
                self.line_searcher.perform_line_search(
155
                                               energy=energy,
156
157
                                               pk=descend_direction,
                                               f_k_minus_1=f_k_minus_1)
158
159
            f_k_minus_1 = energy.value
            energy = new_energy
160
161
162
163
164
165
166
167

            # check convergence
            delta = abs(gradient).max() * (step_length/gradient_norm)
            self.logger.debug("Iteration : %08u   step_length = %3.1E   "
                              "delta = %3.1E" %
                              (iteration_number, step_length, delta))
            if delta == 0:
                convergence = self.convergence_level + 2
168
169
                self.logger.info("Found minimum according to line-search. "
                                 "Stopping.")
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
                break
            elif delta < self.convergence_tolerance:
                convergence += 1
                self.logger.info("Updated convergence level to: %u" %
                                 convergence)
                if convergence == self.convergence_level:
                    self.logger.info("Reached target convergence level.")
                    break
            else:
                convergence = max(0, convergence-1)

            if self.iteration_limit is not None:
                if iteration_number == self.iteration_limit:
                    self.logger.warn("Reached iteration limit. Stopping.")
                    break

            iteration_number += 1

188
        return energy, convergence
189
190

    @abc.abstractmethod
191
    def get_descend_direction(self, energy):
192
        raise NotImplementedError