Real ideal and the duality of semidefinite programming for polynomial optimization

详细信息    查看全文

• 作者：Yoshiyuki Sekiguchi (1)
  Tomoyuki Takenawa (1)
  Hayato Waki (2)
  
• 关键词：Real ideal ; Polynomial optimization ; Semidefinite programming relaxation ; Primary 14P10 ; Secondary 12D15 ; 14P05 ; 90C22
• 刊名：Japan Journal of Industrial and Applied Mathematics
• 出版年：2013
• 出版时间：June 2013
• 年：2013
• 卷：30
• 期：2
• 页码：321-330
• 全文大小：187KB
• 参考文献：1. Becker, E., Neuhaus, R.: Computation of real radicals of polynomial ideals. In: Proceedings of MEGA-92 Nice, pp. 1鈥?0, Birkhauser, Basel (1993)
  2. Bochnak, J., Coste, M., Roy, M.F.: Real algebraic geometry. Springer, Verlag (1998)
  3. Basu, S., Pollack, R., Roy, M.F.: Algorithms in real algebraic geometry, 2nd edn. Springer, Verlag (2006)
  4. Conti, P., Traverso, C.: Algorithms for the real radical, unpublished manuscript, http://www.dm.unipi.it/traverso/Papers/RealRadical.ps (1998)
  5. Dubois, D.W., Efroymson, G.: Algebraic theory of real varieties. I. 1970 Studies and Essays (Presented to Yu-why Chen on his 60th Birthday, April 1), Mathematics Research Center, National Taiwan University, Taipei, pp. 107鈥?35 (1970)
  6. Efroymson G.: Local reality on algebraic varieties. J. Algebra 29, 133鈥?42 (1974) CrossRef
  7. Lasserre J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796鈥?17 (2001) CrossRef
  8. Laurent, M.: Sums of squares, moment matrices and optimization over polynomials, Emerging Applications of Algebraic Geometry, IMA Volumes in Mathematics and its Applications, vol. 149, Springer, Verlag, pp. 157鈥?70 (2009)
  9. Laurent, M., Lasserre, J.-B., Rostalski, P.: Semidefinite characterization and computation of zero-dimensional real radical ideals. Found. Comput. Math. 8, 607鈥?47 (2008)
  10. Marshall M.: Optimization of polynomial functions. Can. Math. Bull. 46, 575鈥?87 (2003) CrossRef
  11. Marshall, M.: Positive polynomials and sums of squares, Mathematical Surveys and Monographs 146, American Mathematical Society, Providence (2008)
  12. Matsumura, H.: Commutative ring theory, Translated from the Japanese by M. Reid. 2nd edn, Cambridge University Press, Cambridge (1989)
  13. Mishra, B.: Algorithmic algebra. Springer, Verlag (1993)
  14. Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization, Ph.D. thesis, California Institute of Technology, May (2000)
  15. Parrilo P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program 96, 293鈥?20 (2003) CrossRef
  16. Schweighofer M.: Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 15, 805鈥?25 (2005) CrossRef
  17. Spang S.J.: A zero-dimensional approach to compute real radicals. Comput. Sci. J. Moldova 16, 64鈥?2 (2008)
  18. Vo C., Muramatsu M., Kojima M.: Equality based contraction of semidefinite programming relaxations in polynomial optimization. J. Oper. Res. Soc. Jpn. 51, 111鈥?25 (2008)
  19. Weil, A.: Foundations of algebraic geometry. American Mathematical Society, Providence (1962)
  
• 作者单位：Yoshiyuki Sekiguchi (1)
  Tomoyuki Takenawa (1)
  Hayato Waki (2)
  
  1. Faculty of Marine Technology, Tokyo University of Marine Science and Technology, 2-1-6 Etchu-jima, Koto-ku, Tokyo, 135-8533, Japan
  2. Institute of Mathematics for Industry, Kyushu University, 744 Motooka, Fukuoka, Nishi-ku, 819-0395, Japan
  
• ISSN：1868-937X

文摘

We study the ideal generated by polynomials vanishing on a semialgebraic set and give elementary proofs for some equivalent conditions for reality of ideals or S-radical ideals. These results can be applied for modifying polynomial optimization problems so that the associated semidefinite programming relaxation problems have no duality gap.