全文

(1)

c オペレーションズ・リサーチ

■学生論文賞受賞論文 要約■

Gauss–Seidel method for multi-leader-follower games

堀 篤史

南山大学大学院理工学研究科システム数理専攻(現:三菱電機株式会社)

指導教員:福島雅夫 南山大学 教授

1.

序論

マルチリーダー・フォロワー(multi-L/F)ゲームは,

一部の複数プレイヤー(リーダー)にイニシアチブが あり,残りのプレイヤー(フォロワー)が彼らを追従 するように戦略を決定するような階層型非協力ゲーム である.その応用に,規制緩和された電力市場や通信 市場などがある.

本研究では,multi-L/Fゲームを均衡制約をもつ均

衡問題(EPEC)と呼ばれる問題に再定式化することに

より,元の問題がもつ数値的取り扱いにくさを解消す るGauss–Seidel法を基盤とした2段階アルゴリズム を提案する.また,提案したアルゴリズムにおいて,強 停留均衡点と呼ばれる解への収束性を証明し,数値実 験によって有効性を確認した.

2. Multi-L/F

ゲームと

EPEC

本節では,本研究で扱うmutli-L/Fゲームの問題設 定とEPECへの再定式化を述べ,停留均衡の概念を述 べる.

N 人のリーダーと1人のフォロワーによるmulti- L/F ゲ ー ム を 考 え る .リ ー ダ ー の ラ ベ ル を ν(=

1, . . . , N)とし,リーダーνの戦略をxνnνとする.

また,それぞれのリーダーは費用関数θν:n+m と制約関数gν:nν rν,hν:nν sν が与え られているものとし,どれもC2級とする.フォロワー はy∈ mと戦略とし,費用関数γ:n+m と 制約関数u:n+mpが与えられているものとし,

どれもC3 級とする.ここで,n := n1+· · ·+nN

とする.リーダー ν は与えられた戦略の組x−ν :=

(x1, . . . , xν−1, xν+1, . . . , xN)n−nνy∈ mに 対して,次の最適化問題を解く.

xνmin θν(xν, x−ν, y)

s.t. gν(xν)0, hν(xν) = 0

(1)

一 方 ,フ ォ ロ ワ ー は 与 え ら れ た 戦 略 の 組 x :=

(x1, . . . , xN)nに対して,次の最適化問題を解く.

y∈minmγ(x, y) s.t.u(x, y)≤0 (2) ここで,フォロワーの問題(2)は任意に与えられた x∈ nに対して,凸最適化問題と仮定すると,KKT 条件は問題(2)に対する必要十分条件となり,以下の 混合相補性問題として等価に扱うことができる.

ψ(x, y, z, λ) : =

yγ(x, y) +∇yu(x, y)λ u(x, y) +z

= 0 (3)

0≤z⊥λ≥0 (4)

ただし,λ∈ pをLagrange乗数とし,z∈ pを不等

式制約u(x, y)≤0に対するスラック変数とする.方

程式系(3), (4)を問題(1)の制約条件に取り込むこと で,リーダーνの問題は以下のようなx−νをパラメー タとする相補性制約をもつ数理計画問題(PMPCC)と して再定式化される.

PMPCCν(x−ν) : min

xν,y,z,λ θν(xν, x−ν, y)

s.t. gν(xν)0, hν(xν) = 0 ψ(xν, x−ν, y, z, λ) = 0 0≤z⊥λ≥0

問題の組(PMPCCν(x−ν))Nν=1の均衡解を見つける 問題は均衡制約をもつ均衡問題(EPEC)と呼ばれる.

変数(y, z, λ)はすべてのリーダーが共通にもつ決定変 数のため,共有変数と呼ぶことにする.

一般に,EPECは均衡解が存在する保証がないうえ,

均衡解かどうかを確かめることは困難なため,本研究 では均衡解の拡張概念である停留均衡解の求解を目標 とする.なかでも,強い性質をもつ強停留均衡解を以 下に定義する.

定義. 戦略の組(x, y, z, λ)がEPEC(もしくは multi-L/Fゲームの)強停留均衡点であるとは,それぞ れのリーダーνに対して,解(xν,∗, y, z, λ)が問題 PMPCCν(x−ν,∗)の強停留点[1]となることである.

722(60)Copyrightcby ORSJ. Unauthorized reproduction of this article is prohibited. オペレーションズ・リサーチ

(2)

3.

提案手法

本節では,EPECを解くためのアルゴリズムを提案 し,multi-L/Fの停留均衡を求める手法を二段階に分 けて紹介する.

3.1 Phase I: Gauss–Seidel型ペナルティ法 準備として,問題の変換を行う.まず,相補性条件 0 z λ 0 はFischer–Burmeister (FB)関 数φ(a, b) := a+b−√

a2+b2 によって,等価な 等式制約として表せる.これにより,リーダーνの PMPCCν(x−ν)は次のように書き換えられる.

Pν(x−ν) : min

xν,y,z,λ θν(xν, x−ν, y)

s.t. gν(xν)0, hν(xν) = 0 Ψ(x⎡ν, x−ν, y, z, λ) :=

ψ(xν, x−ν, y, z, λ) (φ(zi, λi))pi=1

⎦= 0

しかし,FB関数が微分可能ではないため,Pν(x−ν) は数値的に取り扱いにくい.これを避けるために,二 乗FB関数が連続的微分可能である性質を利用する.

問題Pν(x−ν)に対する緩和問題を次のように定める.

Pνρ(x−ν) : min

xν,y,z,λ

θ¯νρ(xν, x−ν, y, z, λ) ただし,

θ¯ρν(xν, x−ν, y, z, λ) :=θν(xν, x−ν, y)+ρ 2

rν

i=1

[gνi(xν)]2+ +

sν

i=1

|hνi(xν)|2 +

m+2p

j=1

|Ψj(xν, x−ν, y, z, λ)|2

とし,ρ >0はペナルティパラメータである.また,

[gνi(xν)]+ := max{0, gνi(xν)}とする.この問題の目 的関数は微分可能である.

アルゴリズムの概要を説明する.k= 0,1,2, . . .をス テップ数とする.各リーダーは緩和問題Pνρk(x−ν,(k)) を順に解き,適当な終了条件が満たされればアルゴリ ズムを終了し,そうでなければペナルティパラメータ を更新して再びν= 1からNまで順に解く.このア ルゴリズムに関して以下の結果を得た.

定理. ρk→ ∞とする.さらに,各リーダーνとス テップkに対してPνρk(x−ν,(k))の解は局所最適解と 仮定する.また,解の点列に極限が存在し,極限にお いてMPCC一次独立制約想定と上位狭義相補性(文 献[1]を参照)が成り立つと仮定する.このとき,極 限はmulti-L/Fゲームの強停留均衡点である.

3.2 Phase II: Refined Gauss–Seidel法

前節のアルゴリズム(phase I)によって得られる解 の精度は必ずしも高くないが,得られた近似解は相補 性制約における有効制約を同定する意味で有用な情報 となる.w¯ν,∗= (xν,∗, yν,∗, zν,∗, λν,∗)をphase Iで得 られたリーダーνの近似解1とする.相補性制約に関 して,次のような有効制約集合を定義する.

I¯ν:={i| |z¯iν,∗|< δ, ¯ν,∗i | ≥δ} J¯ν:={i| |¯ziν,∗|< δ, |¯λν,∗i |< δ} K¯ν:={i| |¯ziν,∗| ≥δ, ¯ν,∗i |< δ}

(5)

ただし,δ >0は十分に小さい数とする.簡単のため,

任意のνに対して,I¯:= ¯Iν,J¯:= ¯Jν,K¯:= ¯Kνが成 り立つと仮定する.以下は近似解wν,∗付近で定義さ れる 相補性制約を含まない 最適化問題である.

Pν(x−ν) : min

xν,y,z,λ θν(xν, x−ν, y)

s.t. gν(xν)0, hν(xν) = 0 ψ(xν, x−ν, y, z, λ) = 0 zi= 0, λi0 (i∈I)¯ zi= 0, λi= 0 (i∈J¯) zi0, λi= 0 (i∈K)¯ Phase IIでは,それぞれのリーダーがPν(x−ν)を順 に解き,適当な終了条件(収束判定)が満たされれば,

アルゴリズムを終了する.最終的に得られた解におい て,Pν(x−ν)のKKT条件がすべてのプレイヤーに対 して成り立てば,強停留均衡点が求まったといえる.

Hu and Fukushima [2]の問題例を用いたところ,強 停留均衡点が見つかったほか,[2]で得られた解よりも 精密な解を得ることに成功した.また,解を更新する 際,逐次過緩和法を用いることで,少ない反復回数で 同程度の精度をもつ近似解を得ることに成功した.

参考文献

[1] H. Scheel and S. Scholtes, “Mathematical programs with complementarity constraints: Stationarity, opti- mality, and sensitivity,” Mathematics of Operations Research,25, pp. 1–22, 2000.

[2] M. Hu and M. Fukushima, “Smoothing approach to Nash equilibrium formulations for a class of equi- librium problems with shared complementarity con- straints,” Computational Optimization and Applica- tions,52, pp. 415–437, 2012.

1 共有変数にラベルνを付すのは,一般に値が各リーダーに よって異なるためである.

2018年11月号 Copyrightcby ORSJ. Unauthorized reproduction of this article is prohibited.(61)723

Updating...

参照

Updating...

関連した話題 :

Scan and read on 1LIB APP