日時：2006年 1月18日（水） 15:00〜18:00 場所：京都大学 本部構内 工学部総合校舎 総合213講義室 講演題目と講演者： ・ 山下 信雄（京都大学 大学院情報学研究科 数理工学専攻） 「スパース構造を利用した準ニュートン法」講演要旨 ・ 平山勝敏（神戸大学海事科学部） 「一般化相互割当問題のための分散ラグランジュ緩和プロトコル」講演要旨
スパース構造を利用した準ニュートン法
山下 信雄（京都大学 大学院情報学研究科 数理工学専攻）
本発表では目的関数のヘッセ行列がスパースとなる大規模な 制約なし最小化問題を考える． 準ニュートン法は制約なし最小化問題の解法の１つであり， すぐれた収束性を持つ．しかし，ヘッセ行列がスパースで あっても，(BFGSやDFPで）生成された近似ヘッセ行列は密な 行列となるため，問題の規模の２乗に比例した計算容量が 必要となる．そのため，大規模な問題には準ニュートン法を 適用することができなかった． 本発表では，ヘッセ行列のスパース構造を利用した近似ヘッセ 行列の更新規則を提案する．提案手法では，まず従来の 準ニュートン公式(BFGS, DFPなど)を用いてスパース構造に 対応した部分行列の更新を行う．次に，その部分行列の (行列式を最大にする)正定値行列補完を求め，その行列を 近似ヘッセ行列とする． 従来(DFP法)と同様の仮定のもとで，提案手法によって生成 される点列が超１次収束することを示す．また，スパース構造が コーダルグラフ(三角化グラフ)に関連した性質を持つとき (持たせれば)，提案手法による近似ヘッセ行列は疎な三角行列の 積として表すことができる．この性質のため，提案手法は従来の 準ニュートン法よりも大幅に少ない計算容量で実装できる．
一般化相互割当問題のための分散ラグランジュ緩和プロトコル
平山 勝敏（神戸大学 海事科学部）
本研究では，一般化割当問題をマルチエージェント環境に 拡張した一般化相互割当問題を提案する．一般化相互割当 問題では，複数のエージェントが各自のジョブを自身あるいは 他のエージェントに割り当てるという状況において，それぞれ の容量制約の下で全体の効用和が最大になるような割当を 求めることが目標となる．また，この一般化相互割当問題の 上下界を求めるピアツーピア型のエージェント間プロトコルと して分散ラグランジュ緩和プロトコルを提案する． 同プロトコルを用いて一般化相互割当問題を解くことにより， 何らかの原因でエージェントに不適切に割り当てられたジョブが， エージェント自身により自律分散的に再配置される． 本講演では，一般化相互割当問題，および，分散ラグランジュ 緩和プロトコルの概要を紹介し，数値実験の結果を報告する．