minUncon¶

Find the minimum point of a smooth function f(x) of a single variable using only function evaluations.

Synopsis¶

minUncon (fcn, a, b)

Required Arguments¶

float fcn(x) (Input/Output): User-supplied function to compute the value of the function to be minimized where x is the point at which the function is evaluated, and fcn is the computed function value at the point x.
float a (Input): The lower endpoint of the interval in which the minimum point of fcn is to be located.
float b (Input): The upper endpoint of the interval in which the minimum point of fcn is to be located.

Return Value¶

The point at which a minimum value of fcn is found. If no value can be computed, NaN is returned.

Optional Arguments¶

xguess, float (Input)

An initial guess of the minimum point of fcn.

Default: xguess = (a + b)/2

step, float (Input)

An order of magnitude estimate of the required change in x.

Default: step = 1.0

errAbs, float (Input)

The required absolute accuracy in the final value of x. On a normal return, there are points on either side of x within a distance errAbs at which fcn is no less than fcn at x.

Default: errAbs = 0.0001

maxFcn, int (Input)

Maximum number of function evaluations allowed.

Default: maxFcn = 1000

Description¶

The function minUncon uses a safeguarded quadratic interpolation method to find a minimum point of a univariate function. Both the code and the underlying algorithm are based on the subroutine ZXLSF written by M.J.D. Powell at the University of Cambridge.

The function minUncon finds the least value of a univariate function, f, which is specified by the function fcn. Other required data are two points a and b that define an interval for finding a minimum point from an initial estimate of the solution, \(x_0\) where \(x_0\) = xguess. The algorithm begins the search by moving from \(x_0\) to \(x=x_0+s\) where s = step is an estimate of the required change in x and may be positive or negative. The first two function evaluations indicate the direction to the minimum point and the search strides out along this direction until a bracket on a minimum point is found or until x reaches one of the endpoints a or b. During this stage, the step length increases by a factor of between two and nine per function evaluation. The factor depends on the position of the minimum point that is predicted by quadratic interpolation of the three most recent function values.

When an interval containing a solution has been found, we have three points,

\[x_1, x_2, x_3, \text{ with } x_1 < x_2 < x_3, f(x_1) ≥ f(x_2), \text{ and } f(x_2) ≤ f(x_3).\]

There are three main rules in the technique for choosing the new x from these three points. They are (i) the estimate of the minimum point that is given by quadratic interpolation of the three function values, (ii) a tolerance parameter η, which depends on the closeness of f to a quadratic, and (iii) whether \(x_2\) is near the center of the range between \(x_1\) and \(x_3\) or is relatively close to an end of this range. In outline, the new value of x is as near as possible to the predicted minimum point, subject to being at least ɛ from \(x_2\), and subject to being in the longer interval between \(x_1\) and \(x_2\), or \(x_2\) and \(x_3\), when \(x_2\) is particularly close to \(x_1\) or \(x_3\).

The algorithm is intended to provide fast convergence when f has a positive and continuous second derivative at the minimum. Also, the algorithm avoids gross inefficiencies in pathological cases, such as

\[f(x) = x + 1.001∣x∣\]

The algorithm can automatically make ɛ large in the pathological cases. In this case, it is usual for a new value of x to be at the midpoint of the longer interval that is adjacent to the least-calculated function value. The midpoint strategy is used frequently when changes to f are dominated by computer rounding errors, which will almost certainly happen if the user requests an accuracy that is less than the square root of the machine precision. In such cases, the subroutine claims to have achieved the required accuracy if it decides that there is a local minimum point within distance δ of x, where δ = errAbs, even though the rounding errors in f may cause the existence of other local minimum points nearby. This difficulty is inevitable in minimization routines that use only function values, so high precision arithmetic is recommended.

Examples¶

Example 1¶

A minimum point of \(f(x)=e^x-5x\) is found.

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


def fcn(x):
    return exp(x) - 5.0 * x


a = -100.0
b = 100.0

x = minUncon(fcn, a, b)
fx = fcn(x)

print("The solution is: %8.4f" % (x))
print("The function evaluated at the solution is: %8.4f" % (fx))

Output¶

The solution is:   1.6094
The function evaluated at the solution is:  -3.0472

Example 2¶

A minimum point of \(f(x)=x(x^3-1)+10\) is found with an initial guess \(x_0=3\).

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


def fcn(x):
    return x * (pow(x, 3) - 1.0) + 10.0


max_fcn = 50
a = -10.0
b = 10.0
xguess = 3.0
step = 0.1
err_abs = 0.001

x = minUncon(fcn, a, b,
             xguess=xguess,
             step=step,
             errAbs=err_abs,
             maxFcn=max_fcn)
fx = fcn(x)

print("The solution is: %8.4f" % (x))
print("The function evaluated at the solution is: %8.4f" % (fx))

Output¶

The solution is:   0.6298
The function evaluated at the solution is:   9.5275

Warning Errors¶

`IMSL_MIN_AT_BOUND`	The final value of `x` is at a bound.
`IMSL_NO_MORE_PROGRESS`	Computer rounding errors prevent further refinement of `x`.
`IMSL_TOO_MANY_FCN_EVAL`	Maximum number of function evaluations exceeded.

Fatal Errors¶

IMSL_STOP_USER_FCN

Request from user supplied function to stop algorithm.

User flag = “#”.