e04lb:: Minimizing or Maximizing a Function (NAG Toolbox)

nag_opt_bounds_mod_deriv2_comp (e04lb) is applicable to problems of the form:

Minimize F (x_{1}, x_{2}, \dots, x_{n}) subject to ​ l_{j} \leq x_{j} \leq u_{j}, j = 1, 2, \dots, n .

Special provision is made for unconstrained minimization (i.e., problems which actually have no bounds on the

x_{j}

), problems which have only non-negativity bounds, and problems in which

l_{1} = l_{2} = \dots = l_{n}

and

u_{1} = u_{2} = \dots = u_{n}

. It is possible to specify that a particular

x_{j}

should be held constant. You must supply a starting point, a funct to calculate the value of

F (x)

and its first derivatives

\frac{\partial F}{\partial x_{j}}

at any point

x

, and a h to calculate the second derivatives

\frac{\partial^{2} F}{\partial x_{i} \partial x_{j}}

There are two sets of convergence criteria – a weaker and a stronger. Whenever the weaker criteria are satisfied, the Lagrange multipliers are estimated for all active constraints. If any Lagrange multiplier estimate is significantly negative, then one of the variables associated with a negative Lagrange multiplier estimate is released from its bound and the next search direction is computed in the extended subspace (i.e.,

n_{z}

is increased). Otherwise, minimization continues in the current subspace until the stronger criteria are satisfied. If at this point there are no negative or near-zero Lagrange multiplier estimates, the process is terminated.

References

Parameters

Compulsory Input Parameters

Optional Input Parameters

Output Parameters

Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

Accuracy

A successful exit (

ifail = 0

) is made from nag_opt_bounds_mod_deriv2_comp (e04lb) when

H^{(k)}

is positive definite and when (B1, B2 and B3) or B4 hold, where

\begin{array}{l} B1 & \equiv & α^{(k)} \times ‖p^{(k)}‖ < (xtol + \sqrt{ε}) \times (1.0 + ‖x^{(k)}‖) \\ B2 & \equiv & |F^{(k)} - F^{(k - 1)}| < ({xtol}^{2} + ε) \times (1.0 + |F^{(k)}|) \\ B3 & \equiv & ‖g_{z}^{(k)}‖ < (ε^{1 / 3} + xtol) \times (1.0 + |F^{(k)}|) \\ B4 & \equiv & ‖g_{z}^{(k)}‖ < 0.01 \times \sqrt{ε} . \end{array}

(Quantities with superscript

k

are the values at the

k

th iteration of the quantities mentioned in Description.

ε

is the machine precision and

‖.‖

denotes the Euclidean norm.)

ifail = 3

5

x_{sol}

may still be a good estimate of

x_{true}

, but the following checks should be made. Let the largest of the first

n_{z}

elements of hesd be

hesd (b)

, let the smallest be

hesd (s)

, and define

k = hesd (b) / hesd (s)

. The scalar

k

is usually a good estimate of the condition number of the projected Hessian matrix at

x_{sol}

. If

(i)	the sequence $\{F (x^{(k)})\}$ converges to $F (x_{sol})$ at a superlinear or fast linear rate,
(ii)	${‖g_{z} (x_{sol})‖}^{2} < 10.0 \times ε$ , and
(iii)	$k < 1.0 / ‖g_{z} (x_{sol})‖$ ,

then it is almost certain that

x_{sol}

is a close approximation to the position of a minimum. When (ii) is true, then usually

F (x_{sol})

is a close approximation to

F (x_{true})

. The quantities needed for these checks are all available via monit; in particular the value of cond in the last call of monit before exit gives

k

Further Comments

Timing

The number of iterations required depends on the number of variables, the behaviour of

F (x)

, the accuracy demanded and the distance of the starting point from the solution. The number of multiplications performed in an iteration of nag_opt_bounds_mod_deriv2_comp (e04lb) is

\frac{n_{z}^{3}}{6} + O (n_{z}^{2})

. In addition, each iteration makes one call of h and at least one call of funct. So, unless

F (x)

and its derivatives can be evaluated very quickly, the run time will be dominated by the time spent in funct and h.

Scaling

Ideally, the problem should be scaled so that, at the solution,

F (x)

and the corresponding values of the

x_{j}

are each in the range

(- 1, + 1)

, and so that at points one unit away from the solution,

F (x)

differs from its value at the solution by approximately one unit. This will usually imply that the Hessian matrix at the solution is well-conditioned. It is unlikely that you will be able to follow these recommendations very closely, but it is worth trying (by guesswork), as sensible scaling will reduce the difficulty of the minimization problem, so that nag_opt_bounds_mod_deriv2_comp (e04lb) will take less computer time.

Unconstrained Minimization

If a problem is genuinely unconstrained and has been scaled sensibly, the following points apply:

(a)	$n_{z}$ will always be $n$ ,
(b)	hesl and hesd will be factors of the full second derivative matrix with elements stored in the natural order,
(c)	the elements of $g$ should all be close to zero at the final point,
(d)	the values of the $istate (j)$ given by monit and on exit from nag_opt_bounds_mod_deriv2_comp (e04lb) are unlikely to be of interest (unless they are negative, which would indicate that the modulus of one of the $x_{j}$ has reached $10^{6}$ for some reason),
(e)	monit's argument gpjnrm simply gives the norm of the first derivative vector.

Example

A program to minimize

F = {(x_{1} + 10 x_{2})}^{2} + 5 {(x_{3} - x_{4})}^{2} + {(x_{2} - 2 x_{3})}^{4} + 10 {(x_{1} - x_{4})}^{4}

subject to the bounds

\begin{aligned} 1 & \leq & x_{1} & \leq & 3 \\ - 2 & \leq & x_{2} & \leq & 0 \\ 1 & \leq & x_{4} & \leq & 3 . \end{aligned}

starting from the initial guess

(3, - 1, 0, 1)

. Before calling nag_opt_bounds_mod_deriv2_comp (e04lb), the program calls nag_opt_check_deriv (e04hc) and nag_opt_check_deriv2 (e04hd) to check the derivatives calculated by user-supplied functions funct and h.

function e04lb_example


fprintf('e04lb example results\n\n');

global monitoring;
monitoring = false;

bl = [ 1; -2; -1000000; 1];
bu = [ 3;  0;  1000000; 3];
x  = [ 3; -1;        0; 1];
ibound  = int64(0);
lh      = int64(6);
iw(1:2) = int64(0);
w       = zeros(34,1);
% Catch warnings and assume ifail=3,5 gives a good estimate
wstat = warning();
warning('OFF');
[bl, bu, x, hesl, hesd, istate, f, g, iw, w, ifail] = ...
  e04lb(@funct, @hess, @monit, ibound, bl, bu, x, lh, iw, w);
warning(wstat);
if (ifail == 0 || ifail == 5 | ifail == 3)
  fprintf('\nMinimum found at x: ');
  fprintf(' %9.4f',x);
  fprintf('\nGradients at x,  g: ');
  fprintf(' %9.4f',g);
  fprintf('\nMinimum value     :  %9.4f\n\n',f);
else   
  fprintf('\n Error: e04lb returns ifail = %d\n',ifail);
end



function [iflag, fc, gc] = funct(iflag, n, xc)
  gc = zeros(n, 1);
  fc = 0;
  x1 = xc(1) + 10*xc(2);
  x2 = xc(3) -    xc(4);
  x3 = xc(2) -  2*xc(3);
  x4 = xc(1) -    xc(4);
  fc = x1^2 + 5*x2^2 + x3^4 + 10*x4^4;
  gc(1) =   2*x1 + 40*x4^3;
  gc(2) =  20*x1 +  4*x3^3;
  gc(3) =  10*x2 -  8*x3^3;
  gc(4) = -10*x2 - 40*x4^3;


function [iflag, fhesl, fhesd] = hess(iflag, n, xc, lh, fhesd)
  fhesl = zeros(lh, 1);

  x3 = xc(2) -  2*xc(3);
  x4 = xc(1) -    xc(4);
  fhesd(1) =    2 + 120*x4^2;
  fhesd(2) =  200 +  12*x3^2;
  fhesd(3) =   10 +  48*x3^2;
  fhesd(4) =   10 + 120*x4^2;
  fhesl(1) =   20;
  fhesl(2) =    0;
  fhesl(3) =  -24*x3^2;
  fhesl(4) = -120*x4^2;
  fhesl(5) =    0;
  fhesl(6) =  -10;


function [] = monit(n, xc, fc, gc, istate, gpjnrm, cond, posdef, niter, nf)

global monitoring;
if (monitoring)
  fprintf('\n Itn     Fn evals         Fn value     Norm of proj gradient\n');
  fprintf(' %3d      %5d    %15.4f      %13.4f\n', niter, nf, fc, gpjnrm);
  fprintf('\n j           x(j)           g(j)         Status\n');
  for j = 1:double(n)
    isj = istate(j);
    if (isj > 0)
      fprintf('%2d %16.4f%15.4f   %s\n', j, xc(j), gc(j), '    Free');
    elseif (isj == -1)
      fprintf('%2d %16.4f%15.4f   %s\n', j, xc(j), gc(j), '    Upper Bound');
    elseif (isj == -2)
      fprintf('%2d %16.4f%15.4f   %s\n', j, xc(j), gc(j), '    Lower Bound');
    elseif (isj == -3)
      fprintf('%2d %16.4f%15.4f   %s\n', j, xc(j), gc(j), '    Constant');
    end
  end
  if (cond ~= 0.0d0)
    if (cond > 1.0d6)
      fprintf('\nEst. condition number of projected Hessian > 10^6\n');
    else
      fprintf('\nEst. condition number of projected Hessian = %10.2f\n', cond);
    end
    if ( not(posdef) )
%     The following statement is included so that this MONIT
%     can be used in conjunction with either of the functions
%     e04kd or e04lb
      fprintf('\nProjected Hessian matrix is not positive definite\n');
    end
  end
end

On entry,	$n < 1$ ,
or	$maxcal < 1$ ,
or	$eta < 0.0$ ,
or	$eta \geq 1.0$ ,
or	$xtol < 0.0$ ,
or	$stepmx < xtol$ ,
or	$ibound < 0$ ,
or	$ibound > 4$ ,
or	$bl (j) > bu (j)$ for some $j$ if $ibound = 0$ ,
or	$bl (1) > bu (1)$ if $ibound = 3$ ,
or	$lh < \max (1, n \times (n - 1) / 2)$ ,
or	$liw < 2$ ,
or	$lw < \max (8, 7 \times n + n \times (n - 1) / 2)$ .

NAG Toolbox: nag_opt_bounds_mod_deriv2_comp (e04lb)

▸▿ Contents

Purpose

Syntax

Description