运筹学学报 ›› 2014, Vol. 18 ›› Issue (1): 134-148.
李浙宁1，凌晨2，王宜举3，杨庆之4,*
出版日期:2014-03-15
发布日期:2014-03-15
通讯作者:
杨庆之
E-mail:qz-yang@nankai.edu.cn
基金资助:国家自然科学基金 (Nos. 11271206, 11171180, 11171083)
LI Zhening1, LING Chen2, WANG Yiju3, YANG Qingzhi4,*
Online:2014-03-15
Published:2014-03-15
摘要： 张量分析 (也称多重数值线性代数) 主要包括张量分解和张量特征值的理论和算法，多项式优化主要包括目标和约束均为多项式的一类优化问题的理论和算法. 主要介绍这两个研究领域中若干新的研究结果. 对张量分析部分，主要介绍非负张量H-特征值谱半径的一些性质及求解方法，还介绍非负张量最大 (小) Z-特征值的优化表示及其解法；对多项式优化部分，主要介绍带单位球约束或离散二分单位取值、目标函数为齐次多项式的优化问题及其推广形式的多项式优化问题和半定松弛解法. 最后对所介绍领域的发展趋势做了预测和展望.
中图分类号:
李浙宁，凌晨，王宜举，杨庆之. 张量分析和多项式优化的若干进展[J]. 运筹学学报, 2014, 18(1): 134-148.
LI Zhening, LING Chen, WANG Yiju, YANG Qingzhi. Some advances in tensor analysis and polynomial optimization[J]. Operations Research Transactions, 2014, 18(1): 134-148.
| Kolda T G, Bader B W. Tensor decompositions and applications [J]. SIAM Review, 2009, 51(3): 455-500. Qi L, Sun W, Wang Y. Numerical multilinear algebra and its applications [J]. Frontiers of Mathematics in China, 2007, 2(4): 501-526. Cichocki A, Zdunek R, Phan A H, et al. Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation [M]. Chichester: John Wiley & Sons，2009. Lim L H, Comon P. Nonnegative approximations of nonnegative tensors [J]. Journal of Chemometrics, 2009, 23(7-8): 432-441. Zhang X, Ling C, Qi L. The best rank-1 approximation of a symmetric tensor and related spherical optimization problems [J]. SIAM Journal on Matrix Analysis and Applications, 2012, 33(3): 806-821. Qi L. Eigenvalues of a real supersymmetric tensor [J]. Journal of Symbolic Computation, 2005, 40(6): 1302-1324. Lim L H. Singular values and eigenvalues of tensors: a variational approach [C]//Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2005, 1: 129-132. Chang K, Pearson K, Zhang T. On eigenvalue problems of real symmetric tensors [J]. Journal of Mathematical Analysis and Applications, 2009, 350(1): 416-422. Chang K, Zhang T. On the uniqueness and non-uniqueness of the positive Z-eigenvector for transition probability tensors [J]. Journal of Mathematical Analysis and Applications, 2013, 408(2): 525–540. Hu S, Huang Z H, Ling C, et al. On determinants and eigenvalue theory of tensors [J]. Journal of Symbolic Computation, 2013, 50: 508-531. Qi L. Eigenvalues and invariants of tensors [J]. Journal of Mathematical Analysis and Applications, 2007, 325(2): 1363-1377. Han D, Dai H, Qi L. Conditions for strong ellipticity of anisotropic elastic materials [J]. Journal of Elasticity, 2009, 97(1): 1-13. Ni Q, Qi L, Wang F. An eigenvalue method for the positive definiteness identification problem [J]. IEEE Transactions on Automatic Control, 2008, 53: 1096-1107. Chang K C, Pearson K, Zhang T. Perron-Frobenius theorem for nonnegative tensors [J]. Communications in Mathematical Sciences, 2008, 6(2): 507-520. Yang Q, Yang Y. Further results for Perron-Frobenius theorem for nonnegative tensors II [J]. SIAM Journal on Matrix Analysis and Applications, 2011, 32(4): 1236-1250. Yang Y, Yang Q. Further results for Perron-Frobenius theorem for nonnegative tensors [J]. SIAM Journal on Matrix Analysis and Applications, 2010, 31(5): 2517-2530. Friedland S, Gaubert S, Han L. Perron-Frobenius theorem for nonnegative multilinear forms and extensions [J]. Linear Algebra and its Applications, 2013, 438(2): 738-749. Chang K, Qi L, Zhou G. Singular values of a real rectangular tensor [J]. Journal of Mathematical Analysis and Applications, 2010, 370(1): 284-294. Yang Y, Yang Q. Singular values of nonnegative rectangular tensors [J]. Frontiers of Mathematics in China, 2011, 6(2): 363-378. Chang K, Qi L, Zhang T. A survey on the spectral theory of nonnegative tensors [J]. Numerical Linear Algebra with Applications, 2013, 20(6): 891-912. Yang Q, Zhang L, Zhang T, et al. Spectral theory of nonnegative tensors [J]. Frontiers of Mathematics in China, Doi：10.1007/s11464-012-0273-7. Yang Y, Yang Q. Geometric simplicity of spectral radius of nonnegative irreducible tensors [J]. Frontiers of Mathematics in China, 2013, 8(1): 129-140. Hu S, Huang Z, Qi L. Strictly nonnegative tensors and nonnegative tensor partition [J]. Science China Mathematics, 2014, 57(1): 181-195. Ng M, Qi L, Zhou G. Finding the largest eigenvalue of a nonnegative tensor [J]. SIAM Journal on Matrix Analysis and Applications, 2009, 31(3): 1090-1099. Chang K, Pearson K J, Zhang T. Primitivity, the convergence of the NQZ method, the largest eigenvalue for nonnegative tensors [J]. SIAM Journal on Matrix Analysis and Applications, 2011, 32(3): 806-819. Zhang L, Qi L. Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor [J]. Numerical Linear Algebra with Applications, 2012, 19(5): 830-841. Qi L, Wang F, Wang Y. Z-eigenvalue methods for a global polynomial optimization problem [J]. Mathematical Programming, 2009, 118(2): 301-316. Chen Z, Qi L, Yang Q, et al. The solution methods for the largest eigenvalue (singular value) of nonnegative tensors and convergence analysis [J]. Linear Algebra and its Applications, 2013, 439: 3713-3733. Zhou G, Caccetta L, Teo K L, et al. Nonnegative polynomial optimization over unit spheres and convex programming relaxations [J]. SIAM Journal on Optimization, 2012, 22(3): 987-1008. Kolda T G, Mayo J R. Shifted power method for computing tensor eigenpairs [J]. SIAM Journal on Matrix Analysis and Applications, 2011, 32(4): 1095-1124. Kofidis E, Regalia P A. On the best rank-1 approximation of higher-order supersymmetric tensors [J]. SIAM Journal on Matrix Analysis and Applications, 2002, 23(3): 863-884. Hu S, Huang Z H, Qi L. Finding the extreme Z-eigenvalues of tensors via a sequential semidefinite programming method [J]. Numerical Linear Algebra with Applications, 2013, 20(6): 972-984. Hu S, Qi L. Algebraic connectivity of an even uniform hypergraph [J]. Journal of Combinatorial Optimization, 2012, 24(4): 564-579. H\"aggl\"of K, Lindberg P, Svensson L. Eigenvalues of tensors and some very basic spectral hypergraph theory [R]. Seminar speaking, 2008. Pearson K J, Zhang T. On spectral hypergraph theory of the adjacency tensor. Graphs and Combinatorics, Doi: 10.1007/s00373-013-1340-x. Xie J, Chang A. On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs [J]. Linear Algebra and its Applications, 2013, 439(8): 2195-2204. Shor N Z. Nondifferentiable Optimization and Polynomial Problems [M]. New York: Kluwer Academic Publishers, 1998. Artin E. \"uber die zerlegung definiter funktionen in quadrate [M]//Abhandlungen aus dem Mathematischen Seminar der Universit\"at Hamburg, New York: Kluwer Academic Publishers, 1927, 5: 100-115. Delzell C. A continuous, constructive solution to Hilbert's 17th problem [J]. Inventiones Mathematicae, 1984, 76(3): 365-384. Basser P J, Mattiello J, LeBihan D. Mr diffusion tensor spectroscopy and imaging [J]. Biophysical Journal, 1994, 66(1): 259-267. Basser P J, Mattiello J, Lebihan D. Estimation of the effective self-diffusion tensor from the NMR spin echo [J]. Journal of Magnetic Resonance, Series B, 1994, 103(3): 247-254. Comon P, Mourrain B. Decomposition of quantics in sums of powers of linear forms [J]. Signal Processing, 1996, 53(2): 93-107. Dahl G, Leinaas J M, Myrheim J, et al. A tensor product matrix approximation problem in quantum physics [J]. Linear Algebra and its Applications, 2007, 420(2): 711-725. Jensen J H, Helpern J A, Ramani A, et al. Diffusional kurtosis imaging: the quantification of non-Gaussian water diffusion by means of magnetic resonance imaging [J]. Magnetic Resonance in Medicine, 2005, 53(6): 1432-1440. Lu H, Jensen J H, Ramani A, et al. Three-dimensional characterization of non-Gaussian water diffusion in humans using diffusion kurtosis imaging [J]. NMR in Biomedicine, 2006, 19(2): 236-247. Mariere B, Luo Z Q, Davidson T N. Blind constant modulus equalization via convex optimization [J]. Signal Processing, IEEE Transactions on, 2003, 51(3): 805-818. Markowitz H. Portfolio selection [J]. Journal of Finance, 1952, 7(1): 77-91. Mattiello J, Basser P J, LeBihan D. Analytical expressions for the phb matrix in NMR diffusion imaging and spectroscopy [J]. Journal of magnetic resonance, Series A, 1994, 108(2): 131-141. Mattiello J, Basser P J, Bihan D Le. The b matrix in diffusion tensor echo-planar imaging [J]. Magnetic Resonance in Medicine, 1997, 37(2): 292-300. Qi L, Teo K L. Multivariate polynomial minimization and its application in signal processing [J]. Journal of Global Optimization, 2003, 26(4): 419-433. H\"aggl\"of K, Lindberg P, Svensson L. Computing global minima to polynomial optimization problems using gr\"obner bases [J]. Journal of Global Optimization, 1995, 7(2): 115-125. He S, Li Z, Zhang S. Approximation algorithms for homogeneous polynomial optimization with quadratic constraints [J]. Mathematical Programming, 2010, 125(2): 353-383. Lasserre J B. Global optimization with polynomials and the problem of moments [J]. SIAM Journal on Optimization, 2001, 11(3): 796-817. Parrilo P A, Sturmfels B. Minimizing polynomial functions [J]. Discrete Math Theo Comput Sci, 2003, 60: 83-99. Lathauwer de L, Moor de~B, Vandewalle J. On the best rank-1 and rank-(r_1, r_2,., r_n) approximation of higher-order tensors [J]. SIAM Journal on Matrix Analysis and Applications, 2000, 21(4): 1324-1342. Ling C, Nie J, Qi L, et al. Biquadratic optimization over unit spheres and semidefinite programming relaxations [J]. SIAM Journal on Optimization, 2009, 20(3): 1286-1310. Ling C, Zhang X, Qi L. Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints [J]. Numerical Linear Algebra with Applications, 2012, 19(1): 113-131. Gurvits L. Classical deterministic complexity of Edmonds' problem and quantum entanglement [C]Proceedings of the 35th annual ACM symposium on Theory of computing, New York: ACM, 2003, 10-19. Nesterov Y. Random walk in a simplex and quadratic optimization over convex polytopes [EB/OL]. [2013-10-09].https://alfresco.uclouvain.be/alfresco/d/d/workspace/SpacesStore/c7741b8a-6de9-4e67-9a09-c0051eff06dd/2003/coredp_2003_71.pdf. Cox D A, Little J B, O'Shea D. Using Algebraic Geometry [M]. Berlin: Springer-Verlag, 1998. Ghosh A, Tsigaridas E P, Descoteaux M, et al. A polynomial based approach to extract the maxima of an antipodally symmetric spherical function and its application to extract fiber directionsfrom the Orientation Distribution Function in Diffusion MRI [C]//CDMRI'08-MICCAI 2008 Workshop on Computational Diffusion MRI, New York: Etats-Unis, 2008. Mourrain B, Pavone J P. Subdivision methods for solving polynomial equations [J]. Journal of Symbolic Computation, 2009, 44(3): 292-306. Mourrain B, Trebuchet P. Generalized normal forms and polynomial system solving [C]//Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, New York: ACM, 2005, 253-260. Qi L. Extrema of a real polynomial [J]. Journal of Global Optimization, 2004, 30(4): 405-433. Qi L, Wan Z, Yang Y. Global minimization of normal quartic polynomials based on global descent directions [J]. SIAM Journal on Optimization, 2004, 15(1): 275-302. Maringer D, Parpas P. Global optimization of higher order moments in portfolio selection [J]. Journal of Global Optimization, 2009, 43(2-3): 219-230. Parpas P, Rustem B. Global optimization of the scenario generation and portfolio selection problems [J]. Computational Science and its Applications-ICCSA 2006, 908-917. Balinski M. Notes-on a selection problem [J]. Management Science, 1970, 17(3): 230-231. Rhys J. A selection problem of shared fixed costs and network flows [J]. Management Science, 1970, 17(3): 200-207. Alizadeh-Dehkharghani F. Combinatorial optimization with interior point methods and semi-definite matrices [D]. Minnesota: University of Minnesota, 1992. Nesterov Y, Nemirovskii A S. Interior-Point Polynomial Algorithms in Convex Programming [M]. Auckland: SIAM, 1994. Nesterov Y. Squared functional systems and optimization problems [J]. High Performance Optimization, 2000, 33: 405-440. Parrilo P A. Semidefinite programming relaxations for semialgebraic problems [J]. Mathematical programming, 2003, 96(2): 293-320. Lasserre J B. Semidefinite programming vs. LP relaxations for polynomial programming [J]. Mathematics of Operations Research, 2002, 27(2): 347-360. Luo Z Q, Sidiropoulos N D, Tseng P, et al. Approximation bounds for quadratic optimization with homogeneous quadratic constraints [J]. SIAM Journal on Optimization, 2007, 18(1): 1-28. 王宜举. 一类齐次多项式优化问题的一个全局优化算法 [J]. 应用数学学报, 2010, 33(2): 328-337. Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J]. Journal of the ACM, 1995, 42(6): 1115-1145. Luo Z Q, Sidiropoulos N D, Tseng P, et al. Approximation bounds for quadratic optimization with homogeneous quadratic constraints [J]. SIAM Journal on Optimization, 2007, 18(1): 1-28. Nemirovski A, Roos C, Terlaky T. On maximization of quadratic form over intersection of ellipsoids with common center [J]. Mathematical Programming, 1999, 86(3): 463-473. Nesterov Y. Semidefinite relaxation and nonconvex quadratic optimization [J]. Optimization Methods and Software, 1998, 9(1-3): 141-160. Ye Y. Approximating quadratic programming with bound and quadratic constraints [J]. Mathematical Programming, 1999, 84(2): 219-226. Ye Y. Approximating global quadratic optimization with convex quadratic constraints [J]. Journal of Global Optimization, 1999, 15(1): 1-17.Ye Y. Approximating quadratic programming with bound and quadratic constraints [J]. Mathematical Programming, 1999, 84(2): 219-226. Jiang B, Li Z, Zhang S. On cones of nonnegative quartic forms [EB/OL]. [2013-09-21]. http://math.shu.edu.cn/teacher/zheningli/quartic_form.pdf. He S, Luo Z Q, Nie J, et al. Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization [J]. SIAM Journal on Optimization, 2008, 19(2): 503-523. Klerk de~E, Laurent M, Parrilo P A. A PTAS for the minimization of polynomials of fixed degree over the simplex [J]. Theoretical Computer Science, 2006, 361(2): 210-225. Barvinok A. Integration and optimization of multivariate polynomials by restriction onto a random subspace [J]. Foundations of Computational Mathematics, 2007, 7(2): 229-244. Luo Z Q, Zhang S. A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints [J]. SIAM Journal on Optimization, 2010, 20(4): 1716-1736. Yang Y, Yang Q. On solving biquadratic optimization via semidefinite relaxation [J]. Computational Optimization and Applications, 2012, 53(3): 845-867. Yang Y, Yang Q, Qi L. Properties and methods for finding the best rank-one approximation to higher-order tensors [J]. Computational Optimization and Applications, Doi: 10.1007/s10589-013-9617-9. Zhang X, Ling C, Qi L. Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints [J]. Journal of Global Optimization, 2011, 49(2): 293-311. Zhang X, Qi L, Ye Y. The cubic spherical optimization problems [J]. Mathematics of Computation, 2012, 81(279): 1513-1525. Yang Y, Yang Q, Qi L. Properties and methods for finding the best rank-one approximation to higher-order tensors [J]. Computational Optimization and Applications, Doi: 10.1007/s10589-013-9617-9. He S, Jiang B, Li Z, et al. Probability bounds for polynomial functions in random variables [EB/OL]. [2013-11-20]. http://dx.doi.org/10.1287/moor.2013.0637. He S, Li Z, Zhang S. Inhomogeneous polynomial optimization over convex set: an approximation approach. Mathematics of Computation, 2014. So A M C. Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems [J]. Mathematical Programming, 2011, 129(2): 357-382. He S, Li Z, Zhang S. Approximation algorithms for discrete polynomial optimization [J]. Journal of the Operations Research Society of China, 2013, 1(1): 3-36. Li Z, He S, Zhang S. Approximation methods for polynomial optimization: Models, Algorithms, and Applications [M]. Springer, New York, 2012. Klerk de E, Laurent M. Error bounds for some semidefinite programming approaches to polynomial minimization on the hypercube [J]. SIAM Journal on Optimization, 2010, 20(6): 3104-3120. Nie J. An approximation bound analysis for lasserre relaxation in multivariate polynomial optimization [J]. Journal of the Operations Research Society of China, 2013, 1(3): 313-332. Henrion D, Lasserre J B. Gloptipoly: global optimization over polynomials with matlab and sedumi [J]. ACM Transactions on Mathematical Software, 2003, 29(2): 165-194. Prajna S, Papachristodoulou A, Parrilo P A. Sostools: sum of squares optimization toolbox for matlab-user’s guide. Control and Dynamical Systems, California Institute of Technology, Pasadena, CA, 91125, 2004. Waki H, Kim S, Kojima M, et al. Algorithm 883: sparse POP---a sparse semidefinite programming relaxation of polynomial optimization problems [J]. ACM Transactions on Mathematical Software, 2008, 35(2): 15. Waki H, Kim S, Kojima M, et al. Sums of squares and semidefinite program relaxations for polynomial optimization problems with structured sparsity [J]. SIAM Journal on Optimization, 2006, 17(1): 218-242. Yamashita M, Fujisawa K, Fukuda M, et al. Latest developments in the sdpa family for solving large-scale sdps [J]. Handbook on Semidefinite, Conic and Polynomial Optimization, 2012, 687-713. Nie J. Certifying convergence of lasserre's hierarchy via flat truncation [J]. Mathematical Programming, 2013, 142(1-2): 485-510. Nie J. Optimality conditions and finite convergence of Lasserre's hierarchy. Mathematical Programming, Doi: 10.1007/s10107-013-0680-x. Riener C, Theobald T, Jansson L, et al. Exploiting symmetries in sdp-relaxations for polynomial optimization [J]. Mathematics of Operations Research, 2013, 38(1): 121-141. Lasserre J B. Inverse polynomial optimization [J]. Mathematics of Operations Research, 2013, 38(3): 418-436. Burer S. On the copositive representation of binary and continuous nonconvex quadratic programs [J]. Mathematical Programming, 2009, 120(2): 479-495. Ahmadi A A, Olshevsky A, Parrilo P A, et al. Np-Hardness of deciding convexity of quartic polynomials and related problems [J]. Mathematical Programming, 2013, 137(1-2): 453-476. Hu S, Huang Z H. Theorems of the alternative for inequality systems of real polynomials [J]. Journal of Optimization Theory and Applications, 2012, 154(1): 1-16. Chen B, He S, Li Z, et al. Maximum block improvement and polynomial optimization [J]. SIAM Journal on Optimization, 2012, 22(1): 87-107. Uschmajew A. Local convergence of the alternating least squares algorithm for canonical tensor approximation [J]. SIAM Journal on Matrix Analysis and Applications, 2012, 33(2): 639-652. |
| [1] | 李鑫荣, 修乃华, 罗自炎. 低秩矩阵优化若干新进展[J]. 运筹学学报, 2020, 24(2): 23-41. |
| [2] | 赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60. |
| [3] | 杨瑞琪, 徐大川, 杜东雷, 张冬梅. 次模函数最大化的流算法综述[J]. 运筹学学报, 2020, 24(2): 73-86. |
| [4] | 简金宝, 杨林峰, 张晨. 电力系统机组组合问题的模型与优化方法[J]. 运筹学学报, 2020, 24(2): 87-102. |
| [5] | 张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130. |
| [6] | 丁志伟, 刘艳云, 孔京, 张洪, 张一, 戴彧虹, 杨周旺. 感染人数期望值估计及新增确诊人数趋势预测的概率模型[J]. 运筹学学报, 2020, 24(1): 1-12. |
| [7] | 黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114. |
| [8] | 耿晓路, 童小娇. 分布鲁棒机会约束优化问题的研究[J]. 运筹学学报, 2020, 24(1): 115-130. |
| [9] | 刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139. |
| [10] | 王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154. |
| [11] | 李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104. |
| [12] | 黄培煌, 朱文兴. 移动传感器网络中的最大价值路径扫描覆盖算法[J]. 运筹学学报, 2019, 23(4): 155-164. |
| [13] | 张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14. |
| [14] | 李建荣. 中国高考招生匹配市场中的算法设计及公平激励机制[J]. 运筹学学报, 2019, 23(2): 75-85. |
| [15] | 仲维亚, 杨若瑶. 工件具有子工件工期的排序问题[J]. 运筹学学报, 2019, 23(2): 67-74. |
| 阅读次数 | ||||||
|
全文 |
|
|||||
|
摘要 |
|
|||||
