The difference of convex algorithm on Hadamard manifolds. (English) Zbl 07839683
Summary: In this paper, we propose a Riemannian version of the difference of convex algorithm (DCA) to solve a minimization problem involving the difference of convex (DC) function. The equivalence between the classical and simplified Riemannian versions of the DCA is established. We also prove that under mild assumptions the Riemannian version of the DCA is well defined and every cluster point of the sequence generated by the proposed method, if any, is a critical point of the objective DC function. Some duality relations between the DC problem and its dual are also established. To illustrate the algorithm’s effectiveness, some numerical experiments are presented.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 49Q99 | Manifolds and measure-geometric topics |
References:
| [1] | Absil, P-A; Baker, C.; Gallivan, K., Trust-region methods on Riemannian manifolds, Found. Comput. Math., 7, 303-330, 2007 · Zbl 1129.65045 · doi:10.1007/s10208-005-0179-9 |
| [2] | Absil, P-A; Mahony, R.; Sepulchre, R., Optimization Algorithms on Matrix Manifolds, 2008, Princeton: Princeton University Press, Princeton · Zbl 1147.65043 · doi:10.1515/9781400830244 |
| [3] | Almeida, YT; Cruz Neto, JX; Oliveira, PR; de Souza, JC, A modified proximal point method for DC functions on Hadamard manifolds, Comput. Optim. Appl., 76, 649-673, 2020 · Zbl 1445.90084 · doi:10.1007/s10589-020-00173-3 |
| [4] | An, LTH; Tao, PD, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46, 2005 · Zbl 1116.90122 · doi:10.1007/s10479-004-5022-1 |
| [5] | Axen, S.D., Baran, M., Bergmann, R., Rzecki, K.: Manifolds.jl: an extensible Julia framework for data analysis on manifolds. ACM Trans. Math. Softw.0 49(4), 1-23 (2023). doi:10.1145/3618296 · Zbl 07912531 |
| [6] | Baçák, M.; Bergmann, R.; Steidl, G., A second order non-smooth variational model for restoring manifold-valued images, SIAM J. Sci. Comput., 38, 1, 567-597, 2016 · Zbl 1382.94007 · doi:10.1137/15M101988X |
| [7] | Bartle, RG; Sherbert, DR, Introduction to Real Analysis, 2000, New York: Wiley, New York |
| [8] | Bergmann, R., Manopt.jl: optimization on manifolds in Julia, J. Open Source Softw., 7, 70, 3866, 2022 · doi:10.21105/joss.03866 |
| [9] | Bergmann, R.; Herzog, R.; Silva Louzeiro, M.; Tenbrinck, D.; Vidal-Núñez, J., Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds, Found. Comput. Math., 21, 6, 1465-1504, 2021 · Zbl 07458819 · doi:10.1007/s10208-020-09486-5 |
| [10] | Bergmann, R.; Persch, J.; Steidl, G., A parallel Douglas-Rachford algorithm for minimizing ROF-like functionals on images with values in symmetric Hadamard manifolds, SIAM J. Imag. Sci., 9, 4, 901-937, 2016 · Zbl 1346.65006 · doi:10.1137/15M1052858 |
| [11] | Bergmann, R.; Weinmann, A., A second-order TV-type approach for inpainting and denoising higher dimensional combined cyclic and vector space data, J. Math. Imaging Vis., 55, 401-427, 2016 · Zbl 1338.65155 · doi:10.1007/s10851-015-0627-3 |
| [12] | Bezanson, J.; Edelman, A.; Karpinski, S.; Shah, V., Julia: a fresh approach to numerical computing, SIAM Rev., 59, 1, 65-98, 2017 · Zbl 1356.68030 · doi:10.1137/141000671 |
| [13] | Bhattacharya, A.; Bhattacharya, R., Statistics on Riemannian manifolds: asymptotic distribution and curvature, Proc. Am. Math. Soc., 136, 8, 2959-2967, 2008 · Zbl 1274.62337 · doi:10.1090/s0002-9939-08-09445-8 |
| [14] | Bourbaki, N., General Topology, 1995, Berlin, Heidelberg: Springer, Berlin, Heidelberg · doi:10.1007/978-3-642-61701-0 |
| [15] | Bredies, K.; Holler, M.; Storath, M.; Weinmann, A., Total generalized variation for manifold-valued data, SIAM J. Imag. Sci., 11, 3, 1785-1848, 2018 · Zbl 1401.94010 · doi:10.1137/17M1147597 |
| [16] | Chen, J., Revels, J.: Robust benchmarking in noisy environments. doi:10.48550/arXiv.1608.04295 (2016) |
| [17] | Cruz Neto, JX; Ferreira, OP; Pérez, LRL, Contributions to the study of monotone vector fields, Acta Math. Hungar., 94, 307-320, 2002 · Zbl 0997.53012 · doi:10.1023/a:1015643612729 |
| [18] | de Oliveira, W., The ABC of DC programming, Set Valued Variat. Anal., 28, 679-706, 2020 · Zbl 1467.90037 · doi:10.1007/s11228-020-00566-w |
| [19] | do Carmo, M.P.: Riemannian Geometry. Birkhäuser, Boston (1992) · Zbl 0752.53001 |
| [20] | Edelman, A.; Arias, TA; Smith, ST, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl., 20, 2, 303-353, 1998 · Zbl 0928.65050 · doi:10.1137/S0895479895290954 |
| [21] | Esposito, M.; Hennersperger, C.; Göbl, R.; Demaret, L.; Storath, M.; Navab, N.; Baust, M.; Weinmann, A., Total variation regularization of pose signals with an application to 3D freehand ultrasound, IEEE Trans. Med. Imaging, 38, 10, 2245-2258, 2019 · doi:10.1109/TMI.2019.2898480 |
| [22] | Fletcher, PT, Geodesic regression and the theory of least squares on Riemannian manifolds, Int. J. Comput. Vis., 105, 171-185, 2013 · Zbl 1304.62092 · doi:10.1007/s11263-012-0591-y |
| [23] | Freifeld, O., Black, M.J.: Lie Bodies: a manifold representation of 3D human shape. In: Fitzgibbon, A, Lazebnik, S, Perona, P, Sato, Y, Schmid, C (eds) Computer vision—ECCV 2012. ECCV 2012. Lecture Notes in Computer Science 7572. Springer, Berlin, Heidelberg, pp 1-14. doi:10.1007/978-3-642-33718-5_1 (2012) |
| [24] | Horev, I.; Yger, F.; Sugiyama, M., Geometry-aware principal component analysis for symmetric positive definite matrices, Mach. Learn., 106, 493-522, 2017 · Zbl 1459.62236 · doi:10.1007/s10994-016-5605-5 |
| [25] | Huang, W.; Gallivan, KA; Absil, P-A, A Broyden class of quasi-Newton methods for Riemannian optimization, SIAM J. Optim., 25, 3, 1660-1685, 2015 · Zbl 1461.65156 · doi:10.1137/140955483 |
| [26] | Kantorovich, LV; Akilov, GP, Functional Analysis, 1982, New York: Pergamon Press, New York · Zbl 0484.46003 |
| [27] | Lang, S., Fundamentals of Differential Geometry, 1999, New York: Springer, New York · Zbl 0932.53001 · doi:10.1007/978-1-4612-0541-8 |
| [28] | Le Thi, HA; Pham Dinh, T., DC programming and DCA: thirty years of developments, Math. Program., 169, 1, 5-68, 2018 · Zbl 1387.90197 · doi:10.1007/s10107-018-1235-y |
| [29] | Le Thi, H.A., Pham Dinh, T.: Open issues and recent advances in DC programming and DCA. J. Glob. Optim. 1-58 (2023). doi:10.1007/s10898-023-01272-1 |
| [30] | Li, C.; López, G.; Martín-Márquez, V., Monotone vector fields and the proximal point algorithm on Hadamard manifolds, J. Lond. Math. Soc., 79, 3, 663-683, 2009 · Zbl 1171.58001 · doi:10.1112/jlms/jdn087 |
| [31] | Li, C.; Mordukhovich, BS; Wang, J.; Yao, J-C, Weak sharp minima on Riemannian manifolds, SIAM J. Optim., 21, 4, 1523-1560, 2011 · Zbl 1236.49089 · doi:10.1137/09075367X |
| [32] | Lim, Y., Factorizations and geometric means of positive definite matrices, Linear Algebra Appl., 437, 9, 2159-2172, 2012 · Zbl 1251.15019 · doi:10.1016/j.laa.2012.05.039 |
| [33] | Manton, JH, A framework for generalising the Newton method and other iterative methods from Euclidean space to manifolds, Numer. Math., 129, 1, 91-125, 2015 · Zbl 1307.49025 · doi:10.1007/s00211-014-0630-4 |
| [34] | Miller, SA; Malick, J., Newton methods for nonsmooth convex minimization: connections among \({\cal{U} } \)-Lagrangian, Riemannian Newton and SQP methods, Math. Program., 104, 609-633, 2005 · Zbl 1124.90021 · doi:10.1007/s10107-005-0631-2 |
| [35] | Muscoloni, A.; Thomas, JM; Ciucci, S.; Bianconi, G.; Cannistraci, CV, Machine learning meets complex networks via coalescent embedding in the hyperbolic space, Nat. Commun., 8, 1615, 2017 · doi:10.1038/s41467-017-01825-5 |
| [36] | Nesterov, YE; Todd, MJ, On the Riemannian geometry defined by self-concordant barriers and interior-point methods, Found. Comput. Math. J. Soc. Found. Comput. Math., 2, 333-361, 2002 · Zbl 1049.90127 · doi:10.1007/s102080010032 |
| [37] | Nickel, M., Kiela, D.: Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In: Dy, J., Krause, A. (eds) Proceedings of the 35th International Conference on Machine Learning, PMLR 80, pp. 3779-3788 (2018) |
| [38] | Park, FC; Bobrow, JE; Ploen, SR, A Lie group formulation of robot dynamics, Int. J. Robot. Res., 14, 6, 609-618, 1995 · doi:10.1177/027836499501400606 |
| [39] | Rapcsák, T.: Smooth Nonlinear Optimization in \({\textbf{R} }^n \). Kluwer Academic Publishers, Dordrecht (1997). doi:10.1007/978-1-4615-6357-0 · Zbl 1009.90109 |
| [40] | Rosenbrock, HH, An automatic method for finding the greatest or least value of a function, Comput. J., 3, 3, 175-184, 1960 · doi:10.1093/comjnl/3.3.175 |
| [41] | Rothaus, O.S: Domains of positivity. Abhandlungen aus dem Mathematischen Seminar der Universit \(\ddot{\text{a}}\) t Hamburg 24, 189-235 (1960). doi:10.1007/BF02942030 · Zbl 0096.27903 |
| [42] | Sakai, T., Riemannian geometry, 1996, Providence: American Mathematical Society, Providence · Zbl 0886.53002 · doi:10.1090/mmono/149 |
| [43] | Sharpee, TO, An argument for hyperbolic geometry in neural circuits, Curr. Opin. Neurobiol., 58, 101-104, 2019 · doi:10.1016/j.conb.2019.07.008 |
| [44] | Silva Louzeiro, M.; Bergmann, R.; Herzog, R., Fenchel duality and a separation theorem on Hadamard manifolds, SIAM J. Optim., 32, 2, 854-873, 2022 · Zbl 07534676 · doi:10.1137/21m1400699 |
| [45] | Smith, S.T.: Optimization techniques on Riemannian manifolds. In: Hamiltonian and Gradient Flows, Algorithms and Control. Fields Institute Communications, vol 3. American Mathematical Society, Providence, pp 113-136 (1994) · Zbl 0816.49032 |
| [46] | Souza, JCO; Oliveira, PR, A proximal point algorithm for DC fuctions on Hadamard manifolds, J. Global Optim., 63, 797-810, 2015 · Zbl 1329.49056 · doi:10.1007/s10898-015-0282-7 |
| [47] | Tabaghi, P., Dokmanić, I.: Hyperbolic distance matrices. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Association for Computing Machinery, Virtual Event, pp. 1728-1738. doi:10.1145/3394486.3403224 (2020) |
| [48] | Tabaghi, P.; Dokmanić, I., On procrustes analysis in hyperbolic space, IEEE Signal Process. Lett., 28, 1120-1124, 2021 · doi:10.1109/lsp.2021.3081379 |
| [49] | Tao, P.D., Souad, E.B.: Algorithms for solving a class of nonconvex optimization problems. Methods of subgradients. In: FERMAT Days 85: Mathematics for Optimization (Toulouse, 1985), vol. 129. North-Holland, Amsterdam, pp. 249-271 (1986). doi:10.1016/S0304-0208(08)72402-2 · Zbl 0638.90087 |
| [50] | Tao, P.D., Souad, E.B.: Duality in D.C. (Difference of convex functions) optimization. Subgradient methods. In: Hoffmann, K.H., Zowe, J., Hiriart-Urruty, J.B., Lemarechal, C. (eds) Trends in Mathematical Optimization : 4th French-German Conference. Birkh \(\ddot{\text{ a }}\) user, Basel, pp. 277-293 (1988). doi:10.1007/978-3-0348-9297-1_18 · Zbl 0634.49009 |
| [51] | Udrişte, C., Convex Functions and Optimization Methods on Riemannian Manifolds, 1994, Dordrecht: Kluwer Academic Publishers Group, Dordrecht · Zbl 0932.53003 · doi:10.1007/978-94-015-8390-9 |
| [52] | Wang, X.; Li, C.; Wang, J.; Yao, J-C, Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds, SIAM J. Optim., 25, 4, 2334-2358, 2015 · Zbl 1326.65072 · doi:10.1137/14099961X |
| [53] | Weber, M.; Sra, S., Riemannian optimization via Frank-Wolfe methods, Math. Program., 199, 525-556, 2023 · Zbl 1522.46052 · doi:10.1007/s10107-022-01840-5 |
| [54] | Weinmann, A.; Demaret, L.; Storath, M., Total variation regularization for manifold-valued data, SIAM J. Imag. Sci., 7, 4, 2226-2257, 2014 · Zbl 1309.65071 · doi:10.1137/130951075 |
| [55] | Weinmann, A.; Demaret, L.; Storath, M., Mumford-Shah and Potts regularization for manifold-valued data, J. Math. Imaging Vis., 55, 428-445, 2016 · Zbl 1344.49055 · doi:10.1007/s10851-015-0628-2 |
| [56] | Wen, Z.; Yin, W., A feasible method for optimization with orthogonality constraints, Math. Program., 142, 397-434, 2012 · Zbl 1281.49030 · doi:10.1007/s10107-012-0584-1 |
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.
