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

多项式优化问题的半定规划松弛

基本信息

批准号：
06J05736
负责人：
脇隼人
金额：
$ 1.22万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2006
资助国家：
日本
起止时间：
2006 至 2007
项目状态：
已结题

项目摘要

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

今年，我们改进了去年发布的对多项式优化问题执行半定规划松弛的程序“SparsePOP”。对于具有大量变量和约束表达式的问题，我们由于在在构造规划问题时，我们主要改进了这部分。因此，我们能够改进“传感器放置问题”，这是多项式优化问题的一个应用示例。另一方面，对于具有 1000 个传感器的问题，我们能够比解决使用少量传感器获得的半定编程问题快几倍。“放置问题”是一个问题。布置无线传感器以精确观测温度、音量、光线等的优化问题。这项研究是与东京工业大学小岛正和教授和韩国金教授合作进行的研究。我们还将 SparsePOP 移植到 C++。我们使用“SDPA”作为半定规划问题的求解器。现阶段，它尚未完成，但它适用于某些多项式优化问题。数值实验表明 SeDuMi 返回更多。比 SDPA 更准确的结果。在具有等式约束的多项式优化问题的正定规划松弛中，我们可以得到半定规划问题具有称为自由变量的属性，根据经验可知，具有自由变量的半定规划问题通常无法获得准确的结果，在今年的研究中，我们构建了一种消除自由变量的方法。尽可能破坏半定规划问题的稀疏性，并进行了数值实验。这项研究是与东京工业大学小岛正和教授合作进行的。