×

zbMATH — the first resource for mathematics

On solving trust-region and other regularised subproblems in optimization. (English) Zbl 1193.65098
This paper revisits the popular Gay-Moré-Sorensen algorithm [D. M. Gay; SIAM J. Sci. Stat. Comput. 2, 186–197 (1981; Zbl 0467.65027); J. J. Moré and D. C. Sorensen, SIAM J. Sci. Stat. Comput. 4, 553–572 (1983; Zbl 0551.65042)] for the direct solution of the trust-region subproblem using factorization in unconstrained optimization problems, and to provide flexible software for the related regularised quadratic subproblem. The optimality conditions for the trust-region subproblem is discussed, leading to a robust framework for its solution. Enhancements are provided such that the underlying method is both globally and superlinearly convergent in all cases. The ideas have been implemented as a pair of thread-safe Fortran 95 packages. Some numerical experiments are presented to show the effectiveness of the enhancements.

MSC:
65K05 Numerical mathematical programming methods
65F22 Ill-posedness and regularization problems in numerical linear algebra
65H05 Numerical computation of solutions to single equations
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
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] Absil P.-A., Mahony R., Sepulchre R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008) · Zbl 1147.65043
[3] Amestoy P., Duff I.S., Pralet S., Voemel C.: Adapting a parallel sparse direct solver to SMP architectures. Parallel Comput. 29(11–12), 1645–1668 (2003)
[4] Apostol T.M.: Mathematical Analysis. 2nd edn. Addison-Wesley, Reading (1974) · Zbl 0309.26002
[5] Berkes P., Wiskott L.: Analysis and interpretation of quadratic models of receptive fields. Nat. Protoc. 2(2), 400–407 (2007)
[6] Busygin S., Ag C., Butenko S., Pardalos P.M.: A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere. J. Comb. Optim. 6(3), 287–297 (2002) · Zbl 1046.90071
[7] Cartis, C., Gould, N.I.M., Toint, Ph.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. Ser. A 51 pages (2009) doi: 10.1007/s10107-009-0286-5 · Zbl 1229.90192
[8] Cartis C., Gould N.I.M., Toint Ph.L.: Trust-region and other regularisations of linear least-squares problems. BIT 49(1), 21–53 (2009) · Zbl 1165.65019
[9] Chabrillac Y., Crouzeix J.-P.: Definiteness and semidefiniteness of quadratic forms revisited. Linear Algebra Appl. 63, 283–292 (1984) · Zbl 0548.15027
[10] Cline A.K., Moler C.B., Stewart G.W., Wilkinson J.H.: An estimate for the condition number of a matrix. SIAM J. Numer. Anal. 16(2), 368–375 (1979) · Zbl 0403.65012
[11] Conn A.R., Gould N.I.M., Toint Ph.L.: Trust-Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071
[12] Demmel J.W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017
[13] Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002) · Zbl 1049.90004
[14] Dollar, H.S.: On Taylor series approximations for trust-region and regularized subproblems in optimization. Internal Technical Report Internal-2009-1, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England (2009)
[15] Dollar, H.S., Gould, N.I.M., Robinson, D.P.: On solving trust-region and other regularised subproblems in optimization. Technical Report RAL-TR-2009-003, Rutherford Appleton Laboratory (2009)
[16] Duff I.S.: MA57–a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30(2), 118–144 (2004) · Zbl 1070.65525
[17] Duff I.S., Reid J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9(3), 302–325 (1983) · Zbl 0515.65022
[18] Erway J.B., Gill P.E.: A subspace minimization method for the trust-region step. SIAM J. Optim. 20(3), 1439–1461 (2009) · Zbl 1195.49042
[19] 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
[20] Gander W.: On the Linear Least Squares Problem with a Quadratic Constraint. Technical Report STAN-CS-78-697. Computer Science Department, Stanford University, California (1978)
[21] Gay D.M.: Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2(2), 186–197 (1981) · Zbl 0467.65027
[22] Gertz E.M., Gill P.E.: A primal-dual trust region algorithm for nonlinear optimization. Math. Program. Ser. B 100(1), 49–94 (2004) · Zbl 1146.90514
[23] Gould N.I.M.: On practical conditions for the existence and uniqueness of solutions to the general equality quadratic-programming problem. Math. Program. 32(1), 90–99 (1985) · Zbl 0591.90068
[24] Gould, N.I.M., Hu, Y., Scott, J.A.: A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations. ACM Trans. Math. Softw. 32(2), Article 10 (2007) · Zbl 1365.65129
[25] Gould N.I.M., Lucidi S., Roma M., Toint Ph.L.: Solving the trust-region subproblem using the Lanczos method. SIAM J. Optim. 9(2), 504–525 (1999) · Zbl 1047.90510
[26] Gould N.I.M., Orban D., Toint Ph.L.: CUTEr (and SifDec), a Constrained and Unconstrained Testing Environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003) · Zbl 1068.90526
[27] Gould N.I.M., Orban D., Toint Ph.L.: GALAHAD–a library of thread-safe fortran 90 packages for large-scale nonlinear optimization. ACM Trans. Math. Softw. 29(4), 353–372 (2003) · Zbl 1068.90525
[28] Gould N.I.M., Scott J.A.: A numerical evaluation of HSL packages for the direct solution of large sparse, symmetric linear systems of equations. ACM Trans. Math. Softw. 30(3), 300–325 (2004) · Zbl 1073.65022
[29] Griewank A.: The Modification of Newton’s Method for Unconstrained Optimization by Bounding Cubic Terms. Technical Report DAMTP/NA12. Department of Applied Mathematics and Theoretical Physics, Cambridge University, Cambridge (1981)
[30] Hager W.W.: Condition estimates. SIAM J. Sci. Stat. Comput. 5(2), 311–316 (1984) · Zbl 0542.65023
[31] Hager W.W.: Minimizing a quadratic over a sphere. SIAM J. Optim. 12(1), 188–208 (2001) · Zbl 1058.90045
[32] Hebden M.D.: An Algorithm for Minimization Using Exact Second Derivatives. Technical Report T.P. 515. AERE, Harwell Laboratory, Harwell (1973)
[33] Higham N.J.: Fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation. ACM Trans. Math. Softw. 14(4), 381–396 (1988) · Zbl 0665.65043
[34] Hogg J.D.: A DAG-Based Parallel Cholesky Factorization for Multicore Systems. Technical Report RAL-TR-2008-029. Rutherford Appleton Laboratory, Chilton (2008)
[35] Hogg J.D., Reid J.K., Scott J.A.: A DAG-Based Sparse Cholesky Solver for Multicore Architectures. Technical Report RAL-TR-2009-004. Rutherford Appleton Laboratory, Chilton (2009)
[36] Montero A.: Study of SU(3) vortex-like configurations with a new maximal center gauge fixing method. Phys. Lett. B467, 106–111 (1999)
[37] Moré J.J.: Recent developments in algorithms and software for trust region methods. In: Bachem, A., Grötschel, M., Korte, B. (eds) Mathematical Programming: The State of the Art, pp. 258–287. Springer, Heidelberg (1983)
[38] Moré J.J., Sorensen D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4(3), 553–572 (1983) · Zbl 0551.65042
[39] Nesterov Yu., Polyak B.T.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177–205 (2006) · Zbl 1142.90500
[40] Parlett, B.N.: The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs, New Jersey, USA, 1980. Reprinted as Classics in Applied Mathematics 20, SIAM, Philadelphia, USA (1998) · Zbl 0431.65017
[41] Poljack S., Wolkowicz H.: Convex relaxations of (0,1)–quadratic programming. Math. Oper. Res. 20(3), 550–561 (1995) · Zbl 0845.90089
[42] Reid J.K., Scott J.A.: An Out-of-Core Sparse Cholesky Solver. Technical Report RAL-TR-2006-013. Rutherford Appleton Laboratory, Chilton (2006) · Zbl 1364.65071
[43] Reinsch C.: Smoothing by spline functions II. Numerische Mathematik 16(5), 451–454 (1971) · Zbl 1248.65020
[44] Schenk O., Christen M., Burkhart H.: Algorithmic performance studies on graphics processing units. J. Parallel Distrib. Comput. 68, 1360–1369 (2008) · Zbl 06059830
[45] 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
[46] Toint Ph.L.: Towards an efficient sparsity exploiting Newton method for minimization. In: Duff, I.S. (eds) Sparse Matrices and Their Uses, pp. 57–88. Academic Press, London (1981) · Zbl 0463.65045
[47] Traub J.F.: Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs (1964) · Zbl 0121.11204
[48] Trefethen L.N., Bai D.: Numerical Linear Algebra. SIAM, Philadelphia (1997)
[49] Weiser M., Deuflhard P., Erdmann B.: Affine conjugate adaptive Newton methods for nonlinear elastomechanics. Optim. Methods Softw. 22(3), 413–431 (2007) · Zbl 1128.74007
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.