Subgradient projection algorithms for convex feasibility on Riemannian manifolds with lower bounded curvatures. (English) Zbl 1308.90131
Summary: Under the assumption that the sectional curvature of the manifold is bounded from below, we establish convergence result about the cyclic subgradient projection algorithm for convex feasibility problem presented in a paper by G. C. Bento and J. G. Melo on Riemannian manifolds [J. Optim. Theory Appl. 152, No. 3, 773–785 (2012; Zbl 1270.90101)]. If, additionally, we assume that a Slater type condition is satisfied, then we further show that, without changing the step size, this algorithm terminates in a finite number of iterations. Clearly, our results extend the corresponding ones due to Bento and Melo and, in particular, we solve partially the open problem proposed in the paper by Bento and Melo [loc. cit.].
MSC:
| 90C25 | Convex programming |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 65K05 | Numerical mathematical programming methods |
Keywords:
convex feasibility problem; cyclic subgradient projection algorithm; Riemannian manifold; sectional curvatureCitations:
Zbl 1270.90101References:
| [1] | Bauschke, H.H., Borwein, J.M.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38(3), 367-426 (1996) · Zbl 0865.47039 · doi:10.1137/S0036144593251710 |
| [2] | Bauschke, H.H., Combettes, P.L., Kruk, S.G.: Extrapolation algorithm for affine-convex feasibility problems. Numer. Algorithms 41, 239-274 (2006) · Zbl 1098.65060 · doi:10.1007/s11075-005-9010-6 |
| [3] | Censor, Y.: Mathematical Optimization for the Inverse Problem of Intensity-Modulated Radiation Therapy. Medical Physics Publisher, Madison (2003) |
| [4] | Censor, Y., Altschuler, M.D., Powlis, W.D.: On the use of Cimmino’s simultaneous projections method for computing a solution of the inverse problem in radiation therapy treatment planning. Inverse Probl. 4, 607-623 (1988) · Zbl 0653.65049 · doi:10.1088/0266-5611/4/3/006 |
| [5] | Censor, Y., Zenios, S.A.: Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, New York (1997) · Zbl 0945.90064 |
| [6] | Combettes, P.L.: The foundations of set theoretic estimation. Proc. IEEE 81, 182-208 (1993) · doi:10.1109/5.214546 |
| [7] | Combettes, P.L.: The convex feasibility problem in image recovery. Adv. Imaging Electron Phys. 95, 155-270 (1996) · doi:10.1016/S1076-5670(08)70157-5 |
| [8] | Combettes, P.L.: Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections. IEEE Trans. Image Process. 6(4), 493-506 (1997) · doi:10.1109/83.563316 |
| [9] | Herman, G.: Image Reconstruction from Projections. The Fundamentals of Computerized Tomography. Academic Press, New York (1980) · Zbl 0538.92005 |
| [10] | Marks, L.D., Sinkler, W., Landree, E.: A feasible set approach to the crystallographic phase problem. Acta Crystallogr. 55(4), 601-612 (1999) · doi:10.1107/S0108767398014408 |
| [11] | Censor, Y., Lent, A.: A Cyclic Subgradient Projections Method for the Convex Feasibility Problems. Technical Report. University of Haifa, Israel (1980) · Zbl 0444.49025 |
| [12] | Butnariu, D., Censor, Y., Gurfil, P., Hadar, E.: On the behavior of subgradient projections methods for convex feasibility problems in Euclidean spaces. SIAM J. Optim. 19, 786-807 (2008) · Zbl 1161.49033 · doi:10.1137/070689127 |
| [13] | Kiwiel, K.C.: The efficiency of subgradient projection. SIAM J. Control Optim. 34, 677-697 (1996) · Zbl 0846.90085 · doi:10.1137/S0363012994261483 |
| [14] | Kiwiel, K.C.: The efficiency of subgradient projection methods for convex optimization I: General level methods. SIAM J. Control Optim. 34, 660-676 (1996) · Zbl 0846.90084 · doi:10.1137/0334031 |
| [15] | dos Santos, L.T.: A parallel subgradient method for the convex feasibility problem. J. Comput. Appl. Math. 18, 307-320 (1987) · Zbl 0623.90076 · doi:10.1016/0377-0427(87)90004-5 |
| [16] | Li, C., Mordukhovich, B.S., Wang, J.H., Yao, J.C.: Weak sharp minima on Riemannian manifolds. SIAM J. Optim. 21(4), 1523-1560 (2011) · Zbl 1236.49089 · doi:10.1137/09075367X |
| [17] | Rapcsák, T.: Smooth Nonlinear Optimization in \[{\mathbb{R}}^nRn\]. Nonconvex Optimization and its Applications, vol. 19. Kluwer, Dordrecht (1997) · Zbl 1009.90109 · doi:10.1007/978-1-4615-6357-0 |
| [18] | Adler, R., Dedieu, J.P., Margulies, J., 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) · Zbl 1056.92002 · doi:10.1093/imanum/22.3.359 |
| [19] | Burke, J.V., Lewis, A., Overton, M.: Optimal stability and eigenvalue multiplicity. Found. Comput. Math. 1, 205-225 (2001) · Zbl 0994.15022 · doi:10.1007/PL00021726 |
| [20] | Ferreira, O.P., Pérez, L.R.L., Nemeth, S.Z.: Singularities of monotone vector fields and an extragradient-type algorithm. J. Glob. Optim. 31(1), 133-151 (2005) · Zbl 1229.58007 · doi:10.1007/s10898-003-3780-y |
| [21] | Greene, R., Wu, H.: On the subharmonicity and plurisubharmonicity of geodesically convex functions. Indiana Univ. Math. J. 22, 641-653 (1972) · Zbl 0235.53039 · doi:10.1512/iumj.1973.22.22052 |
| [22] | Mahony, R.E.: The constrained Newton method on a Lie group and the symmetric eigenvalue problem. Linear Algebr. Appl. 248, 67-89 (1996) · Zbl 0864.65032 · doi:10.1016/0024-3795(95)00171-9 |
| [23] | Miller, S.A., Malick, J.: Newton methods for nonsmooth convex minimization: connections among U-Lagrangian, Riemannian Newton and SQP methods. Math. Program. 104, 609-633 (2005) · Zbl 1124.90021 · doi:10.1007/s10107-005-0631-2 |
| [24] | Smith, S.T.: Geometric Optimization Methods for Adaptive Filtering. Division of Applied Sciences. PhD Thesis, Harvard University, Cambridge, MA (1993) · Zbl 0846.90084 |
| [25] | Udriste, C.: Convex Functions and Optimization Methods on Riemannian Manifolds. Mathematics and Its Applications, vol. 297. Kluwer, Dordrecht (1994) · Zbl 0932.53003 · doi:10.1007/978-94-015-8390-9 |
| [26] | Absil, P.A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7(3), 303-330 (2007) · Zbl 1129.65045 · doi:10.1007/s10208-005-0179-9 |
| [27] | Bridson, M., Haefliger, A.: Metric Spaces of Non-positive Curvature. Springer, Berlin (1999) · Zbl 0988.53001 · doi:10.1007/978-3-662-12494-9 |
| [28] | Ferreira, O.P., Oliveira, P.R.: Subgradient algorithm on Riemannian manifolds. J. Optim. Theory Appl. 97(1), 93-104 (1998) · Zbl 0907.90244 · doi:10.1023/A:1022675100677 |
| [29] | Ferreira, O.P., Oliveira, P.R.: Proximal point algorithm on Riemannian Manifold. Optimization 51(2), 257-270 (2002) · Zbl 1013.49024 · doi:10.1080/02331930290019413 |
| [30] | Gabay, D.: Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl. 37(2), 177-219 (1982) · Zbl 0458.90060 · doi:10.1007/BF00934767 |
| [31] | 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, 663-683 (2009) · Zbl 1171.58001 · doi:10.1112/jlms/jdn087 |
| [32] | Li, C., Wang, J.H.: Newton’s method for sections on Riemannian manifolds: generalized covariant \[\alpha\] α-theory. J. Complex. 24, 423-451 (2008) · Zbl 1153.65059 · doi:10.1016/j.jco.2007.12.003 |
| [33] | Li, C., Yao, J.C.: Variational inequalities for set-valued vector fields on Riemannian manifolds: convexity of the solution set and the proximal point algorithm. SIAM J. Control Optim. 50(4), 2486-2514 (2012) · Zbl 1257.49011 · doi:10.1137/110834962 |
| [34] | Luenberger, D.G.: The gradient projection method along geodesics. Manag. Sci. 18, 620-631 (1972) · Zbl 0253.90050 · doi:10.1287/mnsc.18.11.620 |
| [35] | Wang, J.H., Huang, S.C., Li, C.: Extended Newton’s algorithm for mappings on Riemannian manifolds with values in a cone. Taiwan J. Math. 13, 633-656 (2009) · Zbl 1182.65084 |
| [36] | Wang, J.H., López, G., Martín-Márquez, V., Li, C.: Monotone and accretive vector fields on Riemannian manifolds. J. Optim. Theory Appl. 146, 691-708 (2010) · Zbl 1208.53049 · doi:10.1007/s10957-010-9688-z |
| [37] | Yang, Y.: Globally convergent optimization algorithms on Riemannian manifolds: uniform framework for unconstrained and constrained optimization. J. Optim. Theory Appl. 132(2), 245-265 (2007) · Zbl 1153.90017 · doi:10.1007/s10957-006-9081-0 |
| [38] | Bento, G.C., Melo, J.G.: Subgradient algorithm for convex feasibility on Riemannian manifolds. J. Optim. Theory Appl. 152(3), 773-785 (2012) · Zbl 1270.90101 · doi:10.1007/s10957-011-9921-4 |
| [39] | da Cruz Neto, J.X., de Lima, L., Oliverira, P.R.: Geodesic algorithms in Riemannian geometry. Balkan J. Geom. Appl. 3, 89-100 (1998) · Zbl 1033.58018 |
| [40] | Sakai, T.: Riemannian Geometry. Translations of Mathematical Monographs, vol. 149. American Mathematical Society, Providence (1996) · Zbl 0886.53002 |
| [41] | do Carmo, M.P.: Riemannian Geometry. Birkhauser, Boston (1992) · Zbl 0752.53001 · doi:10.1007/978-1-4757-2201-7 |
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.
