Optimization Toolbox

Nonlinear Minimization with Gradient and Hessian Sparsity Pattern

Next, solve the same problem but the Hessian matrix is now approximated by sparse finite differences instead of explicit computation. To use the large-scale method in fminunc, you must compute the gradient in fun; it is not optional as in the medium-scale method.

The M-file function brownfg computes the objective function and gradient.

Step 1: Write an M-file brownfg.m that computes the objective function and the gradient of the objective.

• function [f,g] = brownfg(x,dummy)
  % BROWNFG Nonlinear minimization test problem
  % 
  % Evaluate the function
  n=length(x); y=zeros(n,1);
  i=1:(n-1);
  y(i)=(x(i).^2).^(x(i+1).^2+1) + ...
          (x(i+1).^2).^(x(i).^2+1);
    f=sum(y);
  % Evaluate the gradient if nargout > 1
    if nargout > 1
       i=1:(n-1); g = zeros(n,1);
       g(i) = 2*(x(i+1).^2+1).*x(i).* ...
                ((x(i).^2).^(x(i+1).^2))+ ...
                2*x(i).*((x(i+1).^2).^(x(i).^2+1)).* ...
                log(x(i+1).^2);
       g(i+1) = g(i+1) + ...
                2*x(i+1).*((x(i).^2).^(x(i+1).^2+1)).* ...
                log(x(i).^2) + ...
                2*(x(i).^2+1).*x(i+1).* ...
                ((x(i+1).^2).^(x(i).^2));
    end
  

To allow efficient computation of the sparse finite-difference approximation of the Hessian matrix H(x), the sparsity structure of H must be predetermined. In this case assume this structure, Hstr, a sparse matrix, is available in file brownhstr.mat. Using the spy command you can see that Hstr is indeed sparse (only 2998 nonzeros). Use optimset to set the HessPattern parameter to Hstr. When a problem as large as this has obvious sparsity structure, not setting the HessPattern parameter requires a huge amount of unnecessary memory and computation because fminunc attempts to use finite differencing on a full Hessian matrix of one million nonzero entries.

You must also set the GradObj parameter to 'on' using optimset, since the gradient is computed in brownfg.m. Then execute fminunc as shown in Step 2.

Step 2: Call a nonlinear minimization routine with a starting point xstart.

• fun = @brownfg;
  load brownhstr          % Get Hstr, structure of the Hessian
  spy(Hstr)               % View the sparsity structure of Hstr
  n = 1000;
  xstart = -ones(n,1); 
  xstart(2:2:n,1) = 1;
  options = optimset('GradObj','on','HessPattern',Hstr);
  [x,fval,exitflag,output] = fminunc(fun,xstart,options); 
  

This 1000-variable problem is solved in eight iterations and seven conjugate gradient iterations with a positive exitflag indicating convergence. The final function value and measure of optimality at the solution x are both close to zero (for fminunc, the first-order optimality is the infinity norm of the gradient of the function, which is zero at a local minimum):

• exitflag =
       1
  fval =
    7.4738e-017
  output.iterations
  ans =
       8
  output.cgiterations
  ans =
       7
  output.firstorderopt
  ans =
    7.9822e-010
  

Nonlinear Minimization with Gradient and Hessian

Nonlinear Minimization with Bound Constraints and Banded Preconditioner