特別研究報告書
非線形相補性問題に対する 近接点法の実用性に関する考察
指導教官 福嶋 雅夫 教授 山下 信雄 助手
情報学科数理工学コース平成8年度入学
田島 潤
平成12年2月15日提出
非線形相補性問題に対する 近接点法の実用性に関する考察
田島 潤
摘要
経済，生産計画，システム設計などさまざまな分野において現れる問題は，しばしば非線 形相補性問題として定式化される．非線形相補性問題に対して，これまでにその性質に関 する多くの解析がなされ，またこの問題を解くためのさまざまなアルゴリズムが提案され てきた．そのようなアルゴリズムの中でも近接点法は，扱う関数に対する比較的緩い条件 のもとで優れた収束性を持つことが理論的に示されている．ところが，非線形相補性問題 に対する近接点法の実装に関する報告やその実用性についての研究はあまり行われてい ない．
本報告書では，まず近接点法の実装に際して困難を伴う点を指摘する．次に，その考察 に基づいてアルゴリズムの実装法を提案する．具体的には，部分問題に対する終了条件を 工夫することによってより少ない反復数で解が得られるようにアルゴ リズムを改良する．
このアルゴリズムに対して，いくつかの問題を用いた数値実験を行い，その実用性に関す る性能評価をした．その結果，初期点やパラメータを非常に巧妙に選ばないと解が得られ ないような問題もわずかながら存在したが，大部分の問題に対しては解を効率良く求めら れることがわかった．
目 次
1 序論 1
2 準備 2
2.1 数学的概念 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2
2.2 非線形相補性問題の再定式化: : : : : : : : : : : : : : : : : : : : : : : : : : 3
3 非線形相補性問題に対する近接点法 4
3.1 近接点法の概要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
3.2 部分問題の解法 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
3.3 アルゴ リズムPP : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6
4 近接点法の実装上の問題点とその解決法 7
4.1 近接点法の実装上の問題点 : : : : : : : : : : : : : : : : : : : : : : : : : : : 7
4.2 改良1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
4.3 改良2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9
5 数値実験 9
5.1 実験内容 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 10
5.1.1 実験1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
5.1.2 実験2 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13
5.2 実験結果 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14
6 結論 14
1
序論
昨今，経済，生産計画，システム設計などさまざまな分野において，オペレーションズ リサーチの手法が用いられその有効性が報告されている．そのようなオペレーションズリ サーチで扱われる問題は，しばしば相補性条件を含む数学モデルとして定式化される．な お，2つのベクトルx=(x1
;111;x
n )
T
;y=(y
1
;111;y
n )
Tに対して，
x
i
0; y
i
0; x
i y
i
=0; (i=1;111;n)
が成り立つとき，つまり2つのベクトルの各成分が非負であり，さらにそれらの少なくと も一方が0となるようなとき，ベクトルxとyは相補性条件を満たしているという．
相補性条件を含む問題の例として以下のものが挙げられる．多くの最適化問題は制約つ き非線形最小化問題として定式化することができる．この問題における局所的最適解の必 要条件は相補性条件を含むカルーシュ1キューン1タッカー条件として記述できることが知 られている[2]．また，複数の利害の異なる意思決定者が各々の利益を最大にするように 行動するようなゲームにおいて，このゲームの戦略の均衡点を求める問題は相補性条件を 伴った数学モデルで記述される[2,4]．他にも，2段階計画問題などの均衡制約を持つ数理 計画問題は制約条件に相補性条件を持つ数理計画問題と考えることができる[4]．このよう に，幅広い分野の問題が相補性条件を含む数学モデルに定式化されるので,相補性条件をと もなった問題を考察することは非常に重要である．本報告書では，相補性条件を含む問題 の中でも最も代表的な問題のクラスである非線形相補性問題(NonlinearComplementarity Problem, NCP)と呼ばれる問題を扱う．
非線形相補性問題は，与えられた写像F :<n!<nに対し,次のような条件を満たすベ クトルx2<nを求める問題である[10]．
[NCP(F)] F(x)0; x0; hx;F(x)i=0
ここで，h1;1iはベクトルの内積を表す．F(x)0;x 0という条件のもとで，hx;F(x)i=0 が成り立つためには，すべてのiに対して，xi
F
i
(x)=0が成立しなければならない，この
ことよりNCP(F)が相補性条件を含む問題であることがわかる．また，Fがアフィン関数
であるときは線形相補性問題という．非線形相補性問題に定式化される問題には，不等式 制約つき非線形最小化問題や，非協力ゲームのナッシュ均衡点を求める問題などがある．
非線形相補性問題については，これまでにその性質について多くの解析がなされ，また この問題を解くためのさまざまなアルゴリズムが提案されてきた[1]．そのようなアルゴリ ズムの1つに近接点法(ProximalPointAlgorithm,PPA)がある．近接点法は，扱う関数 に対する比較的緩い条件のもとで優れた収束性を持つことが理論的に示されており[12,9]， 従来のアルゴ リズムに比べて問題をより効率良く解くことが期待されている．ところが，
非線形相補性問題に対する近接点法が実装されたという報告はほとんどされておらず，そ の実用性についてはこれまでよく分かっていない．一方，オペレーションズリサーチの手 法を用いて社会的な問題を解決する立場から見ると，アルゴリズムを実装して実用に耐え 得るものにすることは重要である．
本報告書では，数値実験を通して近接点法の実用性について考察を行う．そのために，
まず近接点法の実用化に際しての課題を指摘する．次に，その考察に基づいてアルゴリズ
ムの実装法を提案する．さらに，いくつかの問題に対して近接点法を用いた数値実験を行 い，その実用性に関する性能評価をする．
2
準備
ここでは，本報告書で必要となる数学的な概念を導入する．また非線形相補性問題を等 価な方程式系，または最小化問題に再定式化する手法を紹介する．
2.1 数学的概念
この節では,以下の議論に必要となるいくつかの関数のクラスやB微分の導入を行う．
定義 1
(a) 関数Fに対して，次の関係式が成り立つときFは単調であるという．
hx0y;F(x)0F(y)i0 8x;y2<
n
(b) 関数Fに対して，次の関係式が成り立つときFは係数>0の強単調であるという．
hx0y;F(x)0F(y)ijjx0yjj 2
8x;y2<
n
(c) 関数Fに対して，次の関係式が成り立つときFはP0関数であるという．
max
i:x
i 6=y
i (x
i 0y
i )(F
i
(x)0F
i
(y))0 8x;y2<
n
;x6=y
本報告書で考察する近接点法の収束性はFの単調性などと密接な関係がある[10]．また，
この定義より明らかに強単調な関数は単調であり，単調な関数はP0関数である．
本報告書で扱うNCP(F)に対する近接点法では，次節で導入するNCP(F)と等価な方 程式系をニュートン法型の手法で解く．ニュートン法を適用するには,方程式を表す関数 の微分が必要である．しかし，等価な方程式系を構成する関数の多くは微分不可能な関数 である．そこで，微分不可能な点に対して微分の概念を拡張したB微分という概念を導入 する．
定義 2 H :<n ! <mを局所リプシッツ連続関数とする．そのとき，次式で定義される
m2n行列の集合をHのxにおけるB微分という．
@
B
H(x):=f lim
x i
2D
H
;x i
!x H
0
(x i
)g
ここでDHはHが微分可能な点の集合である．
ニュートン法では次の反復点を求めるために，扱う関数のヤコビ行列が正則である必要 がある．そこで，B微分の正則性に関連した次の概念を定義する[7]．
定義 3 点x3 2<nにおいて，すべてのV 2@B H(x
3
)が正則行列であるとき, x3はHに 関してBD正則であるという．
この定義より，Hに関してBD正則である点xでは，どのようなV 2 @BH(x)をとっ てもV の逆行列が存在することがわかる．
2.2 非線形相補性問題の再定式化
この節では, ある関数Gに対する非線形相補性問題NCP(G)を等価な方程式系または 最小化問題に再定式化する方法について述べる．
NCP(G)の解x3において，各々のiに対してx3
i
= 0またはGi (x
3
) = 0が成り立つ．
よって，すべての組合せをしらみ潰しに調べれば解が得られるが，この組合せは2n通り あり全ての可能性を列挙していくのは現実的ではない．そこで，NCP(G)を等価な方程式 系に再定式化することによってNCP(G)を解くアプローチが，近年活発に研究されてい る[9, 10,12]．
NCP(G)を等価な方程式系に再定式化するために，次のような性質を持つ関数:<2!<
を考える．
(a;b)=0()a0;b0;ab=0
このような性質をもつ関数をNCP関数と呼ぶ．この関数を用いて，HG :<
n
!<
nを
H
G (x):=
0
B
B
@ (x
1
;G
1 (x))
.
.
.
(x
n
;G
n (x))
1
C
C
A
と定義すれば，NCP(G)は方程式
H
G
(x)=0
と等価であることがわかる．
NCP関数としては，例えば
(a;b)=minfa;bg
(a;b)=0ab+ 1
2
minf0;a+bg 2
などが考えられるが，ここでは次のような関数FB :<
2
!<を用いる[3]．
FB
(a;b):=a+b0 p
a 2
+b 2
この関数はFischer-Burmeister関数と呼ばれ, 他のNCP関数に比べ多くの利点があるた め，近年よく用いられている[10]．Fischer-Burmeister関数から定義されるHGは，関数
Gが微分可能であればあるiに対してxi
=G
i
(x)=0となる点を除いて微分可能である．
また，至るところでB微分可能である．
次に，関数HGを用いて, メリット関数8G :<n!<を次式で定義する．
8
G (x):=
1
2 jjH
G (x)jj
2
NCP(G)と方程式(2)は等価であるので,関数8GはNCP(G)の解において，大域的最小 値0をとる．よって，NCP(G)は8G
(x)を最小化する問題とも等価である．このメリット 関数は反復法においてステップサイズを決めるときや,エラーバウンド 性を保証するのに 用いられる．また，8Gは微分可能な関数である．
3
非線形相補性問題に対する近接点法
この節では，文献[9,12]などで提案された近接点法のアルゴリズムおよびその性質を紹 介する．
3.1 近接点法の概要
NCPに対するPPAは次のように記述できる．点xk2<nが与えられたとき，問題
[NCP(F k
)] F(x k
)0; x0; hx;F k
(x)i=0
の解をxkに対する近接点(proximalp oint)と呼び,Pk (x
k
)と表す．ここで，Fk:<n!<n はパラメータck
>0を用いて
F k
(x):=F(x)+c
k (x0x
k
)
で定義される関数である．NCP(Fk)は正則化項ck(x0xk)があるため，NCP(F)よりも解 きやすい問題となっている．PPAは，任意の初期点x0から始めて,反復公式xk +1=Pk(xk) によって近接点の点列fxkgを生成していく反復法である．このときckの値が大きくなる と部分問題NCP(Fk)は解きやすくなるが，FとFkの差が大きくなるため，NCP(Fk)は
元の問題NCP(F)からかけ離れた問題になる．一方ckが0に近くなると，部分問題は扱
いにくくなるがもとの問題に近くなる．したがって，PPAの収束特性はパラメータckの 更新の方法に大きく依存する．このことは，超一次収束性などの理論的証明において顕著 である．なお，5節において数値実験によりこの依存性を確かめている．
各反復において，近接点を正確に求めることは容易ではないが,Ro ckafellar[8]は，近接 点を正確に求めなくても,点列fxkgがNCP(F)の解に収束するためのある近似基準を提 案した．
近似基準 1:
jjx k +1
0P
k (x
k
)jj
k
minf1;jjx k +1
0x k
jjg
1
X
k =0
k
<1;
k
0(k=0;1;111)
近接点法では
1. 部分問題の正確な解が分からない状態で近似基準1を満たしているかをどのように 判断するか
2. 部分問題をど う解くか
が重要な問題となる．前者については，次の補題が示すエラーバウンド 性を用いることに より，解決することが可能である．
補題 1 [エラーバウンド 性][6]
Fが単調かつ，係数L>0のリプシッツ連続関数であれば，jjHF k
(x)jjはNCP(Fk)に 対する大域的エラーバウンドを与える．つまり，
jjx0P
k (x
k
)jj
B(L+1)
c
k jjH
F
k(x)jj 8x2<
n
が成り立つ．ここで，BはFkに依存しない正の定数である． □ 後者の部分問題の解法については次節で考察する．
3.2 部分問題の解法
この節では，NCP(F)においてPPAによって生成される部分問題NCP(Fk)を解く方 法について説明する．部分問題を解くのにはDeLuca, Facchinei,Kanzow[1]によって提 案された一般化ニュートン法(GeneralizedNewtonmethod)を用いる．以下に，そのアル ゴ リズムを示す．
手続きGN (NCP(Fk)に対する一般化ニュートン法)
Step 1: パラメータ2(0;1
2
);p>2および2(0;1)を選ぶ．y0 :=xk; j:=0とする．
Step 2: もしyjがNCP(Fk)の近似解であれば終了する．
Step 3: 行列Vj 2@
B H
F k(y
j
)を選び,ニュートン方程式
V
j
d=0H
F k(y
j
)
を解いて探索方向djを決める．もし，
hd j
;r8
F k(y
j
)i0jjd j
jj p
が成り立たないならば，
d j
=0r8(y j
)
とする．
Step 4: もしyj+djがNCP(Fk)の近似解であれば終了し,そうでなければ，以下の式を 満たすもっとも小さい非負整数iを求め,それをijとおく．
8
F k
(y j
+2 0i
d j
)08
F k
(y j
)2 0i
hd j
;r8
F k
(y j
)i
Step 5: y j+1
:=2 0i
j
d j
;j :=j+1として，Step2へ. ここで，手続きGNに対し次の定理が成立している[1]． 定理 1 手続きGNで生成される点列の任意の集積点は関数8F
kの停留点である．
また，近接点法で定義されるFkおよびFkから定義されるHF k;8
F
kに対し，次の補題 が成立する[1, 9,12]．
補題 2
(a) FがP0関数であれば，任意のx 2<nにおいて，全てのV 2@B H
F
k(x)は正則行列 である．
(b) FがP0関数であれば，limjjxjj!1 8
F k
(x)=1が成り立つ．
(c) FがP0関数のとき，関数8F
kの停留点はNCP(Fk)の解である．
この補題と定理1により，FがP0関数ならば手続きGNで生成される点列はNCP(Fk) の解に収束することがわかる．よって，手続きGNは有限回の反復で終了する．
3.3 アルゴリズムPP
この節では，NCP(F)に対するPPAのアルゴリズムを紹介する．文献[9, 12]で提案さ れたアルゴリズムは以下のように記述される．
アルゴリズムPP
Step 1: パラメータ2(0;1); c0 2(0;1)と初期点x02<nを選ぶ．k:=0とする．
Step 2: もしxkがNCP(F)の近似解であれば,終了する．
Step 3: 関数Fk :<n!<nを
F k
(x):=F(x)+c
k (x0x
k
)
で定義し,次の条件を満たすNCP(Fk)の近似解xk +1を手続きGNを用いて求める．
jjH
F k(x
k +1
)jj k
minf1;jjx k
0x k +1
jjg (1)
ここで，kはのk乗をあらわす．
Step 4: c
k +1を更新し,k:=k+1として，Step2へ．
Step3の条件1は，近似基準1を保証するための条件であり，jjHk
F
(x)jjがNCP(Fk)に 対するエラーバウンドを与えるときには，この条件は近似基準1と等価な条件となる．
アルゴ リズムPPの大域的収束性に関しては,次のような定理が成り立つ[9,12]． 定理 2 [大域的収束性]
(a) 関数Fは単調かつリプシッツ連続であり,fckgは有界であるとする．NCP(F)が少なく とも一つの解を持てば，アルゴリズムPPによって生成される点列fxkgは,NCP(F) のある解に収束する．
(b) FがP0関数であり，NCP(F)の解集合は空でなく有界であるとする．このとき，アル ゴ リズムPPによって生成される点列fxkgに対して，ck
x k
!0が成り立てばfxk g
は有界となりその任意の集積点はNCP(F)の解である． □ アルゴ リズムPPの収束の速さについて以下の定理が成り立っている[9,12].
定理 3 [超一次収束性]
c
k
!0とする．このとき，以下のことが成り立つ．
(a) 関数Fが単調でアルゴリズムPPによって生成される点列fxkgはNCP(F)の解x3に 収束するとする．このとき，jjHF(x)jjがx3の近傍でNCP(F)に対する局所的エラーバウ ンドを与えるならば，数列fdist(xk;X)gは0に超一次収束する．ここで，XはNCP(F) の解集合である．
(b) アルゴリズムPPによって生成される点列fxkgの集積点の一つx3がHF に関してBD 正則であれば，点列fxkgはx3に超一次収束する． □
また，部分問題を解く速さに関して次の定理が成立している[10]．
定理 4 FがP0関数であり，アルゴ リズムPPで生成される点列はNCP(F)のある解x3 に収束するとする．このとき，x3がHF に関してBD正則でありck
=O(jjx k
0P
k (x
k
)jj)
であるならば，十分大きいkに対して, NCP(Fk)に対する一般化ニュートン法の一回の 反復で得た点はアルゴリズムPPのStep3の条件(1)を満たす． □
定理4の条件を満たすckの更新規則としては
c
k
:=minf k
;8
F (x
k
)g (2)
が考えられる.
よって，アルゴリズムPPはFが単調であるか解集合が有界なP0関数であれば解に超 一次収束するという優れた性質を持つことがわかる．一方，このアルゴ リズムには理論的 に優れた性質を持つということだけでなく実用上優れた性質を持つことも求められ，この 観点からアルゴリズムの実装は非常に重要である．次節ではアルゴリズムの実装法につい て考察する．
4
近接点法の実装上の問題点とその解決法
4.1 近接点法の実装上の問題点
アルゴリズムPPが理論的に優れた性質を持つことはすでに述べた．一方，このアルゴ リズムに対して実装上の課題として次の点があげられる．
アルゴリズムPPでは反復の初期の段階において，部分問題を解くために手続きGN の反復数が多くなることが予想される．これは，条件(1)において初期点x0の情報 が用いられておらず，一般に手続きGNの終了条件が厳しくなりすぎてしまうから である．
一般にはFがP0関数でないようなNCP(F)も多いが，このようなときに手続きGN で条件(1)を満たす点を見つけることができず，アルゴリズムPPが終了しないとい う事態が起こり得ることがわかる．
そこで，次節では上記の課題を克服する手法を与える．
4.2 改良1
前節でも触れたようにアルゴ リズムPPでは，反復の初期段階で部分問題に対する手続 きGNの反復数が多くなることが予想される．そこで，理論的に解への大域的収束性や超 一次収束性が保たれる範囲で近似条件を緩和することを提案する．
まず，条件(1)の代わりに次の条件を考える．
jjH
F k(x
k +1
)jjM
k
k
minf1;jjx k
0x k +1
jjg (3)
ここで，kはのk乗をあらわす．また，Mkはある正の定数b1
;b
2に対してb1
<M
k
<b
2
を満たすパラメータである．
以下に，この条件を取り入れたアルゴ リズムPP2を示す．
アルゴリズムPP2
Step 1: パラメータ 2(0;1);c0
2(0;1)と初期点x0 2<nを選ぶ．また，k:= 0とし，
定数M0
ge0を選ぶ．
Step 2: もしxkがNCP(F)の近似解であれば,終了する．
Step 3: 関数Fk :<n!<nを
F k
(x):=F(x)+c
k (x0x
k
)
で定義し,次の条件を満たすNCP(Fk)の近似解xk+1を一般化ニュートン法を用い て求める．
jjH
F k
(x k +1
)jjM
k
k
minf1;jjx k
0x k +1
jjg
Step 4: c
k +1
;M
k +1を更新し,k:=k+1として，Step2へ．
アルゴ リズムPP2に対しても，定理2，定理3，定理4が成立することが示せる．
また，定数Mkの選び方としては，
M
k :=
jjH
F 0(x)jj~
minf1;jjx 0
0xjjg~
(k=0;1;111)
などが考えられる．ここで，x~はNCP(F0)に対して,一般化ニュートン法による反復を1 回適用して得られる点である．なお，このように定義されたMkはkに依存しない定数で ある．こうすることによって，初期の段階において一般化ニュートン法による反復数を少 なくすることができる．
4.3 改良2
FがP0関数でないような場合には，アルゴリズムPPおよびアルゴ リズムPP2は必ず
しもNCP(F)の解に収束するとは限らない．実際に，手続きGNにおいて部分問題の解
でないような停留点に収束してしまうことがしばしばある．このような場合，手続きGN で生成される点列は終了条件(1)を満たすことができず，手続きGNは無限ループに陥っ てしまう．
そこで，終了条件(1)を次の条件に置き換えることを提案する．
jjr8
F k(x
k +1
)jjM k
minf1;jjx k
0x k +1
jjg (4)
ここで， 2(0;1)は定数である．こうすることによって8F
kの停留点の十分近くの点に おいて，手続きGNは終了条件を満たすことができる．
このような変更によって，一般には近接点法のNCP(F)の解への大域的収束性は理論 的な保証ができなくなる．しかしながら，Fが単調な場合は以下に示すように大域的収束 性を保証することができる．
定理 5 Fが単調な関数でNCP(F)が少なくとも1つの解を持ち，全てのkに対してk
k
c
kを満たす定数 2(0;1)が存在するとする．このとき，条件(4)を部分問題の終了条 件として用いたアルゴリズムPP2はNCP(F)のある解に収束する． □ 証明 Vkを@BHF
k (x
k
)の任意の要素とする．ここで，Fが単調な関数であれば，次の不等 式が成り立つような正の定数Cが存在する[10]．
jjV 01
k jj
C
c
k
これより，条件(4)が満たされるとき，
jjH
F k(x
k +1
)jj jjV 01
k jjjjV
T
k H
F k(x
k +1
)jj
C
c
k jjr8
F k
(x k +1
)jj
CM
k
c
k
k
minf1;jjx k
0x k +1
jjg
CM
k
k
minf1;jjx k
0x k +1
jjg
となり，条件(3)が成り立つ．したがって，この定理が成立することが分かる． □
Fが単調でない場合には，一般にNCP(F)の解に収束することは望めないが，手続き
GNの終了条件を変更したことにより，少なくともアルゴリズムが有限回の反復で終了す ることは保証できる．なお，これ以降アルゴ リズムPP2においてStep 3の終了条件(3) を(4)で置き換えたアルゴリズムをアルゴリズムPP3と呼ぶこととする．
5
数値実験
3節では，近接点法について説明し，この方法が理論的に優れた性質を持つことを紹介 した．また4節では，近接点法を実装する際の課題を指摘し，その解決法を提案した．こ
こでは，本報告書で紹介または提案したアルゴリズムを用いていくつかの問題に対し数値 実験を行い，その性能について評価する．
5.1 実験内容
本報告における実験では，7つのテスト問題を扱った．プログラムはc言語でコーディ ングし，サンマイクロシステム社のSun sparc 60上で実験を行なった．
本実験では，以下の項目について比較した．
正則化パラメータckの更新規則によるアルゴ リズムPPの収束速度の変化
アルゴリズムの違いによる収束速度の変化 手続きGNのStep3においてVj
2@
B H
F k
(y j
)を計算する必要があるが，これまでその具 体的な計算法には触れなかった．ここでは，その計算法について説明する．Vj
2@
B H
F k(y
j
)
は次のような形になる[1]．
V
j
=D
a +D
b rF
k
(x) T
ただし，Da;Dbは対角成分が,
((D
a )
ii
;(D
b )
ii )=
8
<
:
10 x
i
p
x 2
i +F
k
i (x)
2
;10 F
k
i (x)
p
x 2
i +F
k
i (x)
2
if (x
i
;F k
i
(x))6=(0;0)
(10
i
;10
i
) otherwise
で与えられる対角行列であり,(i
;
i )は2
i +
2
i
=1を満たす点であり，次の計算法によっ て求めることができる[1]．
(
i
;
i
)の計算法
Step 1: D:=fijx
i
=F k
i
(x)=0gとおく．
Step 2: i2Dとなるすべてのiに対してzi
6=0となるz2<nをとる．
Step 3: i2Dに対して，
(
i
;
i )=(
z
i
q
z 2
i
+(rF k
i (x)
T
z) 2
;
rF k
i (x)
T
z
q
z 2
i
+(rF k
i (x)
T
z) 2
)
とする．
各実験において，初期点の各成分は[0;100]の一様乱数で生成した．各実験で比較検討する アルゴリズムに対して，100回初期点を生成し，そのアルゴリズムが終了条件を満たすまで に解いたニュートン方程式の回数を測定した．各アルゴリズムの終了条件はjjr8F
(x)jj 2
<
10
08とし，各アルゴリズムに共通するパラメータは =0:8;=0:01; =1008;p=2:4 に固定した．各アルゴリズムに対して，反復回数の上限は200回とし，反復がこの上限に 達した場合は解は得られなかったものとして直ちに終了した．同様に，手続きGNに対し ても反復回数の上限を200回と定めた．
次に，本実験で用いた問題の説明をする．
問題1 線形相補性問題F(x)=Mx+q. ここで，x2<100であり，
M = 0
B
B
B
B
B
B
B
B
B
@
4 01 0 ::: 0
01 4 .
.
. .
.
. .
.
.
0 .
.
. .
.
. .
.
.
0
.
.
. .
.
. .
.
.
4 01
0 ::: 0 01 4 1
C
C
C
C
C
C
C
C
C
A
である．またqの第i成分ははqi
=sin
2
iである．この問題は単調なLCPとなる．
問題2 線形相補性問題F(x)=Mx+q. ここで，Mは
P
0
=
1 02
02 4
!
; Q
0
=(5)
P
k +1
= P
k 0A
T
k
A
k Q
k
!
; Q
k +1
= 0
B
@ Q
k 0B
T
k 0C
T
k
B
k P
k O
C
k
O Q
k 1
C
A
; (k=1;2;111)
A
k
= 0
B
B
@
03 111 03
.
.
. .
.
. .
.
.
03 111 03 1
C
C
A
; B
k
= 0
B
B
@
01 111 01
.
.
. .
.
. .
.
.
01 111 01 1
C
C
A
; C
k
= 0
B
B
@
4 111 4
.
.
. .
.
. .
.
.
4 111 4 1
C
C
A
としたときに，M =P5 2 <
1232123
となるような行列である．また，qの第i成分 は，qi
=(01) n
iである．一般に行列X ;Y;Zに対してX ;Y が半正定値ならば，行列
X 0Z T
Z Y
!
も半正定値となる．したがって，この問題においてMは半正定値であり，この問題 は単調なLCPとなる．
問題3 線形相補性問題F(x)=Mx+q. ここで，MはM =ATAと表され，A2<502100 の各成分は[0;1]の一様乱数である．このときMはランクが落ちるので半正定値で あるが正定値ではない．また，qの各要素は[01;1]の一様乱数である．このとき，問 題3は単調なLCPとなる．
問題4 非線形相補性問題[11]
F(x)= 0
B
B
B
B
@
0 0 0 0
0 1 01 0
0 1 1 0
0 0 0 1
1
C
C
C
C
A 0
B
B
B
B
@ x
1
x
2
x
3
x
4 1
C
C
C
C
A +
0
B
B
B
B
@ x
3
1
x 3
2
2x 3
3
2x 3
4 1
C
C
C
C
A +
0
B
B
B
B
@ 08
3
03
0 1
C
C
C
C
A
この問題において，関数Fは単調である．また解はx=(2;0;1;0)であり，x2
;x
4は 退化している．ここで，解が退化しているとは，あるiに対してxi=Fi(x)=0が 成り立つことをいう．
問題5 線形相補性問題
F(x)=Mx+q
ただし，M2<10210;q2<10はそれぞれ次のように与えられる．
M = 0
B
B
B
B
B
@
1 04 111 04
0 .
.
. .
.
. .
.
.
.
.
. .
.
. .
.
.
04
0 111 0 1 1
C
C
C
C
C
A
; q= 0
B
B
B
B
B
B
B
B
B
B
B
B
@ 0
1
0
01
0
.
.
.
1 1
C
C
C
C
C
C
C
C
C
C
C
C
A
この問題の解はx=(60096;12019;2404;481;96;19;4;1;0;0)T である．また，Fは
P
0関数である．
問題6 非線形相補性問題[5]
F(x)= 0
B
B
B
B
@ 3x
2
1 +2x
1 x
2 +2x
2
2 +x
3 +3x
4 06
2x 2
1 +x
2
2 +x
1 +10x
3 +2x
4 02
3x 2
1 +x
1 x
2 +2x
2
2 +2x
3 +9x
4 09
x 2
1 +3x
2
2 +2x
3 +3x
4 03
1
C
C
C
C
A
これは，Kojima-Shindoの問題と呼ばれ，解は
x 1
=( p
6
2
;0;0;5); x 2
=(1;0;3;0)
の2点である．この問題の関数Fは，単調な関数でもP0関数でもない．
問題7 非線形相補性問題
F(x)= 0
B
B
@ F
1 (x)
.
.
.
F
n (x)
1
C
C
A
ここで，
F
i
(x)=rC
i (x
i
)0p()0x
i
rp()0; (i=1;111;n)
また，
p()=5000 1
0
1
C
i (x
i )=c
i x
i +
i
1+
i L
i
i x
i +1
i
i
= n
X
i=1 x
i
である．この問題は非協力ゲームのナッシュ均衡点を求める問題を定式化した際に 現れる．また，本実験では各パラメータは次のように設定した．
n=10; =1:2
c= 0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@ 5
3
8
5
1
3
7
4
6
3 1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
; L= 0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@ 10
10
10
10
10
10
10
10
10
10 1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
; = 0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@ 1:2
1
0:9
0:6
1:5
1
0:7
1:1
0:95
0:75 1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
この問題は，MCPLIBにnash.gmsという名前のGAMSファイルとして登録されて いる[2]．
5.1.1 実験1
実験1では正則化パラメータckの更新規則によって，アルゴリズムPPの反復回数がど のように変化するかを調べた．ここで，比較した更新規則は以下のものである．
c
k
=minf k
;8
F (x
k
)g
c
k
= k
c
k
=minf k
;8
F (x
k
) 2
g
c
k
=minf k
; q
8
F (x
k
)g
c
k
= k
minf1;
1
jjx k
jj g
ここで，はアルゴ リズムPPのStep3で用いられると同じものである．
5.1.2 実験2
実験2ではアルゴリズムによって，反復回数がどのように変化するかを調べた．ここでは次 のアルゴリズムを比較した．また，実験2においてはckの更新規則はck=minfk;8F(xk)g を用いた．
アルゴリズムPP
アルゴリズムPP2
アルゴリズムPP3
一般化ニュートン法
ここで，一般化ニュートン法は[1]で提案されているアルゴ リズムで，NCP(F)を方程 式HF(x) =0に再定式化した後，それに直接一般化ニュートン法を適用するアルゴ リズ ムである．
5.2 実験結果
実験1および実験2の結果を表1，表2に示す．
なお，表中の数字はニュートン方定式を解いた回数，括弧内は近接点法の反復数を示し ている．また，求解率は解が得られた割合を%で表している．ただし，ここで解が得られ なかったものとして扱っているものには反復があらかじめ指定していた回数を越えたもの も含まれている．また，Best, Worst,Meanはそれぞれ100回計算を行った中での最小反 復回数，最大反復回数，平均反復回数を示している．なお，ここでは規定回数で解が得ら れなかったものは除外している．
実験1の結果を見ると，パラメータckの更新についてはck
= k
minf1;
1
jjx k
jj
gが他の規 則と比べて多少良い収束性を持つことが分かる．しかし，問題5のようにこの更新規則を用 いるとほとんど解が得られなくなってしまう例もある．他の4つの更新規則についてはあま り差が認められなかったが，理論的な収束性なども考慮に入れるとck
=minf k
;8
F (x
k
)g
を用いるのが妥当だといえる．
次に，実験2の結果について考察する．まず，アルゴリズムPPとアルゴリズムPP2を 比較する．表2より，アルゴリズムPP2のニュートン方程式を解いた回数は，ほとんどの 問題に対してアルゴ リズムPPの回数の半分から3分の1であることがわかる．これは，
アルゴ リズムPP2が緩和された近似条件を用いているため，近接点法の初期の反復にお ける手続きGNの反復回数がアルゴリズムPPと比較して少なくすむためである．ただし，
問題7のような例外も見受けられる．次に，アルゴリズムPP2とアルゴリズムPP3を比 較すると，今回の実験ではアルゴ リズムPP2とアルゴリズムPP3の大きな差異は確認で きなかった．最後に，一般化ニュートン法と近接点法の比較を行う．ほとんどの問題に対 して，一般化ニュートン法の反復回数はアルゴリズムPPの反復回数よりより少くアルゴ リズムPP2と同じくらいである．こうしてみると，一見近接点法にはメリットが無いよ うに感じられるが，問題5の結果から分かるように一般化ニュートン法で解けないような 条件の悪い問題に対しても近接点法は安定した収束性を保っている．
6
結論
本報告書では，非線形相補性問題に対する近接点法の実装上の課題を指摘し，その解決 策を示した．また，いくつかの具体的な問題に対して数値実験を行った．数値実験の結果か ら，アルゴリズムにいくつかの工夫を加えることで効率良く解が得られることが分かった．
しかし，近接点法ではパラメータの値や問題によって反復回数が非常に多くなるなどの 不安定要因もあり，今後より厳密な解析を行う必要がある．また，今回実装したプログラ
表1: ckの更新規則による反復回数の変化
問題 更新規則 求解率(%) Best Worst Mean
1 minf
k
;8
F (x
k
)g 100 22(8) 26(8) 24.45(8.00)
1
k
100 23(9) 27(9) 25.45(9.00)
1 minf
k
;8
F (x
k
) 2
g 100 22(8) 26(8) 24.45(8.00)
1 minf
k
; q
8
F (x
k
)g 100 22(8) 26(8) 24.45(8.00)
1
k
minf1;
1
jjx k
jj
g 100 12(6) 14(6) 12.70(6.01)
2 minf
k
;8
F (x
k
)g 100 23(7) 41(7) 28.89(7.02)
2
k
100 25(9) 43(9) 30.85(9.00)
2 minf
k
;8
F (x
k
) 2
g 100 22(6) 41(7) 28.86(6.98)
2 minf
k
; q
8
F (x
k
)g 100 23(7) 41(7) 28.95(7.10)
2
k
minf1;
1
jjx k
jj
g 100 20(5) 39(6) 25.83(5.75)
3 minf
k
;8
F (x
k
)g 100 26(7) 41(11) 33.52(8.33)
3
k
100 28(9) 39(9) 33.80(8.89)
3 minf
k
;8
F (x
k
) 2
g 100 26(7) 41(11) 33.53(8.35)
3 minf
k
; q
8
F (x
k
)g 100 26(7) 41(11) 33.47(8.45)
3
k
minf1;
1
jjx k
jj
g 100 28(9) 39(9) 33.76(8.90)
4 minf
k
;8
F (x
k
)g 100 12(5) 19(5) 16.10(5.05)
4
k
100 14(7) 21(7) 18.05(6.99)
4 minf
k
;8
F (x
k
) 2
g 100 12(5) 19(5) 16.15(5.11)
4 minf
k
; q
8
F (x
k
)g 100 12(5) 20(6) 16.27(5.21)
4
k
minf1;
1
jjx k
jj
g 100 12(6) 19(6) 15.81(5.97)
5 minf
k
;8
F (x
k
)g 100 45(17) 79(18) 64.71(17.92)
5
k
100 46(18) 81(20) 65.85(19.06)
5 minf
k
;8
F (x
k
) 2
g 100 44(16) 79(18) 64.16(17.37)
5 minf
k
; q
8
F (x
k
)g 100 46(18) 80(19) 65.43(18.64)
5
k
minf1;
1
jjx k
jj
g 6 13(4) 15(4) 13.83(4.00)
6 minf
k
;8
F (x
k
)g 58 13(6) 196(7) 25.83(6.76)
6
k
54 18(8) 147(8) 30.61(9.61)
6 minf
k
;8
F (x
k
) 2
g 58 13(6) 81(7) 22.50(6.62)
6 minf
k
; q
8
F (x
k
)g 58 14(7) 108(6) 24.76(7.22)
6
k
minf1;
1
jjx k
jj
g 55 15(7) 83(8) 22.36(7.51)
7 minf
k
;8
F (x
k
)g 99 30(6) 44(8) 36.97(7.35)
7
k
99 26(7) 38(8) 32.44(7.59)
7 minf
k
;8
F (x
k
) 2
g 99 27(6) 45(8) 36.81(7.26)
7 minf
k
; q
8
F (x
k
)g 99 27(6) 42(8) 33.93(6.79)
7
k
minf1;
1
jjx k
jj
g 99 23(4) 38(6) 30.48(5.93)
