immoptibox

1.2. Nonlinear Least Squares Problems   We seek a minimizer x* of the function where the fi are given functions of and is the vector function with fi(x) as its ith component. A minimizer satisfies F'(x*) = 0, where the gradient is given by J(x) is the Jacobian, as defined by The toolbox functions dogleg, marquardt and nlshybrid assume an analytic expression for the Jacobian. In those cases the user must supply a MATLAB function with a header of the form function [f, J] = fun(x,p1,p2,...) The function should return f(x) as a column vector in  f  and the m*n Jacobian in  J . The toolbox functions allow a list of parameters  p1,p2,...  . The implementation of J(x) can be checked by   checkgrad   . The function smarquardt only needs a user supplied function with the header of the form function f = fun(x,p1,p2,...) Also this function should return f(x) as a column vector in  f  .

1.2.1. User's guide to   dogleg This function is based on Powell's dog-leg algorithm, as described eg in Section 3.3 of [L3]. Typical calls are     [X, info] = dogleg(fun, x0)     [X, info] = dogleg(fun, x0, opts, p1,p2,...)     [X, info, perf] = dogleg(.....)
Input parameters
fun	Handle to the function.
x0	Starting guess for x*.
opts	Vector with five elements,
	opts(1)	initial trust region radius   Δ.
	opts(2:5)	used in stopping criteria:
	Default   opts = [0.1(1+||x0||) 1e-4 1e-8 1e-6 100] If the input opts has less than 5 elements, it is augmented by the default values.
p1,p2,...   are passed directly to the function  fun .
Output parameters
X	If perf is present, then X is an array, holding the iterates columnwise, with the computed solution in the last column. Otherwise, X returns the computed solution vector.
info	Performance information, vector with 6 elements:
	info(1:4)
	info(5) =	Number of iteration steps.
	info(6) =	1:   Stopped by small gradient.  2:   Stopped by small x-step.  3:   No. of iteration steps exceeded. -1:   x is not a real valued vector. -2:   f is not a real valued column vector. -3:   J is not a real valued matrix. -4:   Dimension mismatch in x, f and J. -5:   Overflow during computation.
perf	Array, holding perf(1,:)   :   values of   F(x) perf(2,:)   :   values of   || F'(x) ||inf perf(3,:)   :   values of   Δ .

1.2.2. User's guide to   marquardt This function is based on Levenberg-Marquardt damping of the Gauss-Newton method. as described eg in Section 3.2 of [L3]. The updating of the damping parameter is further described in [7].
Typical calls are     [X, info] = marquardt(fun, x0)     [X, info] = marquardt(fun, x0, opts, p1,p2,...)     [X, info, perf] = marquardt(.....)
Input parameters
fun	Handle to the function.
x0	Starting guess for   x* .
opts	Vector with four elements,
	opts(1)	Used to get starting value for damping parameter:
	opts(2:4)	used in stopping criteria:
	Default   opts = [1e-3 1e-4 1e-8 100] If the input opts has less than 4 elements, it is augmented by the default values.
p1,p2,...   are passed directly to the function  fun .
Output parameters
X	If perf is present, then X is an array, holding the iterates columnwise, with the computed solution in the last column. Otherwise, X returns the computed solution vector.
info	Performance information, vector with 6 elements:
	info(1:4)	Final values of
	info(5) =	Number of iteration steps.
	info(6) =	1:   Stopped by small gradient.  2:   Stopped by small x-step.  3:   No. of iteration steps exceeded. -1:   x is not a real valued vector. -2:   f is not a real valued column vector. -3:   J is not a real valued matrix. -4:   Dimension mismatch in x, f and J. -5:   Overflow during computation.
perf	Array, holding perf(1,:)   :   values of   F(x) perf(2,:)   :   values of   || F'(x) ||inf perf(3,:)   :   values of damping parameter   μ .

1.2.3. User's guide to   nlshybrid This function is based on a hybrid between the Gauss-Newton algorithm behind marquardt and a Quasi-Newton algorithm based on BFGS updatings of an approximation to the Hessian. See Section 3.4 in [L3].
Typical calls are
	[X, info] = nlshybrid(fun, x0) [X, info] = nlshybrid(fun, x0, opts, p1,p2,...) [X, info, perf] = nlshybrid(.....)
Input parameters
fun	Handle to the function.
x0	Starting guess for   x* .
opts	Vector with five elements.
	opts(1:4)	as in marquardt,
	opts(5)	d , defines step length in difference approximations.
	Default   opts = [1e-3 1e-4 1e-8 100 1e-5] . If the input opts has less than 5 elements, it is augmented by the default values.
p1,p2,...   are passed directly to the function  fun .
Output parameters
X	As in marquardt .
info	Performance information, vector with 6 elements:
	info(1:5)	As in marquardt .
	info(6) =	1:   Stopped by small gradient.  2:   Stopped by small x-step.  3:   No. of iteration steps exceeded. -1:   x is not a real valued vector. -2:   f is not a real valued column vector. -5:   Overflow during computation. -6:   Error in approximate Jacobian.
perf	As in marquardt .

1.2.4. User's guide to   smarquardt This function is based on the same algorithm as marquardt, but instead of an analytic expression for the Jacobian, this matrix function is approximated by successive updatings. See Section 3.4 in [L3].
The initial approximation is either given as input or it is computed by forward differences,       B(:,j) = (f(x+hj*ej) - f(x))/hj , where   ej   is the unit vector in the jth direction, and   hj = d2   if   xj = 0 , otherwise hj = d*|xj| . d   is an input parameter. Typical calls are
	[X, info] = smarquardt(fun, x0) [X, info] = smarquardt(fun, x0, opts) [X, info] = smarquardt(fun, x0, opts, B0, p1,p2,...) [X, info, perf] = smarquardt(.....) [X, info, perf, B] = smarquardt(.....)
Input parameters
fun	Handle to the function. Only   f(x)   is used
x0	Starting guess for   x* .
opts	Vector with five elements,
	opts(1:4)	As in marquardt
	opts(5)	"Relative" step length d for difference approximations.
	Default   opts = opts = [1e-3 1e-4 1e-8 100 1e-7] If the input opts has less than 5 elements, it is augmented by the default values.
B0	(Approximation to) J(x0) . If B0 is not given or if it is empty, then a forward difference approximation to it is used.
p1,p2,...   are passed directly to the function  fun .
Output parameters
X	As in marquardt .
info	Performance information. Vector with 7 elements:
	info(1:5)	As in marquardt .
	info(6) =	1:   Stopped by small gradient.  2:   Stopped by small x-step.  3:   No. of iteration steps exceeded. -1:   x is not a real valued vector. -2:   f is not a real valued column vector. -4:   Dimension mismatch in x, f and B0. -5:   Overflow during computation. -6:   Error in approximate Jacobian.
	info(7) =	No. of function evaluations.
perf	As in marquardt .
B	Computed approximation to Jacobian at the solution.

1.2.5. Example Consider the function
	function [f, J] = myfun(x, p) f = [p*(x(2) - x(1)^2); 1 - x(1)]; if nargout > 1   J = [-2*p*x(1) p; -1 0]; end
With   p = 10   this is an implementation of the famous Rosenbrock function. In the program
	x0 = [-1.2 1];   p = 10; [x1 ii1] = dogleg(@myfun,x0,[],p) [x2 ii2] = marquardt(@myfun,x0,[],p) [x3 ii3] = nlshybrid(@myfun,x0,[],p) [x4 ii4] = smarquardt(@myfun,x0,[],[],p)
we use the default values for opts and an empty B0 in smarquardt. We get the following results,
	x1 = 1 1   x2 = 0.9999992008 0.9999983957   x3 = 0.9999992008 0.9999983957   x4 = 0.9999998944 0.9999997841
	ii1 = ii2 = ii3 = ii4 =   0   3.21e-13 3.21e-13 6.64e-15     0    5.87e-07 5.87e-07 8.16e-07     6.02e-03 1.17e-04 1.17e-04 2.20e-05     2.16e-01 2.55e-06 7.64e-06 1.79e-06     20 15 15 27     1 1 1 1           50
In all the cases we find a good approximation to the true minimizer,   x* = [1 1] , and   iix(6) = 1   shows that iteration stops because the the infinity norm of the gradient ( iix(2) ) is smaller than the default threshold opts(2) = 1e-4 . nlshybrid performs like marquardt because this converges so fast that there is no change to the Quasi-Newton method. smarquardt uses almost twice as many iterations as marquardt, costing a total of 50 function evaluations, whereas marquardt uses 16 evaluations of f(x) and the Jacobian J(x).