×

trlib: a vector-free implementation of the GLTR method for iterative solution of the trust region problem. (English) Zbl 1390.35364

Summary: We describe trlib, a library that implements a variant of Generalized Lanczos method [N. I. M. Gould et al., SIAM J. Optim. 9, No. 2, 504–525 (1999; Zbl 1047.90510)] for solving the trust region problem. Our implementation has several distinct features that set it apart from preexisting ones. We implement both conjugate gradient (CG) and Lanczos iterations for assembly of Krylov subspaces. A vector- and matrix-free reverse communication interface allows the use of most general data structures, such as those arising after discretization of function space problems. The hard case of the trust region problem frequently arises in sequential methods for nonlinear optimization. In this implementation, we made an effort to fully address the hard case in an exact way by considering all invariant Krylov subspaces. We investigate the numerical performance of trlib on the full subset of unconstrained problems of CUTEst the benchmark set. In addition to this, interfacing the PDE discretization toolkit FEniCS with trlib using the vector-free reverse communication interface is demonstrated for a family of PDE-constrained control trust region problems adapted from the OPTPDE collection.

MSC:

35Q90 PDEs in connection with mathematical programming
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C30 Nonlinear programming

Citations:

Zbl 1047.90510
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Absil, P.-A.; Baker, C. G.; Gallivan, K. A., Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7, 3, 303-330 (2007) · Zbl 1129.65045
[2] Alnæs, M.; Logg, A.; Ølgaard, K.; Rognes, M.; Wells, G., Unified form language: A domain-specific language for weak formulations of partial differential equations, ACM Trans. Math. Softw., 40, 2, 9:1-9:37 (2014) · Zbl 1308.65175
[3] Alnæs, M.; Blechta, J.; Hake, J.; Johansson, A.; Kehlet, B.; Logg, A.; Richardson, C.; Ring, J.; Rognes, M.; Wells, G., The FEniCS project version 1.5, Arch. Numer. Softw., 3, 100, 9-23 (2015)
[4] Byrd, R.; Gould, N.; Nocedal, J.; Waltz, R., An algorithm for nonlinear optimization using linear programming and equality constrained subproblems, Math. Program., 100, 1, 27-48 (2003) · Zbl 1146.90513
[5] Cartis, C.; Gould, N. I.M.; Toint, P. L., Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results, Math. Program., 127, 245-295 (2011) · Zbl 1229.90192
[6] Cartis, C.; Gould, N. I.M.; Toint, P. L., Adaptive cubic regularisation methdos for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity, Math. Program., 130, 295-319 (2011) · Zbl 1229.90193
[7] Casas, E., Control of an elliptic problem with pointwise state constraints, SIAM J. Control Optim., 24, 6, 1309-1318 (1986) · Zbl 0606.49017
[8] Clarke, F., Functional Analysis, Calculus of Variations and Optimal Control (2013), Springer, London · Zbl 1277.49001
[9] Conn, A.; Gould, N.; Toint, P., Trust-Region Methods (2000), SIAM, Philadelphia, PA · Zbl 0958.65071
[10] Curtis, F.; Robinson, D.; Samadi, M., A trust region algorithm with a worst-case iteration complexity of \(####\) for nonconvex optimization, Math. Program., 162, 1-32 (2017) · Zbl 1360.49020
[11] Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[12] Erway, J. B.; Gill, P. E., A subspace minimization method for the trust-region step, SIAM J. Optim., 20, 3, 1439-1461 (2010) · Zbl 1195.49042
[13] Erway, J. B.; Gill, P. E.; Griffin, J. D., Iterative methods for finding a trust-region step, SIAM J. Optim., 20, 2, 1110-1131 (2009) · Zbl 1189.49049
[14] Farrell, P. E.; Ham, D. A.; Funke, S. W.; Rognes, M. E., Automated derivation of the adjoint of high-level transient finite element programs, SIAM J. Sci. Comput., 35, 4, 369-393 (2013) · Zbl 1362.65103
[15] Funke, P. and Farrell, P., A framework for automated PDE-constrained optimisation, preprint (2013). Available at arXiv:1302.3894.
[16] Golub, G.; Vanloan, C., Matrix Computations (1996), John Hopkins University Press, Baltimore, MD · Zbl 0865.65009
[17] Gould, N. I.M.; Lucidi, S.; Roma, M.; Toint, P. L., Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 2, 504-525 (1999) · Zbl 1047.90510
[18] Gould, N. I.M.; Hribar, M. E.; Nocedal, J., On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput., 23, 1376-1395 (2001) · Zbl 0999.65050
[19] Gould, N. I.M.; Orban, D.; Toint, P. L., GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Softw., 29, 4, 353-372 (2004) · Zbl 1068.90525
[20] Gould, N. I.M.; Robinson, D. P.; Thorne, H. S., On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 1, 21-57 (2010) · Zbl 1193.65098
[21] Gould, N., Orban, D., and Toint, P., CUTEst: A constrained and unconstrained testing environment with safe threads, Tech. Rep. RAL-TR-2013-005, 2013. · Zbl 1325.90004
[22] Günnel, A.; Herzog, R.; Sachs, E., A note on preconditioners and scalar products in Krylov subspace methods for self-adjoint problems in Hilbert space, Electron. Trans. Numer. Anal., 41, 13-20 (2014) · Zbl 1295.65062
[23] Hager, W. W., Minimizing a quadratic over a sphere, SIAM J. Optim., 12, 1, 188-208 (2001) · Zbl 1058.90045
[24] Heinkenschloss, M., Mesh independence for nonlinear least squares problems with norm constraints, SIAM J. Optim., 3, 1, 81-117 (1993) · Zbl 0771.65030
[25] Herzog, R., Rösch, A., Ulbrich, S., and Wollner, W., OPTPDE—a collection of problems in PDE-constrained optimization. Available at . · Zbl 1320.49002
[26] Herzog, R., Rösch, A., Ulbrich, S., and Wollner, W., OPTPDE—a collection of problems in PDE-constrained optimization, in Trends in PDE Constrained Optimization, G. Leugering, P. Benner, S. Engell, A. Griewank, H. Harbrecht, M. Hinze, R. Rannacher, S. Ulbrich, eds., International Series of Numerical Mathematics, Vol. 165, Springer, Cham, 2014, pp. 539-543. · Zbl 1320.49002
[27] Hestenes, M. R., Applications of the theory of quadratic forms in Hilbert space to the calculus of variations, Pacific J. Math., 4, 525-581 (1951) · Zbl 0045.20806
[28] Kelley, C. T.; Sachs, E. W., Quasi-Newton methods and unconstrained optimal control problems, SIAM J. Control Optim., 25, 6, 1503-1516 (1987) · Zbl 0634.49014
[29] Kurdila, A.; Zabarankin, M., Convex Functional Analysis (2005), Springer, Basel · Zbl 1077.46002
[30] Kuznetsov, Y., Efficient iterative solvers for elliptic finite element problems on nonmatching grids, Russian J. Numer. Anal. Math. Model., 10, 187-211 (1995) · Zbl 0839.65031
[31] Lehoucq, R.; Sorensen, D.; Yang, C., ARPACK Users’ Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (1998), SIAM, Philadelphia, PA · Zbl 0901.65021
[32] Lenders, F., trbench. Available at .
[33] Lenders, F., trlib. Available at .
[34] Lenders, F., Kirches, C., and Bock, H., pySLEQP: A sequential linear quadratic programming method implemented in Python, in Modeling, Simulation and Optimization of Complex Processes HPSC 2015, H.G. Bock, H.X. Phu, R. Rannacher, J.P. Schlöder, eds., Springer, 2017, pp. 103-113.
[35] Logg, A.; Wells, G. N., DOLFIN: Automated finite element computing, ACM Trans. Math. Softw., 37, 2, 1-28 (2010) · Zbl 1364.65254
[36] Mahajan, A., Leyffer, S., and Kirches, C., Solving mixed-integer nonlinear programs by QP diving, Technical Report ANL/MCS-P2071-0312, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, USA, 2011.
[37] Meyer, C.; Rösch, A.; Tröltzsch, F., Optimal control of PDEs with regularized pointwise state constraints, Comput. Optim. Appl., 33, 2-3, 209-228 (2005) · Zbl 1103.90072
[38] Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572 (1983) · Zbl 0551.65042
[39] Murphy, M. F.; Golub, G. H.; Wathen, A. J., A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 6, 1969-1972 (1999) · Zbl 0959.65063
[40] Nocedal, J.; Wright, S., Numerical Optimization (2006), Springer, New York, NY · Zbl 1104.65059
[41] Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 4, 617-629 (1975) · Zbl 0319.65025
[42] Parlett, B. N.; Reid, J. K., Tracking the progress of the Lanczos algorithm for large symmetric eigenproblems, IMA J. Numer. Anal., 1, 135-155 (1981) · Zbl 0474.65022
[43] Rees, T.; Dollar, H. S.; Wathen, A. J., Optimal solvers for PDE-constrained optimization, SIAM J. Sci. Comput., 32, 1, 271-298 (2010) · Zbl 1208.49035
[44] Rendl, F.; Wolkowicz, H., A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Program. Ser. B, 77, 273-299 (1997) · Zbl 0888.90137
[45] Ridzal, D., Trust-region SQP methods with inexact linear system solves for large-scale optimization, PhD Thesis, Computational and Applied Mathematics, Rice University, Houston, TX, USA, 2006.
[46] Rojas, M.; Santos, S. A.; Sorensen, D. C., A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 3, 611-646 (2000) · Zbl 0994.65067
[47] Rojas, M.; Santos, S. A.; Sorensen, D. C., Algorithm 873: LSTRS: MATLAB software for large-scale trust-region subproblems and regularization, ACM Trans. Math. Softw., 34, 2, 1-28 (2008) · Zbl 1291.65177
[48] Sorensen, D. C., Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7, 141-161 (1997) · Zbl 0878.65044
[49] Steihaug, T., The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal., 20, 3, 626-637 (1983) · Zbl 0518.65042
[50] Toint, P.L., Towards an efficient sparsity exploiting Newton method for minimization, in Sparse Matrices and Their Uses, I. Duff, ed., Academic Press, London, 1981, pp. 57-88. · Zbl 0463.65045
[51] Toint, P. L., Global convergence of a class of trust region methods for nonconvex minimization in Hilbert space, IMA J. Numer. Anal., 8, 2, 231-252 (1988) · Zbl 0698.65043
[52] Ulbrich, M.; Ulbrich, S., Superlinear convergence of affine-scaling interior-point newton methods for infinite-dimensional problems with pointwise bounds, SIAM J. Optim., 38, 6, 1938-1984 (2000) · Zbl 1010.90094
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.