A Semidefinite Approach for Truncated K-Moment Problems

详细信息    查看全文

• 作者：J. William Helton (1)
  Jiawang Nie (1)
  
• 关键词：Truncated moment sequence ; Flat extension ; Representing measure ; Moment matrix ; Localizing matrix ; Semidefinite programming ; Sum of squares ; 44A60 ; 47A57 ; 90C22 ; 90C90
• 刊名：Foundations of Computational Mathematics
• 出版年：2012
• 出版时间：December 2012
• 年：2012
• 卷：12
• 期：6
• 页码：851-881
• 参考文献：1. C. Bayer, J. Teichmann, The proof of Tchakaloff’s theorem, / Proc. Am. Math. Soc. 134, 3035-040 (2006). CrossRef
  2. J.B. Conway, / A?Course in Functional Analysis, 2nd edn. (Springer, Berlin, 1990).
  3. R. Curto, L. Fialkow, Recursiveness, positivity, and truncated moment problems, / Houst. J. Math. 17, 603-35 (1991).
  4. R. Curto, L. Fialkow, / Solution of the Truncated Complex Moment Problem for Flat Data, Memoirs of the American Mathematical Society, vol.?119, no.?568 (1996).
  5. R. Curto, L. Fialkow, / Flat Extensions of Positive Moment Matrices: Recursively Generated Relations, Memoirs of the American Mathematical Society, vol.?136, no.?648 (1998).
  6. R. Curto, L. Fialkow, Solution of the singular quartic moment problem, / J. Oper. Theory 48, 315-54 (2002).
  7. R. Curto, L. Fialkow, Truncated K-moment problems in several variables, / J. Oper. Theory 54, 189-26 (2005).
  8. R. Curto, L. Fialkow, Solution of the truncated hyperbolic moment problem, / Integral Equ. Oper. Theory 52, 181-19 (2005). CrossRef
  9. R. Curto, L. Fialkow, An analogue of the Riesz–Haviland theorem for the truncated moment problem, / J. Funct. Anal. 225, 2709-731 (2008). CrossRef
  10. R. Curto, L. Fialkow, Recursively determined representing measures for bivariate truncated moment sequences, / J.?Oper. Theory, to appear.
  11. L. Fialkow, Truncated multivariable moment problems with finite variety, / J. Oper. Theory 60, 343-77 (2008).
  12. L. Fialkow, J. Nie, Positivity of Riesz functionals and solutions of quadratic and quartic moment problems, / J. Funct. Anal. 258(1), 328-56 (2010). CrossRef
  13. D. Henrion, J. Lasserre, Detecting global optimality and extracting solutions in GloptiPoly, in / Positive Polynomials in Control. Lecture Notes in Control and Inform. Sci., vol.?312 (Springer, Berlin, 2005), pp.?293-10.
  14. D. Henrion, J. Lasserre, J. Loefberg, GloptiPoly 3: moments, optimization and semidefinite programming. http://homepages.laas.fr/henrion/software/gloptipoly3/.
  15. J.B. Lasserre, Global optimization with polynomials and the problem of moments, / SIAM J. Optim. 11(3), 796-17 (2001). CrossRef
  16. J.B. Lasserre, A?semidefinite programming approach to the generalized problem of moments, / Math. Program., Ser. B 112(1), 65-2 (2008). CrossRef
  17. J.B. Lasserre, M. Laurent, P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, / Found. Comput. Math. 8, 607-47 (2008). CrossRef
  18. J.B. Lasserre, / Moments, Positive Polynomials and Their Applications (Imperial College Press, London, 2009). CrossRef
  19. M. Laurent, Revisiting two theorems of Curto and Fialkow on moment matrices, / Proc. Am. Math. Soc. 133(10), 2965-976 (2005). CrossRef
  20. M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in / Emerging Applications of Algebraic Geometry, ed. by M. Putinar, S. Sullivant. IMA Volumes in Mathematics and its Applications, vol.?149 (Springer, Berlin, 2009), pp.?157-70. CrossRef
  21. M. Laurent, P. Rostalski, The approach of moments for polynomial equations, in / Handbook on Semidefinite, Cone and Polynomial Optimization, ed. by M. Anjos, J.B. Lasserre. International Series in Operations Research & Management Science, vol.?166 (Springer, Berlin, 2012), pp.?25-0. CrossRef
  22. R.R. Phelps, / Lectures on Choquet’s Theorem, Springer Lecture Notes (Springer, Berlin, 1966) (2nd edition 2001).
  23. M. Putinar, Positive polynomials on compact semi-algebraic sets, / Indiana Univ. Math. J. 42, 969-84 (1993). CrossRef
  24. K. Schmüdgen, The K-moment problem for compact semialgebraic sets, / Math. Ann. 289, 203-06 (1991). CrossRef
  25. G. Stengle, A?Nullstellensatz and Positivstellensatz in semialgebraic geometry, / Math. Ann. 207, 87-7 (1974). CrossRef
  26. J.F. Sturm, SeDuMi 1.02:a MATLAB toolbox for optimization over symmetric cones, / Optim. Methods Softw. 11 & 12, 625-53 (1999). CrossRef
  27. B. Sturmfels, / Solving Systems of Polynomial Equations. CBMS Regional Conference Series in Mathematics, vol.?97 (American Mathematical Society, Providence, 2002).
  28. V. Tchakaloff, Formules de?cubatures mécanique à coefficients non négatifs, / Bull. Sci. Math. 81, 123-34 (1957).
  29. H. Wolkowicz, R. Saigal, L. Vandenberghe (eds.), / Handbook of Semidefinite Programming (Kluwer, Dordrecht, 2000).
  
• 作者单位：J. William Helton (1)
  Jiawang Nie (1)
  
  1. Department of Mathematics, University of California, San Diego, 9500 Gilman Drive, La Jolla, CA, 92093, USA
  
• ISSN：1615-3383

文摘

A truncated moment sequence (tms) in n variables and of degree d is a finite sequence y=(y α ) indexed by nonnegative integer vectors α:=(α 1,-α n ) such that α 1+?α n ?em class="a-plus-plus">d. Let K?? n be a semialgebraic set. The truncated K-moment problem (TKMP) is: How can one check if a tms y admits a K-measure μ (a nonnegative Borel measure supported in K) such that $y_{\alpha}= \int_{K} x_{1}^{\alpha_{1}}\cdots x_{n}^{\alpha_{n}}\,\mathrm{d}\mu$ for every α? This paper proposes a semidefinite programming (SDP) approach for solving TKMP. When K is compact, we get the following results: whether a tms admits a K-measure or not can be checked via solving a sequence of SDP problems; when y admits no K-measure, a certificate for the nonexistence can be found; when y admits one, a representing measure for y can be obtained from solving the SDP problems under some necessary and some sufficient conditions. Moreover, we also propose a practical SDP method for finding flat extensions, which in our numerical experiments always found a finitely atomic representing measure when it exists.