Top

Numerical Algorithms

Published in:

25-02-2020 | Original Paper

A Riemannian derivative-free Polak–Ribiére–Polyak method for tangent vector field

Authors: Teng-Teng Yao, Zhi Zhao, Zheng-Jian Bai, Xiao-Qing Jin

Published in: Numerical Algorithms | Issue 1/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper is concerned with the problem of finding a zero of a tangent vector field on a Riemannian manifold. We first reformulate the problem as an equivalent Riemannian optimization problem. Then, we propose a Riemannian derivative-free Polak–Ribiére–Polyak method for solving the Riemannian optimization problem, where a non-monotone line search is employed. The global convergence of the proposed method is established under some mild assumptions. To further improve the efficiency, we also provide a hybrid method, which combines the proposed geometric method with the Riemannian Newton method. Finally, some numerical experiments are reported to illustrate the efficiency of the proposed method.

previous article A self-adaptive descent LQP alternating direction method for the structured variational inequalities

next article Superconvergence in H1-norm of a difference finite element method for the heat equation in a 3D spatial domain with almost-uniform mesh

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008)MATHCrossRef

Absil, P.-A., Ishteva, M., Lathauwer, L., van Huffel, S.: A geometric Newton method for Oja’s vector field. Neural Comput. 21, 1415–1433 (2009)MathSciNetMATHCrossRef

Adler, R.L., Dedieu, J.-P., Margulies, J.Y., Martens, M., Shub, M.: Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22, 359–390 (2002)MathSciNetMATHCrossRef

Bento, G.C., Cruz Neto, J.X.: Finite termination of the proximal point method for convex functions on Hadamard manifolds. Optimization 63, 1281–1288 (2014)MathSciNetMATHCrossRef

Bortoloti, M.A.A., Fernandes, T.A., Ferreira, O.P., Yuan, J.Y.: Damped Newton’s Method on Riemannian Manifolds. arXiv:1803.05126 (2018)

Boumal, N., Mishra, B., Absil, P.-A., Sepulchre, R.: Manopt, a Matlab toolbox for optimization on manifolds. J. Mach. Learn. Res. 15, 1455–1459 (2014)MATH

Cai, Y.F., Jia, Z.G., Bai, Z.J.: Perturbation analysis of an eigenvector-dependent nonlinear eigenvalue problem with applications, BIT. https://doi.org/10.1007/s10543-019-00765-4 (2019)

Chen, H., Dai, X., Gong, X., He, L., Zhou, A.: Adaptive finite element approximations for Kohn-Sham models. Multiscale Model. Simul. 12, 1828–1869 (2014)MathSciNetMATHCrossRef

Cheng, W., Li, D.: A derivative-free non-monotone line search and its applications to the spectral residual method. IMA J. Numer. Anal. 29, 814–825 (2009)MathSciNetMATHCrossRef

10.

Cheng, W., Xiao, Y., Hu, Q.J.: A family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. J. Comput. Appl. Math. 224, 11–19 (2009)MathSciNetMATHCrossRef

11.

Cruz, W.L., Martínez, J., Raydan, M.: Spectral residual method without gradient information for solving large-scale nonlinear systems of equations. Math. Comp. 75, 1429–448 (2006)MathSciNetMATHCrossRef

12.

Cruz, W.L., Raydan, M.: Nonmonotone spectral methods for large-scale nonlinear systems. Optim. Methods Softw. 18, 583–599 (2003)MathSciNetMATHCrossRef

13.

Da Cruz Neto, J.X., Ferreira, O.P., Lucambio Perez, L.R.: Monotone point-to-set vector fields. Balkan J. Geom. Appl. 5, 69–79 (2000)MathSciNetMATH

14.

Da Cruz Neto, J.X., Ferreira, O.P., Lucambio Pérez, L.R.: Contributions to the study of monotone vector fields. Acta. Math. Hung. 94, 307–320 (2002)MathSciNetMATHCrossRef

15.

Da Cruz Neto, J.X., Ferreira, O.P., Lucambio Pérez, L.R., Németh, S.Z.: Convex and monotone-transformable mathematical programming problems and a proximal-like point method. J. Global Optim. 35, 53–69 (2006)MathSciNetMATHCrossRef

16.

Dedieu, J.P., Priouret, P., Malajovich, G.: Newton’s method on Riemannian manifolds: covariant alpha theory. IMA J. Numer. Anal. 23, 395–419 (2003)MathSciNetMATHCrossRef

17.

Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20, 303–353 (1998)MathSciNetMATHCrossRef

18.

Fang, X.W., Ni, Q.: A new derivative-free conjugate gradient method for large-scale nonlinear systems of equations. Bull. Aust. Math. Soc. 95, 500–511 (2017)MathSciNetMATHCrossRef

19.

Ferreira, O.P., Oliveira, P.R.: Proximal point algorithm on Riemannian manifolds. Optimization 51, 257–270 (2002)MathSciNetMATHCrossRef

20.

Ferreira, O.P., Pérez, L.R.L., Németh, S.Z.: Singularities of monotone vector fields and an extragradient-type algorithm. J. Global Optim. 31, 133–151 (2005)MathSciNetMATHCrossRef

21.

Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore and London (1996)MATH

22.

Helmke, U., Shayman, M.A.: Critical points of matrix least squares distance functions. Linear Algebra Appl. 215, 1–19 (1995)MathSciNetMATHCrossRef

23.

Jeuris, B.: Riemannian Optimization for Averaging Positive Definite Matrices, Ph.D. Dissertation, Department of Computer Science, KU Leuven (2015)

24.

Li, C., López, G., Martín-Márquez, M.: Monotone vector fields and the proximal point algorithm on Hadamard manifolds. J. Lond. Math. Soc. 79, 663–683 (2009)MathSciNetMATHCrossRef

25.

Li, C., Wang, J.H.: Convergence of the Newton method and uniqueness of zeros of vector fields on Riemannian manifolds. Sci. China Ser. A. 48, 1465–1478 (2005)MathSciNetMATHCrossRef

26.

Li, M.: A derivative-free PRP method for solving large-scale nonlinear systems of equations and its global convergence. Optim. Methods Softw. 29, 503–514 (2014)MathSciNetMATHCrossRef

27.

Martin, R.M.: Electronic Structure: Basic Theory and Practical Methods. Cambridge University Press, Cambridge (2004)MATHCrossRef

28.

Németh, S.Z.: Geodesic monotone vector fields. Lobachevskii J. Math. 5, 13–28 (1999)MathSciNetMATH

29.

Ngo, T., Bellalij, M., Saad, Y.: The trace ratio optimization problem for dimensionality reduction. SIAM J. Matrix Anal. Appl. 31, 2950–2971 (2010)MathSciNetMATHCrossRef

30.

Oja, E.: A simplified neuron model as a principal component analyzer. J. Math. Biol. 15, 267–273 (1982)MathSciNetMATHCrossRef

31.

Oja, E.: Neural networks, principal components, and subspaces. Neural Syst. 1, 61–68 (1989)CrossRef

32.

Ring, W., Wirth, B.: Optimization methods on Riemannian manifolds and their application to shape space. SIAM J. Optim. 22, 596–627 (2012)MathSciNetMATHCrossRef

33.

Saad, Y., Chelikowsky, J.R., Shontz, S.M.: Numerical methods for electronic structure calculations of materials. SIAM Rev. 52, 3–54 (2010)MathSciNetMATHCrossRef

34.

Sato, H., Iwai, T.: A new, globally convergent Riemannian conjugate gradient method. Optimization 64, 1011–1031 (2015)MathSciNetMATHCrossRef

35.

Tang, G.J., Huang, N.J.: An inexact proximal point algorithm for maximal monotone vector fields on Hadamard manifolds. Oper. Res. Lett. 41, 586–591 (2013)MathSciNetMATHCrossRef

36.

Wang, J.H., Li, C., Lopez, G., Yao, J.C.: Convergence analysis of inexact proximal point algorithms on Hadamard manifolds. J. Global Optim. 61, 553–573 (2015)MathSciNetMATHCrossRef

37.

Wang, J.H., Li, C., Lopez, G., Yao, J.C.: Proximal point algorithms on Hadamard manifolds: linear convergence and finite termination. SIAM J. Optim. 26, 2696–2729 (2016)MathSciNetMATHCrossRef

38.

Wang, J.H., López, G., Martín-Márquez, V., Li, C.: Monotone and accretive operators on Riemannian manifolds. J. Optim. Theory Appl. 146, 691–708 (2010)MathSciNetMATHCrossRef

39.

Yao, T.T., Bai, Z.J., Zhao, Z., Ching, W.K.: A Riemannian Fletcher–Reeves conjugate gradient method for doubly stochastic inverse eigenvalue problems. SIAM J. Matrix Anal. Appl. 37, 215–234 (2016)MathSciNetMATHCrossRef

40.

Yao, T.T., Bai, Z.J., Jin, X.Q., Zhao, Z.: A geometric Gauss–Newton method for least squares inverse eigenvalue problems, BIT Numer Math. https://doi.org/10.1007/s10543-019-00798-9 (2020)

41.

Yu, G.H.: A derivative-free method for solving large-scale nonlinear systems of equations. J. Ind. Manag. Optim. 6, 149–160 (2010)MathSciNetMATH

42.

Yu, G.H.: Nonmonotone spectral gradient-type methods for large-scale unconstrained optimization and nonlinear systems of equations. Pac. J. Optim. 7, 387–404 (2011)MathSciNetMATH

43.

Zhang, L.H., Li, R.C.: Maximization of the sum of the trace ratio on the Stiefel manifold, I: theory. Sci. China Math. 57, 2495–2508 (2014)MathSciNetMATHCrossRef

44.

Zhang, L.H., Li, R.C.: Maximization of the sum of the trace ratio on the Stiefel manifold, II: computation. Sci. China Math. 58, 1549–1566 (2015)MathSciNetMATHCrossRef

45.

Zhao, Z., Bai, Z.J., Jin, X.Q.: A Riemannian Newton algorithm for nonlinear eigenvalue problems. SIAM J. Matrix Anal. Appl. 36, 752–774 (2015)MathSciNetMATHCrossRef

46.

Zhao, Z., Jin, X.Q., Bai, Z.J.: A geometric nonlinear conjugate gradient method for stochastic inverse eigenvalue problems. SIAM J. Numer. Anal. 54, 2015–2035 (2016)MathSciNetMATHCrossRef

47.

Zhu, X.: A Riemannian conjugate gradient method for optimization on the Stiefel manifold. Comput. Optim. Appl. 67, 73–110 (2017)MathSciNetMATHCrossRef

Title: A Riemannian derivative-free Polak–Ribiére–Polyak method for tangent vector field
Authors: Teng-Teng Yao
Zhi Zhao
Zheng-Jian Bai
Xiao-Qing Jin
Publication date: 25-02-2020
Publisher: Springer US
Published in: Numerical Algorithms / Issue 1/2021
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-020-00891-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 1/2021

Adaptive total variation and second-order total variation-based model for low-rank tensor completion

Convergence analysis of the product integration method for solving the fourth kind integral equations with weakly singular kernels

Subgradient projection methods extended to monotone bilevel equilibrium problems in Hilbert spaces

On the parameter selection in the transformed matrix iteration method

Superconvergence in H1-norm of a difference finite element method for the heat equation in a 3D spatial domain with almost-uniform mesh

A numerically efficient variational algorithm to solve a fractional nonlinear elastic string equation

Premium Partner