×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
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
[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] 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
[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] CUTEst: A constrained and unconstrained testing environment with safe threads, Tech. Rep. RAL-TR-2013-005, 2013
[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] OPTPDE—a collection of problems in PDE-constrained optimization. Available at
[26] 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
[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] . Available at
[33] . Available at
[34] 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] 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] 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] 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
[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. 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.