The IMSL_FMINV function minimizes a function f(x) of n variables using a quasi-Newton method.

The IMSL_FMINV function uses a quasi-Newton method to find the minimum of a function f(x) of n variables. The problem is stated below:

Given a starting point xc, the search direction is computed according to the formula:

d = –B–1gc

where B is a positive definite approximation of the Hessian and gc is the gradient evaluated at xc.

A line search is then used to find a new point:

xn = xc + λ d, λ > 0

such that:

f(xn) ≤ f(xc) α gTd

where α ∈ (0, 0.5 ) .

Finally, the optimality condition:

|| g(x) || ≤ ε

is checked, where ε is a gradient tolerance.

When optimality is not achieved, B is updated according to the BFGS formula:

where s = xnxc and y = gngc. Another search direction is then computed to begin the next iteration. For more details, see Dennis and Schnabel (1983, Appendix A).

In this implementation, the first stopping criterion for IMSL_FMINV occurs when the norm of the gradient is less than the given gradient tolerance TOL_GRAD. The second stopping criterion for IMSL_FMINV occurs when the scaled distance between the last two steps is less than the step tolerance TOL_STEP.

Since by default, a finite-difference method is used to estimate the gradient for some single-precision calculations, an inaccurate estimate of the gradient may cause the algorithm to terminate at a noncritical point. In such cases, high-precision arithmetic is recommended or keyword GRAD is used to provide more accurate gradient evaluation.

## Examples

### Example 1

The function f(x) = 100 (x2x12)2 + (1 – x1)2 is minimized.

`.RUN`
`; Define the function. `
`FUNCTION f, x`
`xn = x`
`xn(0) = x(1) - x(0)^2 xn(1) = 1 - x(0)`
`RETURN, 100 * xn(0)^2 + xn(1)^2`
`END`
` `
`; Call IMSL_FMINV to compute the minimum. `
`xmin = IMSL_FMINV('f', 2)`
`PM, xmin, Title = 'Solution:'`

IDL prints:

`Solution:`
`0.999986`
`0.999971`

Continue:

`PM, f(xmin), Title = 'Function value:'`

IDL prints:

`Function value:`
`2.09543e-10`

### Example 2

The function f(x) = 100 (x2x12)2 + (1 – x1)2 is minimized with the initial guess x = ( –1.2, 1.0). In the following plot, the asterisk marks the minimum. The results are shown in the plot below.

`.RUN`
`; Define the function. `
`FUNCTION f, x`
`xn = x`
`xn(0) = x(1) - x(0)^2 xn(1) = 1 - x(0)`
`RETURN, 100 * xn(0)^2 + xn(1)^2`
`END`
` `
`.RUN`
`; Define the gradient function. `
`FUNCTION grad, x`
`g = x`
`g(0) = -400 * (x(1) - x(0)^2) * x(0) - 2 * (1 - x(0))`
`g(1) = 200 * (x(1) - x(0)^2) RETURN, g`
`END`
` `
`xmin = IMSL_FMINV('f', 2, grad = 'grad',\$ `
`  XGuess = [-1.2, 1.0], Tol_Grad = .0001)`
` `
`; Call IMSL_FMINV with the gradient function, an initial guess,`
`; and a scaled gradient tolerance. `
`x = 4 * FINDGEN(100)/99 - 2`
`y = x`
`surf = FLTARR(100, 100)`
`FOR i = 0, 99 DO FOR j = 0, 99 do \$`
`  surf(i, j) = f([x(i), y(j)])`
` `
`  ; Evaluate function f on 100 x 100 grid for use in CONTOUR. `
`  str = '(' + STRCOMPRESS(xmin(0)) + ',' + \$ `
`  STRCOMPRESS(xmin(1)) + ',' + STRCOMPRESS(f(xmin)) + ')'`
`  !P.Charsize = 1.5`
`  CONTOUR, surf, x, y, Levels = [20*FINDGEN(6), \$`
`    500 + FINDGEN(7)*500], /C_Annotation, \$ `
`    Title='!18Rosenbrock Function!C' + 'Minimum Point:!C' + \$ `
`    str, Position = [.1, .1, .8, .8]`
`; Call CONTOUR. Customize the contour plot, including the title`
`; of the plot.`
`OPLOT, [xmin(0)], [xmin(1)], Psym = 2, Symsize = 2`
` `
`; Plot the solution as an asterisk.`

Result:

## Errors

### Informational Errors

MATH_STEP_TOLERANCE: Scaled step tolerance satisfied. Current point may be an approximate local solution, but it is also possible that the algorithm is making very slow progress and is not near a solution or that TOL_STEP is too big.

### Warning Errors

MATH_REL_FCN_TOLERANCE: Relative function convergence. Both the actual and predicted relative reductions in the function are less than or equal to the relative function convergence tolerance.

MATH_TOO_MANY_ITN: Maximum number of iterations exceeded.

MATH_TOO_MANY_FCN_EVAL: Maximum number of function evaluations exceeded.

MATH_UNBOUNDED: Five consecutive steps have been taken with the maximum step length.

MATH_NO_FURTHER_PROGRESS: Last global step failed to locate a point lower than the current x value.

### Fatal Errors

MATH_FALSE_CONVERGENCE: Iterates appear to converge to a noncritical point. It is possible that incorrect gradient information is used, or the function is discontinuous, or the other stopping tolerances are too tight.

## Syntax

Result = IMSL_FMINV(f, n [, /DOUBLE] [, GRAD=string] [, FSCALE=string] [, FVALUE=variable] [, IHESS=parameter] [, ITMAX=value] [, MAX_EVALS=value] [, MAX_GRAD=value] [, MAX_STEP=value] [, N_DIGIT=value] [, TOL_GRAD=value] [, TOL_RFCN=value] [, TOL_STEP=value] [, XGUESS=array] [, XSCALE=array])

## Return Value

The minimum point x of the function. If no value can be computed, NaN is returned.

## Arguments

### f

Scalar string specifying a user-supplied function to evaluate the function to be minimized. Function f accepts the point at which the function is evaluated and returns the computed function value at the point.

### n

Number of variables.

## Keywords

### DOUBLE (optional)

If present and nonzero, double precision is used.

Scalar string specifying a user-supplied function to compute the gradient. The GRAD function accepts the point at which the gradient is evaluated and returns the computed gradient at the point.

### FSCALE (optional)

Scalar containing the function scaling. The keyword FSCALE is used mainly in scaling the gradient. See the TOL_GRAD keyword for more detail. The default value is 1.0.

### FVALUE (optional)

Name of a variable into which the value of the function at the computed solution is stored.

### IHESS (optional)

Hessian initialization parameter. If IHESS is zero, the Hessian is initialized to the identity matrix; otherwise, it is initialized to a diagonal matrix containing max(f(t), fs) * si on the diagonal, where t = XGUESS, fs = FSCALE, and s = XSCALE. The default value is 0.

### ITMAX (optional)

Maximum number of iterations. The default value is 100.

### MAX_EVALS (optional)

Maximum number of function evaluations. The default value is 100 400.

Maximum number of gradient evaluations. The default value is 100 400.

### MAX_STEP (optional)

Maximum allowable step size. Default: 1000*max(ε1, ε2), where:

ε2 = || s ||2, s = XSCALE, and t = XGUESS

### N_DIGIT (optional)

Number of good digits in function. Default: machine dependent.

The i-th component of the scaled gradient at x is calculated as:

where:

• g = ∇f(x)
• s = XSCALE
• fs = FSCALE

Default: ε1/21/3 in double), where ε is the machine precision.

### TOL_RFCN (optional)

Relative function tolerance. The default is TOL_RFCN = max(10–10, ε 2/3), max(10–20, ε 2/3) in double.

### TOL_STEP (optional)

Scaled step tolerance.

The i-th component of the scaled step between two points x and y is computed as:

where s = XSCALE. Default: ε 2/3

### XGUESS (optional)

Array with n components containing an initial guess of the computed solution. Default: XGUESS (*) = 0.

### XSCALE (optional)

Array with n components containing the scaling vector for the variables. The keyword XSCALE is used mainly in scaling the gradient and the distance between

two points (see the keywords TOL_GRAD and TOL_STEP for more detail). Default: XSCALE (*) = 1.0.

## Version History

 6.4 Introduced