Nonlinear Equations
*******************

Solvers
=======

Octave can solve sets of nonlinear equations of the form

     F (x) = 0

using the function fsolve, which is based on the MINPACK subroutine hybrd.  This is an iterative technique so a starting point must be provided.  This also has the consequence that convergence is not guaranteed even if a solution exists.

 -- X =: fsolve (FCN, X0)
 -- X =: fsolve (FCN, X0, OPTIONS)
 -- [X, FVAL] =: fsolve (...)
 -- [X, FVAL, INFO] =: fsolve (...)
 -- [X, FVAL, INFO, OUTPUT] =: fsolve (...)
 -- [X, FVAL, INFO, OUTPUT, FJAC] =: fsolve (...)
     Solve a system of nonlinear equations defined by the function FCN.

     FCN is a function handle, inline function, or string containing the name of the function to evaluate.  FCN should accept a vector (array) defining the unknown variables, and return a vector of left-hand sides of the equations.  Right-hand sides are defined to be zeros.  In other words, this function attempts to determine a vector X such that FCN (X) gives (approximately) all zeros.

     X0 is an initial guess for the solution.  The shape of X0 is preserved in all calls to FCN, but otherwise is treated as a column vector.

     OPTIONS is a structure specifying additional parameters which control the algorithm.  Currently, fsolve recognizes these options: "AutoScaling", "ComplexEqn", "FinDiffType", "FunValCheck", "Jacobian", "MaxFunEvals", "MaxIter", "OutputFcn", "TolFun", "TolX", "TypicalX", and "Updating".

     If "AutoScaling" is "on", the variables will be automatically scaled according to the column norms of the (estimated) Jacobian.  As a result, "TolFun" becomes scaling-independent.  By default, this option is "off" because it may sometimes deliver unexpected (though mathematically correct) results.

     If "ComplexEqn" is "on", fsolve will attempt to solve complex equations in complex variables, assuming that the equations possess a complex derivative (i.e., are holomorphic).  If this is not what you want, you should unpack the real and imaginary parts of the system to get a real system.

     If "Jacobian" is "on", it specifies that FCN---when called with 2 output arguments---also returns the Jacobian matrix of right-hand sides at the requested point.

     "MaxFunEvals" proscribes the maximum number of function evaluations before optimization is halted.  The default value is 100 * number_of_variables, i.e., 100 * length (X0). The value must be a positive integer.

     If "Updating" is "on", the function will attempt to use Broyden updates to update the Jacobian, in order to reduce the number of Jacobian calculations.  If your user function always calculates the Jacobian (regardless of number of output arguments) then this option provides no advantage and should be disabled.

     "TolX" specifies the termination tolerance in the unknown variables, while "TolFun" is a tolerance for equations.  Default is 1e-6 for both "TolX" and "TolFun".

     For a description of the other options, see optimset.  To initialize an options structure with default values for fsolve use options = optimset ("fsolve").

     The first output X is the solution while the second output FVAL contains the value of the function FCN evaluated at X (ideally a vector of all zeros).

     The third output INFO reports whether the algorithm succeeded and may take one of the following values:

     1
          Converged to a solution point.  Relative residual error is less than specified by TolFun.

     2
          Last relative step size was less than TolX.

     3
          Last relative decrease in residual was less than TolFun.

     0
          Iteration limit (either MaxIter or MaxFunEvals) exceeded.

     -1
          Stopped by OutputFcn.

     -2
          The Jacobian became excessively small and the search stalled.

     -3
          The trust region radius became excessively small.

     OUTPUT is a structure containing runtime information about the fsolve algorithm.  Fields in the structure are:

     iterations
          Number of iterations through loop.

     successful
          Number of successful iterations.

     funcCount
          Number of function evaluations.

     The final output FJAC contains the value of the Jacobian evaluated at X.

     Note: If you only have a single nonlinear equation of one variable, using fzero is usually a much better idea.

     Note about user-supplied Jacobians: As an inherent property of the algorithm, a Jacobian is always requested for a solution vector whose residual vector is already known, and it is the last accepted successful step.  Often this will be one of the last two calls, but not always.  If the savings by reusing intermediate results from residual calculation in Jacobian calculation are significant, the best strategy is to employ OutputFcn: After a vector is evaluated for residuals, if OutputFcn is called with that vector, then the intermediate results should be saved for future Jacobian evaluation, and should be kept until a Jacobian evaluation is requested or until OutputFcn is called with a different vector, in which case they should be dropped in favor of this most recent vector.  A short example how this can be achieved follows:

          function [fval, fjac] = user_fcn (x, optimvalues, state)
          persistent sav = [], sav0 = [];
          if (nargin == 1)
            ## evaluation call
            if (nargout == 1)
              sav0.x = x; # mark saved vector
              ## calculate fval, save results to sav0.
            elseif (nargout == 2)
              ## calculate fjac using sav.
            endif
          else
            ## outputfcn call.
            if (all (x == sav0.x))
              sav = sav0;
            endif
            ## maybe output iteration status, etc.
          endif
          endfunction

          ## ...

          fsolve (@user_fcn, x0, optimset ("OutputFcn", @user_fcn, ...))

     fzero, optimset

The following is a complete example.  To solve the set of equations

     -2x^2 + 3xy   + 4 sin(y) = 6
      3x^2 - 2xy^2 + 3 cos(x) = -4

you first need to write a function to compute the value of the given function.  For example:

     function y = f (x)
       y = zeros (2, 1);
       y(1) = -2*x(1)^2 + 3*x(1)*x(2)   + 4*sin(x(2)) - 6;
       y(2) =  3*x(1)^2 - 2*x(1)*x(2)^2 + 3*cos(x(1)) + 4;
     endfunction

Then, call fsolve with a specified initial condition to find the roots of the system of equations.  For example, given the function f defined above,

     [x, fval, info] = fsolve (@f, [1; 2])

results in the solution

     x =

       0.57983
       2.54621

     fval =

       -5.7184e-10
        5.5460e-10

     info = 1

A value of info = 1 indicates that the solution has converged.

When no Jacobian is supplied (as in the example above) it is approximated numerically.  This requires more function evaluations, and hence is less efficient.  In the example above we could compute the Jacobian analytically as

     function [y, jac] = f (x)
       y = zeros (2, 1);
       y(1) = -2*x(1)^2 + 3*x(1)*x(2)   + 4*sin(x(2)) - 6;
       y(2) =  3*x(1)^2 - 2*x(1)*x(2)^2 + 3*cos(x(1)) + 4;
       if (nargout == 2)
         jac = zeros (2, 2);
         jac(1,1) =  3*x(2) - 4*x(1);
         jac(1,2) =  4*cos(x(2)) + 3*x(1);
         jac(2,1) = -2*x(2)^2 - 3*sin(x(1)) + 6*x(1);
         jac(2,2) = -4*x(1)*x(2);
       endif
     endfunction

The Jacobian can then be used with the following call to fsolve:

     [x, fval, info] = fsolve (@f, [1; 2], optimset ("jacobian", "on"));

which gives the same solution as before.

 -- X =: fzero (FCN, X0)
 -- X =: fzero (FCN, X0, OPTIONS)
 -- [X, FVAL] =: fzero (...)
 -- [X, FVAL, INFO] =: fzero (...)
 -- [X, FVAL, INFO, OUTPUT] =: fzero (...)
     Find a zero of a univariate function.

     FCN is a function handle, inline function, or string containing the name of the function to evaluate.

     X0 should be a two-element vector specifying two points which bracket a zero.  In other words, there must be a change in sign of the function between X0(1) and X0(2).  More mathematically, the following must hold

          sign (FCN(X0(1))) * sign (FCN(X0(2))) <= 0

     If X0 is a single scalar then several nearby and distant values are probed in an attempt to obtain a valid bracketing.  If this is not successful, the function fails.

     OPTIONS is a structure specifying additional options.  Currently, fzero recognizes these options: "Display", "FunValCheck", "MaxFunEvals", "MaxIter", "OutputFcn", and "TolX".

     "MaxFunEvals" proscribes the maximum number of function evaluations before the search is halted.  The default value is Inf. The value must be a positive integer.

     "MaxIter" proscribes the maximum number of algorithm iterations before the search is halted.  The default value is Inf. The value must be a positive integer.

     "TolX" specifies the termination tolerance for the solution X. The default value is eps.

     For a description of the other options, see optimset. To initialize an options structure with default values for fzero use options = optimset ("fzero").

     On exit, the function returns X, the approximate zero point, and FVAL, the function evaluated at X.

     The third output INFO reports whether the algorithm succeeded and may take one of the following values:

       * 1 The algorithm converged to a solution.

       * 0 Maximum number of iterations or function evaluations has been reached.

       * -1 The algorithm has been terminated by a user OutputFcn.

       * -5 The algorithm may have converged to a singular point.

     OUTPUT is a structure containing runtime information about the fzero algorithm.  Fields in the structure are:

       * iterations Number of iterations through loop.

       * funcCount Number of function evaluations.

       * algorithm The string "bisection, interpolation".

       * bracketx A two-element vector with the final bracketing of the zero along the x-axis.

       * brackety A two-element vector with the final bracketing of the zero along the y-axis.

     optimset, fsolve

Minimizers
==========

Often it is useful to find the minimum value of a function rather than just the zeroes where it crosses the x-axis.  fminbnd is designed for the simpler, but very common, case of a univariate function where the interval to search is bounded.  For unbounded minimization of a function with potentially many variables use fminunc or fminsearch.  The two functions use different internal algorithms and some knowledge of the objective function is required.  For functions which can be differentiated, fminunc is appropriate.  For functions with discontinuities, or for which a gradient search would fail, use fminsearch. See Optimization for minimization with the presence of constraint functions.  Note that searches can be made for maxima by simply inverting the objective function (Fto_max = -Fto_min).

 -- X =: fminbnd (FCN, A, B)
 -- X =: fminbnd (FCN, A, B, OPTIONS)
 -- [X, FVAL, INFO, OUTPUT] =: fminbnd (...)
     Find a minimum point of a univariate function.

     FCN is a function handle, inline function, or string containing the name of the function to evaluate.

     The starting interval is specified by A (left boundary) and B (right boundary).  The endpoints must be finite.

     OPTIONS is a structure specifying additional parameters which control the algorithm.  Currently, fminbnd recognizes these options: "Display", "FunValCheck", "MaxFunEvals", "MaxIter", "OutputFcn", "TolX".

     "MaxFunEvals" proscribes the maximum number of function evaluations before optimization is halted.  The default value is 500. The value must be a positive integer.

     "MaxIter" proscribes the maximum number of algorithm iterations before optimization is halted.  The default value is 500. The value must be a positive integer.

     "TolX" specifies the termination tolerance for the solution X. The default is 1e-4.

     For a description of the other options, see optimset. To initialize an options structure with default values for fminbnd use options = optimset ("fminbnd").

     On exit, the function returns X, the approximate minimum point, and FVAL, the function evaluated X.

     The third output INFO reports whether the algorithm succeeded and may take one of the following values:

       * 1 The algorithm converged to a solution.

       * 0 Iteration limit (either MaxIter or MaxFunEvals) exceeded.

       * -1 The algorithm was terminated by a user OutputFcn.

     Application Notes:

      1. The search for a minimum is restricted to be in the finite interval bound by A and B.  If you have only one initial point to begin searching from then you will need to use an unconstrained minimization algorithm such as fminunc or fminsearch. fminbnd internally uses a Golden Section search strategy.

      2. Use Anonymous Functions to pass additional parameters to FCN. For specific examples of doing so for fminbnd and other minimization functions see the Minimizers section of the GNU Octave manual.

     fzero, fminunc, fminsearch, optimset

 -- X =: fminunc (FCN, X0)
 -- X =: fminunc (FCN, X0, OPTIONS)
 -- [X, FVAL] =: fminunc (FCN, ...)
 -- [X, FVAL, INFO] =: fminunc (FCN, ...)
 -- [X, FVAL, INFO, OUTPUT] =: fminunc (FCN, ...)
 -- [X, FVAL, INFO, OUTPUT, GRAD] =: fminunc (FCN, ...)
 -- [X, FVAL, INFO, OUTPUT, GRAD, HESS] =: fminunc (FCN, ...)
     Solve an unconstrained optimization problem defined by the function FCN.

     fminunc attempts to determine a vector X such that FCN (X) is a local minimum.

     FCN is a function handle, inline function, or string containing the name of the function to evaluate.  FCN should accept a vector (array) defining the unknown variables, and return the objective function value, optionally with gradient.

     X0 determines a starting guess.  The shape of X0 is preserved in all calls to FCN, but otherwise is treated as a column vector.

     OPTIONS is a structure specifying additional parameters which control the algorithm.  Currently, fminunc recognizes these options: "AutoScaling", "FinDiffType", "FunValCheck", "GradObj", "MaxFunEvals", "MaxIter", "OutputFcn", "TolFun", "TolX", "TypicalX".

     If "AutoScaling" is "on", the variables will be automatically scaled according to the column norms of the (estimated) Jacobian.  As a result, "TolFun" becomes scaling-independent.  By default, this option is "off" because it may sometimes deliver unexpected (though mathematically correct) results.

     If "GradObj" is "on", it specifies that FCN---when called with two output arguments---also returns the Jacobian matrix of partial first derivatives at the requested point.

     "MaxFunEvals" proscribes the maximum number of function evaluations before optimization is halted.  The default value is 100 * number_of_variables, i.e., 100 * length (X0). The value must be a positive integer.

     "MaxIter" proscribes the maximum number of algorithm iterations before optimization is halted.  The default value is 400. The value must be a positive integer.

     "TolX" specifies the termination tolerance for the unknown variables X, while "TolFun" is a tolerance for the objective function value FVAL.  The default is 1e-6 for both options.

     For a description of the other options, see optimset.

     On return, X is the location of the minimum and FVAL contains the value of the objective function at X.

     INFO may be one of the following values:

     1
          Converged to a solution point.  Relative gradient error is less than specified by TolFun.

     2
          Last relative step size was less than TolX.

     3
          Last relative change in function value was less than TolFun.

     0
          Iteration limit exceeded---either maximum number of algorithm iterations MaxIter or maximum number of function evaluations MaxFunEvals.

     -1
          Algorithm terminated by OutputFcn.

     -3
          The trust region radius became excessively small.

     Optionally, fminunc can return a structure with convergence statistics (OUTPUT), the output gradient (GRAD) at the solution X, and approximate Hessian (HESS) at the solution X.

     Application Notes:

      1. If the objective function is a single nonlinear equation of one variable then using fminbnd is usually a better choice.

      2. The algorithm used by fminunc is a gradient search which depends on the objective function being differentiable.  If the function has discontinuities it may be better to use a derivative-free algorithm such as fminsearch.

      3. Use Anonymous Functions to pass additional parameters to FCN. For specific examples of doing so for fminunc and other minimization functions see the Minimizers section of the GNU Octave manual.

     fminbnd, fminsearch, optimset

 -- X =: fminsearch (FCN, X0)
 -- X =: fminsearch (FCN, X0, OPTIONS)
 -- X =: fminsearch (PROBLEM)
 -- [X, FVAL, EXITFLAG, OUTPUT] =: fminsearch (...)

     Find a value of X which minimizes the multi-variable function FCN.

     FCN is a function handle, inline function, or string containing the name of the function to evaluate.

     The search begins at the point X0 and iterates using the Nelder & Mead Simplex algorithm (a derivative-free method).  This algorithm is better-suited to functions which have discontinuities or for which a gradient-based search such as fminunc fails.

     Options for the search are provided in the parameter OPTIONS using the function optimset.  Currently, fminsearch accepts the options: "Display", "FunValCheck","MaxFunEvals", "MaxIter", "OutputFcn", "TolFun", "TolX".

     "MaxFunEvals" proscribes the maximum number of function evaluations before optimization is halted.  The default value is 200 * number_of_variables, i.e., 200 * length (X0). The value must be a positive integer.

     "MaxIter" proscribes the maximum number of algorithm iterations before optimization is halted.  The default value is 200 * number_of_variables, i.e., 200 * length (X0). The value must be a positive integer.

     For a description of the other options, see optimset.  To initialize an options structure with default values for fminsearch use options = optimset ("fminsearch").

     fminsearch may also be called with a single structure argument with the following fields:

     objective
          The objective function.

     x0
          The initial point.

     solver
          Must be set to "fminsearch".

     options
          A structure returned from optimset or an empty matrix to indicate that defaults should be used.

     The field options is optional.  All others are required.

     On exit, the function returns X, the minimum point, and FVAL, the function value at the minimum.

     The third output EXITFLAG reports whether the algorithm succeeded and may take one of the following values:

     1
          if the algorithm converged (size of the simplex is smaller than TolX AND the step in function value between iterations is smaller than TolFun).

     0
          if the maximum number of iterations or the maximum number of function evaluations are exceeded.

     -1
          if the iteration is stopped by the "OutputFcn".

     The fourth output is a structure OUTPUT containing runtime about the algorithm.  Fields in the structure are funcCount containing the number of function calls to FCN, iterations containing the number of iteration steps, algorithm with the name of the search algorithm (always: "Nelder-Mead simplex direct search"), and message with the exit message.

     Example:

          fminsearch (@(x) (x(1)-5).^2+(x(2)-8).^4, [0;0])

     Application Notes:

      1. If you need to find the minimum of a single variable function it is probably better to use fminbnd.

      2. The legacy, undocumented syntax for passing parameters to FCN by appending them to the input argument list after OPTIONS is discouraged and will be completely removed in Octave 10.  The preferred, cross-platform compatible method of passing parameters to FCN is through use of Anonymous Functions.  For specific examples of doing so for fminsearch and other minimization functions see the Minimizers section of the GNU Octave manual.

     fminbnd, fminunc, optimset

Certain minimization operations require additional parameters be passed to the function, F, being minimized. E.g., F = F(x, C). Octave's minimizer functions are designed to only pass one optimization variable to F, but parameter passing can be accomplished by defining an Anonymous Function that contains the necessary parameter(s).  See the example below:

     A = 2; B = 3;
     f = @(x) sin (A*x + B);
     fminbnd (f, 0, 2)
        =>   0.8562

Note that anonymous functions retain the value of parameters at the time they are defined.  Changing a parameter value after function definition will not affect output of the function until it is redefined:

     B = 4;
     fminbnd (f, 0, 2)
        =>   0.8562
     f = @(x) sin (A*x + B);
     fminbnd (f, 0, 2)
        =>   0.3562

The function humps is a useful function for testing zero and extrema finding functions.

 -- Y =: humps (X)
 -- [X, Y] =: humps (X)
     Evaluate a function with multiple minima, maxima, and zero crossings.

     The output Y is the evaluation of the rational function:

                  1200*X^4 - 2880*X^3 + 2036*X^2 - 348*X - 88
           Y = - ---------------------------------------------
                   200*X^4 - 480*X^3 + 406*X^2 - 138*X + 17

     X may be a scalar, vector or array.  If X is omitted, the default range [0:0.05:1] is used.

     When called with two output arguments, [X, Y], X will contain the input values, and Y will contain the output from humps.

     Programming Notes: humps has two local maxima located near X = 0.300 and 0.893, a local minimum near X = 0.637, and zeros near X = -0.132 and 1.300.  humps is a useful function for testing algorithms which find zeros or local minima and maxima.

     Try demo humps to see a plot of the humps function. fzero, fminbnd, fminunc, fminsearch