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

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

摘要/Abstract

摘要：

非负正交约束优化问题是同时带有非负约束和正交约束的优化问题, 该类问题在机器学习和数据科学中有着重要的应用。常见的非负正交约束优化问题包括二次指派问题、图匹配问题、非负正交矩阵分解问题、非负主成分分析和K-指示模型等。由于非负约束和正交约束的共同作用, 该类问题具有一定的组合结构, 一般是NP-难的。本文主要介绍非负正交约束优化问题的基本理论性质、求解算法以及相关的应用模型。

关键词: 非负正交约束优化, 置换矩阵约束优化, 精确罚函数, ?_p正则化, 二次指派问题

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

中图分类号:

O221.2

姜波. 非负正交约束优化问题的理论、算法及应用[J]. 运筹学学报, 2023, 27(4): 136-152.

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

参考文献 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]	连淑君, 杜爱华, 唐加会. 等式约束优化问题的一类新的简单光滑精确罚函数[J]. 运筹学学报, 2017, 21(1): 33-43.
[2]	王长钰, 赵文玲. 约束优化问题的一类光滑罚算法的全局收敛特性[J]. 运筹学学报, 2015, 19(3): 151-160.
[3]	连淑君. 不等式约束优化问题的低阶精确罚函数的光滑化算法[J]. 运筹学学报, 2012, 16(2): 51-64.
[4]	尚有林, 刘牧华, 李璞. 一种新的逼近精确罚函数的罚函数及性质[J]. 运筹学学报, 2012, 16(1): 56-66.