阻尼最小二乘法

1、阻尼最小二乘法（damped least squres，又称LevenbergMarquardt algorithm）the LevenbergMarquardt algorithm (LMA)1provides a numerical solution to the problem of minimizing a function, generally nonlinear, over a space of parameters of the function. These minimization problems arise especially in least squares curv

2、e fitting and nonlinear programming.The LMA interpolates between the GaussNewton algorithm (GNA就是最小二乘) and the method of gradient descent.The LMA is more robust than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. For well-behaved functio

3、ns and reasonable starting parameters, the LMA tends to be a bit slower than the GNA. LMA can also be viewed as GaussNewton using a trust region approach.However, the LMA finds only a local minimum, not a global minimum.这和最小二乘一样。这是所有线性反演的通病。The problemThe primary application of the LevenbergMarquard

4、t algorithm is in the least squares curve fitting problem: given a set of m empirical datum pairs ofindependent and dependent variables, (xi, yi), optimize the parameters of the model curve f(x,) so that the sum of the squares of the deviationsbecomes minimal. The solutionLike other numeric min

5、imization algorithms, the LevenbergMarquardt algorithm is an iterative procedure. To start a minimization, the user has to provide an initial guess for the parameter vector, . In cases with only one minimum, an uninformed standard guess like T=(1,1,.,1) will work fine; in cases with multiple minima,

6、 the algorithm converges only if the initial guess is already somewhat close to the final solution.In each iteration step, the parameter vector, is replaced by a new estimate,+. To determine, the functionsare approximated by their linearizationswhereis the gradient (row-vector in this case) of f wit

7、h respect to .At its minimum, the sum of squares, S(), the gradient of S with respect to will be zero. The above first-order approximation of gives.Or in vector notation,.Taking the derivative with respect to and setting the result to zero gives:where J is the Jacobian matrixwhoseithrow equalsJi,and

8、 where and are vectors with ith component and yi, respectively. This is a set of linear equations which can be solved for.上面是传统的最小二乘法的线性方程。Levenberg's contribution is to replace this equation by a "damped version",where I is the identity matrix, giving as the increment, , to the estima

9、ted parameter vector, .The (non-negative) damping factor, , is adjusted at each iteration. If reduction of S is rapid, a smaller value can be used, bringing the algorithm closer to the GaussNewton algorithm, whereas if an iteration gives insufficient reduction in the residual, can be increased, givi

10、ng a step closer to the gradient descent direction. Note that the gradient of S with respect to equals. Therefore, for large values of , the step will be taken approximately in the direction of the gradient.If either the length of the calculated step, , or the reduction of sum of squares from the la

11、test parameter vector, + , fall below predefined limits, iteration stops and the last parameter vector, , is considered to be the solution.Levenberg's algorithm has the disadvantagethat if the value of damping factor, , is large,JTJ + I is not used at all. Marquardt provided the insigh

12、t that we can scale each component of the gradient according to the curvature so that there is larger movement along the directions where the gradient is smaller. This avoids slow convergence in the direction of small gradient. Therefore, Marquardt replaced the identity matrix,I, with the diagonal m

13、atrix consisting of the diagonal elements ofJTJ, resulting in the LevenbergMarquardt algorithm:.Choice of damping parameterVarious more-or-less heuristic arguments have been put forward for the best choice for the damping parameter . Theoretical arguments exist showing why some of these choices guar

14、anteed local convergence of the algorithm; however these choices can make the global convergence of the algorithm suffer from the undesirable properties of steepest-descent, in particular very slow convergence close to the optimum.The absolute values of any choice depends on how well-scaled the init

15、ial problem is. Marquardt recommended starting with a value 0 and afactor >1. Initially setting =0 and computing the residual sum of squares S() after one step from the starting point with the damping factor of =0 and secondly with 0/. If both of these are worse than the initial point then the da

16、mping is increased by successive multiplication by until a better point is found with a new damping factor of 0k for some k.If use of the damping factor / results in a reduction in squared residual then this is taken as the new value of (and the new optimum location is taken as that obtained with th

17、is damping factor) and the process continues; if using / resulted in a worse residual, but using resulted in a better residual then is left unchanged and the new optimum is taken as the value obtained with as damping factor. ExampleIn this example we try to fit the function y = acos(bX) + bsin(

18、aX) using the LevenbergMarquardt algorithm implemented in GNU Octave as the leasqr function.The 3 graphs Fig 1,2,3 show progressively better fitting for the parameters a=100, b=102 used in the initial curve. Only when the parameters in Fig 3 are chosen closest to the original, are the curves fitting exactly. This equation isan example of very sensitive initial conditions for the LevenbergMarquardt algorithm. One reason for this sensitivity is the existence of multiple minima the function cos(x) has minima at parameter value  and