The \({\mathcal {A}}\) -Truncated 详细信息    查看全文

• 作者：Jiawang Nie (1)
  
• 关键词：A ; truncated multisequence ; Flat extension ; Localizing matrix ; Semidefinite program ; Completely positive matrix ; Sums of even powers ; 44A60 ; 47A57 ; 90C22 ; 90C90
• 刊名：Foundations of Computational Mathematics
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：14
• 期：6
• 页码：1243-1276
• 全文大小：580 KB
• 参考文献：1. C. Bayer and J. Teichmann. The proof of Tchakaloff鈥檚 Theorem, / Proc. Amer. Math. Soc., 134(2006), pp. 3035鈥?040.
  2. A. Ben-Tal and A. Nemirovski. / Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001.
  3. F. Barioli, A. Berman. The maximal CP-rank of rank \(k\) completely positive matrices. / Linear Algebra Appl. 363(2003), pp. 17-33.
  4. A. Berman and U. Rothblum. A note on the computation of the CP-rank. / Linear Algebra and its Applications 419 (2006), pp. 1鈥?.
  5. A Berman and N. Shaked-Monderer. / Completely Positive Matrices, World Scientific, 2003.
  6. S. Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. / Mathematical Programming, Ser. A, 120(2009), pp. 479鈥?95.
  7. J. B. Conway. / A course in Functional Analysis. Springer-Verlag, 1990 \(2^{nd}\) edition.
  8. R. Curto and L. Fialkow, Recursivenss, positivity, and truncated moment problems. / Houston J. Math. 17(1991), pp. 603鈥?35.
  9. R. Curto and L. Fialkow. Solution of the truncated complex moment problem for flat data. / Memoirs of the American Mathematical Society, 119(1996), No. 568, Amer. Math. Soc., Providence, RI, 1996.
  10. R. Curto and L. Fialkow. Flat extensions of positive moment matrices: Relations in analytic or conjugate terms. / Operator Th.: Adv. Appl. 104(1998), pp. 59鈥?2.
  11. R. Curto and L. Fialkow. Truncated K-moment problems in several variables. / Journal of Operator Theory, 54(2005), pp. 189-226.
  12. R. Curto and L. Fialkow. An analogue of the Riesz-Haviland Theorem for the truncated moment problem, / J. Functional Analysis, 225(2008), 2709鈥?731.
  13. E. de Klerk and D.V. Pasechnik. Approximating of the stability number of a graph via copositive programming. / SIAM Journal on Optimization, 12(4), 875鈥?92.
  14. P.J. Dickinson and L. Gijben. On the computational complexity of membership problems for the completely positive cone and its dual. / Computational Optimization and Applications 57 (2014), No. 2, 403鈥?15.
  15. P.J. Dickinson and M. D眉r. Linear-time complete positivity detection and decomposition of sparse matrices. / SIAM Journal On Matrix Analysis and Applications, 33 (2012), No. 3, 701鈥?20.
  16. M. D眉r. Copositive Programming - a Survey. In: M. Diehl, F. Glineur, E. Jarlebring, W. Michiels (Eds.), / Recent Advances in Optimization and its Applications in Engineering, Springer 2010, pp. 3鈥?0.
  17. L. Fialkow and J. Nie. Positivity of Riesz functionals and solutions of quadratic and quartic moment problems, / J. Functional Analysis, 258(2010), no. 1, pp. 328鈥?56.
  18. L. Fialkow and J. Nie. The truncated moment problem via homogenization and flat extensions. / J. Functional Analysis 263(2012), no. 6, pp. 1682鈥?700.
  19. J. Harris. / Algebraic Geometry, A First Course. Springer Verlag, 1992.
  20. J.W. Helton and J. Nie. A semidefinite approach for truncated K-moment problems. / Foundations of Computational Mathematics, Vol. 12, No. 6, pp. 851-881, 2012.
  21. D. Henrion and J. Lasserre. Detecting global optimality and extracting solutions in GloptiPoly. / Positive polynomials in control, 293-310, Lecture Notes in Control and Inform. Sci., 312, Springer, Berlin, 2005.
  22. D. Henrion, J. Lasserre and J. Loefberg. / GloptiPoly 3: moments, optimization and semidefinite programming. / Optimization Methods and Software 24(2009), no. 4-5, pp. 761鈥?79.
  23. J. B. Lasserre. Global optimization with polynomials and the problem of moments. / SIAM J. Optim. 11(2001), no.3, pp. 796鈥?17.
  24. J. B. Lasserre. Convergent SDP-relaxations in polynomial optimization with sparsity. / SIAM J. Optim. 17, pp. 822鈥?43, 2006.
  25. J.B. Lasserre. A semidefinite programming approach to the generalized problem of moments. / Mathematical Programming 112 (2008), pp. 65鈥?2.
  26. J. B. Lasserre. / Moments, Positive Polynomials and Their Applications, Imperial College Press, 2009.
  27. J. B. Lasserre. New approximations for the cone of copositive matrices and its dual. / Mathematical Programming, 144 (2014), no. 1-2, Ser. A, 265鈥?76.
  28. M. Laurent. Revisiting two theorems of Curto and Fialkow on moment matrices. / Proceedings of the American Mathematical Society 133(2005), no. 10, pp. 2965鈥?976.
  29. M. Laurent. Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, Vol. 149 of IMA Volumes in Mathematics and its Applications, M. Putinar and S. Sullivant (eds), Springer, pages 157鈥?70, 2009.
  30. M. Laurent and B. Mourrain. A generalized flat extension theorem for moment matrices. / Archiv der Mathematik, 93(1), pp. 87鈥?8, 2009.
  31. Y. Li, A. Kummert, A. Frommer. A linear programming based analysis of the CP-rank of completely positive matrices. / Int. J. Appl. Math. Compu. Sci. 14 (2004), pp. 25鈥?1.
  32. M. Marshall. / Positive Polynomials and Sums of Squares. Mathematical Surveys and Monographs, 146. American Mathematical Society, Providence, RI, 2008.
  33. J. Nie. Discriminants and nonnegative polynomials. / Journal of Symbolic Computation 47(2012), no. 2, pp. 167鈥?91.
  34. J. Nie. Certifying convergence of Lasserre鈥檚 hierarchy via flat truncation. / Mathematical Programming, Ser. A, Vol聽142, No. 1-2, pp. 485鈥?10, 2013.
  35. J. Nie. Optimality conditions and finite convergence of Lasserre鈥檚 hierarchy. / Mathematical Programming, 146 (2014), no. 1-2, Ser. A, 97鈥?21.
  36. M. Putinar. Positive polynomials on compact semi-algebraic sets, / Ind. Univ. Math. J. 42(1993), pp. 969-984.
  37. J. Renegar. On the computational complexity and geometry of the first-order theory of the reals. Parts I, II, III. / J. Symbolic Comput. 13 (1992), no. 3, 255鈥?52.
  38. B. Reznick. Some concrete aspects of Hilbert鈥檚 17th problem. In / Contemp. Math., Vol. 253, pp. 251鈥?72. American Mathematical Society, 2000.
  39. B. Reznick. Sums of even powers of real linear forms. / Mem. Amer. Math. Soc., Vol. 96, No. 463, 1992.
  40. K. Schm眉dgen. The K-moment problem for compact semialgebraic sets. / Math. Ann. 289 (1991), 203鈥?06.
  41. R. Schneider. / Convex bodies: the Brunn-Minkowski theory. Encyclopedia of Mathematics and its Applications, Vol. 44. Cambridge University Press, Cambridge, 1993.
  42. J.F. Sturm. SeDuMi 1.02: A MATLAB toolbox for optimization over symmetric cones. / Optimization Methods and Software, 11 & 12 (1999), pp. 625鈥?53.
  43. B. Sturmfels. / Solving systems of polynomial equations. CBMS Regional Conference Series in Mathematics, 97. American Mathematical Society, Providence, RI, 2002.
  44. V. Tchakaloff. Formules de cubatures m茅canique 脿 coefficients non n茅gatifs. / Bull. Sci. Math. (2) 81(1957), pp. 123鈥?34.
  45. M. Todd. Semidefinite optimization. / Acta Numerica 10(2001), pp. 515鈥?60.
  
• 作者单位：Jiawang Nie (1)
  
  1. Department of Mathematics, University of California San Diego, 9500 Gilman Drive, La Jolla, CA, 92093, USA
  
• ISSN：1615-3383

文摘

Let \({\mathcal {A}}\subseteq {\mathbb {N}}^n\) be a finite set, and \(K\subseteq {\mathbb {R}}^n\) be a compact semialgebraic set. An \({\mathcal {A}}\) -truncated multisequence ( \({\mathcal {A}}\) -tms) is a vector \(y=(y_{\alpha })\) indexed by elements in \({\mathcal {A}}\) . The \({\mathcal {A}}\) -truncated \(K\) -moment problem ( \({\mathcal {A}}\) -TKMP) concerns whether or not a given \({\mathcal {A}}\) -tms \(y\) admits a \(K\) -measure \(\mu \) , i.e., \(\mu \) is a nonnegative Borel measure supported in \(K\) such that \(y_\alpha = \int _K x^\alpha \mathtt {d}\mu \) for all \(\alpha \in {\mathcal {A}}\) . This paper proposes a numerical algorithm for solving \({\mathcal {A}}\) -TKMPs. It aims at finding a flat extension of \(y\) by solving a hierarchy of semidefinite relaxations \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) for a moment optimization problem, whose objective \(R\) is generated in a certain randomized way. If \(y\) admits no \(K\) -measures and \({\mathbb {R}}[x]_{{\mathcal {A}}}\) is \(K\) -full (there exists \(p \in {\mathbb {R}}[x]_{{\mathcal {A}}}\) that is positive on \(K\) ), then \((\mathtt {SDR})_k\) is infeasible for all \(k\) big enough, which gives a certificate for the nonexistence of representing measures. If \(y\) admits a \(K\) -measure, then for almost all generated \(R\) , this algorithm has the following properties: i) we can asymptotically get a flat extension of \(y\) by solving the hierarchy \(\{(\mathtt {SDR})_k\}_{k=1}^\infty \) ; ii) under a general condition that is almost sufficient and necessary, we can get a flat extension of \(y\) by solving \((\mathtt {SDR})_k\) for some \(k\) ; iii) the obtained flat extensions admit a \(r\) -atomic \(K\) -measure with \(r\le |{\mathcal {A}}|\) . The decomposition problems for completely positive matrices and sums of even powers of real linear forms, and the standard truncated \(K\) -moment problems, are special cases of \({\mathcal {A}}\) -TKMPs. They can be solved numerically by this algorithm.