Quasi-Newton methods like dfpmin work well with the approximate line minimization done by lnsrch. The routines powell (§) and frprmn (§), however, need more accurate line minimization, which is carried out by the routine linmin. | 430 Chapter 10. Minimization or Maximization of Functions Quasi-Newton methods like dfpmin work well with the approximate line minimization done by Insrch. The routines powell and frprmn however need more accurate line minimization which is carried out by the routine linmin. Advanced Implementations of Variable Metric Methods Although rare it can conceivably happen that roundoff errors cause the matrix Hi to become nearly singular or non-positive-definite. This can be serious because the supposed search directions might then not lead downhill and because nearly singular Hi s tend to give subsequent Hi s that are also nearly singular. There is a simple fix for this rare problem the same as was mentioned in In case of any doubt you should restart the algorithm at the claimed minimum point and see if it goes anywhere. Simple but not very elegant. Modern implementations of variable metric methods deal with the problem in a more sophisticated way. Instead of building up an approximation to A 1 it is possible to build up an approximation of A itself. Then instead of calculating the left-hand side of directly one solves the set of linear equations A xm - Xi -rf Xi At first glance this seems like a bad idea since solving is a process of order N3 and anyway how does this help the roundoff problem The trick is not to store A but rather a triangular decomposition of A its Cholesky decomposition cf. . The updating formula used for the Cholesky decomposition of A is of order N2 and can be arranged to guarantee that the matrix remains positive definite and nonsingular even in the presence of finite roundoff. This method is due to Gill and Murray 1 2 . CITED REFERENCES AND FURTHER READING Dennis . and Schnabel . 1983 Numerical Methods for Unconstrained Optimization and Nonlinear Equations Englewood Cliffs NJ Prentice-Hall . 1 Jacobs . ed. 1977 The State ofthe ArtinNumericalAnalysis London Academic Press Chapter 3-6 by K.
