第 3 章 多様体上に束縛された非線形力学系による制約条件付最適化 34
3.2 単位シンプレックス上の制約条件付最適化
3.2.1 非線形作用素勾配系モデル
正規化線形等式・非負制約付最適化問題を解く勾配系モデルを考えた場合，制約として
(3.1)式に等式条件が含まれるため，2.2節で考えたように作用素Gを導入して有界領域に
閉じ込めるためモデル(2.4)として，適切なGを恣意的に与えることは容易ではない．そ こで，等式条件の充足には勾配射影法[3, 85, 86, 91]を用い，さらに非負制約の充足を考 えた勾配系モデルを導出する．
(3.1)式の制約領域Xを規定する正規化等式
Xn i=1
xi = 1 (3.3)
の法線ベクトル1= [1,· · · ,1]の直交補空間へ，計量M(x)の下で任意のベクトルを射影 する射影行列は
P1M(x)=I−M(x)−11T(1M(x)−11T)−11 (3.4) で与えられる．ここで，非負制約を考慮し，xi = 0に近いほど対応する勾配成分を縮退さ せるため，
M(x) = diag[1/xi] (3.5)
とおくと，(3.4)式の射影行列P1M(x)は
P1M(x) =I−
x1 · · · x1 ... ... xn · · · xn
(3.6)
となる．したがって，逆勾配−c∇E(x)に計量行列の逆行列M(x)−1を乗じて縮退させて 非負制約を充足させるようにした上で射影行列P1M(x)を用いて単位シンプレックス上に，
−c∇E(x)を射影した方向にxを変化させるモデルは，可変計量勾配射影法モデル1と称 され，
1この文脈における可変計量（Variable Metric）とは，位置xに依存して時間的に連続変化する計量を意味する．一 方，一般に準ニュートン法[3, 14, 23, 65, 91]として知られる可変計量法は，離散時間的に変化（更新）する計量と解
dx(t)
dt =−cP1M(x(t))M(x(t))−1∇E(x(t)) (3.7)
で与えられる[18, 19, 32, 38, 55, 59]．これを成分表現すると，
dxi(t)
dt =−cxi(t)
(∂E(x(t))
∂xi − Xn
j=1
xj(t)∂E(x(t))
∂xj
)
=−c
xi(t)(1−xi(t))∂E(x(t))
∂xi + Xn
j=1 j6=i
(−xi(t)xj(t))∂E(x(t))
∂xj
, i= 1,· · · , n (3.8) となる．この式を(2.6)式と比較すると，
gij(x) =
xi(1−xi), j =i
−xixj, j 6=i
j = 1,· · · , n (3.9)
とおいたことになる．ここで，以下の定理が成り立つことを示す．
定理3.1 (3.9)式のgij(x)を用いた(2.5)式の関数行列G(x)は，(3.1)式で与えられる領 域Xにおいて半正定である．
（証明） 任意のn次元実ベクトルv= [v1,· · · , vn]T に対し，
vTG(x)v = Xn
i=1
Xn j=1
gij(x)vivj = Xn
i=1
xi(1−xi)vi2− Xn
i=1
Xn
j=1 j6=i
xixjvivj
= Xn
i=1
xiv2i − Ã n
X
i=1
Xn j=1
xixjvivj
!
= Xn
i=1
xiv2i − Ã n
X
i=1
xivi
!2
(3.10)
が成り立つ．一方，
¯ v =
Xn i=1
xivi (3.11)
とおくと，等式条件Pn
i=1xi = 1，および非負条件xi ≥0, i= 1,· · · , nのもと，
0≤ Xn
i=1
xi(vi−¯v)2 = Xn
i=1
xi¡
v2i −2vi¯v+ ¯v2¢
= Xn
i=1
xivi2−2¯v Xn
i=1
xivi+ ¯v2 Xn
i=1
xi
= Xn
i=1
xivi2−¯v2 = Xn
i=1
xivi2− Ã n
X
i=1
xivi
!2
(3.12) が成り立つ．したがって，(3.10)式と(3.12)式の同値性から，命題は示された．■
定理3.1より，(3.9)式に対応する関数行列G(x)，すなわち(3.7)式における勾配への作 用P1M(x(t))M(x(t))−1は条件2.1を満たすので，勾配系(3.7)，(3.8)は降下法モデルである ことが示される．
さらに，(2.10)式は dxi duj
=
xi(1−xi), j =i
−xixj, j 6=i
j = 1,· · · , n (3.13)
となり，これを満たす関数f として
xi =fi(u) = expui Pn
j=1expuj, i= 1,· · · , n (3.14) が得られる[55]．この関数は制約領域に対する有界性および全射性は満たすが，単射性は 満足されないために逆関数を与えることはできない．しかし，(3.14)式のf を(2.7) 式へ 当てはめれば，可変計量勾配射影法モデルの内部状態表現を実現することができる．
ところで，(3.8)式の右辺を0とおくことにより，
条件3.1 力学モデル(3.8)の平衡点は，以下の(i)，(ii)のいずれかの条件を満たす．
(i) xi = 0, i= 1,· · · , n，
(ii)
̶E(x)
∂xi − Xn
j=1
xj∂E(x)
∂xj
!
= 0, i= 1,· · · , n．
が得られる．ここで，少なくとも1つの成分について(i)の条件が成り立つとき，xは(3.1)
式で与えられる制約領域Xの境界 bd X =
( x
¯¯
¯ Xn
j=1
xj = 1, xi ≥0, i= 1,· · · , n かつ∃k ∈ {1,· · · , n} xk= 0 )
(3.15) に存在する．さもなければ，x は制約領域Xの内部
intX = (
x
¯¯
¯ Xn
j=1
xj = 1, xi >0, i= 1,· · ·, n )
(3.16) に存在する．このとき，すべての成分が条件3.1の(ii)の条件を満たすことになるが，こ の場合はさらに以下のように場合を分けて考える．
条件3.2 条件3.1の(ii)の場合は，さらに以下の(ii-1)，(ii-2)へ場合分けされる．
(ii-1) ∂E(x)
∂xi = 0, i= 1,· · · , n，
(ii-2) ∃k ∈ {1,· · ·, n} ∂E(x)
∂xk 6= 0，かつ Ã∂E(x)
∂xi − Xn
j=1
xj∂E(x)
∂xj
!
= 0, i= 1,· · · , n．
(ii-1)は，目的関数自体の最小点が制約領域である単位シンプレックス上にちょうど存在
する場合へ対応する．他方，(ii-2)の場合，条件中後者の等式が
∂E(x)
∂xi = Xn
j=1
xj∂E(x)
∂xj = const., i= 1,· · · , n (3.17) と変形され，勾配の全成分が等しい値になることが必要がある．したがって，条件(ii-2) を満たす平衡点は，単位シンプレックス上で勾配が[1,· · · ,1]T 方向に平行する点である り，幾何学的に解釈すればその点における勾配が単位シンプレックス面と直交するため射 影によって潰れてしまう点である．また，これは最適性に関するKarush-Kuhn-Tucker条 件に他ならない．
次に，内部状態表現モデルにおける平衡点について議論する．まず，(3.14)式のfは単 射でなく，決定変数xの1値を与える複数の内部状態量uが存在することを確認する．
具体的には，(3.14)式からxとuとの自明な関係として，
ui(t) = logxi(t), i= 1,· · · , n (3.18)
が見出される[59]．しかし，a6= 0，b= log|a|に対して expui
Pn
j=1expuj
= aexpui aPn
j=1expuj
= aexpui Pn
j=1aexpuj
= expb·expui
Pn
j=1expb·expuj = exp(ui+b) Pn
j=1exp(uj+b) (3.19) がなりたつから，b =−Cとおいて
ui(t) = logxi(t) +C, i= 1,· · ·, n (3.20)
もまた(3.14)式を満足する．これは，xとuの対応関係を2次元の場合を例として図3.1に
示す通り，決定変数空間の1点が，内部状態変数空間では[1,· · · ,1]T を方向ベクトルとす る1本の直線に対応することを意味する．したがって，他の条件なしにxからuを一意 に定めることはできない．
さらに，決定変数に関する平衡点の性質によって場合分けして，内部状態表現モデルと の対応を考えると，以下のことがいえる．
(a) x∈bd Xのとき
xの少なくとも1つの成分，たとえばxk，k ∈ {1,· · ·, n}が制約領域Xの内部int Xか ら境界へ近づくとすると，(3.14)式から
∃k ∈ {1,· · · , n} xk→0 =⇒ uk → −∞ (3.21) となって，内部状態量はその成分に関して負に発散する．
(b) x∈int Xかつ∇E(x) = 0のとき
∇E(x) = 0を(2.9a)式へあてはめると，du/dt =0となるので，内部状態量もその空
間の平衡点になる．この値は，決定変数の平衡点へ一意に対応する内部状態変数空間の直 線に含まれる1点に対応する．
(c) x∈int Xかつ∇E(x)6=0のとき この場合，(3.17)式に対する議論から，
∇E(x) =λ[1,· · · ,1]T, λ6= 0 (3.22) を満たす．したがって，決定変数xは制約領域内部intXである点に収束しても，uは決 定変数の平衡点へ一意に対応する内部状態変数空間の直線，すなわち図3.1のある直線に 沿うように変化し続け，やがて発散する．
2次元の例として，可変計量勾配法の内部状態表現モデルで決定変数が上記(a)〜(c)の 条件にあう平衡点へ収束するとき，対応する内部状態変数のその空間における挙動を示し
た結果は図3.2の通りである．決定変数が制約領域内部で有限値へ収束するにもかかわら ず，内部状態量の発散が起こることはきわめて興味深い．
ところで，集団遺伝学における進化現象の基本モデルとして，複製方程式もしくはレプ リケータモデル[88]と称される力学系
dxi(t)
dt =xi(t){si(x(t))−s(x(t))¯ }
¯
s(x(t)) = Xn
j=1
xj(t)sj(x(t))
(3.23)
がある．ここで，ある集団がn種類の要素から構成されているとするとき，xiは第i要素 が占める割合，si(x)は集団の状態x= [x1,· · · , xn]T に依存した第i要素の適応度，また
¯
s(x)は各要素の適応度をそれぞれの割合で重みづけして和をとった集団全体の平均適応 度である．初期状態を(3.1)式の単位シンプレックス上にとると，(3.23)式によって生成 される軌道x(t)は，その単位シンプレックス上から逸脱することなく時間発展し，すべ ての要素の進化をあらわすものとされている．(3.23)の第2式を第1式に代入すると
dxi(t)
dt =xi(t) (
si(x(t))− Xn j=1
xj(t)sj(x(t)) )
, i= 1,· · · , n (3.24) となり，単位シンプレックス上の非線形作用素勾配系である可変計量勾配射影モデル(3.8) でc= 1とした力学系と比較すると，(3.24)式において
si(x) = −∂E(x)
∂xi , i= 1,· · ·, n (3.25) とおいたものであることがわかる．
なお，レプリケータモデルは，非負領域で定義されるShahshahani計量[89]のもとでの
Riemann多様体上の力学系モデルとして解釈することができる[60, 61] 2．
レプリケータモデルは，生態システムではLotka-VolterraモデルやPrice方程式，分子 システムではQuasispecies方程式など，各種進化モデルと関連づけられるほか[76]，ゲー ム理論への応用[34]をはじめとして，近年でもさかんに研究されている[25, 30, 83]．
2.2節と同様に，関数Eとして2次関数
E(x) =−1 2
Xn i=1
Xn j=1
wijxixj − Xn
i=1
θixi (wij =wji) (3.26)
2Shahshahaniは，(2.1)式の領域Xに対し，x∈X におけるベクトルyとzの内積を，hy,zi=Pn i=1
1 xiyiziと 定義した．これは，(3.5)式を計量行列にとったことに他ならない．
を考えると，
si(x) = Xn
j=1
wijxj +θi (3.27)
となり，この場合(3.23)式は，Fisherが初期に提唱した淘汰方程式となる[22]．このこと を逆に言えば，この淘汰方程式(3.23)は，(3.26)式の2次関数Eを単位シンプレックス上 で最小化する最適化問題，すなわち2次関数最大化問題
maxx
1 2
Xn i=1
Xn j=1
wijxixj+ Xn
i=1
θixi (3.28a)
subject to Xn
j=1
xj = 1, xi ≥0, i= 1,· · · , n (3.28b) を解く力学系のモデルに他ならない．したがって，問題(3.28)に対する複製方程式・淘汰方 程式モデル(3.23)は，−Wを結合係数，−θを閾値として，図3.3に示す相互結合型ニュー ラルネットワークを模した演算回路として実現することができる．文献[60]では，(3.27) のs(x)を用いたレプリケータモデルを，組合せ最適化の計算手法として論じている．
また，統計力学との関連では，スピンモデルを拡張したPottsモデル[101]に対して平 均場近似を適用すると，スピン状態の平均場近似変数は(3.14)の形で与えられ，平均場方 程式は2次関数に対して本項における非線形作用素勾配系の内部状態表現を与えたモデル と同様の構造をとることが示され，文献[81]ではグラフ分割問題に用いられている．ちな みに，グラフ分割問題の特殊な場合が，組合せ最適化における有名な巡回セールスマン問 題（TSP）である．
図 3.1: 決定変数xと内部状態uの対応関係
(a) xが制約領域の境界bd X上の点に収束する場合
(b) xが制約領域の内部int Xで勾配が零となる点に収束する場合
(c) xが制約領域の内部int Xで勾配が零とならない
（単位シンプレックス面に直交する）点に収束する場合 図 3.2: 内部状態量uの軌道
図 3.3: 疑似相互結合ニューラルネットワーク型の演算回路