二次錐相補性問題に対する数値解法について
横浜国立大学成島康史

1

概要
z 相補性問題z 二次錐相補性問題（ＳＯＣＣＰ）
zzzzzz二次錐二次錐に関連したジョルダン代数
ＳＯＣ-Ｃ関数を用いた再定式化
平滑化法
パラメータを変数化した平滑化Newton法
パラメータ調整を組み込んだ平滑化Newton法

z 数値実験例2

相補性問題（CP：Complementarity Problems）
相補性問題（CP）

非線形相補性問題（NCP）

3

2次錐相補性問題（SOCCP）
2次錐相補性問題（SOCCP）

4

二次錐

5

二次錐(n=3)62次錐計画問題

z線形計画問題z凸2次計画問題
zロバスト最適化など

ＬＳＤＰ
ＬＳＯＣＰ
凸ＱＰ
ＬＰ

7

2次錐計画問題と2次錐相補性問題
2次錐計画問題

KKT条件

8

不確実性を含む均衡問題（１/4）
競合相手の戦略が正確には分からない

ロバストＮａｓｈ均衡問題
Player1

Prayer29不確実性を含む均衡問題（2/4）

Player1の解く問題10

不確実性を含む均衡問題（3/4）
Player1

Player2

11不確実性を含む均衡問題（4/4）

12対称錐とジョルダン代数

対称錐の例

13

ジョルダン代数
ジョルダン積14

ジョルダン代数
Arrow 行列15

ジョルダン代数

16

ジョルダン代数

17

ジョルダン代数性質

18

2次錐相補性問題

2次錐相補性問題

19

SOC C-関数

20

SOC C-関数(Fukushima et al. 2001)
Natural Residual(NR)関数

Fischer‐Burmeister(FB)関数

解くべき方程式

21

平滑化

定義

22

平滑化SOC-C関数(Fukushima et al. 2001)
平滑化Natural Residual関数

平滑化Fischer‐Burmeister関数

解くべき方程式

微分可能

23

SOCCPに対する数値解法

平滑化NR関数t:変数t:パラメータ

Chen et al. (2003)Hayashi et al. (2005)

平滑化FB関数 Narushima et al.(2011) Narushima et al.(2012)24

連続微分可能性とヤコビ行列(1/2)

Proposition（ Fukushima et al. 2001 ）25

連続微分可能性とヤコビ行列(2/2)

26ヤコビ行列の正則性仮定
行列がフルランク

Proposition（ Fukushima et al. 2001 ）27

Semismoothness

28

関数HのSemismooth性
Proposition（Sun and Sun 2005）

29

SOCCPに対する数値解法

平滑化NR関数t:変数t:パラメータ

Chen et al. (2003)

Hayashi et al. (2005)

平滑化FB関数 Narushima et al.(2011) Narushima et al.(2012)30

平滑化ニュートン法(Narushima et al. 2011)

Proposition（Qi et al. 2000）31

アルゴリズム

32

実行可能性
Proposition

33

大域的収束性
仮定

Theorem34

局所的収束性
Theorem

35

SOCCPに対する数値解法

平滑化NR関数t:変数t:パラメータ

Chen et al. (2003)

Hayashi et al. (2005)

平滑化FB関数 Narushima et al.(2011) Narushima et al.(2012)36

平滑化Newton法(Narushima et al 2012)アルゴリズムの局所的に速い収束性を得るにはとなる点列を生成する必要がある

Theorem(Ogasawara and Narushima2012)→パラメータtのコントロールで(*)が実現可能
37

パラメータのコントロール(1/2)

38パラメータのコントロール(2/2)
Proposition(Ogasawara and Narushima 2012)39

アルゴリズム（外部反復）40アルゴリズム(内部反復)

41

大域的収束性仮定

Proposition

Theorem42局所的収束性
Theorem43

数値実験
二次錐計画問題

二次錐相補性問題

44

数値実験

45

数値実験結果

数値は各問題100問の平均値46数値例(Nash均衡問題)
プレイヤー1

プレイヤー247数値例(Nash均衡問題)

rho1
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1

rho2
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1

z1(1)
0.60010.55970.5201
0.48140.44430.40910.37670.34730.32120.2982z1(2)0.2331
0.26220.29180.32190.35240.38320.41380.44410.47360.502

z1(3)0.16680.178
0.18810.19670.20330.20770.20950.20860.20520.1998z2(1)0.26380.28240.3006
0.31850.33590.3526
0.36870.384
0.39850.4124z2(2)0.13070.11970.10890.09830.08790.07790.0681
0.05870.04970.0409z2(3)0.60550.59790.5904
0.58320.57620.56950.5632
0.55730.55180.546748

数値例(Nash均衡問題)

rho1
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1

rho2
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1

z1(1)
000
0.126
0.1757
0.19830.21150.22040.22690.2319z1(2)0.80810.75880.71130.61390.57820.5624
0.55350.54770.54370.5408z1(3)0.19190.24120.28870.26010.2461
0.23930.235
0.23190.22940.2273z2(1)0.29780.28510.27440.24050.23
0.22730.22770.22980.23290.2366z2(2)0.6026
0.59870.59340.58580.57160.556
0.5402
0.52440.50880.4932z2(3)0.09960.11620.13230.1737
0.19840.21670.23210.24580.25840.270249まとめz 相補性問題z 二次錐相補性問題（ＳＯＣＣＰ）
zzzzzz二次錐二次錐に関連したジョルダン代数
ＳＯＣ-Ｃ関数を用いた再定式化
平滑化法
パラメータを変数化した平滑化Newton法
パラメータ調整を組み込んだ平滑化Newton法

z 数値実験例50