minUnconGolden

Finds the minimum point of a nonsmooth function of a single variable using the golden section search method.

Synopsis

minUnconGolden (fcn, a, b)

Required Arguments

float fcn (x) (Input)

User-supplied function, $f(x)$, to be minimized.

float a (Input)

The lower endpoint of the interval in which the minimum of f is to be located.

float b (Input)

The upper endpoint of the interval in which the minimum of f is to be located.

Return Value

The approximate minimum point of the function f on the original interval [a, b]. If no value can be computed, NaN is returned.

Optional Arguments

tolerance, float (Input)

The allowable length of the final subinterval containing the minimum point.

Default: tolerance = $\sqrt{\varepsilon}$, where ɛ is the machine precision.

lowerEndpoint (Output)

The lower endpoint of the interval in which the minimum of f is located.

upperEndpoint (Output)

The upper endpoint of the interval in which the minimum of f is located.

Description

The function minUnconGolden uses the golden section search technique to compute to the desired accuracy the independent variable value that minimizes a function of one independent variable, where a known finite interval contains the minimum and where the function is unimodal in the same known finite interval.

Let $\tau$ =tolerance. The number of iterations required to compute the minimizing value to accuracy $\tau$ is the greatest integer less than or equal to

$$\frac{\ln(\tau / (b-a))}{\ln (1-c)} + 1$$

where a and b define the interval and

$$c = \left(3 - \sqrt{5}\right) / 2$$

The first two test points are $v_1$ and $v_2$ that are defined as

$$v_1 =a +c(b - a), \text{ and } v_2 =b - c(b - a)$$

If $f(v_1)<f(v_2)$, then the minimizing value is in the interval $\left(a,v_2\right)$. In this case, $b\leftarrow v_2$, $v_2\leftarrow v_1$, and $v_1\leftarrow a+c(b-a)$. If $f(v_1)\geq f(v_2)$, the minimizing value is in $\left(v_1,b\right)$. In this case, $a\leftarrow v_1$, $v_1\leftarrow v_2$, and $v_2\leftarrow b-c(b-a)$.

The algorithm continues in an analogous manner where only one new test point is computed at each step. This process continues until the desired accuracy $\tau$ is achieved. The point, xmin, producing the minimum value for the current iteration is returned.

Mathematically, the algorithm always produces the minimizing value to the desired accuracy, however, numerical problems may be encountered. If f is too flat in part of the region of interest, the function may appear to be constant to the computer in that region. The user may rectify the problem by relaxing the requirement on $\tau$, modifying (scaling, etc.) the form of f or executing the program in a higher precision.

Remarks

1. On exit from minUnconGolden without any error messages, the following conditions hold:

   $$\texttt{(upperEndpoint-lowerEndpoint)} ≤\texttt{tolerance}$$
   $$\texttt{lowerEndpoint} ≤\texttt{xmin} \text{ and } \texttt{xmin} ≤\texttt{upperEndpoint}$$
   $$\texttt{f(xmin)} ≤\texttt{f(lowerEndpoint)} \text{ and } \texttt{f(xmin)} ≤\texttt{f(upperEndpoint)}$$

2. On exit from minUnconGolden with IMSL_NOT_UNIMODAL error, the following conditions hold:

   $$\texttt{lowerEndpoint} ≤\texttt{xmin} \text{ and } \texttt{xmin} ≤\texttt{upperEndpoint}$$
   $$\texttt{f(xmin)} ≥\texttt{f(lowerEndpoint)} \text{ and } \texttt{f(xmin)} ≥\texttt{f(upperEndpoint)} \text{ (only one equality can hold)}$$

   Further analysis of the function f is necessary in order to determine whether it is not unimodal in the mathematical sense or whether it appears to be not unimodal to the routine due to rounding errors, in which case the lowerEndpoint, upperEndpoint, and xmin returned may be acceptable.

Example

A minimum point of $3x^2-2x+4$ is found.

from __future__ import print_function
from numpy import *
from pyimsl.math.minUnconGolden import minUnconGolden


def fcn(x):
    return 3.0 * (x**2) - 2 * x + 4


lower = []
upper = []
a = 0.0
b = 5.0
tol = 1.0e-3
xmin = minUnconGolden(fcn, a, b,
                      tolerance=tol,
                      lowerEndpoint=lower,
                      upperEndpoint=upper)
fx = fcn(xmin)
print("The minimum is at: %7.3f" % (xmin))
print("The function evaluated at the solution is: %8.3f" % (fx))
print("The final interval is: (%8.3f, %8.3f)" % (lower[0], upper[0]))

Output

The minimum is at:   0.333
The function evaluated at the solution is:    3.667
The final interval is: (   0.333,    0.334)

Warning Errors

IMSL_TOL_TOO_SMALL

tolerance is too small to be satisfied..

Fatal Errors

IMSL_NOT_UNIMODAL	Due to rounding errors, the function does not appear to be unimodal.
IMSL_STOP_USER_FCN	Request from user supplied function to stop algorithm. User flag = “#”.