聯学生論文賞受覚論文

要約鮮、−、∴′、ト‥，…：∴・」・・・恒↑上中ーミ・；車・・、・∴・‥書・一●…十三・・・∴−ごi．本章や涙減作・1・：ぎこj…ヰさYら・∴・・・∴− い：≡…‥・・■∴こJ・・十十．・・∴≡
・．■ユ‥斗丹軽（京都大学大学院工学研究科数理二王二学専攻 現所属：大阪ガス㈱）指導教官 福島雅夫教授

では，特にッ ⅩSDmCPを等価な制約なし虞適化問題
・‥ ∴・に変換して解く方法を考える￠ また，このような拡張線形相補性問題（mCP）や非線形相補性問題（NCP）された問題に対して，解の存在に対する議論は，これは9 最適化問題や各種均衡問題など幅広い応用があり，までにあまりされていない。本論文では，SりNCPのオペレーションズ0リサーチの分野における重要な問解の存在する条件を与える。

題の1つである［2］。そのLCpやNCPに対して，・：恵．南i−1−‥‥・、j −∴数々の拡張された問題が提案されており，それらの拡張された問題に対して，問題の性質や解法が広く研究

この節では，ⅩSⅢLCPを等価な最適化問題に再定されている。このような拡張の流れは大きく 2つある。

式化することができるメリット関数／：ダmx二少∽→

1つは相補性問題を与える関数を一般化するものであし拶を提案し，その関数の性質を示す。

りヲ その間題として拡張線形相補性問題（ⅩLCP）が／（J，ダ）＝il（∬2再2）喜一㌃∴洲2ある［虹 もう且つの流れは，扱う空間をル拶乃のベク＋l臣→餌蝕＋』Ab＋舅＋ll2

トル空間から対称行列の空間に拡張する流れである。

ただし，l拉ル＝、仔云嘉であり，［∬］．は∬の∬ゐへの直交射影である申 開数／に対して次の定理が成り立そのような問題として半正走値線形相補怪聞題（SI〕mCP）やそれを非線形化した辛正志値非線形相一）

補怪聞題（SI）NCP）がある。この間題は組合せ問題
や制御の分野で研究されている半正走値計画問題

定理2．且関数′は夕拍×ダ机上で非負である。さらに，（SDP）の最適性条件にも関連する問題であるu′（∬，〝）＝0かつ（∬，〝）∈ダmxダ椚であることと（∬，〝）

本論文では，この2つの拡張の流れを1つにした次がⅩSI〕LCPの解であることは等価である。のように定式化される拡張半正定借線形相補怪聞題（ⅩS互〕LC亙））を考察する。

この定理により，／を目的関数とした最小化問題が『imd（∬，〃）∈』ダ∽×軋ダ椚such that・．・／ ．．ざⅩSI〕LCPと等価になることがわかる。しかし，′は〆、−・−′′ ．．−り一 f・．・・−

ここで，ダヱは7×gの実対称行列の線形空間を表し，ノ好ニダ都→ダガとA∵もタ粕→Lダ刀は線形写像，レ㌢￣∠⊂

一般に凸関数ではないので，′の停留点がⅩSi〕LCPの解となる条件を調べることは重要である止その条件を示す前にいくつかの定義を与える。まず，

タグ∠は，gX7の半正志値対称行列の凸鍵集合を表す。

線形写像』∴も夕餉→ダ烏に対して，』＊は』の随伴作用

また9 〈0，う〉は9 〈諾，ダ〉：＝tr［∬ダ］で定義される夕川上素とする。さらに，Cのrecession coneを0＋Cで表のノルムである。さらに，集／合Cは線形写像週：タグm

し，0＋Cの極錐を（0十C）＊であらわす。

→ダ克と対称行列あ∈ダゐを用いてC＝（祝∈ダ乃l』〟【ゐ∈∬ゐ〉と表されるものとする。本論文では，集これらの定義を用いてを求めたい条件を与えることができる。

●・、‥・、ノ′・．ニ ー、′′ ご‥・ ミう／、●ソ ニイ′￣・：・￣ ∴定理2．2次の条件のうち少なくとも1つは満たされてと仮定する。

上記で定義されたⅩSI〕LCPはヲ SDLCPやⅩLCPいるとする。の自然な拡張と考えることができるので，ⅩSI）LCP（り 線形写像朋Ⅳ＊は（0＋C）＊上でCOpOSitiveである。

を解く解法として，ⅩmCPやSDLCPに対して考案（ii）、ゐ∈∬烏が成り立つ。

された手法［4，6］が拡張できると期待される。本論文

そのとき9／の停留点はⅩSI〕LCPの解である。

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

オペレーションズ。リサーチ命題3．1F（∬）＝甜（ん協（∬））かつ一様クー関数であると3．SDNCPの解の存在性する．そのとき1imll刈ト∞Ⅴ（∬）＝∞が成り立つ．

この節では，半正定借非線形相補性問題（SDNCP）の解の存在する条件を与える．SDNCPは次のようにこの命題を用いて定理を得ることができる．

定式化される．Findこr∈．9Pm such thatJ∈、訝￣m，F（諾）∈L訝￣m，〈J，F（∬）〉＝0

定理3．3関数Fは微分可能かつF（J）＝餌（人∽。エ（∬））とす

ここでFはLプ∽から」プmへの写像とする．解が存在する．そのときFが一様P一関数なら，SDNCPは解をる条件を与えるために，次のSDNCPのメリット関もつ．

数智（J）が少なくとも1つの停留点をもち，その停留点が解であるということを示す．

4．まとめ
本論文では，拡張半正走値相補怪聞題（ⅩSDLⅤ（￡）＝maX（0，〈∬，F（ェ）〉）2CP）に対するメリット関数を提案した．そして，そ＋‡11（J2＋F（∬）2）1′2−∬−F（捌この関数甘はYamashitaとFukushima［6］が提案の関数を用いてⅩSDLCPを制約なしの最適化問題に再定式化し，メリット関数の停留点が解であるためのした関数である．彼らはこのメリット関数を用いてダ十分条件を確立した．また，SDNCPに対する解の存が単調でかつ狭義実行可能であるならSDNCPは解在条件をあたえた．今後の課題は，ⅩSDLCPの等価を持つことを証明した．これは，∇F（∬）が半正走値な最小化問題を解く効率のよいアルゴリズムの開発なであるなら，甘の停留点はSDNCPの解であることどであ▲る．に基づいている．最近，∇F（∬）が半正定借よりも緩参考文献

い条件である昂【行列であるときでも，このような性質を持つことが示された［3］．ここで，為一行列とは次［1］0．L．Mangasarian andJ．−S．Pang，The extendedのように定義される行列であり，J＝（1，…，∽）とする．

linear complementarity problem，SL4Mノbumalon
劇初宛㌃』肋頭適ぉのぬ㌧製粉仏祖鮎胤仁6：359−368，1995′

定義3．1次の条件を満たすとき線形写像〟：」プm→Lダ∽

を昂一行列と呼ぶ．∬≠0である任意の∬∈Lア∽と任意の正則行列♪∈L穿∽×∽に対して，（如）ど≠0かつ［（如）〟（如）r］露≧0を満たす添字オ∈∫が存在する．ただし，（如）どは行列
如の第オ列を表す．

［2］J．LS．Pang，Complementarityproblems，Hdndbook〆 Global（砂timization，Edited by R．Horstand P．

Pardalos，KluwerAcademicPublishers，1994．
［3］H．D，Qiand X．Chen， On stationary points of
merit functions for semi−definite complementarityproblems，

workingpaper，InstituteofComputational

Mathematics and Scientific／Engineering Computing，
ChineseAcademyofSciences，Beijfng，China，1997．

NCPは扱う関数が一様クー関数なら解をもつことが［4］M．Ⅴ．Solodov，Some optimization reformulation

知られている．そこで，次のようにしダ椚空間におけるfor the extendedlinear complementarity problem，一様クー関数を定義する．

WOrking paper，Instituto de Matem孟tica Pure eAplicada，Estrada Dona Castorina llO，Jardim

定義3．2関数F∴プ∽→Lダmが次の条件を満たす正のBotanico，Rio deJaneiro，RJ22460−320，Brazil．

定数〟が存在するとき一様クー関数と呼ぶ．∬≠〝であ［5］P．Tseng，Merit functions for semi−definite com−

る任意のJ，〝∈．プmと任意の正則行列カに対して，Plementarity problems，MathematicalP和好7ummZng，［♪（ズー〝）（F（ェ）−F（〝））〆】if≧〃llカ（㌃1刑2to appear．

［6］N．Yamashita and M．Fukushima A new meritを満たす添字才∈∫が存在する．

function and a descent method for semidefinite com−

これらの定義を用いて，解の存在性を示すのに必要

plementarity problem，tO aPpearin Rqfbrmula

な命題を与える．ここでu）（t）は1im supt→∞＝a）（t）＝／t2⊥ヽ1川J川りり〟L f）／ハ、川心（チ ∫J〃りり〃上 ∫ぐ〃J／∫〃川（）／ん の〜（′＝0かつ1iminft＿JEa）（t）＝＝∞を意味し，）m。X（x）はxのSmoothing Methodk，M．Fukushima and L，Qi（eds．），

最大固有値を表すとする．
1999年1月号

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

4T