min_uncon_deriv

Finds the minimum point of a smooth function f(x) of a single variable using both function and first derivative evaluations.

Synopsis

#include <imsl.h>

float imsl_f_min_uncon_deriv (float fcn(), float grad(), float a, float b, , 0)

The type double function is imsl_d_min_uncon_deriv.

Required Arguments

float fcn (float 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 grad (float x) (Input/Output)
User-supplied function to compute the first derivative of the function where x is the point at which the derivative is evaluated, and grad is the computed value of the derivative 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.

Synopsis with Optional Arguments

#include <imsl.h>

float imsl_f_min_uncon_deriv (float fcn(), float grad(), float a, float b,

IMSL_XGUESS, float xguess,

IMSL_ERR_REL, float err_rel,

IMSL_GRAD_TOL, float grad_tol,

IMSL_MAX_FCN, int max_fcn,

IMSL_FVALUE, float *fvalue,

IMSL_GVALUE, float *gvalue,

IMSL_FCN_W_DATA, float fcn(), void *data,

IMSL_GRADIENT_W_DATA, float grad(), void *data,

0)

Optional Arguments

IMSL_XGUESS, float xguess (Input)
An initial guess of the minimum point of fcn.
Default: xguess = (a + b)/2

IMSL_ERR_REL, float err_rel (Input)
The required relative accuracy in the final value of x. This is the first stopping criterion. On a normal return, the solution x is in an interval that contains a local minimum and is less than or equal to max (1.0, |x|) *err_rel. When the given err_rel is less than zero,

 

is used as err_rel where ɛ is the machine precision.
Default: err_rel =

IMSL_GRAD_TOL, float grad_tol (Input)
The derivative tolerance used to decide if the current point is a local minimum. This is the second stopping criterion. x is returned as a solution when grad is less than or equal to grad_tol. grad_tol should be nonnegative; otherwise, zero would be used.
Default: grad_tol = where ɛ is the machine precision

IMSL_MAX_FCN, int max_fcn (Input)
Maximum number of function evaluations allowed.
Default: max_fcn = 1000

IMSL_FVALUE, float *fvalue (Output)
The function value at point x.

IMSL_GVALUE, float *gvalue (Output)
The derivative value at point x.

IMSL_FCN_W_DATA, float fcn (float x, void *data), void *data (Input)
User supplied function to compute the value of the function to be minimized, which also accepts a pointer to data that is supplied by the user. data is a pointer to the data to be passed to the user-supplied function. See Passing Data to User-Supplied Functions in the introduction to this manual for more details.

IMSL_GRADIENT_W_DATA, float grad (float x, void *data), void *data, (Input)
User supplied function to compute the first derivative of the function, which also accepts a pointer to data that is supplied by the user. data is a pointer to the data to be passed to the user-supplied function. See Passing Data to User-Supplied Functions in the introduction to this manual for more details.

Description

The function f_min_uncon_deriv uses a descent method with either the secant method or cubic interpolation to find a minimum point sof a univariate function. It starts with an initial guess and two endpoints. If any of the three points is a local minimum point and has least function value, the function terminates with a solution. Otherwise, the point with least function value will be used as the starting point.

From the starting point, say xc, the function value fc = f(xc), the derivative value gc = g(xc), and a new point xn defined by xn = xc  gc are computed. The function fn = f(xn), and the derivative gn = g(xn) are then evaluated. If either fn  fc or gn has the opposite sign of gc, then there exists a minimum point between xc and xn, and an initial interval is obtained. Otherwise, since xc is kept as the point that has lowest function value, an interchange between xn and xc is performed. The secant method is then used to get a new point

 

Let xn = xs, and repeat this process until an interval containing a minimum is found or one of the convergence criteria is satisfied. The convergence criteria are as follows:

Criterion 1: xc  xn  ɛc

Criterion 2: gc  ɛg

where ɛc = max {1.0, xc} ɛ, ɛ is an error tolerance, and ɛg is a gradient tolerance.

When convergence is not achieved, a cubic interpolation is performed to obtain a new point. Function and derivative are then evaluated at that point, and accordingly a smaller interval that contains a minimum point is chosen. A safeguarded method is used to ensure that the interval be reduced by at least a fraction of the previous interval. Another cubic interpolation is then performed, and this function is repeated until one of the stopping criteria is met.

Examples

 

Example 1

In this example, a minimum point of f(x) = ex  5x is found.

 

#include <imsl.h>

#include <math.h>

 

float fcn(float);

float deriv(float);

 

int main ()

{

float a = -10.0;

float b = 10.0;

float fx, gx, x;

 

x = imsl_f_min_uncon_deriv (fcn, deriv, a, b, 0);

fx = fcn(x);

gx = deriv(x);

 

printf ("The solution is: %7.3f\n", x);

printf ("The function evaluated at the solution is: %9.3f\n", fx);

printf ("The derivative evaluated at the solution is: %7.3f\n", gx);

}

 

 

float fcn(float x)

{

return exp(x) - 5.0*(x);

}

 

 

float deriv (float x)

{

return exp(x) - 5.0;

}

Output

 

The solution is: 1.609

The function evaluated at the solution is: -3.047

The derivative evaluated at the solution is: -0.001

Example 2

A minimum point of f(x) = x(x3  1) + 10 is found with an initial guess x0 = 3.

 

#include <imsl.h>

#include <stdio.h>

 

float fcn(float);

float deriv(float);

 

int main ()

{

int max_fcn = 50;

float a = -10.0;

float b = 10.0;

float xguess = 3.0;

float fx, gx, x;

 

x = imsl_f_min_uncon_deriv (fcn, deriv, a, b,

IMSL_XGUESS, xguess,

IMSL_MAX_FCN, max_fcn,

IMSL_FVALUE, &fx,

IMSL_GVALUE, &gx,

0);

printf ("The solution is: %7.3f\n", x);

printf ("The function evaluated at the solution is: %7.3f\n", fx);

printf ("The derivative evaluated at the solution is: %7.3f\n", gx);

}

 

float fcn(float x)

{

return x*(x*x*x-1) + 10.0;

}

 

float deriv(float x)

{

return 4.0*(x*x*x) - 1.0;

}

Output

 

The solution is: 0.630

The function evaluated at the solution is: 9.528

The derivative evaluated at the solution is: 0.000

Warning Errors

IMSL_MIN_AT_LOWERBOUND

The final value of x is at the lower bound.

IMSL_MIN_AT_UPPERBOUND

The final value of x is at the upper bound.

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 = "#".