多項式最適化問題に対する半正定値計画緩和

今年度は,去年度公開した多項式最適化問題に対する半正定値計画緩和を実行するプログラム"SparsePOP"の改良を行った.変数の数や制約式が多い問題においては,入力した問題から半正定値計画問題を構築する部分で,莫大な時間を費やしていたので,主にその部分の改善を行った.これにより,多項式最適化問題の応用例である"センサー配置問題"に対して,センサーの数が1000個の問題に対して,少なくても得られた半正定値計画問題を解くよりも数倍速く,半正定値計画問題を構築することができた."センサー配置問題"とは,温度,音量や光などを精度よく観測する為にワイヤレスセンサーを配置する最適化問題である.なお,この研究は,東工大の小島政和先生と韓国のKim先生との共同研究である.SparsePOPのC++への移植も行っている.半正定値計画問題を解くソルバーとして"SDPA"を利用している.現段階では,まだ完成していないが,ある種の多項式最適化問題に対してはSDPAよりもSeDuMiの方が精度の良い結果を返すことが数値実験でわかった.等式制約を持つ多項式最適化問題に対する半正定値計画緩和では,得られる半正定値計画問題は自由変数と呼ばれる変数を持つ性質がある.自由変数を持つ半正定値計画問題に対しては,しばしば精度の良い結果が得られないことが経験的に知られている.今年度の研究ではできるだけ半正定値計画問題の疎性を壊さずに,自由変数を消去する手法を構築し,数値実験を行った.なお,この研究は,東工大の小島政和先生との共同研究である.

今年度は,去年度公開した多項式最適化問題に対する半正定値計画緩和を実行するプログラム"SparsePOP"の改良を行った.変数の数や制約式が多い問題においては,入力した問題から半正定値計画問題を構築する部分で,莫大な時間を費やしていたので,主にその部分の改善を行った.これにより,多項式最適化問題の応用例である"センサー配置問題"に対して,センサーの数が1000個の問題に対して,少なくても得られた半正定値計画問題を解くよりも数倍速く,半正定値計画問題を構築することができた."センサー配置問題"とは,温度,音量や光などを精度よく観測する為にワイヤレスセンサーを配置する最適化問題である.なお,この研究は,東工大の小島政和先生と韓国のKim先生との共同研究である.SparsePOPのC++への移植も行っている.半正定値計画問題を解くソルバーとして"SDPA"を利用している.現段階では,まだ完成していないが,ある種の多項式最適化問題に対してはSDPAよりもSeDuMiの方が精度の良い結果を返すことが数値実験でわかった.等式制約を持つ多項式最適化問題に対する半正定値計画緩和では,得られる半正定値計画問題は自由変数と呼ばれる変数を持つ性質がある.自由変数を持つ半正定値計画問題に対しては,しばしば精度の良い結果が得られないことが経験的に知られている.今年度の研究ではできるだけ半正定値計画問題の疎性を壊さずに,自由変数を消去する手法を構築し,数値実験を行った.なお,この研究は,東工大の小島政和先生との共同研究である.