学生論文賞受賞論文　要約　A Continuation Method for Complementarity Problems

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

.学生論文賞受賞論文

要約・

111111111111111111111111111111111111111111111111111111111111111111111111111川l刷 1111111111111111111111111111111111111111111111111111111川1IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIHIUlIIIIIIIIIIIIIIIIUlIIIIUlII11101111

A C

o

n

t

i

n

u

a

t

i

o

n

Method f

o

r

C

o

m

p

l

e

m

e

n

t

a

r

i

t

y

P

r

o

b

l

e

m

s

(相補性問題を解くための連続変形法について〕

東京工業大学大学院総合理工学研究科システム科学専攻 野間 俊人{指導教官小島政和助教授)

11111111111111111111111111111111川 111111111111111111111111111111111111111111111111111111111肌111川111川111111附11川111川川H聞11川111刷111111111川1111川11川11川川11川11川11111111川11川川11川111川1111川111川11川11川111111川11川11川川11川川11川川H川附H聞H川川H川H川H削111111111111川11111川111111川111川11111附川H川111川11111111川111川111川11111111111111111111111111111111111111111111111111111111111111111111111111111

1.はじめに

線形計画問題の解法として，その実行可能領域の 内部にある

path o

f

centers と呼ばれる連続な曲 線を辿ってゆくことにより解に到達するとし寸方法 が近年提案され研究された.

([3J

,

[6J等)また，こ の考え方は，より一般の問題である，半正定値行列 に関する線形相補佐問題にも適用できることが示さ れた. [4J 本論文では，同様な方法が，ある種の非線 形相補佐問題に対しても有効であることを示す. Rn を n 次宏 Euclid 空間， R♂をその非負象限 {x ERπ: x~O} とするとき，与えられた関数 f:R+n →Rn に対して，

(1) y=f (x)

,

Xi Yi=

0

(i= 1

, …,

n)

,

(x， y) ε R+加 を満たす (x， 引を求めると L 、う問題が相補性問題であ る.ここで， xi および仇は，それぞれニr， yの第 t 成分を 表わす.本論文では ， f が連続な単調関数の場合と，連 続な一様 P 関数の場合を考察の対象とする .f が単調関 数であるとは， <X1_X2

,

f(x1_{) ーf(x}2_{)> ~} 0 VX1_{， X}2_ER+π が成り立つことができる. ただしく・，・〉は内積を意 味する.また ，f が一様 P 関数で、あるとは，ヨ σ>0 に対し

max

(Xi1-X♂ )(fd が )-fdx2)) ミ σ Ilxl_X2112

1:五 i:玉"

V

x

1

_,

_x

2 _ER+偽 が成り立つことである.徴分可能な凸計厨問題(線形計 画問題や凸 2 次計画問題を含む)は，連続な単調関数に 関する相補性問題に帰着させることができるので，ここ での考察対象はかなり広範な問題を含んで・いる.

2

.

連続な単調関数に関する相補性問題

相補性問題(1)に対応して，関数 F: R+2n→R2n を次 のように定義する. F(x， y)=( ゆ (x， y) ，

7Jf

(x

,

y)) ただし， ゆ (X， y)=(x1Yh … ， xn仇)

7

J

f

(x

,

y)=y-f(x) 1989 年 1 月号 。 ~x F 〆'ーー旬、主 1・-〆 F-1 b R~+X \(f(R~"r) 。 α 1 図 関数 F による RHM と R+ 戸 x 7Jf (R++2n) の聞の同相対応 この関数 F を用いると，相補性問題(1)は，

(

2

)

F(x

,

y)=O

,

(x

,

y)ER+2n を満たす (X， y) を求めるという問題に書き換えることが できる. R++犯は Rn の正象限 {xER飽: x>O} を表わすものと する.このとき ， (R++2n) =R+♂となることは容易に わかるが，実はより強く次の定理[2J ， [5J が成り立つ. 定理 1 f が連続な単調関数のとき ， F は R++2n をR++n X 7Jf (R++2九)の上へ同相に写す. (すなわち ， F は R付加 を R++nx 7Jf (R++加)の上へ l 対 1 に写し ， F も F-l も連続 である.) (図 1 参照)

定理 2 (xk

,

yk) E R++2n で (ak ，bk)=F(xk

,

yk) とする.

(k=I ， 2 ， …)このとき，ある a ER+旬と bE 7Jf (R++2n) に 対して lim(ak

_,

_bk)

₌

_{(a， b) ならば，点列} k-令。。 {(Xk

,

yk): k=I ， 2 ，"""} は有界であり，したがって収束す るような部分点列をとることができる. 以下， 0 E 7Jf (R++2η) を仮定することにする.この条件 のもとで，相補性問題 (1) には解が存在し(ただし，唯一 つとは限らな L 、)，その解が連続変形法の考え方によって 求められるということを次のように示すことができる. 任意にが ER+♂を選び， それに応じてが ER++胞を 適当に選んでが=7Jf(XO

,

yO)E R♂とする. また ， aO=

ゆ (XO ， yO) とすれば，結局 (aO，bO )=F (XO， yO) となる.

今 ，

t

E (0

,

1J に対して W(t)=t (aO，bO) とおけば ，

A=

4

3

定理 3 の主張には ，1Jf (B+2n)=Rn という y _b 晶 ことも含まれている.また，定理 1 と比べる (x~ 110) F (a~ bO_{) =F(x~ 11}0₎ と，定理 3 はより強く， R+znの境界上も含め て F が同相写像となることを主張している. したがって，式 (2) を満たす (x， y) ， すなわ

t=

1 〆'ーー、亀

、ー-O

'

"ル

(/t → +0

F-1 S

,

p 1旨 x 図 2 関数 F による曲線 T と線分 d の対応 {W(t い tE ₍₀

,

1J} は原点と (aO，bO) を結ぶ線分(原点は 含まな L 、)である. 0 E

1

J

f

(B++2n) とし、う仮定からR♂ C 1Jf (B++知)となることが 1Jfの定義より容易にわかるので， A cB+♂ xR♂ cR++ n X

1

J

f

(B++卸)となる.したがって，

t

E (0

,

1J を 1 つ固定したとき，定理 1 より (3) F

(x

,

y)=W (t)

,

(x， y) ε R++卸 の解 (x， y)=(x(t) ， 事 (t) )が唯 1 つ存在し，その解の集 合 T={(x(t) ，

y

(

t

)

)

:

t

E (0

,

1J} は連続な曲線(軌跡)と なる.この軌跡 T 上の点 (x(t) ， y(t)) を考えてみると， t=1 のとき (x(

1),

y

(

1

)

)

= (XO

,

yo) である.また t→ +0 のときは定理 2 から (x(t) ， y(t)) が有界で集積点をもつ が，式 (3) が t→ +0 のとき式 (2) になることに注意すれ ば，その集積点は式 (2) を満たし，したがって相補性問題 の解であることがわかる. こうして，軌跡 T は t→ +0 のとき相補性問題(1)の 解全体の集合 SCP (学。)に限りなく近づくことが示され た.実は，少し条件を強めると(たとえば， f が線形で あるとすると)， T は t→ +0 のとき SCP 内のある I 点、に 収束するということもわかる. (図 2 参照) したがって，何らかの数値的な計算手段を使って，軌 跡 T を (XO， yO) から出発して t→ +0 となるように追跡 してゆけば，相補性問題(1)の(近似)解が得られる.こ れが，連続変形法による相補性問題の解法のアイデアで ある.

3

.

連続な一様 P 関数に関する相補性問

題

f が連続な一様 P 関数の場合にも，関数 F を単調関数 の場合と同様に定義すれば，次の定理[

1

]を示すことが できる. 定理 3 fが連続な一様 P 関数のとき ， F は R+加をR♂ xBn の上へ問相に写す.

4

4

t=

1 α ち f に関する相補性 (1) 問題の解は存在して しかも唯 1 つであることがわかる. 単調関数の場合に述べた，連続変形法によ る解法のアイデアは，この場合にも有効であ る.ただし，初期点 (XO_{， yo) は RHM 内に任} 意に選んでよく，また軌跡Tは t→ +0のとき 相補佐問題(1)の唯 1 つの解に収束するので，より簡明に なる.

4

.

New加n法の反復による軌跡の追跡

軌跡を追跡するための具体的な計算手段としては，連 続変形法の分野で確立された種々の方法を用いることが できる.たとえば ，f が連続微分可能 (Cl級)の場合には， Newton 法の反復によって軌跡を追跡することができ る.すなわち ，

(XO

,

yO) を初期点として，その点から少 し離れた軌跡 T上の点を目標点として定め，その近似点 を Newton 法で求める. 次に，求まった点を新たな初期点として，再び目標点 を近くに定め Newton 法でその近似点を求める.これを 繰り返して，目標点を少しずつ t→ +0 となるように動か してゆけば，近似的に軌跡 Tを辿りながら相補性問題の 解に到達することができる. 参考文献

[1] M. Kojima

,

S

.

Mizuno and T. Noma

, “

A

New Continuation Method f

o

r

Complementarity

Problems with Uniform P.Functions

,>>

t

o

appear

i

n

Mathematical Programming.

[2] M. Kojima

,

S

.

Mizuno and T. Noma

,

“

Limiting B

ehavior o

f

T

r

a

j

e

c

t

o

r

i

e

s

Generated

by a Continuation Method f

o

r

Monotone

Comlementarity Problems

,"

B・ 199 ，

Dept. o

f

Information Sciencs

,

Tokyo I

n

s

t

i

t

u

t

e

o

f

Technology

,

January

1988.

[

3

] M. Kojima

,

S

.

Mizuno and A. Yoshise

, “

A

Primal.Dual I

n

t

e

r

i

o

r

P

o

i

n

t

AIgorithm f

o

r

Linear Programming

,"

t

o

appear i

n

Research

I

s

s

u

e

s

i

n

Linear Programming: Proceedings of

t

h

e

Asilomar Conference

,

(

S

p

r

i

n

g

e

r

.

V

e

r

l

a

g

)

.

オベレーションズ・リサーチ

[

4

] M. Kojima

,

S

.

Mizuno and A. Y

oshise

,

“

A P

o

ly

n

om

i

a

l

-Time Algorithm f

o

r

a C

l

a

s

s

o

f

Linear Complementarity Problems

,"

t

o

appear i

n

Mathematical Programming.

[

5

] L

.

McLinden, “

The C

omplementarity

Problem f

o

r

Maximal Monotone Multifunctions,“

Chapter 17

,

25 ト270

i

n

:

R. W. Cottle

,

F

.

G

i

a

n

n

e

s

s

i

and J

.

-

L

.

Lions

,

eds.

,

Variational

I

n

e

q

u

a

l

i

t

i

e

s

and Complementarity Problems

,

(Wiley

,

New York

,

1

9

8

0

)

.

[6] N. Megiddo,“

Pathways t

o

t

h

e

Optimal S

e

t

i

n

Linear Programming,"

Proceedings of t

h

e

6

t

h

M a

t

h

e

m

a

t

i

c

a

l

Programming Symposium of

Japan (Nagoya

,

Japan

,

1986) ト 35.

ソフトウエア・主ヲJング

片岡雅憲著 本書は， ソフトウェアの「モデリング」 と「再利用」を軸としてまとめられた， ソフトウェア設計技術の解説書である. ソフトウェアの開発過程の各段潜におけ る生産物をモデルや部品により徹底的に 標準化することにより「再利用」の推進 を図ろうとするのが本書の考え方である. 再利用技術に関する最新の動向を体系的 に解説する.

A5 判・ 496貰・定価4 ， 900円干300円

〔主要目次〕第 I 郎 ソフトウ z アの再 利用(再利用の設計パラダイム/再利用 技術の意味と役割/再利用とプロトタイ ピング/再利用と品質) 第 H 節 ソフ トウェア・モデリング(人聞の情報処理 の特性/概念モデル(1)概念モデルの枠組 み /(2)知識モデルとモジュール化/仕様 モデル(1)仕様モデルの枠組み /(2)型モデ ルとモジュール化他)

ソフトウェア・エンジニアリング

菅野文友箸 A5 ・定価5 ， 200円干300円 菅野文友監修

ソフトウェア・デザインレビュー

A5 ・定価3 ， 200円〒250円

ソフトウェア信頼性ガイドブック

R.L.グラス箸，菅野文友訳 A5 ・定価3 ， 500円干250円

盛田科技連出版社

1989 年 1 月号

ソフトウェアの品質評価法

三錆武箸 A5 ・定価4 ， 500円苧300 円 〒 151 東京都渋谷区千駄ヶ谷5-4-2 振替東京7-7309 電話03(352)2231

FAX

0

3

(

3

5

6

)

3

4

1

9

(図・目録送呈〕

45

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.