Engee documentation

lsqnonlin

Page in progress.

A solver of nonlinear least squares problems.

Library

EngeeOptimization

Description

Function lsqnonlin solves the nonlinear least squares problem of the form:

where



The function is called when solving an optimization problem. optimize or creating optimization settings OptimizeOptions.

Solver Settings

All algorithms

Algorithm

Choose one of the algorithms: "trust-region-reflective" or "levenberg-marquardt" (by default).

Argument Algorithm defines the preferred algorithm for solving the problem.

Diagnostics

Display diagnostic information about the function to be minimized or solved. Available options: false (by default) or true.

DiffMaxChange

The maximum change in variables for finite difference gradients (positive scalar). Default value — nothing.

DiffMinChange

Minimal change of variables for finite difference gradients (positive scalar). Default value — nothing.

Display

Output level:

  • "off" or "none" — there is no output.

  • "iter" (by default) — data output at each iteration and a standard completion message.

  • "iter-detailed" — data output at each iteration and a technical completion message.

  • "final" — output of only the final data and a standard completion message.

  • "final-detailed" — output of only the final data and a technical completion message.

FiniteDifferenceStepSize

Scalar or vector step size coefficient for the finite difference method. If the argument is FiniteDifferenceStepSize set as a vector v, then the increments delta for one-sided finite differences, they are calculated using the formula:

delta = v.*sign′(x).*max(abs(x),TypicalX);

where sign′(x) = sign(x), except for the case sign′(0) = 1. For central finite differences:

delta = v.*max(abs(x),TypicalX);

Scalar value FiniteDifferenceStepSize converted to a vector. Default value — sqrt(eps) for one-sided finite differences and eps^(1/3) for central finite differences.

FiniteDifferenceType

The final differences used to estimate gradients can be "forward" (by default) or "central". Calculation "central" It requires twice as many calls to the function, but provides higher accuracy.

When evaluating both types of finite differences, the algorithm strictly adheres to the specified boundaries. For example, instead of a direct difference, the inverse can be used to avoid calculating the function at a point outside the acceptable range.

FunctionTolerance

Tolerance for the value of the function to terminate the algorithm; non-negative scalar. Default value — 0.001.

FunValCheck

Checking the correctness of function values. When choosing true An error message is displayed if the function returns a complex value., Inf or NaN. The default mode is false, in which the error is not displayed.

MaxFunctionEvaluations

The maximum allowed number of calculations of the function, set as a non-negative integer. The default value is 100 * numberOfVariables for the algorithm "trust-region-reflective", 200 * numberOfVariables for the algorithm "levenberg-marquardt".

MaxIterations

The maximum allowed number of iterations, set as a non-negative integer. The default value is 100 for algorithms "trust-region-reflective" and "levenberg-marquardt".

OptimalityTolerance

The tolerance for the stopping condition according to the optimality criterion of the first order, given as a non-negative scalar. Default value — 0.001.

Algorithm "levenberg-marquardt" uses an optimality tolerance (stopping criterion) equal to 1e−4 multiplied by the argument FunctionTolerance, and does not use the argument OptimalityTolerance.

OutputFcn

Specify one or more custom functions that the optimization function will call at each iteration. Pass a pointer to a function or an array with function pointers. By default, there are no functions (nothing).

PlotFcn

Plotting various graphs reflecting the progress of the algorithm; you can select ready-made graphs or create your own. The argument is passed a name, a pointer to a function, or an array containing names or pointers to functions. For custom charting functions, pointers to functions should be passed. By default, charting is disabled (value nothing).

Custom charting functions use the same syntax as the output functions.

SpecifyObjectiveGradient

If the value is set to false The solver approximates the Jacobian using the finite difference method. If the value is set to true (by default), the solver uses the Jacobian specified by the user (in the function ), or information about the Jacobian (when using JacobMult) for the objective function.

StepTolerance

Variable tolerance , set as a non-negative scalar, to terminate the algorithm. The default value is 0.001 for algorithms "trust-region-reflective" and "levenberg-marquardt".

TypicalX

Typical values . The number of items in TypicalX is equal to the number of elements in (the starting point). Default value — ones(numberofvariables, 1). The solver uses TypicalX to scale the finite differences when estimating the gradient.

UseParallel

Option for using parallel computing to estimate gradients, set to one of the following values:

  • true — evaluation of gradients is performed in parallel. If the pool of parallel processes is not open, the solver starts it using the default cluster profile.

  • false (default value) — gradients are evaluated sequentially.

Algorithm "trust-region-reflective"

JacobianMultiplyFcn

The multiplication function by the Jacobi matrix, specified as a pointer to the function. For large-scale problems with a special structure, this function computes the product J*Y, J'Y or J'(J*Y), without forming the matrix itself J explicitly. For lsqnonlin the function has the form:

W = jmfun(Jinfo, Y, flag)

where Jinfo contains the data needed for the calculation J*Y (or J'Y or J'(J*Y)).

Function lsqnonlin transmits data Jinfo, Y, flag, and your function jmfun calculates the result according to the rules given below. Y — this is a matrix whose size depends on the value flag. Let — the number of components of the objective function fun, and — the number of task variables in the vector x. The Jacobi matrix has the size on (as described in ). Function jmfun returns one of the following results:

  • If flag == 0 Then W = J' * (J * Y) and the matrix Y It has a size on .

  • If flag > 0 Then W = J * Y and the matrix Y has a size of on .

  • If flag < 0 Then W = J' * Y and the matrix Y has a size of on .

In all cases, the matrix J it is not formed explicitly. The solver uses Jinfo to perform multiplication operations.

In order for the solver to transmit Jinfo from the function fun to the function jmfun, the argument SpecifyObjectiveGradient must be set to true.

JacobPattern

The Jacobian sparsity pattern for the finite difference method. Install JacobPattern(i,j) = 1 if fun(i) depends on x(j); otherwise, install JacobPattern(i,j) = 0. In other words, JacobPattern(i,j) = 1 if the partial derivative ∂fun(i)/∂x(j) it may be non-zero.

Use JacobPattern in cases where the calculation of the Jacobi matrix J inside the function fun it is difficult, but it is possible to determine (for example, by analysis) whether it depends on fun(i) from x(j). If available JacobPattern the solver can approximate J using the sparse finite difference method.

If the structure of the matrix is unknown, do not specify JacobPattern. By default, the behavior corresponding to a dense matrix consisting of units is used; in this case, at each iteration, the solver calculates a complete finite-difference approximation. For high-dimensional tasks, this can be a resource-intensive process, so it is usually preferable to determine the sparsity structure.

SubproblemAlgorithm

Defines the method for calculating the iteration step. When using the default option ("factorization") the step is calculated slower, but more accurately than in the method "cg".

Algorithm "levenberg-marquardt"

InitDamping

The initial value of the Levenberg—Marquardt parameter is a positive scalar. Default value — 0.01.

ScaleProblem

Meaning "jacobian" sometimes it allows you to improve the convergence of a poorly scaled task; the default value is "none".

Information output by the solver

# resnorm — the square of the discrepancy norm

+ a non-negative real number

Details

The square of the discrepancy norm, returned as a non-negative real number. resnorm — this is the square of the second norm of the discrepancy at the point : .

# residual — the value of the objective function at the solution point

+ array

Details

The value of the objective function at the solution point, returned as an array. In the general case: .

# exitflag — the reason for stopping the solver

+ an integer

Details

The reason for stopping the solver, returned as an integer.

Meaning Reason

1

The function has converged to a solution .

2

Change less than the specified tolerance, or the Jacobian at the point not defined.

3

The discrepancy change is less than the specified tolerance.

4

The relative magnitude of the search direction is less than the tolerance by a step.

0

The number of iterations exceeded the value MaxIterations, or the number of calculations of the function exceeded the value MaxFunctionEvaluations.

−1

The plotting function or the output function has stopped the solver.

−2

A valid point was not found. The borders and are contradictory, or the solver stopped at an invalid point.

# output — information about the optimization process

+ structure

Details

Information about the optimization process returned as a structure with fields:

Field Name Content

firstorderopt

A measure of optimality of the first order.

iterations

The number of iterations performed.

funcCount

The number of calculations of the function.

cgiterations

Total number of iterations of the conjugate gradient method (PCG) (for the algorithm "trust-region-reflective").

stepsize

The final offset in x.

algorithm

The optimization algorithm used.

message

Exit message.

# lambda — Lagrange multipliers at the solution point

+ structure

Details

Lagrange multipliers at the solution point, returned as a structure with fields:

Field Name Content

lower

Lower bounds corresponding to .

upper

Upper bounds corresponding to .

# jacobian — the Jacobian at the decision point

+ the real matrix

Details

The Jacobian at the solution point, returned as a real matrix. Element jacobian(i,j) It is a partial derivative of a function by variable at the decision point .

For problems in which there are active constraints at the solution point, the Jacobian is not suitable for estimating confidence intervals.

Additional Info

Local and global minimum

Details

A local minimum of a function is a point at which the value of the function is less than at neighboring points, but possibly greater than at any remote point.

The global minimum is the point at which the value of the function is less than at all other acceptable points.

lsqnonlin 1 en

Solver algorithms try to find a local minimum. The result may be a global minimum.

A measure of optimality of the first order

Details

For unconditional optimization problems, the measure of optimality of the first order is the maximum absolute value of the components of the gradient vector (also called the infinite gradient norm). At the minimum point, this value should be zero.

For problems with constraints, the measure of optimality of the first order is the maximum in the index. values . Here — -I am a component of the gradient, — the current point, and

еслиотрицательныйградиентнаправленкграницевдругомслучае

If If it is located on the border, then it is equal to zero. If If it is not located on the border, then at the minimum point the gradient must be equal to zero. Therefore, at the point of the minimum, the measure of optimality of the first order should be zero.

Tolerances

Details

As a rule, tolerance is a threshold value, at which the iterative process of the solver stops.

  • OptimalityTolerance — defines the acceptable deviation for the measure of optimality of the first order. The iterative process ends when the value of the first-order optimality measure becomes less than OptimalityTolerance.

  • FunctionTolerance — determines the amount of the last change in the value of the objective function.

lsqnonlin 2 en

The magnitude of the gradient

Details

The gradient vector is the gradient of the sum of squares. For unconditional optimization problems, the gradient value is considered to be the maximum absolute value of the components of the gradient vector (also called the infinite gradient norm). At the minimum point, this value should be zero.

For problems with constraints, the gradient value is defined as the maximum by the index values . Here — -I am a component of the gradient, — the current point, and

еслиотрицательныйградиентнаправленкграницевдругомслучае

If If it is located on the border, then it is equal to zero. If If it is not on the border, then at the minimum point the gradient must be equal to zero. Therefore, the gradient value should be zero at the minimum point.

Current step size

Details

The size of the current step is the amount of change in the position of the current point in the last iteration.

The local singularity

Details

The Levenberg—Marquardt regularization parameter is related to the inverse of the radius of the confidence region. It takes on large values when the sum of the squares of the function values differs significantly from the quadratic model.

When calculating the Jacobian is impossible

Details

The algorithms evaluate the Jacobian of the target vector function using the finite difference method. If, during the calculation of the final difference, the calculated point has gone beyond the area where the objective function is defined correctly, then this can lead to Inf, NaN or a complex number.

Algorithms

The Levenberg—Marquardt methods and the confidence region with reflection are based on algorithms of the nonlinear least squares method.

  • The default reflection confidence region algorithm is a subspace confidence region method and is based on Newton’s method with internal reflection described in [1] and [2]. Each iteration includes an approximate solution of a large linear system using the preconditioned conjugate gradients (PCG) method.

  • The Levenberg—Marquardt method is described in [4], [5] and [6].

Literature

  1. Coleman, T.F. and Y. Li. An Interior, Trust Region Approach for Nonlinear Minimization Subject to Bounds. SIAM Journal on Optimization, Vol. 6, 1996, pp. 418–445.

  2. Coleman, T.F. and Y. Li. On the Convergence of Reflective Newton Methods for Large-Scale Nonlinear Minimization Subject to Bounds. Mathematical Programming, Vol. 67, Number 2, 1994, pp. 189–224.

  3. Dennis, J. E. Jr. Nonlinear Least-Squares. State of the Art in Numerical Analysis, ed. D. Jacobs, Academic Press, pp. 269–312.

  4. Levenberg, K. A Method for the Solution of Certain Problems in Least-Squares. Quarterly Applied Mathematics 2, 1944, pp. 164–168.

  5. Marquardt, D. An Algorithm for Least-squares Estimation of Nonlinear Parameters. SIAM Journal Applied Mathematics, Vol. 11, 1963, pp. 431–441.

  6. Moré, J. J. The Levenberg-Marquardt Algorithm: Implementation and Theory. Numerical Analysis, ed. G. A. Watson, Lecture Notes in Mathematics 630, Springer Verlag, 1977, pp. 105–116.

  7. Moré, J. J., B. S. Garbow, and K. E. Hillstrom. User Guide for MINPACK 1. Argonne National Laboratory, Rept. ANL–80–74, 1980.

  8. Powell, M. J. D. A Fortran Subroutine for Solving Systems of Nonlinear Algebraic Equations. Numerical Methods for Nonlinear Algebraic Equations, P. Rabinowitz, ed., Ch.7, 1970.