minUnconMultivar

Minimizes a function \(f(x)\) of n variables using a quasi-Newton method.

Synopsis

minUnconMultivar (fcn, n)

Required Arguments

float fcn (n, x[]) (Input/Output)

User-supplied function to evaluate the function to be minimized where n is the size of x, x is the point at which the function is evaluated, and fcn is the computed function value at the point x.

int n (Input)

Number of variables.

Return Value

The minimum point x of the function. If no solution can be computed, then None is returned.

Optional Arguments

xguess, float[] (Input)

Array with n components containing an initial guess of the computed solution.

Default: xguess = 0

grad, void grad (n, x[], g[]) (Input/Output)

User-supplied function to compute the gradient at the point x where n is the size of x, x is the point at which the gradient is evaluated, and g is the computed gradient at the point x.

xscale, float[] (Input)

Array with n components containing the scaling vector for the variables. xscale is used mainly in scaling the gradient and the distance between two points. See keywords gradTol and stepTol for more details.

Default: xscale[] = 1.0

fscale, float (Input)

Scalar containing the function scaling. fscale is used mainly in scaling the gradient. See keyword gradTol for more details.

Default: fscale = 1.0

gradTol, float (Input)

Scaled gradient tolerance. The i-th component of the scaled gradient at x is calculated as

\[\frac {\left|g_i\right|*\max\left(\left|x_i\right|, 1/s_i\right)} {\max\left(\left|f(x)\right|, f_s\right)}\]

where \(g=\nabla f(x)\), s = xscale, and \(f_s\) = fscale.

Default: gradTol = \(\sqrt{\varepsilon}\), \(\sqrt[3]{\varepsilon}\) in double where ɛ is the machine precision.

stepTol, float (Input)

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

\[\frac{\left|x_i-y_i\right|}{\max\left(\left|x_i\right|, 1/ s_i\right)}\]

where s = xscale.

Default: stepTol = \(\varepsilon^{2/3}\)

maxStep, float (Input)

Maximum allowable step size.

Default: maxStep = \(1000 \max(\varepsilon_1,\varepsilon_2)\) where,

\[\varepsilon_1 = \sqrt{\textstyle\sum_{i=1}^{n} \left(s_it_i\right)^2}\]

\(\varepsilon_2=\|s\|^2\), s = xscale, and t = xguess.

goodDigit, int (Input)

Number of good digits in the function. The default is machine dependent.

maxItn, int (Input)

Maximum number of iterations.

Default: maxItn = 100

maxFcn, int (Input)

Maximum number of function evaluations.

Default: maxFcn = 400

maxGrad, int (Input)

Maximum number of gradient evaluations.

Default: maxGrad = 400

initHessian, int (Input)

Hessian initialization parameter. If initHessian is zero, the Hessian is initialized to the identity matrix; otherwise, it is initialized to a diagonal matrix containing

\[\max\left(\left|f(t)\right|, f_s\right) * s_i^2\]

on the diagonal where t = xguess, \(f_s\) = fscale, and s = xscale.

Default: initHessian = 0

fvalue, float (Output)

The value of the function at the computed solution.

Description

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

\[\min_{x \in R^n} f(x)\]

Given a starting point \(x_c\), the search direction is computed according to the formula

\[d = -B-1gc\]

where B is a positive definite approximation of the Hessian, and \(g_c\) is the gradient evaluated at \(x_c\). A line search is then used to find a new point

\[x_n = x_c + λd, λ > 0\]

such that

\[f(x_n) ≤ f(x_c) + ag^Td,α  ∈ (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

\[B \leftarrow B - \frac{Bss^TB}{s^TBs} + \frac{yy^T}{y^Ts}\]

where \(s=x_n-x_c\) and \(y=g_n-g_c\). 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 minUnconMultivar occurs when the norm of the gradient is less than the given gradient tolerance gradTol. The second stopping criterion for minUnconMultivar occurs when the scaled distance between the last two steps is less than the step tolerance stepTol.

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; the keyword grad should be used to provide more accurate gradient evaluation.

Figure 8.6 — Plot of the Rosenbrock Function

Examples

Example 1

The function

\[f(x) = 100 \left(x_2 - x_1^2\right)^2 + \left(1 - x_1\right)^2\]

is minimized. In the following plot, the solid circle marks the minimum.

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


def rosbrk(n, x):
    f1 = x[1] - x[0] * x[0]
    f2 = 1.0 - x[0]
    return 100.0 * f1 * f1 + f2 * f2


# Minimize Rosenbrock function
n = 2
result = minUnconMultivar(rosbrk, n)
fx = rosbrk(n, result)

# Print results
print("The solution is      ", end=' ')
for i in range(0, n):
    print("%8.3f" % (result[i]), end=' ')
print("")
print("The function value is %8.3f" % (fx))

Output

The solution is          1.000    1.000 
The function value is    0.000

Example 2

The function

\[f(x) = 100 \left(x_2 - x_1^2\right)^2 + \left(1 - x_1\right)^2\]

is minimized with the initial guess \(x=(-1.2,1.0)\). The initial guess is marked with an open circle in Plot of the Rosenbrock Function.

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


def rosbrk(n, x):
    f1 = x[1] - x[0] * x[0]
    f2 = 1.0e0 - x[0]
    return 100.0 * f1 * f1 + f2 * f2


def rosgrd(n, x, g):
    g[0] = -400.0 * (x[1] - x[0] * x[0]) * x[0] - 2.0 * (1.0 - x[0])
    g[1] = 200.0 * (x[1] - x[0] * x[0])


n = 2
fx = []
xguess = [-1.2e0, 1.0e0]
grad_tol = .0001

# Minimize Rosenbrock function using initial guesses of -1.2 and 1.0
result = minUnconMultivar(rosbrk, n,
                          xguess=xguess,
                          grad=rosgrd,
                          gradTol=grad_tol,
                          fvalue=fx)

print("The solution is      ", end=' ')
for i in range(0, n):
    print("%8.3f" % (result[i]), end=' ')
print("")
print("The function value is %8.3f" % (fx[0]))

Output

The solution is          1.000    1.000 
The function value is    0.000

Informational Errors

IMSL_STEP_TOLERANCE

Scaled step tolerance satisfied. The 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 stepTol is too big.

Warning Errors

IMSL_TOO_MANY_ITN	Maximum number of iterations exceeded.
IMSL_TOO_MANY_FCN_EVAL	Maximum number of function evaluations exceeded.
IMSL_TOO_MANY_GRAD_EVAL	Maximum number of gradient evaluations exceeded.
IMSL_UNBOUNDED	Five consecutive steps have been taken with the maximum step length.
IMSL_NO_FURTHER_PROGRESS	The last global step failed to locate a lower point than the current x value.

Fatal Errors

IMSL_FALSE_CONVERGENCE	False convergence—The iterates appear to be converging to a noncritical point. Possibly incorrect gradient information is used, or the function is discontinuous, or the other stopping tolerances are too tight.
IMSL_STOP_USER_FCN	Request from user supplied function to stop algorithm. User flag = “#”.