■学生論文賞受賞論文

Equivalent Differentiab］e Unconstrained Optimization
for Comprementarity Problems
山下 信雄（奈良先端科学技術大学院大学情報科学研究科 現所属：同大学情報科学研究科博士後期課程）
指導教官福島雅夫教授

1． はじめにけることは重要である．本論文では，この問題に対す非線形相補作間題（NCP）は，交通量割り当て問題や経済の均衡問題，最適化問題などを定式化するために使われる問題で次のように定義される甘る1つの結果が得られたので，それについて報告する．

次に非線形相補性問題を一般化した相補性問題に対する陰ラグランジュ関数を提案し，その性質を調べる．特に，その陰ラグランジュ関数の停留点が，一般［NCPI Find3：∈Rnsuchthatェ≧0，ダ（ェ）≧0，ごγダ（〇）＝0．
ここで，ダは」㍗→点れの関数である∴最近，Mangasar−ianとSolodov囲はこの問題と等価な次の制約のない
巌小化問題を提案した．

非線形相補性問題の解となるための条件を調べる．また，非線形相補性問題に対する陰ラグランジュ関数の制約なし最小化問題に対する降下法を提案し，その大域的収束性を示す．最後に，計算機実験の結果を報告する．

なお，本修士論文の結果は論文t4】，t5】に含まれて

min〟α（ェ）Jいる．

ここで，〟αは次式で定義される′実数値関数である，〟α（ご）㌔顆）十去川（−α嘩）＋拓‖2−＝珊＋lI（一α〇＋ダ（ヱ））＋ll2

2．未解決問題に対する1つの解答
関数G，∬：月m→月nを次式で定義する．
G（∬）＝（−αF（諾）十‡）＋−〇

一岬（可‖2）ガ（ヱ）＝（−αヱ＋ダ（ご））＋−ダ（ヱ）ただしα∈（1，∞）はパラメータであり，llllはユーク
リッド・ノルム，（∬）十は第哀成分をmax（0，〇i）とする

この関数G，∬を用いると仇（〇）の勾配は次式で表さベクトルを表す．この関数〟αを陰ラグランジュ関数れる．

（implicitIJagrangian）と呼ぶ．この関数については，α∇〟α（諾）＝ ∇ダ（げ（−αG（∬）＋ガ（諾））次の性質がわかっている．

＋（C（訂）−αガ（ヱ））定理1伸すべてのヱに対して〟α（〇）は非負であり，また，Cと飢こは次の興味深い性質が成り立つ．

〃α（ヱ）＝0と諾がⅣCPの解であることは同値である．
補畏1ダ（諾）が微分可能かつ∇ダ（〇）が正則であり，ヱ

この定理は，NCPに解が存在するとき，〟αの大域的が関数吼の停留点のとき，次の3つの条件は同値で娘通解がNCPの解となることを示している．

ある．

ManaSarianら【3］は陰ラグランジュ関数に対して，次の未解決問題を提示している．

リーαG（∬）＋ガ（∬）＝0
2ノG（霊）−αガ（昔）＝0

・どのような仮定のもとで，〟。（〇）の停留点がNCPの解になるか？

りG（諾）＝0，ガ（∬）＝0ロ

次の定理は，陰ラグランジュ関数吼の停留点が現在提案されているほとんどの最適化のアルゴリズ

NCPの解になるための十分条件を与えている．

ムは，＝的関数の停留点を求めるものであるので，定理2∇∫（ヱ）が正定借ならば，〟。（‡）の停留点は仇（〇）の停留点がNCPの解となるための条件をみつⅣCタの解である．

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

□オペレーションズ・リサーチ3．一般非線形相補性問題

なければた：＝た＋1としてステップ1へ

次にN（〕pを拡張した次の−・般非線形相補性問題
このアルゴリズムに村して以下の収束定理がなり（GNCP）を考える．

【GNCP］ Findx∈Rnsuchthatβ（ご）≧0，ダ（芯）≧0，β（〇）Tダ（ご）＝0たつ．

定理3ダが強単調のとき上記のアルゴリズムは収束し，（ごりの任意の集積点はⅣCf，の解である．

ここで，β，ダほ」㍗→点れの写像である．

口GNCPに対して，〟αを川・般化した関数を用いた次5．数値実験の最小化問題を提案する．
min底（∬）

ここで，陰ラグランジュ関数加Lの性質を実際に確かめるた
めに数値実験をおこなった．実験では，Ⅹanzow【2】が如）＝且げ瑚＋去川（坤）−α瑚）＋1l2

提案している非線形相補性問題と等価な制約なし最小化問題を構成する関数との比較をおこなった．関数−1lβ（ェ）】l2＋l岬（ヱトαβ（ェ））＋ll2の最小化のアルゴリズムとしては，パッケージソフト

NPSOL4．0の準ニュートン法と4節で提案した降下法一陣（可＝2）である．この〟αに対して，次のことを示した．

を用いた．いくつかの代表的なテスト問題に対して◆おこなった実験において，∇ダ（訂）が正定借である問題に・おα（〇）は非負である．また，おα（ェ）＝0となる

おいては，きわめて良好な結果を得ることができた．

ことと，ごがGNCPの解であることと同値である．すなわち，愈αの最小化問題がGNCPと等価である．

参考文献【1】Harker，P．T．andPang，J．−S．，Finile−Dimensional・α≠1で，∇g（ヱ），∇ダ（〇）が正則とする．このとγαγねfよ0れαJ九叩祝αJ軸αれdⅣ0几J五乃eαγCom〆emeかき，次の条件（a），（b），（c）を満たす花火几行列ねr軸アγ0抽mごA5一視γγey O／meory，A如γ軌mβ5（ご），r（ヱ）とり∈月カゞ存在すれば臆。（諾）の停and AppLicalions，Mathematical Programmlng，

留点はGNCPの角牢である．

48（1990），16ト220．
【2］Kanzow，C．，Ⅳ0乃J豆乃eαγ仇m〆em帥ねわfyαβ仇−（a）5（〇）∇β（霊）rが正定低

COnStrainedOplimization，Preprint67，Institutf辻r（b）r（ヱ）∇ダ（ヱ）rが正定低

Angewandte Mathematik，Universit去・t Hamburg，（c）た＋J＞0，たJ≧0かつ，た5（ご）∇ダ（ヱ）T＋Hamburg，Germany，1993．

J（r（〇）∇β（￡）T）アが正志値対角行列．

【3］Manga．sarian，0．L．andSolodov，M．Ⅴ．，NonLin−

4．降下法

eαγCompJeme†けαγ軸αβ打乃CO那加inedα乃d Co乃−

陰ラグランジュ関数〟αを最小化する次のアルゴリズムを提案する．このアルゴリズムでは，探索方向を求めるために∇ダ（ヱ）を計算する必要はない．

Slrained Minimizalion）MathematicalProgram−ming，62（1993），877−898．

【4］Tseng，P．，Yamashita，N．，and Fukushima，M．

降下法のアルゴリズム

β押わαJe乃Ce q′com〆eme乃ねわfypγ0あJe〝lβfo d￠

ステップ0：初期．串二〇0を適当に選びた：＝0とする．

／eγeγl血鋸e m盲乃盲叩盲zα如乃ニA肌所ed叩prOαCん，tO

ステップ1：次式により点ご頼1を定める．

appearin SIAMJournaLon Oplimization．

Ⅰ5】Yamashita，N．and Fukushima，M．，On station−

ご頼1：＝ヱん＋tたdん

ここで，dた＝αG（叶トガ世）再（αガ（ヱんトC（㌔））であり，tkはArmijoの方法で求められるステップサイズである．なお，βは十分小さいil二の足数とする．

ステップ2；収束判定条件を満たせば終￣rし，そうで1996年1月号

αγypO査几ねげ加古m〆豆c盲f上叩γα乃タiα几わr乃0乃J査乃eαγ

COmPLementarityproblems，JournalofOptimiza，−tion Theory and Applications，84，（1995），653−
663．

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

53