Algorithm 702: TNPACK–a truncated Newton minimization package for large-scale problems: I. Algorithm and usage

ABSTRACT

We present a FORTRAN package of subprograms for minimizing multivariate functions without constraints by a truncated Newton algorithm. The algorithm is especially suited for problems involving a large number of variables. Truncated Newton methods allow approximate, rather than exact, solutions to the Newton equations. Truncation is accomplished in the present version by using the preconditioned Conjugate Gradient algorithm (PCG) to solve approximately the Newton equations. The preconditioner M is factored in PCG using a sparse modified Cholesky factorization based on the Yale Sparse Matrix Package. In this paper we briefly describe the method and provide details for program usage.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)
      G.1.6 Optimization
          Subjects: Nonlinear programming

General Terms:
Algorithms

Keywords:
nonlinear optimization, preconditioned conjugate gradient, sparse matrices, truncated Newton methods