Memoryless quasi-Newton methods based on the spectral-scaling Broyden family for Riemannian optimization. (English) Zbl 1515.65159
Summary: We consider iterative methods for unconstrained optimization on Riemannian manifolds. Though memoryless quasi-Newton methods are effective for large-scale unconstrained optimization in the Euclidean space, they have not been studied over Riemannian manifolds. Therefore, in this paper, we propose a memoryless quasi-Newton method in Riemannian manifolds. The proposed method is based on the spectral-scaling Broyden family with additional modifications to ensure the sufficient descent condition. We present an algorithm for the proposed method that uses the Wolfe line search conditions and show that this algorithm guarantees global convergence. We emphasize that global convergence is guaranteed without any assumptions regarding the convexity of the objective function or the isometric property of the vector transport. In addition, we derive appropriate selections for the parameter vector contained in the proposed method. Numerical experiments are conducted to compare the proposed method with conventional conjugate gradient methods using typical test problems. The results show that the proposed method is superior to the tested conjugate gradient methods.
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C48 | Programming in abstract spaces |
| 90C53 | Methods of quasi-Newton type |
Keywords:
Riemannian optimization; memoryless quasi-Newton methods; Broyden family; global convergenceReferences:
| [1] | Absil, P-A; Baker, CG; Gallivan, KA, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7, 303-330 (2007) · Zbl 1129.65045 |
| [2] | Absil, P.-A., Gallivan, K.A.: Joint diagonalization on the oblique manifold for independent component analysis. In: 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, (2006) |
| [3] | Absil, P-A; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds (2008), Princeton: Princeton University Press, Princeton · Zbl 1147.65043 |
| [4] | Al-Baali, M., On measure functions for the self-scaling updating formulae for quasi-Newton methods, Optimization, 32, 59-69 (1995) · Zbl 0816.49023 |
| [5] | Al-Baali, M.; Narushima, Y.; Yabe, H., A family of three-term conjugate gradient methods with sufficient descent property for unconstrained optimization, Comput. Optim. Appl., 60, 89-110 (2015) · Zbl 1315.90051 |
| [6] | Bergmann, R., Manopt.jl: optimization on manifolds in Julia, J. Open Source Softw., 7, 3866 (2022) |
| [7] | Boumal, N.: An Introduction to Optimization on Smooth Manifolds, (2020), http://www.nicolasboumal.net/book · Zbl 1532.90001 |
| [8] | Boumal, N.; Absil, P-A; Cartis, C., Global rates of convergence for nonconvex optimization on manifolds, IMA J. Num. Anal., 39, 1-33 (2019) · Zbl 1483.65092 |
| [9] | 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) · Zbl 1319.90003 |
| [10] | Chen, Z.; Cheng, W., Spectral-scaling quasi-Newton methods with updates from the one parameter of the Broyden family, J. Comput. Appl. Mathem., 248, 88-98 (2013) · Zbl 1271.65095 |
| [11] | Cheng, WY; Li, DH, Spectral scaling BFGS method, J. Optim. Theory Appl., 146, 305-319 (2010) · Zbl 1198.90355 |
| [12] | Comon, P.; Golub, GH, Tracking a few extreme singular values and vectors in signal processing, Proc. IEEE, 78, 1327-1343 (1990) |
| [13] | Cook, RD, Fisher lecture: dimension reduction in regression, Stat. Sci., 22, 1-26 (2007) · Zbl 1246.62148 |
| [14] | Cook, RD; Forzani, L., Likelihood-based sufficient dimension reduction, J. Am. Stat. Assoc., 104, 197-208 (2009) · Zbl 1388.62041 |
| [15] | Dai, YH; Kou, CX, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search, SIAM J. Optim., 23, 296-320 (2013) · Zbl 1266.49065 |
| [16] | Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Progr., 91, 201-213 (2002) · Zbl 1049.90004 |
| [17] | Hager, WW; Zhang, H., A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16, 170-192 (2005) · Zbl 1093.90085 |
| [18] | Hager, WW; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 35-58 (2006) · Zbl 1117.90048 |
| [19] | Hager, WW; Zhang, H., Algorithm 851: CG_DESCENT, a conjugate gradient method with guaranteed descent, ACM Trans. Math. Softw., 32, 113-137 (2006) · Zbl 1346.90816 |
| [20] | Huang, W.: Optimization Algorithms on Riemannian Manifolds with Applications. In: Ph.D. thesis, Florida State University, (2013) |
| [21] | Huang, W.; Gallivan, KA; Absil, P-A, A Broyden class of quasi-Newton methods for Riemannian optimization, SIAM J. Optim., 25, 1660-1685 (2015) · Zbl 1461.65156 |
| [22] | Huang, W.; Absil, P-A; Gallivan, KA, A Riemannian symmetric rank-one trust-region method, Math. Progr., 150, 179-216 (2015) · Zbl 1314.65083 |
| [23] | Huang, W.; Gallivan, KA; Srivastava, A.; Absil, P-A, Riemannian optimization for registration of curves in elastic shape analysis, J. Math. Imag. Vision, 54, 320-343 (2016) · Zbl 1338.49088 |
| [24] | Huang, W.; Absil, P-A; Gallivan, KA, A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems, SIAM J. Optim., 28, 470-495 (2018) · Zbl 1382.65177 |
| [25] | Kressner, D.; Steinlechner, M.; Vandereycken, B., Low-rank tensor completion by Riemannian optimization, BIT Num. Math., 54, 447-468 (2014) · Zbl 1300.65040 |
| [26] | Kobayashi, H.; Narushima, Y.; Yabe, H., Descent three-term conjugate gradient methods based on secant conditions for unconstrained optimization, Optim. Methods Softw., 32, 1313-1329 (2017) · Zbl 1375.90283 |
| [27] | Kou, CX; Dai, YH, A modified self-scaling memoryless Broyden-Fletcher-Goldfarb-Shanno method for unconstrained optimization, J. Optim. Theor. Appl., 165, 209-224 (2015) · Zbl 1319.49042 |
| [28] | Liu, C.; Boumal, N., Simple algorithms for optimization on Riemannian manifolds with constraints, Appl. Math. Optim., 82, 949-981 (2020) · Zbl 1468.65072 |
| [29] | Li, DH; Fukushima, M., A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129, 15-35 (2001) · Zbl 0984.65055 |
| [30] | Moyi, AU; Leong, WJ, A sufficient descent three-term conjugate gradient method via symmetric rank-one update for large-scale optimization, Optimization, 65, 121-143 (2016) · Zbl 1335.65054 |
| [31] | Nakayama, S., A hybrid method of three-term conjugate gradient method and memoryless quasi-Newton method for unconstrained optimization, SUT J. Math., 54, 79-98 (2018) · Zbl 1422.90055 |
| [32] | Nakayama, S.; Narushima, Y.; Nishio, H.; Yabe, H., An active-set memoryless quasi-Newton method based on a spectral-scaling Broyden family for bound constrained optimization, Res. Control Optim., 3 (2021) |
| [33] | Nakayama, S.; Narushima, Y.; Yabe, H., A memoryless symmetric rank-one method with sufficient descent property for unconstrained optimization, J. Oper. Res. Soc. Jpn., 61, 53-70 (2018) · Zbl 1391.90493 |
| [34] | Nakayama, S.; Narushima, Y.; Yabe, H., Memoryless quasi-Newton methods based on spectral-scaling Broyden family for unconstrained optimization, J. Indus. Manag. Optim., 15, 1773-1793 (2019) · Zbl 1438.90331 |
| [35] | Nakamura, W.; Narushima, Y.; Yabe, H., Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization, J. Indus. Manag. Optim., 9, 595-619 (2013) · Zbl 1281.90057 |
| [36] | Narushima, Y.; Yabe, H., Conjugate gradient methods based on secant conditions that generate descent search directions for unconstrained optimization, J. Comput. Appl. Math., 236, 4303-4317 (2012) · Zbl 1258.65059 |
| [37] | Narushima, Y.; Yabe, H., A survey of sufficient descent conjugate gradient methods for unconstrained optimization, SUT J. Math., 50, 167-203 (2014) · Zbl 1329.90142 |
| [38] | Narushima, Y.; Yabe, H.; Ford, JA, A three-term conjugate gradient method with sufficient descent property for unconstrained optimization, SIAM J. Optim., 21, 212-230 (2011) · Zbl 1250.90087 |
| [39] | Nocedal, J., Updating quasi-Newton matrices with limited storage, Math. Comput., 35, 773-782 (1980) · Zbl 0464.65037 |
| [40] | Nocedal, J.; Wright, SJ, Numerical Optimization (2006), New York: Springer Series in Operations Research, New York · Zbl 1104.65059 |
| [41] | Obara, M.; Okuno, T.; Takeda, A., Sequential quadratic optimization for nonlinear optimization problems on Riemannian manifolds, SIAM J. Optim., 32, 822-853 (2022) · Zbl 1517.65050 |
| [42] | Ring, W.; Wirth, B., Optimization methods on Riemannian manifolds and their application to shape space, SIAM J. Optim., 22, 596-627 (2012) · Zbl 1250.90111 |
| [43] | Sato, H., A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe conditions, Comput. Optim. Appl., 64, 101-118 (2016) · Zbl 1338.65164 |
| [44] | Sato, H.: Riemannian Optimization and Its Applications, Springer Cham, (2021) · Zbl 1456.90001 |
| [45] | Sato, H.; Iwai, T., A new, globally convergent Riemannian conjugate gradient method, Optimization, 64, 1011-1031 (2015) · Zbl 1311.65072 |
| [46] | Sakai, H.; Iiduka, H., Hybrid Riemannian conjugate gradient methods with global convergence properties, Comput. Optim. Appl., 77, 811-830 (2020) · Zbl 1466.90123 |
| [47] | Sakai, H.; Iiduka, H., Sufficient descent Riemannian conjugate gradient methods, J. Optim. Theor. Appl., 190, 130-150 (2021) · Zbl 1472.65072 |
| [48] | Shanno, DF, Conjugate gradient methods with inexact searches, Math. Oper. Res., 3, 244-256 (1978) · Zbl 0399.90077 |
| [49] | Sugiki, K.; Narushima, Y.; Yabe, H., Globally convergent three-term conjugate gradient methods that use secant conditions and generate descent search directions for unconstrained optimization, J. Optim. Theor. Appl., 153, 733-757 (2012) · Zbl 1262.90170 |
| [50] | Sun, W.; Yuan, Y., Optimization Theory and Methods: Nonlinear Programming (2006), New York: Springer, New York · Zbl 1129.90002 |
| [51] | Townsend, J.; Koep, N.; Weichwald, S., Pymanopt: a Python toolbox for optimization on manifolds using automatic differentiation, J. Mach. Learn. Res., 17, 1-5 (2016) · Zbl 1416.65580 |
| [52] | Vandereycken, B., Low-rank matrix completion by Riemannian optimization, SIAM J. Optim., 23, 1214-1236 (2013) · Zbl 1277.15021 |
| [53] | Yamakawa, Y.; Sato, H., Sequential optimality conditions for nonlinear optimization on Riemannian manifolds and a globally convergent augmented Lagrangian method, Comput. Optim. Appl., 81, 397-421 (2022) · Zbl 1487.90640 |
| [54] | Yger, F., Berar, M., Gasso, G., Rakotomamonjy, A.: Adaptive canonical correlation analysis based on matrix manifolds. In: Proceedings of the 29th International Conference on Machine Learning, pp. 1071-1078 (2012) |
| [55] | Zhang, Y.; Tewarson, RP, Quasi-Newton algorithms with updates from the preconvex part of Broyden’s family, IMA J. Num. Anal., 8, 487-509 (1988) · Zbl 0661.65061 |
| [56] | Zhang, L.; Zhou, W.; Li, DH, Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search, Num. Math., 104, 561-572 (2006) · Zbl 1103.65074 |
| [57] | Zhang, L.; Zhou, W.; Li, DH, A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence, IMA J. Num. Anal., 26, 629-640 (2006) · Zbl 1106.65056 |
| [58] | Zhang, L.; Zhou, W.; Li, DH, Some descent three-term conjugate gradient methods and their global convergence, Optim. Methods Softw., 22, 697-711 (2007) · Zbl 1220.90094 |
| [59] | Zhu, X.; Sato, H., Riemannian conjugate gradient methods with inverse retraction, Comput. Optim. Appl., 77, 779-810 (2020) · Zbl 1466.90124 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
