Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Global convergence of SSM for minimizing a quadratic over a sphere

Authors: William W. Hager and Soonchul Park
Journal: Math. Comp. 74 (2005), 1413-1423
MSC (2000): Primary 90C20, 65F10, 65Y20
Published electronically: December 30, 2004
MathSciNet review: 2137009
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. R. H. BYRD, R. B. SCHNABEL, AND G. A. SCHULTZ, A trust region algorithm for nonlinearly constrained optimization, SIAM J. Numer. Anal., 24 (1987), pp. 1152-1170. MR 0909071 (89f:65069)
  • 2. M. CELIS, J. E. DENNIS, AND R. A. TAPIA, A trust region strategy for nonlinear equality constrained optimization, in Numerical Optimization 1984, SIAM, Philadelphia, PA, 1985, pp. 71-82.MR 0802084 (87c:90175)
  • 3. M. EL-ALEM, Celis-Dennis-Tapia trust region algorithm for constrained optimization, SIAM J. Numer. Anal., 28 (1991), pp. 266-290. MR 1083336 (91k:90161)
  • 4. G. H. GOLUB AND U. VON MATT, Quadratically constrained least squares and quadratic problems, Numer. Math., 59 (1991), pp. 561-580. MR 1124128 (92f:65049)
  • 5. G. H. GOLUB AND C. F. VAN LOAN, Matrix Computations, Johns Hopkins University Press, Baltimore, 1989. MR 1002570 (90d:65055)
  • 6. N. I. M. GOULD, S. LUCIDI, M. ROMA, AND P. L. TOINT, Solving the trust-region subproblem using the Lanczos Method, SIAM J. Optim, 9 (1999), pp. 504-525. MR 1686795 (2000b:90046)
  • 7. W. W. HAGER, Iterative methods for nearly singular linear systems, SIAM J. Sci. Comp., 22 (2000), pp. 747-766. MR 1780623 (2001g:65031)
  • 8. W. W. HAGER, Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), pp. 188-208. MR 1870591 (2002m:90054)
  • 9. W. W. HAGER AND Y. KRYLYUK, Graph partitioning and continuous quadratic programming, SIAM J. Discrete Math., 12 (1999), pp. 500-523. MR 1720400 (2000k:90066)
  • 10. W. W. HAGER AND Y. KRYLYUK, Multiset graph partitioning, Math. Methods Oper. Res., 55 (2002), pp. 1-10. MR 1892714 (2003k:90079)
  • 11. W. MENKE, Geophysical Data Analysis: Discrete Inverse Theory, Academic Press, San Diego, 1989.
  • 12. J. J. MOR´E, Recent developments in algorithms and software for trust region methods, in A. Bachem, M. Grotschel, and B. Korte, editors, Mathematical Programming: State of the Art, Springer-Verlag, Berlin, 1983, pp. 258-287. MR 0717404 (85b:90066)
  • 13. J. J. MOR´E AND D. C. SORENSEN, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4 (1983), pp. 553-572. MR 0723110 (86b:65063)
  • 14. B. N. PARLETT, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliff, NJ, 1980. MR 0570116 (81j:65063)
  • 15. M. J. D. POWELL AND Y. YUAN, A trust region algorithm for equality constrained optimization, Math. Programming, 49 (1991), pp. 189-211. MR 1087453 (91m:90162)
  • 16. R. RENDL AND H. WOLKOWICZ, A semidefinite framework for trust region subproblems with applications to large scale minimization, Math. Programming, 77 (1997), pp. 273-299. MR 1461384 (98i:90063)
  • 17. 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.
  • 18. D. C. SORENSEN, Newton's method with a model trust region modification, SIAM J. Numer. Anal., 16 (1982), pp. 409-426. MR 0650060 (84h:49061)
  • 19. D. C. SORENSEN, Minimization of a large-scale quadratic function subject to a spherical constraint, SIAM J. Optim., 7 (1997), pp. 141-161. MR 1430561 (98b:90102)
  • 20. A. TARANTOLA, Inverse Problem Theory, Elsevier, Amsterdam, 1987. MR 0930881 (89b:65007)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 90C20, 65F10, 65Y20

Retrieve articles in all journals with MSC (2000): 90C20, 65F10, 65Y20

Additional Information

William W. Hager
Affiliation: Department of Mathematics, P.O. Box 118105, University of Florida, Gainesville, Florida 32611-8105

Soonchul Park
Affiliation: Department of Mathematics, P.O. Box 118105, University of Florida, Gainesville, Florida 32611-8105

Keywords: Quadratic optimization, quadratic programming, trust region subproblem, large-scale optimization, sparse optimization.
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
Article copyright: © Copyright 2004 American Mathematical Society

American Mathematical Society