Truncated Newton method for sparse unconstrained optimization using automatic differentiation.

*(English)*Zbl 0632.90060When solving large complex optimization problems, the user is faced with three major problems. These are: (i) the cost in human time in obtaining accurate expressions for the derivatives involved; (ii) the need to store second derivative information; and (iii) of lessening importance, the time taken to solve the problem on the computer. For many problems, a significant part of the latter can be attributed to solving Newton-like equations. In the algorithm described, the equations are solved using a conjugate direction method which only needs the Hessian at the current point when it is multiplied by a trial vector. In this paper, we present a method that finds this product using automatic differentiation while only requiring vector storage. The method takes advantage of any sparsity in the Hessian matrix and computes exact derivatives. It avoids the complexity of symbolic differentiation, the inaccuracy of numerical differentiation, the labor of finding analytic derivatives, and the need for matrix store. When far from a minimum, an accurate solution to the Newton equations is not justified, so an approximate solution is obtained by using a version of R. Dembo and T. Steihaug’s truncated Newton algorithm [Math. Program. 26, 190-212 (1982; Zbl 0523.90078)].

Reviewer: L.C.W.Dixon

##### MSC:

90C30 | Nonlinear programming |

49M37 | Numerical methods based on nonlinear programming |

65K05 | Numerical mathematical programming methods |

##### Keywords:

large complex optimization; conjugate direction method; automatic differentiation; sparsity; Hessian matrix; approximate solution; truncated Newton algorithm
PDF
BibTeX
XML
Cite

\textit{L. C. W. Dixon} and \textit{R. C. Price}, J. Optim. Theory Appl. 60, No. 2, 261--275 (1989; Zbl 0632.90060)

Full Text:
DOI

##### References:

[1] | Dembo, R., andSteihaug, T.,Truncated Newton Methods for Large Scale Optimization, Mathematical Programming, Vol. 26, pp. 190-212, 1982. · Zbl 0523.90078 · doi:10.1007/BF02592055 |

[2] | Rall, L. B.,Automatic Differentiation: Techniques and Applications, Springer-Verlag, Berlin, Germany, 1981. · Zbl 0473.68025 |

[3] | Dixon, L. C. W., andPrice, R. C.,Numerical Experience with the Truncated Newton Method, Numerical Optimisation Centre, Hatfield Polytechnic, Technical Report No. 169, 1986. |

[4] | Dixon, L. C. W., Dolan, P. D., andPrice, R. C.,Finite Element Optimization, Proceedings of the Meeting on Simulation and Optimization of Large Systems, Reading, England, 1986, edited by A. J. Osiadacz, Oxford Science Publications, Oxford, England, 1988. |

[5] | Pope, J., andShepherd, J.,On the Integrated Analysis of Catch-at-Age and Groundfish Survey or CPUE Data, Ministry of Fisheries and Food, Lowestoft, England, 1984. |

[6] | Dembo, R., Eisenstat, S. C., andSteihaug, T.,Inexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 19, pp. 400-408, 1982. · Zbl 0478.65030 · doi:10.1137/0719025 |

[7] | Steihaug, T.,The Conjugate Gradient Method and Trust Regions in Large Scale Optimization, SIAM Journal on Numerical Analysis, Vol. 20, pp. 626-637, 1983. · Zbl 0518.65042 · doi:10.1137/0720042 |

[8] | Anonymous,Optima Manual, Numerical Optimisation Centre, Hatfield Polytechnic, Hatfield, Hertfordshire, England, 1984. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.