Operations Research Transactions ›› 2014, Vol. 18 ›› Issue (1): 134-148.
• Original Articles • Previous Articles Next Articles
LI Zhening1, LING Chen2, WANG Yiju3, YANG Qingzhi4,*
Online:
2014-03-15
Published:
2014-03-15
CLC Number:
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.
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
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] | LI Xinrong, XIU Naihua, LUO Ziyan. Some advances in low-rank matrix optimization [J]. Operations Research Transactions, 2020, 24(2): 23-41. |
[2] | ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect [J]. Operations Research Transactions, 2020, 24(2): 42-60. |
[3] | YANG Ruiqi, XU Dachuan, DU Donglei, ZHANG Dongmei. A survey on streaming algorithms for maximizing submodular functions [J]. Operations Research Transactions, 2020, 24(2): 73-86. |
[4] | ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130. |
[5] | DING Zhiwei, LIU Yanyun, KONG Jing, ZHANG Hong, ZHANG Yi, DAI Yuhong, YANG Zhouwang. A probability model for estimating the expected number of the newly infected and predicting the trend of the diagnosed [J]. Operations Research Transactions, 2020, 24(1): 1-12. |
[6] | CHEN Yong, WANG Wei, XU Yifan. An stochastic algorithm for global optimization with linear constraints based on intermittent diffusion [J]. Operations Research Transactions, 2020, 24(1): 88-100. |
[7] | GENG Xiaolu, TONG Xiaojiao. A review on distributionally robust chance constrained optimization problems [J]. Operations Research Transactions, 2020, 24(1): 115-130. |
[8] | LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139. |
[9] | WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154. |
[10] | LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104. |
[11] | HUANG Peihuang, ZHU Wenxing. Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks [J]. Operations Research Transactions, 2019, 23(4): 155-164. |
[12] | ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14. |
[13] | LI Jianrong. Algorithm design and the fair incentive mechanism in Chinese college admissions matching market [J]. Operations Research Transactions, 2019, 23(2): 75-85. |
[14] | ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74. |
[15] | CHEN Xinbei, ZHU Mingkang, CHEN Jianli. Iterative projection gradient hard thresholding pursuit algorithm for sparse optimization [J]. Operations Research Transactions, 2019, 23(1): 1-14. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||