Global convergence of SSM for minimizing a quadratic over a sphere
HTML articles powered by AMS MathViewer
- by William W. Hager and Soonchul Park;
- Math. Comp. 74 (2005), 1413-1423
- DOI: https://doi.org/10.1090/S0025-5718-04-01731-4
- Published electronically: December 30, 2004
- PDF | Request permission
Abstract:
In an earlier paper [Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), 188–208], we presented the sequential subspace method (SSM) for minimizing a quadratic over a sphere. This method generates approximations to a minimizer by carrying out the minimization over a sequence of subspaces that are adjusted after each iterate is computed. We showed in this earlier paper that when the subspace contains a vector obtained by applying one step of Newton’s method to the first-order optimality system, SSM is locally, quadratically convergent, even when the original problem is degenerate with multiple solutions and with a singular Jacobian in the optimality system. In this paper, we prove (nonlocal) convergence of SSM to a global minimizer whenever each SSM subspace contains the following three vectors: (i) the current iterate, (ii) the gradient of the cost function evaluated at the current iterate, and (iii) an eigenvector associated with the smallest eigenvalue of the cost function Hessian. For nondegenerate problems, the convergence rate is at least linear when vectors (i)–(iii) are included in the SSM subspace.References
- Richard H. Byrd, Robert B. Schnabel, and Gerald A. Shultz, A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numer. Anal. 24 (1987), no. 5, 1152–1170. MR 909071, DOI 10.1137/0724076
- M. R. Celis, J. E. Dennis, and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization, Numerical optimization, 1984 (Boulder, Colo., 1984) SIAM, Philadelphia, PA, 1985, pp. 71–82. MR 802084
- Mahmoud El-Alem, A global convergence theory for the Celis-Dennis-Tapia trust-region algorithm for constrained optimization, SIAM J. Numer. Anal. 28 (1991), no. 1, 266–290. MR 1083336, DOI 10.1137/0728015
- Gene H. Golub and Urs von Matt, Quadratically constrained least squares and quadratic problems, Numer. Math. 59 (1991), no. 6, 561–580. MR 1124128, DOI 10.1007/BF01385796
- Gene H. Golub and Charles F. Van Loan, Matrix computations, 2nd ed., Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1989. MR 1002570
- Nicholas I. M. Gould, Stefano Lucidi, Massimo Roma, and Philippe L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim. 9 (1999), no. 2, 504–525. MR 1686795, DOI 10.1137/S1052623497322735
- William W. Hager, Iterative methods for nearly singular linear systems, SIAM J. Sci. Comput. 22 (2000), no. 2, 747–766. MR 1780623, DOI 10.1137/S106482759834634X
- William W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim. 12 (2001), no. 1, 188–208. MR 1870591, DOI 10.1137/S1052623499356071
- William W. Hager and Yaroslav Krylyuk, Graph partitioning and continuous quadratic programming, SIAM J. Discrete Math. 12 (1999), no. 4, 500–523. MR 1720400, DOI 10.1137/S0895480199335829
- William W. Hager and Yaroslav Krylyuk, Multiset graph partitioning, Math. Methods Oper. Res. 55 (2002), no. 1, 1–10. MR 1892714, DOI 10.1007/s001860200173
- W. Menke, Geophysical Data Analysis: Discrete Inverse Theory, Academic Press, San Diego, 1989.
- J. J. Moré, Recent developments in algorithms and software for trust region methods, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 258–287. MR 717404
- Jorge J. Moré and D. C. Sorensen, Computing a trust region step, SIAM J. Sci. Statist. Comput. 4 (1983), no. 3, 553–572. MR 723110, DOI 10.1137/0904038
- Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1980. MR 570116
- M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Math. Programming 49 (1990/91), no. 2, (Ser. A), 189–211. MR 1087453, DOI 10.1007/BF01588787
- Franz Rendl and Henry Wolkowicz, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Programming 77 (1997), no. 2, Ser. B, 273–299. Semidefinite programming. MR 1461384, DOI 10.1016/S0025-5610(96)00080-9
- M. Rojas, A Large-scale Trust-region Approach to the Regularization of Discrete Ill-posed Problems, PhD Dissertation, Computational and Applied Mathematics, Rice University, Houston, TX, May, 1998.
- D. C. Sorensen, Newton’s method with a model trust region modification, SIAM J. Numer. Anal. 19 (1982), no. 2, 409–426. MR 650060, DOI 10.1137/0719026
- D. C. Sorensen, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim. 7 (1997), no. 1, 141–161. MR 1430561, DOI 10.1137/S1052623494274374
- Albert Tarantola, Inverse problem theory, Elsevier Science Publishers, B.V., Amsterdam, 1987. Methods for data fitting and model parameter estimation. MR 930881
Bibliographic Information
- William W. Hager
- Affiliation: Department of Mathematics, P.O. Box 118105, University of Florida, Gainesville, Florida 32611-8105
- Email: hager@math.ufl.edu
- Soonchul Park
- Affiliation: Department of Mathematics, P.O. Box 118105, University of Florida, Gainesville, Florida 32611-8105
- Email: scp@math.ufl.edu
- Received by editor(s): August 12, 2003
- Received by editor(s) in revised form: March 27, 2004
- Published electronically: December 30, 2004
- Additional Notes: This material is based upon work supported by the National Science Foundation under Grant No. 0203270
- © Copyright 2004 American Mathematical Society
- Journal: Math. Comp. 74 (2005), 1413-1423
- MSC (2000): Primary 90C20, 65F10, 65Y20
- DOI: https://doi.org/10.1090/S0025-5718-04-01731-4
- MathSciNet review: 2137009