Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds. (English) Zbl 1326.65072
Summary: We study the convergence issue of the subgradient algorithm for solving the convex feasibility problems in Riemannian manifolds, which was first proposed and analyzed by G. C. Bento and J. G. Melo [J. Optim. Theory Appl. 152, No. 3, 773–785 (2012; Zbl 1270.90101)]. The linear convergence property about the subgradient algorithm for solving the convex feasibility problems with the Slater condition in Riemannian manifolds are established, and some step sizes rules are suggested for finite convergence purposes, which are motivated by the work due to A. R. De Pierro and A. N. Iusem [Appl. Math. Optim. 17, No. 3, 225–235 (1988; Zbl 0655.65085)]. As a by-product, the convergence result of this algorithm is obtained for the convex feasibility problem without the Slater condition assumption. These results extend and/or improve the corresponding known ones in both the Euclidean space and Riemannian manifolds.
MSC:
| 65K05 | Numerical mathematical programming methods |
Keywords:
convex feasibility problem; subgradient projection algorithm; Riemannian manifold; sectional curvature; linear convergence; finite terminationReferences:
| [1] | P. A. Absil, R. Mahony, and R. Sepulchre, {\it Optimization Algorithms on Matrix Manifolds}, Princeton University Press, Princeton, NJ, 2008. · Zbl 1147.65043 |
| [2] | R. Adler, J. P. Dedieu, J. Margulies, M. Martens, and M. Shub, {\it Newton’s method on Riemannian manifolds and a geometric model for the human spine}, IMA J. Numer. Anal., 22 (2002), pp. 359-390. · Zbl 1056.92002 |
| [3] | B. Afsari, R. Tron, and R. Vidal, {\it On the convergence of gradient descent for finding the Riemannian center of mass}, SIAM J. Control Optim., 51 (2013), pp. 2230-2260. · Zbl 1285.90031 |
| [4] | D. Azagra, J. Ferrera, and F. López-Mesas, {\it A maximum principle for evolution Hamilton-Jacobi equations on Riemannian manifolds}, J. Math. Anal. Appl., 323 (2005), pp. 473-480. · Zbl 1108.58015 |
| [5] | H. H. Bauschke and J. M. Borwein, {\it On the convergence of von Neumann’s alternating projection algorithm for two sets}, Set-Valued Anal., 1 (1993), pp. 185-212. · Zbl 0801.47042 |
| [6] | H. H. Bauschke and J. M. Borwein, {\it On projection algorithms for solving convex feasibility problems}, SIAM Rev., 38 (1996), pp. 367-426. · Zbl 0865.47039 |
| [7] | M. Bačák, I. Searston, and B. Sims, {\it Alternating projections in CAT(0) spaces}, J. Math. Anal. Appl., 385 (2012), pp. 599-607. · Zbl 1232.47047 |
| [8] | G. C. Bento and J. G. Melo, {\it Subgradient algorithm for convex feasibility on Riemannian manifolds}, J. Optim. Theory Appl., 152 (2012), pp. 773-785. · Zbl 1270.90101 |
| [9] | J. M. Borwein, G. Li, and L. Yao, {\it Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebratic convex sets}, SIAM J. Optim., 24 (2014), pp. 498-527. · Zbl 1296.41011 |
| [10] | M. Bridson and A. Haefliger, {\it Metric Spaces of Non-Positive Curvature}, Springer-Verlag, Berlin, 1999. · Zbl 0988.53001 |
| [11] | J. V. Burke, A. Lewis, and M. Overton, {\it Optimal stability and eigenvalue multiplicity}, Found. Comput. Math., 1 (2001), pp. 205-225. · Zbl 0994.15022 |
| [12] | Y. Censor, {\it Mathematical Optimization for the Inverse Problem of Intensity-Modulated Radiation Therapy}, Medical Physics Publishing, Madison, WI, 2003. |
| [13] | Y. Censor, M. D. Altschuler, and W. D. Powlis, {\it On the use of Cimmino’s simultaneous projections method for computing a solution of the inverse problem in radiation-therapy treatment planning}, Inverse Problems, 4 (1988), pp. 607-623. · Zbl 0653.65049 |
| [14] | Y. Censor and A. Lent, {\it Cyclic subgradient projections}, Math. Program., 24 (1982), pp. 233-235. · Zbl 0491.90077 |
| [15] | Y. Censor and S. A. Zenios, {\it Parallel Optimization: Theory, Algorithms, and Applications}, Oxford University Press, New York, 1997. · Zbl 0945.90064 |
| [16] | J. Cheeger and D. Gromoll, {\it On the structure of complete manifolds of nonnegative curvature}, Ann. of Math., 96 (1972), pp. 413-443. · Zbl 0246.53049 |
| [17] | P. L. Combettes, {\it The foundations of set theoretic estimation}, Proc. IEEE, 81 (1993), pp. 182-208. |
| [18] | P. L. Combettes, {\it The convex feasibility problem in image recovery}, Adv. Imaging Electron Phys., 95 (1996), pp. 155-270. |
| [19] | P. L. Combettes, {\it Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections}, IEEE Trans. Image Process., 6 (1997), pp. 493-506. |
| [20] | M. P. DoCarmo, {\it Riemannian Geometry}, Birkhäuser Boston, Boston, MA, 1992. |
| [21] | A. R. De Pierro and A. N. Iusem, {\it A finite convergent “row-action” method for the convex feasibility problem}, Appl. Math. Optim., 17 (1988), pp. 225-235. · Zbl 0655.65085 |
| [22] | A. Edelman, T. Arias, and S. Smith, {\it The geometry of algorithms with orthogonality constraints}, SIAM J. Matrix Anal. Appl., 20 (1998), pp. 303-353. · Zbl 0928.65050 |
| [23] | O. P. Ferreira, L. R. lucambio Pérez, and S. Z. Németh, {\it Singularities of monotone vector fields and an extragradient-type algorithm}, J. Global Optim., 31 (2005), pp. 133-151. · Zbl 1229.58007 |
| [24] | O. P. Ferreira and P. R. Oliveira, {\it Proximal point algorithm on Riemannian manifold}, Optimization, 51 (2002), pp. 257-270. · Zbl 1013.49024 |
| [25] | R. E. Greene and H. Wu, {\it On the subharmonicity and plurisubharmonicity of geodesically convex functions}, Indiana Univ. Math. J., 22 (1973), pp. 641-653. · Zbl 0235.53039 |
| [26] | D. Groisser, {\it Newton’s method, zeros of vector fields, and the Riemannian center of mass}, Adv. Appl. Math., 33 (2004), pp. 95-135. · Zbl 1062.53025 |
| [27] | G. T. Herman, {\it Image Reconstruction from Projections: The Fundamentals of Computerized Tomography}, Academic Press, New York, 1980. · Zbl 0538.92005 |
| [28] | A. Kristály, {\it Location of Nash equilibria: A Riemannian geometrical approach}, Proc. Amer. Math. Soc., 138 (2010), pp. 1803-1810. · Zbl 1189.91018 |
| [29] | Y. S. Ledyaev and Q. J. Zhu, {\it Nonsmooth analysis on smooth manifolds}, Trans. Amer. Math. Soc., 359 (2007), pp. 3687-3732. · Zbl 1157.49021 |
| [30] | A. S. Lewis and J. Malick, {\it Alternating projections on manifolds}, Math. Oper. Res., 33 (2008), pp. 216-234. · Zbl 1163.65040 |
| [31] | C. Li, G. López, and V. Martín-Márquez, {\it Monotone vector fields and the proximal point algorithm on Hadamard manifolds}, J. Lond. Math. Soc., 79 (2009), pp. 663-683. · Zbl 1171.58001 |
| [32] | C. Li, G. López, V. Martín-Márquez, and J. H. Wang, {\it Resolvents of set-valued monotone vector fields in Hadamard manifolds}, Set-Valued Var. Anal., 19 (2011), pp. 361-383. · Zbl 1239.47043 |
| [33] | C. Li, B. S. Mordukhovich, J. Wang, and J. C. Yao, {\it Weak sharp minima on Riemannian manifolds}, SIAM J. Optim., 21 (2011), pp. 1523-1560. · Zbl 1236.49089 |
| [34] | C. Li and J. H. Wang, {\it Newton’s method for sections on Riemannian manifolds: Generalized covariant \(α\)-theory}, J. Complex., 24 (2008), pp. 423-451. · Zbl 1153.65059 |
| [35] | C. Li and J. C. Yao, {\it 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 (2012), pp. 2486-2514. · Zbl 1257.49011 |
| [36] | S. L. Li, C. Li, Y. C. Liou, and J. C. Yao, {\it Existence of solutions for variational inequalities on Riemannian manifolds}, Nonlinear Anal., 71 (2009), pp. 5695-5706. · Zbl 1180.58012 |
| [37] | R. E. Mahony, {\it The constrained Newton method on Lie group and the symmetric eigenvalue problem}, Linear Algebra Appl., 248 (1996), pp. 67-89. · Zbl 0864.65032 |
| [38] | L. D. Marks, W. Sinkler, and E. Landree, {\it A feasible set approach to the crystallographic phase problem}, Acta Crystallogr., 55 (1999), pp. 601-612. |
| [39] | M. McAsey and L. Mou, {\it A proof of a general maximum principle for optimal controls via a multiplier rule on metric space}, J. Math. Anal. Appl., 337 (2008), pp. 1072-1088. · Zbl 1140.49017 |
| [40] | B. S. Mordukhovich and L. Mou, {\it Necessary conditions for nonsmooth optimization problems with operator constraints in metric spaces}, J. Convex Anal., 16 (2009), pp. 913-937. · Zbl 1182.49014 |
| [41] | S. Z. Németh, {\it Geodesic monotone vector fields}, Lobachevskii J. Math., 5 (1999), pp. 13-28. · Zbl 0970.53021 |
| [42] | S. Z. Németh, {\it Monotone vector fields}, Publ. Math. Debrecen, 54 (1999), pp. 437-449. · Zbl 0963.47036 |
| [43] | T. Rapcsák, {\it Smooth Nonlinear Optimization in \(\mathbb{R}^n\)}, Kluwer Academic Publishers, Dordrecht, the Netherlands, 1997. · Zbl 1009.90109 |
| [44] | T. Sakai, {\it Riemannian Geometry}, Transl. Math. Monogr., AMS, Providence, 1996. · Zbl 0886.53002 |
| [45] | C. Udriste, {\it Convex Functions and Optimization Methods on Riemannian Manifolds}, Math. Appl., Springer, New York, 1994. · Zbl 0932.53003 |
| [46] | R. Walter, {\it On the metric projection onto convex sets in Riemannian spaces}, Arch. Math., 25 (1974), pp. 91-98. · Zbl 0311.53054 |
| [47] | J. H. Wang, G. López, V. Martín-Márquez, and C. Li, {\it Monotone and accretive vector fields on Riemannian manifolds}, J. Optim. Theory Appl., 146 (2010), pp. 691-708. · Zbl 1208.53049 |
| [48] | X. M. Wang, C. Li, and J. C. Yao, {\it Subgradient projection algorithms for convex feasibility on Riemannian manifolds with lower bounded curvatures}, J. Optim. Theory Appl., 164 (2015), pp. 202-217. · Zbl 1308.90131 |
| [49] | S. T. Yau, {\it Non-existence of continuous convex functions on certain Riemannian manifolds}, Math. Ann., 207 (1974), pp. 269-270. · Zbl 0261.53036 |
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.
