半正定値計画問題に対する実用的な主双対内点法の実現とその一般公開

半定规划问题实用原对偶内点法的实现及其公开发布

基本信息

批准号：
14750049
负责人：
中田和秀
金额：
$ 1.28万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

项目摘要

研究期間の最終年度となる本年度の研究業績は次の通りである。1.主双対内点法を効率よく並列計算する手法を提案し、MPIを利用することにより実装を行った。そして、東京工業大学松岡研究室のpcクラスタPresto IIIや東京電機大学藤澤研究室のpcクラスタSDPAで実証実験を行った。その結果、開発したソフトウェアは、既存のソフトウェアに比べ非常に高いスケーラビリティを有し、大規模な半正定値計画問題と解くことが可能であることが確認できた。これらの成果は、Journal of Optimization Methoeds and Software誌に掲載予定の論文と東京工業大学数理・計算科学専攻のテクニカルレポートで報告している。さらに、現在2本の論文を投稿中である。2.本研究課題の成果物を多くの人に利用してもらうため、ソフトウェアのソースコードをインターネット上で一般に公開した。ホームページのアドレスはhttp://grid.r.dendai.ac.jp/sdpa/である。これにより、ANSI C準拠のコンパイラがあれば、誰でもすぐに超大規模な半正定値計画問題を解くことが可能となった。また、ソフトウェアのドキュメントは、東京工業大学数理・計算科学専攻のテクニカルレポートとしてまとめた。3.現実社会の問題として、ロバスト・トラッキングエラー最小化問題に適用し、上記の手法の有効性を検証した。この成果は日本オペレーションズ・リサーチ学会誌に掲載されることが決まっている。3年間の研究期間が終了したが、この期間の一連の研究により、当初の目標である、実用的な計算資源で超大規模な半正定値計画問題を解く主双対内点法を実現し、そのソフトウェアをインターネットで一般に公開する、という研究課題は十分に達成することが出来た。

本研究期的最后一年，今年的研究成果如下。 1.提出了一种高效并行计算原对偶内点法的方法，并使用MPI实现。然后，我们在东京工业大学松冈实验室的 PC 集群 Presto III 和东京电机大学藤泽实验室的 PC 集群 SDPA 上进行了演示实验。结果证实，所开发的软件比现有软件具有更高的可扩展性，能够解决大规模半定规划问题。这些结果发表在《优化方法与软件杂志》上计划发表的论文以及东京工业大学数学与计算科学系的技术报告中。此外，目前正在提交两篇论文。 2.为了让更多人使用本研究项目的成果，该软件的源代码在互联网上向公众开放。主页地址是http://grid.r.dendai.ac.jp/sdpa/。这使得任何拥有 ANSI C 兼容编译器的人都可以立即解决极其大规模的半定编程问题。此外，该软件文档由东京工业大学数学与计算科学系汇编为技术报告。 3.通过将其应用于鲁棒跟踪误差最小化问题作为实际问题，验证了上述方法的有效性。研究结果将发表在日本运筹学会杂志上。三年的研究期现已结束，通过这段时间的一系列研究，我们实现了最初的目标：用原对偶内点法求解超大规模正半定规划问题实际的计算资源，我们已经实现了这个目标，我们能够完全实现我们的研究目标，即在互联网上向公众提供软件。