Abstract

This paper deals with the quasi-Newton type scheme for solving generalized equations involving set-valued vector fields on Riemannian manifolds. We establish some conditions ensuring the superlinear convergence for the iterative sequence which approximates a solution of the generalized equations. Such conditions can be viewed as an extension of the classical theorem of J. E. Dennis and J. J. Moré [see: A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Computation 28/126 (1974) 549–560] as well as the Riemannian Dennis-Moré condition established by K. A. Gallivan, C. Qi and P.-A. Absil [A Riemannian Dennis-Moré Condition, in: High-Performance Scientific Computing: Algorithms and Applications, M. W. Berry et al. (eds.), Springer, London (2012) 281–293]. Furthermore, we also apply these results to consider the convergence of a Broyden-type update for the problem of solving generalized equations in Riemannian context. Our results are new even for classical equations defined by single-valued vector fields.

Author information

Contact details are reproduced from the original publication and may be historical.

Huynh Van Ngai

Dept. of Mathematics and Statistics, Quy Nhon University, Quy Nhon, Binh Dinh, Vietnam

ngaivn@yahoo.com

Van Vu Nguyen

Dept. of Mathematics and Statistics, Quy Nhon University, Quy Nhon, Binh Dinh, Vietnam

nguyenvanvu@qnu.edu.vn

Keywords

  • Variational inclusion
  • point-to-set vector fields
  • quasi-Newton methods
  • Riemannian manifold
  • Dennis-Moré condition
  • superlinear convergence

Mathematics Subject Classification

65J99, 65K15, 58C06, 47H04

References

  1. P.-A. Absil, R. Mahony, R. Sepulchre: Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton (2008).https://doi.org/10.1515/9781400830244Google Scholar
  2. P.-A. Absil, R. Mahony, R. Sepulchre: Optimization on manifolds: methods and applications, in: Recent Advances in Optimization and its Applications in Engineering, M. Diehl et al. (eds.), Springer, Berlin (2010) 125–144.https://doi.org/10.1007/978-3-642-12598-0_12Google Scholar
  3. R. L. Adler, J.-P. Dedieu, J. Y. Margulies, M. Martens, M. Shub: Newton’s method on Riemannian manifolds and a geometric model for the human spine, IMA J. Numer. Analysis 22/3 (2002) 359–390.https://doi.org/10.1093/imanum/22.3.359Google Scholar
  4. S. Adly, R. Cibulka, H. V. Ngai: Newton methods for solving inclusions using set-valued approximations, SIAM J. Optimization 25/1 (2015) 159–184.https://doi.org/10.1137/130926730Google Scholar
  5. S. Adly, H. V. Ngai: Quasi-Newton methods for solving nonsmooth equations: generalized Dennis-Moré theorem and Broyden’s update, J. Convex Analysis 25/4 (2018) 1075–1104.https://doi.org/10.68381/jca25069Google Scholar
  6. S. Adly, H. V. Ngai, N. V. Vu: Newton-type method for solving generalized equations on Riemannian manifolds, J. Convex Analysis 25/2 (2018) 341–370.https://doi.org/10.68381/jca25025Google Scholar
  7. Q. Ansari, F. Babu, X.-B. Li: Variational inclusion problems in Hadamard manifolds, J. Nonlinear Convex Analysis 19/1 (2018) 219–237.Google Scholar
  8. F. J. Aragón Artacho, A. Belyakov, A. L. Dontchev, M. López: Local convergence of quasi-Newton methods under metric regularity, Comp. Optimization Appl. 58/1 (2013) 225–247.https://doi.org/10.1007/s10589-013-9615-yGoogle Scholar
  9. J. X. da Cruz Neto, O. P. Ferreira, L. R. Lucambio Pérez: Monotone point-to-set vector fields, Balkan J. Geometry Appl. 5/1 (2000) 69–79.Google Scholar
  10. J.-P. Dedieu, P. Priouret, G. Malajovich: Newton’s method on Riemannian manifolds: covariant alpha theory, IMA J. Numer. Analysis 23/3 (2003) 395–419.https://doi.org/10.1093/imanum/23.3.395Google Scholar
  11. J. E. Dennis jun., J. J. Moré: A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Computation 28/126 (1974) 549–560.https://doi.org/10.1090/S0025-5718-1974-0343581-1Google Scholar
  12. J. E. Dennis jun., J. J. Moré: Quasi-Newton methods, motivation and theory, SIAM Review 19/1 (1977) 46–89.https://doi.org/10.1137/1019005Google Scholar
  13. M. Dilshad, M. Akram: Multi-valued variational inclusion problems in Hadamard manifolds, Bull. Math. Analysis Appl. 12/1 (2020) 29–40.Google Scholar
  14. M. P. do Carmo: Riemannian Geometry, Mathematics: Theory & Applications, Birkhäuser, Basel (1992).https://doi.org/10.1007/978-1-4757-2201-7Google Scholar
  15. A. L. Dontchev: Generalizations of the Dennis-Moré theorem, SIAM J. Optimization 22/3 (2012) 821–830.https://doi.org/10.1137/110833567Google Scholar
  16. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings: A View from Variational Analysis, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York (2014).https://doi.org/10.1007/978-1-4939-1037-3Google Scholar
  17. O. P. Ferreira, B. F. Svaiter: Kantorovich’s theorem on Newton’s method in Riemannian manifolds, J. Complexity 18/1 (2002) 304–329.https://doi.org/10.1006/jcom.2001.0582Google Scholar
  18. K. A. Gallivan, C. Qi, P.-A. Absil: A Riemannian Dennis-Moré condition, in: High-Performance Scientific Computing: Algorithms and Applications, W. M. Berry et al. (eds.), Springer, London (2012) 281–293.https://doi.org/10.1007/978-1-4471-2437-5_14Google Scholar
  19. M. Gaydu, M. H. Geoffroy: A Newton iteration for differentiable set-valued maps, J. Appl. Math. Analysis Appl. 399/1 (2013) 213–224.https://doi.org/10.1016/j.jmaa.2012.10.012Google Scholar
  20. A. Griewank: Broyden updating, the good and the bad, Documenta Mathematica (2012) 301–315.https://doi.org/10.4171/dms/6/32Google Scholar
  21. S. Hosseini, M. R. Pouryayevali: Nonsmooth optimization techniques on Riemannian manifolds, J. Optimization Theory Appl. 158/2 (2013) 328–342.https://doi.org/10.1007/s10957-012-0250-zGoogle Scholar
  22. W. Huang, K. A. Gallivan, P.-A. Absil: A Broyden class of quasi-Newton methods for Riemannian optimization, SIAM J. Optimization 25/3 (2015) 1660–1685.https://doi.org/10.1137/140955483Google Scholar
  23. A. F. Izmailov, M. V. Solodov: Newton-Type Methods for Optimization and Variational Problems, Springer Series in Operation Research and Finacial Engineering, Springer, Cham (2014).https://doi.org/10.1007/978-3-319-04247-3Google Scholar
  24. Yu. S. Ledyaev, Q. J. Zhu: Nonsmooth analysis on smooth manifolds, Trans. Amer. Math. Soc. 359 (2007) 3687–3732.https://doi.org/10.1090/S0002-9947-07-04075-5Google Scholar
  25. C. Li, B. S. Mordukhovich, J. Wang, J.-C. Yao: Weak sharp minima on Riemannian manifolds, SIAM J. Optimization 21/4 (2011) 1523–1560.https://doi.org/10.1137/09075367XGoogle Scholar
  26. C. Li, J. Yao: Variational inequalities for set-valued vector fields on Riemannian manifolds: convexity of the solution set and the proximal point algorithm, SIAM J. Control Optimization 50/4 (2012) 2486–2514.https://doi.org/10.1137/110834962Google Scholar
  27. S.-L. Li, C. Li, Y.-C. Liou, J.-C. Yao: Existence of solutions for variational inequalities on Riemannian manifolds, Nonlinear Anal. Theory Meth. Appl. 71/11 (2009) 5695–5706.https://doi.org/10.1016/j.na.2009.04.048Google Scholar
  28. J. M. Martínez: Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math. 124 (2000) 97–121.https://doi.org/10.1016/S0377-0427(00)00434-9Google Scholar
  29. S. Z. Németh: Variational inequalities on Hadamard manifolds, Nonlinear Anal. Theory Meth. Appl. 52/5 (2003) 1491–1498.https://doi.org/10.1016/S0362-546X(02)00266-3Google Scholar
  30. C. Qi: Numerical Optimization Methods on Riemannian Manifolds, PhD Thesis, Florida State University, Tallahassee (2011).Google Scholar
  31. C. Qi, K. A. Gallivan, P.-A. Absil: Riemannian BFGS algorithm with applications, in: Recent Advances in Optimization and its Applications in Engineering, M. Diehl et al. (eds.), Springer, Berlin (2010) 183–192.https://doi.org/10.1007/978-3-642-12598-0_16Google Scholar
  32. W. Ring, B. Wirth: Optimization methods on Riemannian manifolds and their application to shape space, SIAM J. Optimization 22/2 (2012) 596–627.https://doi.org/10.1137/11082885XGoogle Scholar
  33. S. M. Robinson: Generalized equations and their solutions. I: Basic theory, Math. Programming Studies 10 (1979) 128-141.https://doi.org/10.1007/BFb0120850Google Scholar
  34. S. M. Robinson: Strongly regular generalized equations, Math. Oper. Research 5/1 (1980) 43–62.https://doi.org/10.1287/moor.5.1.43Google Scholar
  35. S. M. Robinson: Generalized equations, in: Mathematical Programming: The State of the Art, A. Bachem et al. (eds.), Springer, Berlin (1982) 346–367.https://doi.org/10.1007/978-3-642-68874-4_14Google Scholar
  36. E. W. Sachs: Broyden’s method in Hilbert space, Math. Programming 35/1 (1986) 71–82.https://doi.org/10.1007/BF01589442Google Scholar
  37. T. Sakai: Riemannian Geometry, Translations of Mathematical Monographs 149, American Mathematical Society, Providence (1996).https://doi.org/10.1090/mmono/149Google Scholar
  38. M. Seibert, M. Kleinstauber, K. Hüper: Properties of the BFGS method on Riemannian manifolds, in: Mathematical System Theory, K. Hüper and J. Trumpf (eds.), CreateSpace, Amazon, North Charleston (2013) 395–412.Google Scholar
  39. S. T. Smith: Optimization techniques on Riemannian manifolds, in: Hamiltonian and Gradient Flows, Algorithms and Control, Fields Institute Communications 3, American Mathematical Society, Providence (1994) 113–136.https://doi.org/10.1090/fic/003/09Google Scholar
  40. C. Udrişte: Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and Its Applications 297, Springer, Amsterdam (1994).https://doi.org/10.1007/978-94-015-8390-9Google Scholar
  41. J.-H. Wang, C. Li: Uniqueness of the singular points of vector fields on Riemannian manifolds under the γ-condition, J. Complexity 22/4 (2006) 533–548.https://doi.org/10.1016/j.jco.2005.11.004Google Scholar

Suggested citation

S. Adly, H. V. Ngai, V. V. Nguyen. “Dennis-Moré Condition for Set-Valued Vector Fields and the Superlinear Convergence of Broyden Updates in Riemannian Manifolds.” Journal of Convex Analysis 29 (2022), No. 3, 669–701. https://doi.org/10.68381/jca29038

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2022. Rights now held by Banach Press LLC.