平成12年度12月 最適化とアルゴリズム研究部会
- 日時:12月9日(土) 14:00 〜 17:30
- 場所:上智大学7号館12階第1215号室
- 発表1:武田 朗子 氏 (東京工業大学 数理・計算科学専攻)
-
『組合せ的な条件の付いた線形不等式系の全解列挙に対する
並列計算アルゴリズム』
-
1995年にPolyhedral Homotopy法が提案されて以来,多項式方程式系
の全根列挙問題に関する研究は飛躍的に進歩した.
Polyhedral Homotopy法は従来のHomotopy法に比べて計算量が少なく済む
という素晴らしい性質を持つ反面,Homotopy法に必要な"初期補助方程式
系"を形成するための「組合せ的な条件の付いた線形不等式系の全解列挙」
という新たな問題が生じる.現在,多項式方程式系の全根列挙に必要な計
算時間の約3分の1が,この組合せ問題を解くことに費されており,この部
分の高速化が望まれている.
本発表では,組合せ的な条件の付いた線形不等式系の全解列挙問題に対
して,線形計画問題の解法であるシンプレックス法,および,双対理論を
使ったアルゴリズムを提案する.また,本アルゴリズムに対して効率の良
い並列計算処理が可能であり,その結果,今まで解かなかった規模の問題
まで扱えるようになった.
- 発表2:吉瀬 章子 氏 (筑波大学 社会工学系)
- 『P_0, P_*, 単調な相補性問題に対する内点法』
- 線形計画問題に対する主双対内点法が提案されたごく初期の段階から,この内点法の
自然な拡張として,単調な線形相補性問題に対する内点法が提案されてきた.
タイトルにある P_*, P_0 相補性問題を,この内点法との関連で性格付けるならば,
反復回数を同様な道具立てで導出できるクラスのひとつが P_* 線形相補性問題であり,
内点法の各反復が定義可能であるクラスのひとつが P_0 線形相補性問題であると位置
付けることができる.元来,単調な相補性問題の技術的な拡張と考えられて来た P_*
相補性問題であるが,最近の研究により,特に非線形な P_* 相補性問題が,内点法の
成功に不可欠な中心パスと密接な関係をもつ,大きな役割をもつクラスであることが
わかってきた.本発表では,各クラスの相補性問題,応用例,内点法について概説した
のち,これらの最近の成果を紹介する.また, P_* (非線形)相補性問題に対する解法
として,自己正則(self-regular)な関数を用いた内点法についても言及する.
SOA Home Page へ.