in commons-math-legacy/src/main/java/org/apache/commons/math4/legacy/optim/univariate/BrentOptimizer.java [115:287]
protected UnivariatePointValuePair doOptimize() {
final boolean isMinim = getGoalType() == GoalType.MINIMIZE;
final double lo = getMin();
final double mid = getStartValue();
final double hi = getMax();
final UnivariateFunction func = getObjectiveFunction();
// Optional additional convergence criteria.
final ConvergenceChecker<UnivariatePointValuePair> checker
= getConvergenceChecker();
double a;
double b;
if (lo < hi) {
a = lo;
b = hi;
} else {
a = hi;
b = lo;
}
double x = mid;
double v = x;
double w = x;
double d = 0;
double e = 0;
double fx = func.value(x);
if (!isMinim) {
fx = -fx;
}
double fv = fx;
double fw = fx;
UnivariatePointValuePair previous = null;
UnivariatePointValuePair current
= new UnivariatePointValuePair(x, isMinim ? fx : -fx);
// Best point encountered so far (which is the initial guess).
UnivariatePointValuePair best = current;
while (true) {
final double m = 0.5 * (a + b);
final double tol1 = relativeThreshold * JdkMath.abs(x) + absoluteThreshold;
final double tol2 = 2 * tol1;
// Default stopping criterion.
final boolean stop = JdkMath.abs(x - m) <= tol2 - 0.5 * (b - a);
if (!stop) {
double p = 0;
double q = 0;
double r = 0;
double u = 0;
if (JdkMath.abs(e) > tol1) { // Fit parabola.
r = (x - w) * (fx - fv);
q = (x - v) * (fx - fw);
p = (x - v) * q - (x - w) * r;
q = 2 * (q - r);
if (q > 0) {
p = -p;
} else {
q = -q;
}
r = e;
e = d;
if (p > q * (a - x) &&
p < q * (b - x) &&
JdkMath.abs(p) < JdkMath.abs(0.5 * q * r)) {
// Parabolic interpolation step.
d = p / q;
u = x + d;
// f must not be evaluated too close to a or b.
if (u - a < tol2 || b - u < tol2) {
if (x <= m) {
d = tol1;
} else {
d = -tol1;
}
}
} else {
// Golden section step.
if (x < m) {
e = b - x;
} else {
e = a - x;
}
d = GOLDEN_SECTION * e;
}
} else {
// Golden section step.
if (x < m) {
e = b - x;
} else {
e = a - x;
}
d = GOLDEN_SECTION * e;
}
// Update by at least "tol1".
if (JdkMath.abs(d) < tol1) {
if (d >= 0) {
u = x + tol1;
} else {
u = x - tol1;
}
} else {
u = x + d;
}
double fu = func.value(u);
if (!isMinim) {
fu = -fu;
}
// User-defined convergence checker.
previous = current;
current = new UnivariatePointValuePair(u, isMinim ? fu : -fu);
best = best(best,
best(previous,
current,
isMinim),
isMinim);
if (checker != null && checker.converged(getIterations(), previous, current)) {
return best;
}
// Update a, b, v, w and x.
if (fu <= fx) {
if (u < x) {
b = x;
} else {
a = x;
}
v = w;
fv = fw;
w = x;
fw = fx;
x = u;
fx = fu;
} else {
if (u < x) {
a = u;
} else {
b = u;
}
if (fu <= fw ||
Precision.equals(w, x)) {
v = w;
fv = fw;
w = u;
fw = fu;
} else if (fu <= fv ||
Precision.equals(v, x) ||
Precision.equals(v, w)) {
v = u;
fv = fu;
}
}
} else { // Default termination (Brent's criterion).
return best(best,
best(previous,
current,
isMinim),
isMinim);
}
incrementIterationCount();
}
}