Algorithm 896: LSA: Algorithms for large-scale optimization

ABSTRACT

We present 14 basic Fortran subroutines for large-scale unconstrained and box constrained optimization and large-scale systems of nonlinear equations. Subroutines PLIS and PLIP, intended for dense general optimization problems, are based on limited-memory variable metric methods. Subroutine PNET, also intended for dense general optimization problems, is based on an inexact truncated Newton method. Subroutines PNED and PNEC, intended for sparse general optimization problems, are based on modifications of the discrete Newton method. Subroutines PSED and PSEC, intended for partially separable optimization problems, are based on partitioned variable metric updates. Subroutine PSEN, intended for nonsmooth partially separable optimization problems, is based on partitioned variable metric updates and on an aggregation of subgradients. Subroutines PGAD and PGAC, intended for sparse nonlinear least-squares problems, are based on modifications and corrections of the Gauss-Newton method. Subroutine PMAX, intended for minimization of a maximum value (minimax), is based on the primal line-search interior-point method. Subroutine PSUM, intended for minimization of a sum of absolute values, is based on the primal trust-region interior-point method. Subroutines PEQN and PEQL, intended for sparse systems of nonlinear equations, are based on the discrete Newton method and the inverse column-update quasi-Newton method, respectively. Besides the description of methods and codes, we propose computational experiments which demonstrate the efficiency of the proposed algorithms.

REFERENCES

• 1: Al-Baali, M. and Fletcher, R. 1985. Variational methods for nonlinear least squares. J. Optimiz. Theor. Appl. 36, 405--421.
• 2: Brown, P. N. and Saad, Y. 1994. Convergence theory of nonlinear Newton-Krylov algorithms. SIAM J. Optimiz. 4, 297--330.
• 3: Byrd, R. H., Nocedal, J., and Waltz, R. A. 2006. KNITRO: An integrated package for nonlinear optimization. In Large-Scale Nonlinear Optimization, G. di Pillo and M. Roma, Eds. (More information is on http://www.ziena.com/documentation.htm). Springer-Verlag, Berlin, Germany, 35--59.
• 4: Coleman, T. F. and Moré, J. J. 1983. Estimation of sparse Jacobian and graph coloring problem. SIAM J. Numer. Anal. 20, 187--209.
• 5: Coleman, T. F. and Moré, J. J. 1984. Estimation of sparse Hessian matrices and graph coloring problem. Math. Program. 28, 243--270.
• 6: Curtis, A. R., Powell, M. J. D., and Reid, J. K. 1974. On the estimation of sparse Jacobian matrices. IMA J. Appl. Math. 13, 117--119.
• 7: Dembo, R. S., Eisenstat, S. C., and Steihaug, T. 1982. Inexact Newton methods. SIAM J. Numer. Anal. 19, 400--408.
• 8: Dembo, R. S. and Steihaug, T. 1983. Truncated Newton algorithms for large-scale optimization. Math. Program. 26, 190--212.
• 9: John E. Dennis, Jr. , Howell H Mei, An Unconstrained Optimization Algorithm Which Uses Function and Gradient Values, Cornell University, Ithaca, NY, 1975
• 10: Gill, P. E. and Murray, W. 1974. Newton type methods for unconstrained and linearly constrained optimization. Math. Program. 7, 311--350.
• 11: Griewank, A. and Toint, P. L. 1982. Partitioned variable metric updates for large-scale structured optimization problems. Numer. Math. 39, 119--137.
• 12: D. C. Liu , J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical Programming: Series A and B, v.45 n.3, p.503-528, Dec. 1989 [doi>10.1007/BF01589116]
• 13: L. Lukšan, Hybrid methods for large sparse nonlinear least squares, Journal of Optimization Theory and Applications, v.89 n.3, p.575-595, June 1996 [doi>10.1007/BF02275350]
• 14: Lukšan, L., Matonoha, C., and Vlček, J. 2004. A shifted Steihaug-Toint method for computing a trust-region step. Rep. V-914. ICS AS CR, Prague.
• 15: Lukšan, L., Matonoha, C., and Vlček, J. 2005a. Primal interior-point method for large sparse minimax optimization. Tech. rep. V-941, ICS AS CR, Prague, Czech Republic.
• 16: Lukšan, L., Matonoha, C., and Vlček, J. 2005b. Trust-region interior point method for large sparse l₁ optimization. Tech. rep. V-942. ICS AS CR, Prague, Czech Republic.
• 17: Ladislav Lukšan , Emilio Spedicato, Variable metric methods for unconstrainted optimization and nonlinear least squares, Journal of Computational and Applied Mathematics, v.124 n.1-2, p.61-95, Dec. 2000 [doi>10.1016/S0377-0427(00)00420-9]
• 18: Lukšan, L., Tůma, M., Hartman, J., Vlček, J., Ramešová, N., Šiška, M., and Matonoha, C. 2006. Interactive system for universal functional optimization (UFO). Version 2006. Tech. rep. V-977. ICS AS CR, Prague, Czech Republic.
• 19: Lukšan, L. and Vlček, J. 1998a. Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations. Optimiz. Meth. Softw. 8, 201--223.
• 20: Lukšan, L. and Vlček, J. 1998b. Sparse and partially separable test problems for unconstrained and equality constrained optimization. Tech. rep. V-767. ICS AS CR, Prague, Czech Republic.
• 21: Lukšan, L. and Vlček, J. 2006. Variable metric method for minimization of partially separable nonsmooth functions. Pacific J. Optimiz. 2, (Jan.), 59--70.
• 22: Martinez, J. M. and Zambaldi, M. C. 1992. An inverse column-updating method for solving large-scale nonlinear systems of equations. Optimiz. Meth. Softw. 1, 129--140.
• 23: Moré, J. J. and Sorensen, D. C. 1983. Computing a trust region step. SIAM J. Sci. Statist. Computat. 4, 553--572.
• 24: Nocedal, J. 1980. Updating quasi-Newton matrices with limited storage. Math. Comp. 35, 773--782.
• 25: Nowak, U. and Weimann, L. 1991. A family of Newton codes for systems of highly nonlinear equations. Tech. rep. TR-91-10. Konrad-Zuse-Zentrum für Informationstechnik, Berlin, Germany.
• 26: Michael Pernice , Homer F. Walker, NITSOL: A Newton Iterative Solver for Nonlinear Systems, SIAM Journal on Scientific Computing, v.19 n.1, p.302-318, Jan. 1998 [doi>10.1137/S1064827596303843]
• 27: Tamar Schlick , Aaron Fogelson, TNPACK—A truncated Newton minimization package for large-scale problems: I. Algorithm and usage, ACM Transactions on Mathematical Software (TOMS), v.18 n.1, p.46-70, March 1992 [doi>10.1145/128745.150973]
• 28: Steihaug, T. 1983. The conjugate gradient method and trust regions in large-scale optimization. SIAM J. Numer. Anal. 20, 626--637.
• 29: Toint, P. L. 1981. Towards an efficient sparsity exploiting Newton method for minimization. In Sparse Matrices and Their Uses, I. S. Duff, Ed. Academic Press, London, 57--88.
• 30: Toint, P. L. 1995a. Subroutine VE08: Harwell subroutine library. specifications. AEA Tech. 2, 1162--1174.
• 31: Toint, P. L. 1995b. Subroutine VE10: Harwell subroutine library. specifications. AEA Tech. 2, 1187--1197.
• 32: Tong, C. H. 1992. A comparative study of preconditioned Lanczos methods for nonsymmetric linear systems. Sandia rep. SAND91-8240B. Sandia National Laboratories, Livermore.
• 33: Tůma, M. 1988. A note on direct methods for approximations of sparse Hessian matrices. Aplikace Matematiky 33, 171--176.
• 34: Vlček, J. and Lukšan, L. 2001. Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization. J. Optimiz. Theor. Appl. 111, 407--430.
• 35: Jan Vlček , Ladislav Lukšan, Shifted limited-memory variable metric methods for large-scale unconstrained optimization, Journal of Computational and Applied Mathematics, v.186 n.2, p.365-390, 15 February 2006 [doi>10.1016/j.cam.2005.02.010]
• 36: Ciyou Zhu , Richard H. Byrd , Peihuang Lu , Jorge Nocedal, Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization, ACM Transactions on Mathematical Software (TOMS), v.23 n.4, p.550-560, Dec. 1997 [doi>10.1145/279232.279236]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design

Keywords:
Large-scale optimization, discrete Newton methods, large-scale nonlinear least squares, large-scale nonlinear minimax, large-scale nonsmooth optimization, large-scale systems of nonlinear equations, limited-memory methods, partially separable problems, primal interior-point methods, quasi-Newton methods, sparse problems