Algorithm 711: BTN: software for parallel unconstrained optimization

ABSTRACT

BTN is a collection of FORTRAN subroutines for solving unconstrained nonlinear optimization problems. It currently runs on both Intel hypercube computers (distributed memory) and Sequent computers (shared memory), and can take advantage of vector processors if they are available. The software can also be run on traditional computers to simulate the performance of a parallel computer. BTN is a general-purpose algorithm, capable of solving problems with a large numbers of variables and suitable for users inexperienced with parallel computing. It is designed to be as easy to use as traditional algorithms for this problem, requiring only that a (scalar) subroutine be provided to evaluate the objective function and its gradient vector of first derivatives. The algorithm is based on a block truncated-Newton method. Truncated-Newton methods obtain the search direction by approximately solving the Newton equations via some iterative method. The particular method used in BTN is a block version of the Lanczos method, which is numerically stable for nonconvex problems. In addition to the optimization software, a parallel derivative checker is also provided.

REFERENCES

• 1: DEMBO, R. S., ~ STEIHAUG, T. Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26, 2 (June 1983), 190-212.
• 2: NASH, S.G. Preconditioning of truncated-Newton methods. SIAM J. Sci. Stat. Comput. 6, 3 (July 1985), 599-616.
• 3: NASH, S. G., AND NOCEDAL, J. A numerical study of the limited memory BFGS method and the truncated-Newton method for large scale optimization. SIAM J. Opt. 1, 3 (Aug. 1991), 358-372.
• 4: NASH, S, G., AND SOFER, A. A parallel line search for Newton-type methods. In Computer Sczence and Statistzcs: Proceedzngs of the 21st Symposium of the Interface (Alexandria, VA), K. Berk and L. Malone, Eds. ASA, 1989, pp. 134-137.
• 5: S. G. Nash , A. Sofer, Block truncated-Newton methods for parallel optimization, Mathematical Programming: Series A and B, v.45 n.3, p.529-546, Dec. 1989 [doi>10.1007/BF01589117]
• 6: NASH, S. G., AND SOFER, h. A general-purpose parallel algorithm for unconstrained optimization. SIAM J. Opt. 1, 4 (Nov 1991). To be published
• 7: O'LEARY, D P. The block conjugate-gradient algorithm and related methods. Lln. Algebra Appl. 29 (1980), 293-322.
• 8: O'LEARY, D. P A discrete Newton algorithm for minimizing a function of many varmbles. Math Program. 23, I (Jan. 1983), 20-33.
• 9: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
      G.1.6 Optimization
          Subjects: Gradient methods; Nonlinear programming

General Terms:
Algorithms, Documentation

Keywords:
conjugate gradient method, nonlinear optimization, parallel computing, truncated-Newton method