平成１０年度１０月　ＲＡＭＰの案内

• 日時：10月17日（土） 14:00 〜 17:00
• 場所：上智大学10号館3階322号室

• 発表１：山下信雄氏 (京都大学数理工学専攻）

  『単調な非線形相補性問題に対する近接点法』
  

  本発表では、単調な非線形相補性問題(NCP)の解法として、 「再定式化のアプローチ」、「一般化ニュートン法」、「近接点法」 の３つの手法を組み合わせたアルゴリズムを提案し、その収束性について考察する。 NCPは、等式と不等式のシステムによって構成された問題であり、 そのままの形で扱うことは難しい。 そこで、まず、「再定式化のアプローチ」を用いることによって、 この問題を解きやすい等価な方程式系に変換する。 ただし、このような方程式系を与える写像は一般に微分不可能である。 このため、微分不可能な方程式系に対する「一般化ニュートン法」 を用いて、その方程式を解く。この「再定式化のアプローチ」と 「一般化ニュートン法」の組み合わせた手法は、 これまでに多くの研究者によって提案されてきている。 しかしながら、それらのアルゴリズムが超一次収束するためには、 NCPが扱う写像にある種の正則性の仮定が必要とされていた。 今回の発表ではこの正則性の仮定を外すため、 上記の手法に「近接点法」を組み合わせた手法を提案する。 近接点法は、正則化された部分問題を解くことによって、 次の反復点を求める手法である。 非退化の仮定のもとで、このアルゴリズムが超一次収束することを示す。 今のところ、非退化の仮定を取り除くことはできていない。 その理由について述べ、合わせて、将来の展望を話すつもりである。

• 発表２：茨木俊秀氏（京都大学数理工学専攻）

  『NP困難問題を解く実用的アルゴリズム：現状と課題』
  

  NP困難問題は、困難ではあるが、複雑さのクラスの中では比較的 下位に属し、種々の近似アルゴリズムを適用することができる。実際、 最近の、メタ・ヒューリスティクスの進歩によって、実用的には比較的 扱いやすいとの認識が広がりつつある。今回は、当研究室のアルゴリズム 開発を中心に、種々の問題に対する計算結果を紹介するとともに、 今後の課題、とくに理論的研究の必要性について触れたい。