EQUALITY BASED CONTRACTION OF SEMIDEFINITE PROGRAMMING RELAXATIONS IN POLYNOMIAL OPTIMIZATION

• Vo Cong

  DaiTri Joint Stock Company

• Muramatsu Masakazu

  The University of Electro-Communications

• Kojima Masakazu

  Tokyo Institute of Technology

抄録

The SDP (semidefinite programming) relaxation for general POPs (polynomial optimization problems), which was proposed as a method for computing global optimal solutions of POPs by Lasserre, has become an active research subject recently. We propose a new heuristic method exploiting the equality constraints in a given POP, and strengthen the SDP relaxation so as to achieve faster convergence to the global optimum of the POP. We can apply this method to both of the dense SDP relaxation which was originally proposed by Lasserre, and the sparse SDP relaxation which was later proposed by Kim, Kojima, Muramatsu and Waki. Especially, our heuristic method incorporated into the sparse SDP relaxation method has shown a promising performance in numerical experiments on large scale sparse POPs. Roughly speaking, we induce valid equality constraints from the original equality constraints of the POP, and then use them to convert the dense or sparse SDP relaxation into a new stronger SDP relaxation. Our method is enlightened by some strong theoretical results on the convergence of SDP relaxation for POPs with equality constraints provided by Lasserre, Parrilo and Laurent, but we place the main emphasis on the practical aspect to compute more accurate lower bounds of larger sparse POPs.

収録刊行物

• 日本オペレーションズ・リサーチ学会論文誌

  日本オペレーションズ・リサーチ学会論文誌 51 (1), 111-125, 2008

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• Nonlinear programming
• optimization
• polynomial optimization
• global optimization
• semidefinite programming
• equality constraints
• exploiting sparsity

詳細情報

• CRID: 1390001204109183872
• NII論文ID: 110006632508
• NII書誌ID: AA00703935
• DOI: 10.15807/jorsj.51.111
• ISSN: 21888299
• ISSN: 04534514
• NDL書誌ID: 9421051
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I9421051
• Web Site: https://www.jstage.jst.go.jp/article/jorsj/51/1/51_KJ00004879572/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可