均衡点問題に対するパス追跡型算法

概要

論文の詳細を見る
Ωをm本の線形不等式a^i・x<__=b_(i⋴M)で決まる1R^nの有界多面体とし、f(x)=Dx+Cを1R^nから1R^nへのアフィン関数とする。このとき、Ωのすべての点xにつ1。、てf(x^^^)・x^^^<__=f(x^^^)・xが成立するΩの点x^^^を均衡点と呼ぶ。均衡点を計算する問題は均衡点問題と呼ばれ、2次計画問題、行列ゲーム、経済均衡問題などから派生する問題である。本論文ではこの問題に対するパス追跡算法を提案する。Ωの各フェイスFに対して、I⫋︀MをFの任意の点xについてa^i・x=b_iが成立する添字iの集合とし、F^*={y|y=Σ__<i⋴1>μ_ia^i、μ_i>__=0(i⋴I)とすると、均衡点問題は、ΩのあるフェイスFに対してx^^^⋴Fかつ-f(x^^^)⋴F^*が成立する点x^^^を求める問題である。Ωの点wを任意に与えられた初期点としたとき、点wを含まないΩのフェイスFに対してwF={x|x=dw+(1-d)z、 z⋴F、 d⋴[0、1]}とし、L={wF×F^*|Fはwを含まないΩのフェイス}とすると、Lはn+1次元の分割多様体となる。Lの各点(x、y)に対してh(x、y)=y+f(x〕とすると、Lの境界は方程式系(1) h(x、y)=0、 (x、y)⋴|L|の自明な解(x^0、y^0)=(w、一f(w))を含む境界と、ΩのすべてのフェイスFについてのF×F^*の和集合で作られる境界とから成る。方程式系(1)はn本の方程式より成っていることと、Lがn+1次元の多様体であることより、正則性の仮定の下で、自明な形ともう一方の境界上の点をつなぐ(1)の解から成る区分的に線形で有限長さのパスが存在する。提案する算法はこのパスを追跡して、(1)を満たし、かつあるフェイスFについて(x^^^、y^^^)⋴F×F^*となる点(x^^^、y^^^)を求める。h(x^^^、y^^^)=0よりy^^^=-f(x^^^)であるから、x^^^は均衡点である。この算法はΩの端点と一般には同数の半直線虫持つ可変次元不動点アルゴリズムと考えることができる。
社団法人日本オペレーションズ・リサーチ学会の論文

均衡点問題に対するパス追跡型算法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク