Unconstrained Nonlinear Optimization Examples

On this page…
Example: fminunc Unconstrained Minimization Example: Nonlinear Minimization with Gradient and Hessian Example: Nonlinear Minimization with Gradient and Hessian Sparsity Pattern

Example: fminunc Unconstrained Minimization

Consider the problem of finding a set of values [x₁, x₂] that solves

(6-16)

To solve this two-dimensional problem, write a file that returns the function value. Then, invoke the unconstrained minimization routine fminunc.

Step 1: Write a file objfun.m.

This code ships with the toolbox. To view, enter type objfun:

function f = objfun(x)
f = exp(x(1)) * (4*x(1)^2 + 2*x(2)^2 + 4*x(1)*x(2) + 2*x(2) + 1);

Step 2: Invoke one of the unconstrained optimization routines.

x0 = [-1,1];    % Starting guess
options = optimset('LargeScale','off');
[x,fval,exitflag,output] = fminunc(@objfun,x0,options);

This produces the following output:

Local minimum found.

Optimization completed because the size of the gradient is less
than the default value of the function tolerance.

View the results:

x,fval,exitflag,output

x =
    0.5000   -1.0000

fval =
  3.6609e-015

exitflag =
     1

output = 
   iterations: 8
    funcCount: 66
     stepsize: 1
firstorderopt: 1.2284e-007
    algorithm: 'medium-scale: Quasi-Newton line search'
      message: [1x438 char]

The exitflag tells whether the algorithm converged. exitflag = 1 means a local minimum was found. The meanings of exitflags are given in function reference pages.

The output structure gives more details about the optimization. For fminunc, it includes the number of iterations in iterations, the number of function evaluations in funcCount, the final step-size in stepsize, a measure of first-order optimality (which in this unconstrained case is the infinity norm of the gradient at the solution) in firstorderopt, the type of algorithm used in algorithm, and the exit message (the reason the algorithm stopped).

Pass the variable options to fminunc to change characteristics of the optimization algorithm, as in

x = fminunc(@objfun,x0,options);

options is a structure that contains values for termination tolerances and algorithm choices. Create an options structure using the optimset function:

options = optimset('LargeScale','off');

You can also create an options structure by exporting from the Optimization Tool.

In this example, we have turned off the default selection of the large-scale algorithm and so the medium-scale algorithm is used. Other options include controlling the amount of command line display during the optimization iteration, the tolerances for the termination criteria, whether a user-supplied gradient or Jacobian is to be used, and the maximum number of iterations or function evaluations. See optimset, the individual optimization functions, and Optimization Options Reference for more options and information.

Back to Top

Example: Nonlinear Minimization with Gradient and Hessian

This example involves solving a nonlinear minimization problem with a tridiagonal Hessian matrix H(x) first computed explicitly, and then by providing the Hessian's sparsity structure for the finite-differencing routine.

The problem is to find x to minimize

(6-17)

where n = 1000.

Step 1: Write a file brownfgh.m that computes the objective function, the gradient of the objective, and the sparse tridiagonal Hessian matrix.

The file is lengthy so is not included here. View the code with the command

type brownfgh

Because brownfgh computes the gradient and Hessian values as well as the objective function, you need to use optimset to indicate that this information is available in brownfgh, using the GradObj and Hessian options.

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

n = 1000;
xstart = -ones(n,1);
xstart(2:2:n,1) = 1;
options = optimset('GradObj','on','Hessian','on');
[x,fval,exitflag,output] = fminunc(@brownfgh,xstart,options);

This 1000 variable problem is solved in about 7 iterations and 7 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 =
  2.8709e-017
output = 
       iterations: 7
        funcCount: 8
     cgiterations: 7
    firstorderopt: 4.7948e-010
        algorithm: 'large-scale: trust-region Newton'
          message: [1x498 char]

Back to Top

Example: 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 brownfg file computes the objective function and gradient.

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

function [f,g] = brownfg(x)
% 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 option to Hstr. When a problem as large as this has obvious sparsity structure, not setting the HessPattern option 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 option 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 seven 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,fval,output

exitflag =
     1

fval =
  7.4738e-017

output = 
         iterations: 7
          funcCount: 8
       cgiterations: 7
      firstorderopt: 7.9822e-010
          algorithm: 'large-scale: trust-region Newton'
            message: [1x498 char]
    constrviolation: []

Back to Top

Unconstrained Nonlinear Optimization Algorithms

Constrained Nonlinear Optimization Algorithms

© 1984-2012- The MathWorks, Inc.    -   Site Help   -   Patents   -   Trademarks   -   Privacy Policy   -   Preventing Piracy   -   RSS