Operations Research Transactions >
2023 , Vol. 27 >Issue 4: 136 - 152
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.04.007
On the theories, algorithms, and applications of optimization with nonnegative orthogonality constraints
Received date: 2023-05-02
Online published: 2023-12-07
Optimization with nonnegative orthogonality constraints, which includes both nonnegative constraints and orthogonality constraints, has important applications in machine learning and data science. Some typical instances of optimization with nonnegative orthogonality constraints include the quadratic assignment problem, graph matching problem, orthogonal nonnegative matrix factorization problem, nonnegative principal component analysis, and K-indicator model, etc. Due to the coupling effects of nonnegative and orthogonal constraints, this type of problem has a certain combinatorial structure and is generally NP-hard. This paper mainly introduces the basic theoretical properties, algorithms, and related applications of optimization with nonnegative orthogonality constraints.
Bo JIANG . On the theories, algorithms, and applications of optimization with nonnegative orthogonality constraints[J]. Operations Research Transactions, 2023 , 27(4) : 136 -152 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.007
| 1 | Absil P-A , Mahony R , Sepulchre R . Optimization Algorithms on Matrix Manifolds[M]. Princeton: Princeton University Press, 2008. |
| 2 | Wen Z , Yin W . A feasible method for optimization with orthogonality constraints[J]. Mathematical Programming, 2013, 142 (1-2): 397- 434. |
| 3 | Huang W , Absil P-A , Gallivan K A . A Riemannian symmetric rank-one trust-region method[J]. Mathematical Programming, 2015, 150 (2): 179- 216. |
| 4 | Huang W , Gallivan K A , Absil P-A . A Broyden class of quasi-Newton methods for Riemannian optimization[J]. SIAM Journal on Optimization, 2015, 25 (3): 1660- 1685. |
| 5 | Jiang B , Dai Y H . A framework of constraint preserving update schemes for optimization on Stiefel manifold[J]. Mathematical Programming, 2015, 153 (2): 535- 575. |
| 6 | Wei H , Yang W H . A Riemannian subspace limited-memory SR1 trust region method[J]. Optimization Letters, 2016, 10 (8): 1705- 1723. |
| 7 | 高斌, 刘歆, 袁亚湘. 正交约束优化问题的一阶算法[J]. 运筹学学报, 2017, 21 (4): 57- 68. |
| 8 | Jiang B, Ma S, So A M-C, et al. Vector transport-free SVRG with general retraction for Riemannian optimization: Complexity analysis and practical implementation[J]. 2017, arXiv. 1705.09059. |
| 9 | Gao B , Liu X , Chen X , et al. A new first-order algorithmic framework for optimization problems with orthogonality constraints[J]. SIAM Journal on Optimization, 2018, 28 (1): 302- 332. |
| 10 | Hu J , Milzarek A , Wen Z , et al. Adaptive quadratically regularized Newton method for Riemannian optimization[J]. SIAM Journal on Matrix Analysis and Applications, 2018, 39 (3): 1181- 1207. |
| 11 | Gao B , Liu X , Yuan Y . Parallelizable algorithms for optimization problems with orthogonality constraints[J]. SIAM Journal on Scientific Computing, 2019, 41 (3): A1949- A1983. |
| 12 | Hu J , Jiang B , Lin L , et al. Structured quasi-Newton methods for optimization with orthogonality constraints[J]. SIAM Journal on Scientific Computing, 2019, 41 (4): A2239- A2269. |
| 13 | Liu H , So A M-C , Wu W . Quadratic optimization with orthogonality constraint: Explicit ?ojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods[J]. Mathematical Programming, 2019, 178, 215- 262. |
| 14 | Chen S , Ma S , So A M-C , et al. Proximal gradient method for nonsmooth optimization over the Stiefel manifold[J]. SIAM Journal on Optimization, 2020, 30 (1): 210- 239. |
| 15 | Hu J , Liu X , Wen Z , et al. A brief introduction to manifold optimization[J]. Journal of the Operations Research Society of China, 2020, 8, 199- 248. |
| 16 | Wang L , Gao B , Liu X . Multipliers correction methods for optimization problems over the Stiefel manifold[J]. CSIAM Transactions on Applied Mathematics, 2021, 2, 508- 531. |
| 17 | Xiao N, Liu X. Solving optimization problems over the Stiefel manifold by smooth exact penalty function[J]. 2021, arXiv. 2110.08986. |
| 18 | Wang B , Ma S , Xue L . Riemannian stochastic proximal gradient methods for nonsmooth optimization over the Stiefel manifold[J]. The Journal of Machine Learning Research, 2022, 23 (1): 4599- 4631. |
| 19 | Wang L , Liu X . Decentralized optimization over the Stiefel manifold by an approximate augmented Lagrangian function[J]. IEEE Transactions on Signal Processing, 2022, 70, 3029- 3041. |
| 20 | Wang L , Zhang L H , Li R C . Trace ratio optimization with an application to multi-view learning[J]. Mathematical Programming, 2022, 1- 35. |
| 21 | Xiao N , Liu X , Yuan Y . A class of smooth exact penalty function methods for optimization problems with orthogonality constraints[J]. Optimization Methods and Software, 2022, 37 (4): 1205- 1241. |
| 22 | Tang Y , Luo G , Yang Q . An efficient PGM-based algorithm with backtracking strategy for solving quadratic optimization problems with spherical constraint[J]. Journal of Computational and Applied Mathematics, 2023, 422, 114915. |
| 23 | Hiriart-Urruty J B , Seeger A . A variational approach to copositive matrices[J]. SIAM Review, 2010, 52 (4): 593- 629. |
| 24 | Koopmans T C , Beckmann M . Assignment problems and the location of economic activities[J]. Econometrica: Journal of the Econometric Society, 1957, 25 (1): 53- 76. |
| 25 | Zass R, Shashua A. Nonnegative sparse PCA[C]//Advances in Neural Information Processing Systems, 2007: 1561-1568. |
| 26 | Jiang B , Meng X , Wen Z , et al. An exact penalty approach for optimization with nonnegative orthogonality constraints[J]. Mathematical Programming, 2023, 198, 855- 897. |
| 27 | Ding C, Li T, Peng W, et al. Orthogonal nonnegative matrix $t$-factorizations for clustering[C]//Proceedings of the 12th ACM SIGKDD, 2006: 126-135. |
| 28 | Yang Z , Oja E . Linear and nonlinear projective nonnegative matrix factorization[J]. IEEE Transactions on Neural Networks, 2010, 21 (5): 734- 749. |
| 29 | Toli? D , Antulov-Fantulin N , Kopriva I . A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering[J]. Pattern Recognition, 2018, 82, 40- 55. |
| 30 | Rahiche A, Cheriet M. Kernel orthogonal nonnegative matrix factorization: Application to multispectral document image decomposition[C]//IEEE International Conference on Acoustics, Speech and Signal Processing, 2021: 3275-3279. |
| 31 | Rahiche A , Cheriet M . Nonlinear orthogonal NMF on the Stiefel manifold with graph-based total variation regularization[J]. IEEE Signal Processing Letters, 2022, 29, 1457- 1461. |
| 32 | Rahiche A , Cheriet M . Variational Bayesian orthogonal nonnegative matrix factorization over the Stiefel manifold[J]. IEEE Transactions on Image Processing, 2022, 31, 5543- 5558. |
| 33 | Pan J , Ng M K , Liu Y , et al. Orthogonal nonnegative tucker decomposition[J]. SIAM Journal on Scientific Computing, 2021, 43 (1): B55- B81. |
| 34 | Kuang D, Ding C, Park H. Symmetric nonnegative matrix factorization for graph clustering[C]//Proceedings of the 2012 SDM, 2012: 106-117. |
| 35 | Lin X , Guan J , Chen B , et al. Unsupervised feature selection via orthogonal basis clustering and local structure preserving[J]. IEEE Transactions on Neural Networks and Learning Systems, 2021, 33 (11): 6881- 6892. |
| 36 | Chen B , Guan J , Li Z . Unsupervised feature selection via graph regularized nonnegative CP decomposition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 45 (2): 2582- 2594. |
| 37 | Miao J , Yang T , Sun L , et al. Graph regularized locally linear embedding for unsupervised feature selection[J]. Pattern Recognition, 2022, 122, 108299. |
| 38 | Zhang X , Xiu X , Zhang C . Structured joint sparse orthogonal nonnegative matrix factorization for fault detection[J]. IEEE Transactions on Instrumentation and Measurement, 2023, 72, 1- 15. |
| 39 | Chen W S , Zeng Q , Pan B . A survey of deep nonnegative matrix factorization[J]. Neurocomputing, 2022, 491, 305- 320. |
| 40 | Chen F, Yang Y, Xu L, et al. Big-data clustering: $K$-means or $K$-indicators? [J]. 2019, arXiv. 1906.00938. |
| 41 | Boutsidis C, Drineas P, Mahoney M W. Unsupervised feature selection for the $k$-means clustering problem[C]//Advances in Neural Information Processing Systems, 2009: 153-161. |
| 42 | Wang P, Liu H, Zhou Z, So A M-C. Optimal non-convex exact recovery in stochastic block model via projected power method[C]//International Conference on Machine Learning, 2021: 10828-10838. |
| 43 | Yang W H , Zhang L H , Song R . Optimality conditions for the nonlinear programming problems on Riemannian manifolds[J]. Pacific Journal of Optimization, 2014, 10 (2): 415- 434. |
| 44 | Bergmann R , Herzog R . Intrinsic formulation of KKT conditions and constraint qualifications on smooth manifolds[J]. SIAM Journal on Optimization, 2019, 29 (4): 2423- 2444. |
| 45 | Liu C , Boumal N . Simple algorithms for optimization on Riemannian manifolds with constraints[J]. Applied Mathematics & Optimization, 2020, 82, 949- 981. |
| 46 | Luo Z Q , Pang J S , Ralph D , et al. Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints[J]. Mathematical Programming, 1996, 75 (1): 19- 76. |
| 47 | Luo Z Q , Pang J S , Ralph D . Mathematical Programs with Equilibrium Constraints[M]. Cambridge: Cambridge University Press, 1996. |
| 48 | Facchinei F , Pang J S . Finite-dimensional Variational Inequalities and Complementarity Problems[M]. Berlin: Springer, 2003. |
| 49 | Chen X , Lu Z , Pong T K . Penalty methods for a class of non-Lipschitz optimization problem[J]. SIAM Journal on Optimization, 2016, 26 (3): 1465- 1492. |
| 50 | Luo Z Q , Pang J S . Error bounds for analytic systems and their applications[J]. Mathematical Programming, 1994, 67 (1-3): 1- 28. |
| 51 | Li G , Mordukhovich B S , Pham T . New fractional error bounds for polynomial systems with applications to H?lderian stability in optimization and spectral theory of tensors[J]. Mathematical Programming, 2015, 153 (2): 333- 362. |
| 52 | Qian Y , Pan S , Xiao L . Error bound and exact penalty method for optimization problems with nonnegative orthogonal constraint[J]. IMA Journal of Numerical Analysis, 2023, drac084. |
| 53 | X. Chen, Y. He, and Z. Zhang. Tight error bounds for nonnegative orthogonality constraints and exact penalties[J]. 2022, arXiv: 2210.05164. |
| 54 | Li B , Zhou G , Cichocki A . Two efficient algorithms for approximately orthogonal nonnegative matrix factorization[J]. IEEE Signal Processing Letters, 2015, 22 (7): 843-846. |
| 55 | Wang S, Chang T H, Cui Y, et al. Clustering by orthogonal non-negative matrix factorization: a sequential non-convex penalty approach[C]//IEEE International Conference on Acoustics, Speech and Signal Processing, 2019: 5576-5580. |
| 56 | Wang S , Chang T H , Cui Y , et al. Clustering by orthogonal NMF model and non-convex penalty optimization[J]. IEEE Transactions on Signal Processing, 2021, 69, 5273- 5288. |
| 57 | Dehghanpour J , Mahdavi-Amiri N . Orthogonal nonnegative matrix factorization problems for clustering: A new formulation and a competitive algorithm[J]. Annals of Operations Research, 2022, 1- 17. |
| 58 | Zhang J , Liu H , Wen Z , et al. A sparse completely positive relaxation of the modularity maximization for community detection[J]. SIAM Journal on Scientific Computing, 2018, 40 (5): A3091- A3120. |
| 59 | Pompili F , Gillis N , Absil P-A , et al. Two algorithms for orthogonal nonnegative matrix factorization with application to clustering[J]. Neurocomputing, 2014, 141, 15- 25. |
| 60 | Zhou Y , Bao C , Ding C , et al. A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds[J]. Mathematical Programming, 2022, 201, 1- 61. |
| 61 | Yoo J, Choi S. Orthogonal nonnegative matrix factorization: multiplicative updates on Stiefel manifolds[C]//Intelligent Data Engineering and Automated Learning, 2008: 140-147. |
| 62 | Pan J , Ng M K . Orthogonal nonnegative matrix factorization by sparsity and nuclear norm optimization[J]. SIAM Journal on Matrix Analysis and Applications, 2018, 39 (2): 856- 875. |
| 63 | Zhang K, Zhang S, Liu J, et al. Greedy orthogonal pivoting algorithm for non-negative matrix factorization[C]// International Conference on Machine Learning, 2019: 7493-7501. |
| 64 | Chen Y Y , Xu F F . Randomized algorithms for orthogonal nonnegative matrix factorization[J]. Journal of the Operations Research Society of China, 2023, 11, 327- 345. |
| 65 | Charikar M, Hu L. Approximation algorithms for orthogonal non-negative matrix factorization[C]//International Conference on Artificial Intelligence and Statistics, 2021: 2728-2736. |
| 66 | Huang W, Wei M, Gallivan K A, et al. A Riemannian optimization approach to clustering problems[J]. 2022, arXiv: 2208.03858. |
| 67 | Carson T, Mixon D G, Villar S. Manifold optimization for $k$-means clustering[C]//International Conference on Sampling Theory and Applications, IEEE, 2017: 73-77. |
| 68 | Xu Y , Yin W . A globally convergent algorithm for nonconvex optimization based on block coordinate update[J]. Journal of Scientific Computing, 2017, 72 (2): 700- 734. |
| 69 | Barzilai J , Borwein J M . Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis, 1988, 8 (1): 141- 148. |
| 70 | Attouch H , Bolte J , Svaiter B F . Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods[J]. Mathematical Programming, 2013, 137 (1): 91- 129. |
| 71 | Xiao X , Li Y , Wen Z , et al. A regularized semi-smooth Newton method with projection steps for composite convex programs[J]. Journal of Scientific Computing, 2016, 76, 364- 389. |
| 72 | Milzarek A , Xiao X , Cen S , et al. A stochastic semismooth Newton method for nonsmooth nonconvex optimization[J]. SIAM Journal on Optimization, 2019, 29 (4): 2916- 2948. |
| 73 | Li X , Sun D , Toh K C . On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope[J]. Mathematical Programming, 2020, 179, 419- 446. |
| 74 | Xia Y . An efficient continuation method for quadratic assignment problems[J]. Computers & Operations Research, 2010, 37 (6): 1027- 1032. |
| 75 | Liu Z Y , Qiao H , Xu L . An extended path following algorithm for graph-matching problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34 (7): 1451- 1456. |
| 76 | Zaslavskiy M , Bach F , Vert J P . A path following algorithm for the graph matching problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31 (12): 2227- 2242. |
| 77 | Lyzinski V , Fishkind D E , Fiori M , et al. Graph matching: Relax at your own risk[J]. IEEE transactions on Pattern Analysis and Machine Intelligence, 2015, 38 (1): 60- 73. |
| 78 | Jiang B , Liu Y F , Wen Z . $l_p$-norm regularization algorithms for optimization over permutation matrices[J]. SIAM Journal on Optimization, 2016, 26 (4): 2284- 2313. |
| 79 | Chen X , Xu F , Ye Y . Lower bound theory of nonzero entries in solutions of $\ell_2$-$\ell_p$ minimization[J]. SIAM Journal on Scientific Computing, 2010, 32 (5): 2832- 2852. |
| 80 | Lu Z . Iterative reweighted minimization methods for $l_p$ regularized unconstrained nonlinear programming[J]. Mathematical Programming, 2014, 147 (1-2): 277- 307. |
| 81 | Li X , Pong T K , Sun H , et al. A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem[J]. Computational Optimization and Applications, 2021, 78 (3): 853- 891. |
| 82 | Zhang J , Jin Z , Jiang B , et al. Stochastic augmented projected gradient methods for the large-scale precoding matrix indicator selection problem[J]. IEEE Transactions on Wireless Communications, 2022, 21 (11): 9553- 9565. |
/
| 〈 |
|
〉 |
