二次計画問題の狭小な半正定値緩和に基づく多項式最適化の大域的解法の展開

点击翻译按钮获取中文摘要

本研究は多項式最適化問題の正確な最適解を計算できる条件の解析を通じて、多項式最適化問題の計算方法の構築を目指している。本年度は研究計画に従い、多項式最適化問題の正確な最適解を計算できる条件の解明について取り組んだ。まず、多項式最適化問題に関して、対応する二次制約付き二次計画問題を正確に解くことができるかを比較しながら予備的な計算機実験を行った。多項式最適化問題を二次制約付き二次計画問題へ変換する際にその手順は一つに定まらず、対応する二次制約付き二次計画問題は複数存在することから、この実験はそれらの問題の計算可能性と性質を比較することが目的である。変数や制約の数が少ない問題であっても、最適解を計算できる問題へ定式化するための規則性が観測されなかったことから、全ての多項式最適化問題を一括で扱える理論的条件の不適当さが示された。また、2次の多項式最適化問題として定式化可能なランク1行列補完問題に対しては、前処理後の2階のLasserre階層の双対問題を考えたとき、常に退化次数が1である最適解を構成できることを示した。近年提案されたランク1行列補完問題を正確に解くための条件では、鎖構造が連結していることを用いて、双対解の退化次数が1になることを示すことが鍵となっている。本研究の結果は鎖構造を必要としておらず、既存研究の条件を更に緩和するために活用できる。実際に、斉次の等式制約を二乗することで不等式制約に置きかえることによって、鎖構造という条件を無視できることが予備実験で確認できた。