Nonconvex weak sharp minima on Riemannian manifolds. (English) Zbl 1426.49014
Summary: We establish some necessary conditions (of the primal and dual types) for the set of weak sharp minima of a nonconvex optimization problem on a Riemannian manifold. Here, we provide a generalization of some characterizations of weak sharp minima for convex problems on Riemannian manifold introduced by C. Li et al. [SIAM J. Optim. 21, No. 4, 1523–1560 (2011; Zbl 1236.49089)] for nonconvex problems. We use the theory of the Fréchet and limiting subdifferentials on Riemannian manifold to give some necessary conditions of the dual type. We also consider a theory of contingent directional derivative and a notion of contingent cone on Riemannian manifold to give some necessary conditions of the primal type. Several definitions have been provided for the contingent cone on Riemannian manifold. We show that these definitions, under some modifications, are equivalent. We establish a lemma about the local behavior of a distance function. We use this lemma to establish some necessary conditions by expressing the Fréchet subdifferential (contingent directional derivative) of a distance function on a Riemannian manifold in terms of normal cones (contingent cones). As an application, we show how one can use weak sharp minima property to model a Cheeger-type constant of a graph as an optimization problem on a Stiefel manifold.
MSC:
| 49J50 | Fréchet and Gateaux differentiability in optimization |
| 90C26 | Nonconvex programming, global optimization |
| 05C40 | Connectivity |
| 58C20 | Differentiation theory (Gateaux, Fréchet, etc.) on manifolds |
Keywords:
weak sharp minima; Riemannian manifolds; distance functions; nonconvex functions; generalized differentiation; graph clusteringCitations:
Zbl 1236.49089References:
| [1] | Udrişte, C.: Convex Functions and Optimization Methods on Riemannian Manifolds, Mathematics and Its Applications, vol. 297. Kluwer Academic Publishers Group, Dordrecht (1994) · Zbl 0932.53003 |
| [2] | 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 |
| [3] | Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2007) · Zbl 1147.65043 |
| [4] | Smith, ST; Bloch, A. (ed.), Optimization techniques on Riemannian manifolds, No. 3, 113-136 (1994), Providence · Zbl 0816.49032 |
| [5] | Grohs, P., Hosseini, S.: Nonsmooth trust region algorithms for locally Lipschitz functions on Riemannian manifolds. IMA J. Numer. Anal. 36(3), 1167-1192 (2016) · Zbl 1433.90124 |
| [6] | Hosseini, R., Sra, S.: An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization. Math. Program. (2019). https://doi.org/10.1007/s10107-019-01381-4 · Zbl 1441.62168 · doi:10.1007/s10107-019-01381-4 |
| [7] | Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2), 303-353 (1999) · Zbl 0928.65050 |
| [8] | Dong, X., Frossard, P., Vandergheynst, P., Nefedov, N.: Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds. IEEE Trans. Signal Process. 62(4), 905-918 (2014) · Zbl 1394.94973 |
| [9] | Journée, M., Bach, F., Absil, P.A., Sepulchre, R.: Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim. 20(5), 2327-2351 (2010) · Zbl 1215.65108 |
| [10] | Shalit, U., Weinshall, D., Chechik, G.: Online learning in the embedded manifold of low-rank matrices. J. Mach. Learn. Res. 13, 429-458 (2012) · Zbl 1283.68302 |
| [11] | Sun, J., Qu, Q., Wright, J.: Complete dictionary recovery over the sphere II: recovery by Riemannian trust-region method. IEEE Trans. Inf. Theory 63(2), 885-914 (2017) · Zbl 1364.94165 |
| [12] | Vandereycken, B.: Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2), 1214-1236 (2013) · Zbl 1277.15021 |
| [13] | Adler, R.L., Dedieu, J.P., Margulies, J.Y., Martens, M., Shub, M.: Newton’s method on Riemannian manifolds and a geometric model for the human spine. IMA J. Numer. Anal. 22(3), 359-390 (2002) · Zbl 1056.92002 |
| [14] | Ishteva, M., Absil, P.A., Van Huffel, S., De Lathauwer, L.: Best low multilinear rank approximation of higher-order tensors, based on the Riemannian trust-region scheme. SIAM J. Matrix Anal. Appl. 32(1), 115-135 (2011) · Zbl 1218.65041 |
| [15] | Mishra, B., Meyer, G., Bach, F., Sepulchre, R.: Low-rank optimization with trace norm penalty. SIAM J. Optim. 23(4), 2124-2149 (2013) · Zbl 1286.65078 |
| [16] | Bento, G.C., Ferreira, O.P., Oliveira, P.R.: Proximal point method for a special class of nonconvex functions on Hadamard manifolds. Optimization 64(2), 289-319 (2015) · Zbl 1310.49006 |
| [17] | Hosseini, S., Uschmajew, A.: A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim. 27(1), 173-189 (2017) · Zbl 1357.49062 |
| [18] | Burke, J.V., Ferris, M.C., Qian, M.: On the Clarke subdifferential of the distance function of a closed set. J. Math. Anal. Appl. 166(1), 199-213 (1992) · Zbl 0761.49009 |
| [19] | Mordukhovich, B.S., Nam, N.M.: Subgradient of distance functions with applications to Lipschitzian stability. Math. Program. 104(2-3, Ser. B), 635-668 (2005) · Zbl 1077.49019 |
| [20] | Li, C., Mordukhovich, B.S., Wang, J., Yao, J.C.: Weak sharp minima on Riemannian manifolds. SIAM J. Optim. 21(4), 1523-1560 (2011) · Zbl 1236.49089 |
| [21] | Polyak, B.T.: Sharp minima, institute of control sciences lecture notes, Moscow, USSR, 1979; Presented at the IIASA Workshop on Generalized Lagrangians and Their Applications. IIASA, Laxenburg, Austria (1979) |
| [22] | Ferris, M.C.: Weak sharp minima and penalty functions in mathematical programming. Ph.D. thesis, University of Cambridge, Cambridge (1988) |
| [23] | Burke, J.V., Deng, S.: Weak sharp minima revisited. II. Application to linear regularity and error bounds. Math. Program. 104(2-3, Ser. B), 235-261 (2005) · Zbl 1124.90349 |
| [24] | Burke, J.V., Ferris, M.C.: Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31(5), 1340-1359 (1993) · Zbl 0791.90040 |
| [25] | Mordukhovich, B.S., Nam, N.M., Yen, N.D.: Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming. Optimization 55(5-6), 685-708 (2006) · Zbl 1121.49017 |
| [26] | Ng, K.F., Zheng, X.Y.: Global weak sharp minima on Banach spaces. SIAM J. Control Optim. 41(6), 1868-1885 (2003) · Zbl 1045.90067 |
| [27] | Studniarski, M., Ward, D.E.: Weak sharp minima: characterizations and sufficient conditions. SIAM J. Control Optim. 38(1), 219-236 (1999) · Zbl 0946.49011 |
| [28] | Ward, D.E.: Characterizations of strict local minima and necessary conditions for weak sharp minima. J. Optim. Theory Appl. 80(3), 551-571 (1994) · Zbl 0797.90101 |
| [29] | Zhou, J., Mordukhovich, B.S., Xiu, N.: Complete characterizations of local weak sharp minima with applications to semi-infinite optimization and complementarity. Nonlinear Anal. 75(3), 1700-1718 (2012) · Zbl 1236.49038 |
| [30] | Hosseini, S., Pouryayevali, M.R.: On the metric projection onto prox-regular subsets of Riemannian manifolds. Proc. Am. Math. Soc. 141(1), 233-244 (2013) · Zbl 1277.58005 |
| [31] | Ledyaev, Y.S., Zhu, Q.J.: Nonsmooth analysis on smooth manifolds. Trans. Am. Math. Soc. 359(8), 3687-3732 (2007) · Zbl 1157.49021 |
| [32] | Penot, J.P.: Calculus Without Derivatives, Graduate Texts in Mathematics, vol. 266. Springer, New York (2013) · Zbl 1264.49014 |
| [33] | Azagra, D., Ferrera, J., López-Mesas, F.: Nonsmooth analysis and Hamilton-Jacobi equations on Riemannian manifolds. J. Funct. Anal. 220(2), 304-361 (2005) · Zbl 1067.49010 |
| [34] | Motreanu, D., Pavel, N.: Quasi-tangent vectors in flow-invariance and optimization problems on Banach manifolds. J. Math. Anal. Appl. 88(1), 116-132 (1982) · Zbl 0504.58037 |
| [35] | Grigor’yan, A.: Heat Kernel and Analysis on Manifolds, AMS/IP Studies in Advanced Mathematics, vol. 47. American Mathematical Society, Providence (2009) · Zbl 1206.58008 |
| [36] | Lang, S.: Differential and Riemannian Manifolds, Graduate Texts in Mathematics, vol. 160, 3rd edn. Springer, New York (1995) · Zbl 0824.58003 |
| [37] | Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 330. Springer, Berlin (2006) |
| [38] | Németh, S.Z.: Variational inequalities on Hadamard manifolds. Nonlinear Anal. 52(5), 1491-1498 (2003) · Zbl 1016.49012 |
| [39] | Kristály, A.: Nash-type equilibria on Riemannian manifolds: a variational approach. J. Math. Pures Appl. (9) 101(5), 660-688 (2014) · Zbl 1302.91010 |
| [40] | Daneshgar, A., Hajiabolhassan, H., Javadi, R.: On the isoperimetric spectrum of graphs and its approximations. J. Comb. Theory Ser. B 100(4), 390-412 (2010) · Zbl 1203.05063 |
| [41] | Tudisco, F., Hein, M.: A nodal domain theorem and a higher-order Cheeger inequality for the graph \[p\] p-Laplacian. J. Spectr. Theory 8(3), 883-908 (2018) · Zbl 1491.05126 |
| [42] | von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395-416 (2007) |
| [43] | Rothaus, O.S.: Analytic inequalities, isoperimetric inequalities and logarithmic Sobolev inequalities. J. Funct. Anal. 64(2), 296-313 (1985) · Zbl 0578.46028 |
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.
