1// Copyright ©2015 The Gonum Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package optimize
6
7import (
8	"math"
9)
10
11// Converger returns the convergence of the optimization based on
12// locations found during optimization. Converger must not modify the value of
13// the provided Location in any of the methods.
14type Converger interface {
15	Init(dim int)
16	Converged(loc *Location) Status
17}
18
19var (
20	_ Converger = NeverTerminate{}
21	_ Converger = (*FunctionConverge)(nil)
22)
23
24// NeverTerminate implements Converger, always reporting NotTerminated.
25type NeverTerminate struct{}
26
27func (NeverTerminate) Init(dim int) {}
28
29func (NeverTerminate) Converged(loc *Location) Status {
30	return NotTerminated
31}
32
33// FunctionConverge tests for insufficient improvement in the optimum value
34// over the last iterations. A FunctionConvergence status is returned if
35// there is no significant decrease for FunctionConverge.Iterations. A
36// significant decrease is considered if
37//   f < f_best
38// and
39//  f_best - f > FunctionConverge.Relative * maxabs(f, f_best) + FunctionConverge.Absolute
40// If the decrease is significant, then the iteration counter is reset and
41// f_best is updated.
42//
43// If FunctionConverge.Iterations == 0, it has no effect.
44type FunctionConverge struct {
45	Absolute   float64
46	Relative   float64
47	Iterations int
48
49	first bool
50	best  float64
51	iter  int
52}
53
54func (fc *FunctionConverge) Init(dim int) {
55	fc.first = true
56	fc.best = 0
57	fc.iter = 0
58}
59
60func (fc *FunctionConverge) Converged(l *Location) Status {
61	f := l.F
62	if fc.first {
63		fc.best = f
64		fc.first = false
65		return NotTerminated
66	}
67	if fc.Iterations == 0 {
68		return NotTerminated
69	}
70	maxAbs := math.Max(math.Abs(f), math.Abs(fc.best))
71	if f < fc.best && fc.best-f > fc.Relative*maxAbs+fc.Absolute {
72		fc.best = f
73		fc.iter = 0
74		return NotTerminated
75	}
76	fc.iter++
77	if fc.iter < fc.Iterations {
78		return NotTerminated
79	}
80	return FunctionConvergence
81}
82