非负正交约束优化问题的理论、算法及应用

doi:10.15960/j.cnki.issn.1007-6093.2023.04.007

Abstract

Abstract:

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.

Key words: optimization with nonnegative orthogonality constraints, optimization with permutation matrices constraints, exact penalty, ?_p regularization, quadratic assignment problem

CLC Number:

O221.2

Bo JIANG. On the theories, algorithms, and applications of optimization with nonnegative orthogonality constraints[J]. Operations Research Transactions, 2023, 27(4): 136-152.

References 82

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. doi: 10.1007/s10107-012-0584-1
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. doi: 10.1007/s10107-014-0765-1
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. doi: 10.1137/140955483
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. doi: 10.1007/s10107-014-0816-7
6	Wei H , Yang W H . A Riemannian subspace limited-memory SR1 trust region method[J]. Optimization Letters, 2016, 10 (8): 1705- 1723. doi: 10.1007/s11590-015-0977-1
7	高斌, 刘歆, 袁亚湘. 正交约束优化问题的一阶算法[J]. 运筹学学报, 2017, 21 (4): 57- 68. doi: 10.15960/j.cnki.issn.1007-6093.2017.04.004
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. doi: 10.1137/16M1098759
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. doi: 10.1137/17M1142478
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. doi: 10.1137/18M1221679
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. doi: 10.1137/18M121112X
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. doi: 10.1007/s10107-018-1285-1
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. doi: 10.1137/18M122457X
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. doi: 10.1007/s40305-020-00295-9
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. doi: 10.4208/csiam-am.SO-2020-0008
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. doi: 10.1109/TSP.2022.3182883
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. doi: 10.1080/10556788.2020.1852236
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. doi: 10.1016/j.cam.2022.114915
23	Hiriart-Urruty J B , Seeger A . A variational approach to copositive matrices[J]. SIAM Review, 2010, 52 (4): 593- 629. doi: 10.1137/090750391
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. doi: 10.2307/1907742
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. doi: 10.1007/s10107-022-01794-8
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. doi: 10.1109/TNN.2010.2041361
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. doi: 10.1016/j.patcog.2018.04.029
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. doi: 10.1109/LSP.2022.3179168
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. doi: 10.1109/TIP.2022.3194701
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. doi: 10.1137/19M1294708
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. doi: 10.1016/j.patcog.2021.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. doi: 10.1016/j.neucom.2021.08.152
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. doi: 10.1137/18M1181602
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. doi: 10.1007/BF02592205
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. doi: 10.1137/15M1028054
50	Luo Z Q , Pang J S . Error bounds for analytic systems and their applications[J]. Mathematical Programming, 1994, 67 (1-3): 1- 28. doi: 10.1007/BF01582210
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. doi: 10.1007/s10107-014-0806-9
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. doi: 10.1093/imanum/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. doi: 10.1109/LSP.2014.2371895
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. doi: 10.1109/TSP.2021.3102106
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. doi: 10.1137/17M1141904
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. doi: 10.1016/j.neucom.2014.02.018
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. doi: 10.1137/16M1107863
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. doi: 10.1007/s40305-020-00322-9
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. doi: 10.1007/s10915-017-0376-0
69	Barzilai J , Borwein J M . Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis, 1988, 8 (1): 141- 148. doi: 10.1093/imanum/8.1.141
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. doi: 10.1137/18M1181249
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. doi: 10.1007/s10107-018-1342-9
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. doi: 10.1109/TPAMI.2012.45
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. doi: 10.1109/TPAMI.2008.245
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. doi: 10.1137/15M1048021
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. doi: 10.1137/090761471
80	Lu Z . Iterative reweighted minimization methods for $l_p$ regularized unconstrained nonlinear programming[J]. Mathematical Programming, 2014, 147 (1-2): 277- 307. doi: 10.1007/s10107-013-0722-4
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. doi: 10.1007/s10589-020-00261-4
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. doi: 10.1109/TWC.2022.3177840

[1]	CHEN Xingwen, PAN Shaohua. Equivalent Lipschitz optimization model for the group zero-norm regularized problem [J]. Operations Research Transactions, 2018, 22(3): 139-144.
[2]	LIAN Shujun, DU Aihua, TANG Jiahui. A new class of simple smooth exact penalty functions for equality constrained optimization problems [J]. Operations Research Transactions, 2017, 21(1): 33-43.
[3]	WANG Changyu, ZHAO Wenling. Global convergence of a class smooth penalty algorithm of constrained optimization problem [J]. Operations Research Transactions, 2015, 19(3): 151-160.
[4]	ZHANG Huizhen, WEI Xin, MA Liang. A new solution method by linearization for a special kind of quadratic assignment problem [J]. Operations Research Transactions, 2013, 17(4): 87-95.
[5]	Shu-jun Lian. On the Smoothing of the Lower Order Exact Penalty Function for Inequality Constrained Optimization [J]. Operations Research Transactions, 2012, 16(2): 51-64.
[6]	Shang-You-Lin, LIU Mu-Hua, LI Pu. A New Penalty Function Based on Non-coercive Penalty Functions [J]. Operations Research Transactions, 2012, 16(1): 56-66.

On the theories, algorithms, and applications of optimization with nonnegative orthogonality constraints

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 82

Related Articles 6

Recommended Articles

Metrics

Comments