Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (2): 199-248.doi: 10.1007/s40305-020-00295-9
收稿日期:2019-06-12
修回日期:2019-12-10
出版日期:2020-06-30
发布日期:2020-07-07
通讯作者:
Zai-Wen Wen, Jiang Hu, Xin Liu, Ya-Xiang Yuan
E-mail:wenzw@pku.edu.cn;jianghu@pku.edu.cn;liuxin@lsec.cc.ac.cn;yyx@lsec.cc.ac.cn
Jiang Hu1, Xin Liu2,3, Zai-Wen Wen1, Ya-Xiang Yuan2
Received:2019-06-12
Revised:2019-12-10
Online:2020-06-30
Published:2020-07-07
Contact:
Zai-Wen Wen, Jiang Hu, Xin Liu, Ya-Xiang Yuan
E-mail:wenzw@pku.edu.cn;jianghu@pku.edu.cn;liuxin@lsec.cc.ac.cn;yyx@lsec.cc.ac.cn
Supported by:中图分类号:
. [J]. Journal of the Operations Research Society of China, 2020, 8(2): 199-248.
Jiang Hu, Xin Liu, Zai-Wen Wen, Ya-Xiang Yuan. A Brief Introduction to Manifold Optimization[J]. Journal of the Operations Research Society of China, 2020, 8(2): 199-248.
| [1] Lai, R., Wen, Z., Yin, W., Gu, X., Lui, L.M.: Folding-free global conformal mapping for genus-0 surfaces by harmonic energy minimization. J. Sci. Comput. 58, 705-725(2014) [2] Schoen, R.M., Yau, S.-T.: Lectures on Harmonic Maps, vol. 2. American Mathematical Society, Providence (1997) [3] Simon, D., Abell, J.: A majorization algorithm for constrained correlation matrix approximation. Linear Algebra Appl. 432, 1152-1164(2010) [4] Gao, Y., Sun, D.: A majorized penalty approach for calibrating rank constrained correlation matrix problems, tech. report, National University of Singapore (2010) [5] Waldspurger, I., d'Aspremont, A., Mallat, S.: Phase recovery, maxcut and complex semidefinite programming. Math. Program. 149, 47-81(2015) [6] Cai, J.-F., Liu, H., Wang, Y.: Fast rank-one alternating minimization algorithm for phase retrieval. J. Sci. Comput. 79, 128-147(2019) [7] Hu, J., Jiang, B., Liu, X., Wen, Z.: A note on semidefinite programming relaxations for polynomial optimization over a single sphere. Sci. China Math. 59, 1543-1560(2016) [8] Singer, A., Shkolnisky, Y.: Three-dimensional structure determination from common lines in cryoem by eigenvectors and semidefinite programming. SIAM J. Imaging Sci. 4, 543-572(2011) [9] Liu, X., Wen, Z., Zhang, Y.: An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations. SIAM J. Optim. 25, 1571-1608(2015) [10] Liu, X., Wen, Z., Zhang, Y.: Limited memory block Krylov subspace optimization for computing dominant singular value decompositions. SIAM J. Sci. Comput. 35, A1641-A1668(2013) [11] Wen, Z., Yang, C., Liu, X., Zhang, Y.: Trace-penalty minimization for large-scale eigenspace computation. J. Sci. Comput. 66, 1175-1203(2016) [12] Wen, Z., Zhang, Y.: Accelerating convergence by augmented Rayleigh-Ritz projections for largescale eigenpair computation. SIAM J. Matrix Anal. Appl. 38, 273-296(2017) [13] Zhang, J., Wen, Z., Zhang, Y.: Subspace methods with local refinements for eigenvalue computation using low-rank tensor-train format. J. Sci. Comput. 70, 478-499(2017) [14] Oja, E., Karhunen, J.: On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. J. Math. Anal. Appl. 106, 69-84(1985) [15] Shamir, O.: A stochastic PCA and SVD algorithm with an exponential convergence rate. Int. Conf. Mach. Learn. 144-152(2015) [16] Li, C.J., Wang, M., Liu, H., Zhang, T.: Near-optimal stochastic approximation for online principal component estimation. Math. Program. 167, 75-97(2018) [17] Pulay, P.: Convergence acceleration of iterative sequences. The case of SCF iteration. Chem. Phys. Lett. 73, 393-398(1980) [18] Pulay, P.: Improved SCF convergence acceleration. J. Comput. Chem. 3, 556-560(1982) [19] Toth, A., Ellis, J.A., Evans, T., Hamilton, S., Kelley, C., Pawlowski, R., Slattery, S.: Local improvement results for Anderson acceleration with inaccurate function evaluations. SIAM J. Sci. Comput. 39, S47-S65(2017) [20] Zhang, X., Zhu, J., Wen, Z., Zhou, A.: Gradient type optimization methods for electronic structure calculations. SIAM J. Sci. Comput. 36, C265-C289(2014) [21] Wen, Z., Milzarek, A., Ulbrich, M., Zhang, H.: Adaptive regularized self-consistent field iteration with exact Hessian for electronic structure calculation. SIAM J. Sci. Comput. 35, A1299-A1324(2013) [22] Dai, X., Liu, Z., Zhang, L., Zhou, A.: A conjugate gradient method for electronic structure calculations. SIAM J. Sci. Comput. 39, A2702-A2740(2017) [23] Zhao, Z., Bai, Z.-J., Jin, X.-Q.: A Riemannian Newton algorithm for nonlinear eigenvalue problems. SIAM J. Matrix Anal. Appl. 36, 752-774(2015) [24] Zhang, L., Li, R.: Maximization of the sum of the trace ratio on the Stiefel manifold, Ⅱ: computation. Sci. China Math. 58, 1549-1566(2015) [25] Gao, B., Liu, X., Chen, X., Yuan, Y.: A new first-order algorithmic framework for optimization problems with orthogonality constraints. SIAM J. Optim. 28, 302-332(2018) [26] Lai, R., Lu, J.: Localized density matrix minimization and linear-scaling algorithms. J. Comput. Phys. 315, 194-210(2016) [27] Ulbrich, M., Wen, Z., Yang, C., Klockner, D., Lu, Z.: A proximal gradient method for ensemble density functional theory. SIAM J. Sci. Comput. 37, A1975-A2002(2015) [28] Jiang, B., Liu, Y.-F., Wen, Z.: L_p-norm regularization algorithms for optimization over permutation matrices. SIAM J. Optim. 26, 2284-2313(2016) [29] Zhang, J., Liu, H., Wen, Z., Zhang, S.: A sparse completely positive relaxation of the modularity maximization for community detection. SIAM J. Sci. Comput. 40, A3091-A3120(2018) [30] Cho, M., Lee, J.: Riemannian approach to batch normalization. Adv. Neural Inf. Process. Syst. 5225-5235(2017). https://papers.nips.cc/paper/7107-riemannian-approach-to-batch-normalization.pdf [31] Jolliffe, I.T., Trendafilov, N.T., Uddin, M.: A modified principal component technique based on the lasso. J. Comput. Graph. Stat. 12, 531-547(2003) [32] Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Program. Comput. 4, 333-361(2012) [33] Vandereycken, B.: Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23, 1214-1236(2013) [34] Wei, K., Cai, J.-F., Chan, T.F., Leung, S.: Guarantees of Riemannian optimization for low rank matrix recovery. SIAM J. Matrix Anal. Appl. 37, 1198-1222(2016) [35] Cambier, L., Absil, P.-A.: Robust low-rank matrix completion by Riemannian optimization. SIAM J. Sci. Comput. 38, S440-S460(2016) [36] Zhang, Y., Lau, Y., Kuo, H.-w., Cheung, S., Pasupathy, A., Wright, J.: On the global geometry of sphere-constrained sparse blind deconvolution. Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit. 4894-4902(2017) [37] Zass, R., Shashua, A.: Nonnegative sparse PCA. Adv. Neural Inf. Process. Syst. 1561-1568(2007). https://papers.nips.cc/paper/3104-nonnegative-sparse-pca [38] Montanari, A., Richard, E.: Non-negative principal component analysis: message passing algorithms and sharp asymptotics. IEEE Trans. Inf. Theory 62, 1458-1484(2016) [39] Carson, T., Mixon, D.G., Villar, S.: Manifold optimization for K-means clustering. Int. Conf. Sampl. Theory. Appl. SampTA 73-77. IEEE (2017) [40] Liu, H., Cai, J.-F., Wang, Y.: Subspace clustering by (k, k)-sparse matrix factorization. Inverse Probl. Imaging 11, 539-551(2017) [41] Xie, T., Chen, F.: Non-convex clustering via proximal alternating linearized minimization method. Int. J. Wavelets Multiresolut. Inf. Process. 16, 1840013(2018) [42] Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton, NJ (2008) [43] Absil, P.-A., Gallivan, K.A.: Joint diagonalization on the oblique manifold for independent component analysis. Proc. IEEE Int. Conf. Acoust. Speech Signal Process 5, 945-958(2006) [44] Bhatia, R.: Positive Definite Matrices, vol. 24. Princeton University Press, Princeton (2009) [45] Journée, M., Bach, F., Absil, P.-A., Sepulchre, R.: Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim. 20, 2327-2351(2010) [46] Massart, E., Absil, P.-A.: Quotient geometry with simple geodesics for the manifold of fixed-rank positive-semidefinite matrices. SIAM J. Matrix Anal. Appl. 41, 171-198(2020) [47] Yang, W.H., Zhang, L.-H., Song, R.: Optimality conditions for the nonlinear programming problems on Riemannian manifolds. Pac. J. Optim. 10, 415-434(2014) [48] Gabay, D.: Minimizing a differentiable function over a differential manifold. J. Optim. Theory Appl. 37, 177-219(1982) [49] Smith, S.T.: Optimization techniques on Riemannian manifolds. Fields Institute Communications 3(1994) [50] Kressner, D., Steinlechner, M., Vandereycken, B.: Low-rank tensor completion by Riemannian optimization. BIT Numer. Math. 54, 447-468(2014) [51] Hu, J., Milzarek, A., Wen, Z., Yuan, Y.: Adaptive quadratically regularized Newton method for Riemannian optimization. SIAM J. Matrix Anal. Appl. 39, 1181-1207(2018) [52] Absil,P.-A.,Malick,J.:Projection-likeretractionsonmatrixmanifolds.SIAMJ.Optim. 22,135-158(2012) [53] Duchi, J., Hazan, E., Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res. 12, 2121-2159(2011) [54] Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142, 397-434(2013) [55] Jiang, B., Dai, Y.-H.: A framework of constraint preserving update schemes for optimization on Stiefel manifold. Math. Program. 153, 535-575(2015) [56] Zhu, X.: A Riemannian conjugate gradient method for optimization on the Stiefel manifold. Comput. Optim. Appl. 67, 73-110(2017) [57] Siegel, J.W.: Accelerated optimization with orthogonality constraints, arXiv:1903.05204(2019) [58] Iannazzo, B., Porcelli, M.: The Riemannian Barzilai-Borwein method with nonmonotone line search and the matrix geometric mean computation. IMA J. Numer. Anal. 00, 1-23(2017) [59] Edelman, A., Arias, T.A., Smith, S.T.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20, 303-353(1999) [60] Nishimori, Y., Akaho, S.: Learning algorithms utilizing quasi-geodesic flows on the Stiefel manifold. Neurocomputing 67, 106-135(2005) [61] Huang, W.: Optimization algorithms on Riemannian manifolds with applications, Ph.D. thesis, The Florida State University (2013) [62] Lezcano-Casado,M.,Martínez-Rubio,D.:Cheaporthogonalconstraintsinneuralnetworks:asimple parametrization of the orthogonal and unitary group, arXiv:1901.08428(2019) [63] Li, J., Fuxin, L., Todorovic, S.: Efficient Riemannian optimization on the Stiefel manifold via the Cayley transform, Conference arXiv:2002.01113(2020) [64] Huang, W., Gallivan, K.A., Absil, P.-A.: A Broyden class of quasi-Newton methods for Riemannian optimization. SIAM J. Optim. 25, 1660-1685(2015) [65] Huang, W., Absil, P.-A., Gallivan, K.A.: Intrinsic representation of tangent vectors and vector transports on matrix manifolds. Numer. Math. 136, 523-543(2017) [66] Hu, J., Milzarek, A., Wen, Z., Yuan, Y.: Adaptive regularized Newton method for Riemannian optimization, arXiv:1708.02016(2017) [67] Zhang, H., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043-1056(2004) [68] Udriste, C.: Convex Functions and Optimization Methods on Riemannian Manifolds, vol. 297. Springer, Berlin (1994) [69] Absil, P.-A., Baker, C.G., Gallivan, K.A.: Trust-region methods on Riemannian manifolds. Found. Comput. Math. 7, 303-330(2007) [70] Qi, C.: Numerical optimization methods on Riemannian manifolds, Ph.D. thesis, Florida State University (2011) [71] Ring, W., Wirth, B.: Optimization methods on Riemannian manifolds and their application to shape space. SIAM J. Optim. 22, 596-627(2012) [72] Seibert, M., Kleinsteuber, M., Hüper, K.: Properties of the BFGS method on Riemannian manifolds. Mathematical System Theory C Festschrift in Honor of Uwe Helmke on the Occasion of his Sixtieth Birthday, pp. 395-412(2013) [73] Huang, W., Absil, P.-A., Gallivan, K.A.: A Riemannian symmetric rank-one trust-region method. Math. Program. 150, 179-216(2015) [74] Huang, W., Absil, P.-A., Gallivan, K.: A Riemannian BFGS method without differentiated retraction for nonconvex optimization problems. SIAM J. Optim. 28, 470-495(2018) [75] Hu, J., Jiang, B., Lin, L., Wen, Z., Yuan, Y.-X.: Structured quasi-Newton methods for optimization with orthogonality constraints. SIAM J. Sci. Comput. 41, A2239-A2269(2019) [76] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006) [77] Wu, X., Wen, Z., Bao, W.: A regularized Newton method for computing ground states of Bose-Einstein condensates. J. Sci. Comput. 73, 303-329(2017) [78] Kass, R.E.: Nonlinear regression analysis and its applications. J. Am. Stat. Assoc. 85, 594-596(1990) [79] Sun, W., Yuan, Y.: Optimization Theory and Methods: Nonlinear Programming, vol. 1. Springer, Berlin (2006) [80] LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature 521, 436(2015) [81] Bonnabel, S.: Stochastic gradient descent on Riemannian manifolds. IEEE Trans. Autom. Control. 58, 2217-2229(2013) [82] Zhang, H., Sra, S.: First-order methods for geodesically convex optimization, In: Conference on Learning Theory, pp. 1617-1638(2016) [83] Liu, Y., Shang, F., Cheng, J., Cheng, H., Jiao, L.: Accelerated first-order methods for geodesically convex optimization on Riemannian manifolds. Adv. Neural Inf. Process. Syst. 4868-4877(2017) [84] Zhang, H., Reddi, S.J., Sra, S.: Riemannian SVRG: fast stochastic optimization on Riemannian manifolds. Adv. Neural Inf. Process. Syst. 4592-4600(2016) [85] Sato, H., Kasai, H., Mishra, B.: Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. SIAM J. Optim. 29, 1444-1472(2019) [86] Jiang, B., Ma, S., So, A.M.-C., Zhang, S.: Vector transport-free svrg with general retraction for Riemannian optimization: Complexity analysis and practical implementation, arXiv:1705.09059(2017) [87] Bécigneul, G., Ganea, O.-E.: Riemannian adaptive optimization methods, arXiv:1810.00760(2018) [88] Dirr, G., Helmke, U., Lageman, C.: Nonsmooth Riemannian optimization with applications to sphere packing and grasping. In: Lagrangian and Hamiltonian Methods for Nonlinear Control 2006, pp. 29-45. Springer, Berlin (2007) [89] Borckmans, P.B., Selvan, S.E., Boumal, N., Absil, P.-A.: A Riemannian subgradient algorithm for economic dispatch with valve-point effect. J Comput. Appl. Math. 255, 848-866(2014) [90] Hosseini, S.: Convergence of nonsmooth descent methods via Kurdyka-Lojasiewicz inequality on Riemannian manifolds, Hausdorff Center for Mathematics and Institute for Numerical Simulation, University of Bonn (2015). https://ins.uni-bonn.de/media/public/publication-media/8_INS1523.pdf [91] Grohs, P., Hosseini, S.: Nonsmooth trust region algorithms for locally Lipschitz functions on Riemannian manifolds. IMA J. Numer. Anal. 36, 1167-1192(2015) [92] Hosseini, S., Uschmajew, A.: A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim. 27, 173-189(2017) [93] Bacák, M., Bergmann, R., Steidl, G., Weinmann, A.: A second order nonsmooth variational model for restoring manifold-valued images. SIAM J. Sci. Comput. 38, A567-A597(2016) [94] de Carvalho Bento, G., da Cruz Neto, J.X., Oliveira, P.R.: A new approach to the proximal point method:convergenceongeneralRiemannianmanifolds.JOptim.TheoryAppl. 168,743-755(2016) [95] Bento, G., Neto, J., Oliveira, P.: Convergence of inexact descent methods for nonconvex optimization on Riemannian manifolds, arXiv:1103.4828(2011) [96] Bento, G.C., Ferreira, O.P., Melo, J.G.: Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds. J Optim. Theory Appl. 173, 548-562(2017) [97] Chen, S., Ma, S., So, A.M.-C., Zhang, T.: Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM J. Optim. 30, 210-239(2019) [98] Xiao, X., Li, Y., Wen, Z., Zhang, L.: A regularized semi-smooth Newton method with projection steps for composite convex programs. J. Sci. Comput. 76, 1-26(2018) [99] Huang, W., Wei, K.: Riemannian proximal gradient methods, arXiv:1909.06065(2019) [100] Chen, S., Ma, S., Xue, L., Zou, H.: An alternating manifold proximal gradient method for sparse PCA and sparse cca, arXiv:1903.11576(2019) [101] Huang, W., Wei, K.: Extending FISTA to Riemannian optimization for sparse PCA, arXiv:1909.05485(2019) [102] Lai, R., Osher, S.: A splitting method for orthogonality constrained problems. J. Sci. Comput. 58, 431-449(2014) [103] Kovnatsky, A., Glashoff, K., Bronstein, M.M.: Madmm: a generic algorithm for non-smooth optimization on manifolds. In: Leibe, B., Matas, J., Sebe, N., Welling, M. (eds.) Computer Vision ECCV, pp. 680-696. Springer, Berlin (2016) [104] Wang, Y., Yin, W., Zeng, J.: Global convergence of admm in nonconvex nonsmooth optimization. J. Sci. Comput. 78, 29-63(2019) [105] Zhang, J., Ma, S., Zhang, S.: Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, arXiv:1710.02236(2017) [106] Birgin, E.G., Haeser, G., Ramos, A.: Augmented lagrangians with constrained subproblems and convergence to second-order stationary points. Comput. Optim. Appl. 69, 51-75(2018) [107] Liu, C., Boumal, N.: Simple algorithms for optimization on Riemannian manifolds with constraints, arXiv:1901.10000(2019) [108] Boumal, N., Absil, P.-A., Cartis, C.: Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numer. Anal. 39, 1-33(2018) [109] Zhang, J., Zhang, S.: A cubic regularized Newton's method over Riemannian manifolds, arXiv:1805.05565(2018) [110] Agarwal, N., Boumal, N., Bullins, B., Cartis, C.: Adaptive regularization with cubics on manifolds with a first-order analysis, arXiv:1806.00065(2018) [111] Vishnoi,N.K.:Geodesicconvexoptimization:differentiationonmanifolds,geodesics,andconvexity, arXiv:1806.06373(2018) [112] Liu, X., Wang, X., Wen, Z., Yuan, Y.: On the convergence of the self-consistent field iteration in Kohn-Sham density functional theory. SIAM J. Matrix Anal. Appl. 35, 546-558(2014) [113] Liu, X., Wen, Z., Wang, X., Ulbrich, M., Yuan, Y.: On the analysis of the discretized Kohn-Sham density functional theory. SIAM J. Numer. Anal. 53, 1758-1785(2015) [114] Cai, Y., Zhang, L.-H., Bai, Z., Li, R.-C.: On an eigenvector-dependent nonlinear eigenvalue problem. SIAM J. Matrix Anal. Appl. 39, 1360-1382(2018) [115] Bai, Z., Lu, D., Vandereycken, B.: Robust Rayleigh quotient minimization and nonlinear eigenvalue problems. SIAM J. Sci. Comput. 40, A3495-A3522(2018) [116] Yuan, H., Gu, X., Lai, R., Wen, Z.: Global optimization with orthogonality constraints via stochastic diffusion on manifold. J. Sci. Comput. 80, 1139-1170(2019) [117] Barvinok, A.I.: Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom. 13, 189-202(1995) [118] Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23, 339-358(1998) [119] Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329-357(2003) [120] Boumal, N., Voroninski, V., Bandeira, A.: The non-convex Burer-Monteiro approach works on smooth semidefinite programs. In: Advances in Neural Information Processing Systems, pp. 2757-2765(2016). https://papers.nips.cc/paper/6517-the-non-convex-burer-monteiro-approach-workson-smooth-semidefinite-programs.pdf [121] Mei, S., Misiakiewicz, T., Montanari, A., Oliveira, R.I.: Solving SDPs for synchronization and maxcut problems via the Grothendieck inequality, arXiv:1703.08729(2017) [122] Bandeira, A.S., Boumal, N., Voroninski, V.: On the low-rank approach for semidefinite programs arising in synchronization and community detection. Conf. Learn. Theor. 361-382(2016) [123] Burer, S., Monteiro, R.D.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 427-444(2005) [124] Boumal, N., Voroninski, V., Bandeira, A.S.: Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs, arXiv:1804.02008(2018) [125] Bandeira, A.S., Kennedy, C., Singer, A.: Approximating the little Grothendieck problem over the orthogonal and unitary groups. Math. Program. 160, 433-475(2016) |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||
