Proximal gradient algorithm with trust region scheme on Riemannian manifold. (English) Zbl 07827860
Summary: We consider the problem of minimizing the sum of a smooth function and nonsmooth function over a Riemannian manifold. We develop a Riemannian proximal gradient algorithm with a trust region scheme for the problem. Global convergence is presented under natural assumptions. We establish an \(O(1/{\varepsilon^2})\) iteration complexity bound that matches the best-known complexity bound of Riemannian trust region methods for smooth optimization. Moreover, we give a nonmonotone version and an accelerated version of the Riemannian proximal gradient algorithm with a trust region scheme. Their global convergence is established. Numerical results demonstrate the effectiveness of the proposed methods.
MSC:
| 90C48 | Programming in abstract spaces |
Keywords:
Riemannian optimization; Riemannian proximal gradient method; trust region methods; nonmonotone; oblique manifold; Stiefel manifoldReferences:
| [1] | Absil, P.; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds, 2008, Princeton, NJ: Princeton University Press, Princeton, NJ · Zbl 1147.65043 · doi:10.1515/9781400830244 |
| [2] | Absil, PA; Baker, CG; Gallivan, KA, Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7, 3, 303-330, 2007 · Zbl 1129.65045 · doi:10.1007/s10208-005-0179-9 |
| [3] | Aravkin, AY; Baraldi, R.; Orban, D., A proximal quasi-newton trust-region method for nonsmooth regularized optimization, SIAM J. Optim., 32, 2, 900-929, 2022 · Zbl 1493.90139 · doi:10.1137/21M1409536 |
| [4] | Beck, A., First-Order Methods in Optimization, 2017, Princeton, NJ: SIAM, Princeton, NJ · Zbl 1384.65033 · doi:10.1137/1.9781611974997 |
| [5] | Bento, GC; Ferreira, OP; Melo, JG, Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds, J. Optim. Theor. Appl., 173, 548-562, 2017 · Zbl 1400.90277 · doi:10.1007/s10957-017-1093-4 |
| [6] | Bertsekas, DP, Nonlinear programming, J. Oper. Res. Soc., 48, 3, 334-334, 1997 · doi:10.1057/palgrave.jors.2600425 |
| [7] | Boumal, N., Absil, P.: RTRMC: a Riemannian trust-region method for low-rank matrix completion. In 24th International Conference on Neural Information Processing Systems pp. 406-414 (2011) |
| [8] | Cartis, C.; Gould, NI; Toint, PL, On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming, SIAM J. Optim., 21, 4, 1721-1739, 2011 · Zbl 1236.90118 · doi:10.1137/11082381X |
| [9] | Chavel, I., Riemannian Geometry, 2006, Woodbine, NJ: Cambridge University Press, Woodbine, NJ · Zbl 1099.53001 · doi:10.1017/CBO9780511616822 |
| [10] | Chen, S.; Ma, S.; So, MC; Zhang, T., Proximal gradient method for nonsmooth optimization over the stiefel manifold, SIAM J. Optim., 30, 1, 210-239, 2020 · Zbl 1434.90195 · doi:10.1137/18M122457X |
| [11] | Chen, Z.; Milzarek, A.; Wen, Z., A trust-region method for nonsmooth nonconvex optimization, J. Comput. Math., 41, 659-692, 2023 · Zbl 1524.90254 · doi:10.4208/jcm.2110-m2020-0317 |
| [12] | Deng, NY; Xiao, Y.; Zhou, FJ, Nonmonotonic trust region algorithm, J. Optim. Theor. Appl., 76, 2, 259-285, 1993 · Zbl 0797.90088 · doi:10.1007/BF00939608 |
| [13] | Ferreira, OP; Oliveira, PR, Proximal point algorithm on Riemannian manifolds, Optimization, 51, 2, 257-270, 2002 · Zbl 1013.49024 · doi:10.1080/02331930290019413 |
| [14] | Genicot, M., Huang, W., Trendafilov, N.T.: Weakly correlated sparse components with nearly orthonormal loadings. Geometric Science of Information pp. 484-490 (2015) · Zbl 1406.94012 |
| [15] | Ghadimi, S.; Lan, G., Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Math. Program., 156, 1-2, 59-99, 2016 · Zbl 1335.62121 · doi:10.1007/s10107-015-0871-8 |
| [16] | Grohs, P.; Hosseini, S., Nonsmooth trust region algorithms for locally Lipschitz functions on Riemannian manifolds, IMA J. Numer. Anal., 36, 1167-1192, 2016 · Zbl 1433.90124 · doi:10.1093/imanum/drv043 |
| [17] | Grohs, P.; Hosseini, S., \( \varepsilon \)-subgradient algorithms for locally lipschitz functions on Riemannian manifolds, Adv. Comput. Math., 42, 2, 333-360, 2016 · Zbl 1338.49029 · doi:10.1007/s10444-015-9426-z |
| [18] | Hosseini, S.; Pouryayevali, MR, Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds, Nonlinear Anal. Theor. Methods Appl., 74, 12, 3884-3895, 2011 · Zbl 1225.49046 · doi:10.1016/j.na.2011.02.023 |
| [19] | Hotellings, H., Analysis of a complex of statistical variables into principal components, Br. J. Educ. Psychol., 24, 417-520, 1933 · JFM 59.1182.04 · doi:10.1037/h0071325 |
| [20] | Hu, J.; Liu, X.; Wen, ZW; Yuan, YX, A brief introduction to manifold optimization, J. Oper. Res. Soc. China, 8, 2, 2194-6698, 2020 · Zbl 1474.49093 · doi:10.1007/s40305-020-00295-9 |
| [21] | Huang, W.: Optimization algorithms on Riemannian manifolds with applications. Dissertations and Theses-Gradworks (2013) |
| [22] | Huang, W.; Absil, P.; Gallivan, KA, A Riemannian BFGS method for nonconvex optimization problems, Numer. Math. Adv. Appl. ENUMATH, 2015, 627-634, 2016 · Zbl 1352.65153 |
| [23] | Huang, W.; Absil, PA; Gallivan, KA, A Riemannian symmetric rank-one trust-region method, Math. Program., 150, 2, 179-216, 2015 · Zbl 1314.65083 · doi:10.1007/s10107-014-0765-1 |
| [24] | Huang, W.; Absil, PA; Gallivan, KA, A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems, SIAM J. Optim., 28, 1, 470-495, 2018 · Zbl 1382.65177 · doi:10.1137/17M1127582 |
| [25] | Huang, W.; Wei, K., An extension of fast iterative shrinkage-thresholding algorithm to Riemannian optimization for sparse principal component analysis, Numer. Linear Algebra Appl., 29, 1, 2022 · Zbl 07511590 · doi:10.1002/nla.2409 |
| [26] | Huang, W.; Wei, K., Riemannian proximal gradient methods, Math. Program., 194, 1-2, 371-413, 2022 · Zbl 1492.90012 · doi:10.1007/s10107-021-01632-3 |
| [27] | Jolliffe, IT; Uddin, TM, A modified principal component technique based on the LASSO, J. Comput. Graph. Stat., 12, 3, 531-547, 2003 · doi:10.1198/1061860032148 |
| [28] | Li, H.; Lin, Z., Accelerated proximal gradient methods for nonconvex programming, Adv. Neural Inf. Process. Syst., 28, 379-387, 2015 |
| [29] | Liu, JJ; Xu, XM; Cui, XH, An accelerated nonmonotone trust region method with adaptive trust region for unconstrained optimization, Comput. Optim. Appl., 69, 1, 1573-2894, 2018 · Zbl 1393.90117 · doi:10.1007/s10589-017-9941-6 |
| [30] | Mo, J.; Liu, C.; Yan, S., A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values, J. Comput. Appl. Math., 209, 1, 97-108, 2007 · Zbl 1142.65049 · doi:10.1016/j.cam.2006.10.070 |
| [31] | Nemirovsky, AS; Yudin, DB, Problem complexity and method efficiency in optimization, J. Oper. Res. Soc., 35, 5, 455-455, 1984 · doi:10.1057/jors.1984.92 |
| [32] | Ozolins, V.; Lai, R.; Caflisch, R.; Osher, S., Compressed modes for variational problems in mathematics and physics, Proc. Natl. Acad. Sci., 110, 46, 18368-18373, 2013 · Zbl 1292.81024 · doi:10.1073/pnas.1318679110 |
| [33] | Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 1, 3, 127-239, 2014 · doi:10.1561/2400000003 |
| [34] | Ring, W.; Wirth, B., Optimization methods on Riemannian manifolds and their application to shape space, SIAM J. Optim., 22, 2, 596-627, 2012 · Zbl 1250.90111 · doi:10.1137/11082885X |
| [35] | Sato, H.; Toshihiro, Iwai, A new, globally convergent Riemannian conjugate gradient method, Optimization, 64, 4, 1011-1031, 2015 · Zbl 1311.65072 · doi:10.1080/02331934.2013.836650 |
| [36] | Sjöstrand, K.; Clemmensen, L., SpaSM: a MATLAB toolbox for sparse statistical modeling, J. Stat. Softw., 84, 10, 1-37, 2018 · doi:10.18637/jss.v084.i10 |
| [37] | Sun, W., Nonmonotone trust region method for solving optimization problems, Appl. Math. Comput., 156, 1, 159-174, 2004 · Zbl 1059.65055 |
| [38] | Sun, WY; Yuan, YX, Optimization Theory and Methods: Nonlinear Programming, 2006, Springer Science Business Media · Zbl 1129.90002 |
| [39] | Tang, J.; Liu, H., An unsupervised feature selection framework for social media data, IEEE Trans. Knowl. Data Eng., 26, 12, 2914-2927, 2015 · doi:10.1109/TKDE.2014.2320728 |
| [40] | Yang, WH; Zhang, LH; Song, RY, Optimality conditions for the nonlinear programming problems on Riemannian manifolds, Pac. J. Optim., 10, 2, 415-434, 2014 · Zbl 1322.90096 |
| [41] | Yang, Y., Shen, H.T., Ma, Z., Zi, H., Zhou, X.: \(l_{21}\)-norm regularized discriminative feature selection for unsupervised learning. In 22th international joint conference on Artificial Intelligence 2, pp. 1589-1594 (2011) |
| [42] | Zhang, HC; Hager, WW, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim., 14, 1043-1056, 2004 · Zbl 1073.90024 · doi:10.1137/S1052623403428208 |
| [43] | Zhang, Y.Q., Lau, Y., Kuo, H.W., Cheung, S., Pasupathy, A., Wright, J.: On the global geometry of sphere-constrained sparse blind deconvolution. In IEEE Conference on Computer Vision and Pattern Recognition pp. 4381-4389 (2017) |
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.
