相補性問題と変分不等式問題に対するメリット関数
福島雅夫，山下信維…l……………………l……………………………………l………l………‖＝‖‖‖‖州l………………………l…lll……‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖州Il…………………ll…ll川l……＝＝‖川………………t…‖‖‖州‖‖‖州‖l……l…lll…lt

1． はじめに次式をみたすべクトルヱ∈∫を求める問題である．

本稿では非線形相補性問題（Nonlinear Comple−【ⅤIP】（ダ（ご），ご−y〉≧O fbrally∈∫mentarity Problem，NCP）と変分不等式問題

ここで，g⊆尺nは閉凸集合である．VIPにおいて，と（VariationalInequalityProblem，VIP）を取り上

くにg＝月号とすればNCPと等価になるので，▲ⅤIP

げる．NCPやⅤIPと聞いても一般の読者にはなじみ

はNCPを含んでいる．また，数理計画問題の1次の最が薄いかもしれない．しかし，最適化問題，経済均衡

適性条件は通常VIPの形で表されるので，最適化問問題，交通流均衡画題などORに関連の深い問題には

題はⅤIPの特別な場合と考えることができる．

NCPやⅤIPに定式化できるものが少なくない．（均衡モデルの定式化に関する簡単な解説は【9】を，様々な応用についての詳細は【4］を参照．）

3． メリット関数とは
NCPやVIPを，それを等価な制約なしあるいは制VIPやNCPに対してはこれまで様々な研究が行わ

約つき最適化問題に再定式化したとき，その最適化問れている．とくにLCPに対しては，Lemke法【3］や内題の目的関数となる関数をメリット関数と呼ぶ．メリ点法【17】など，実用的，かつ理論的に優れた方法が提案

ット関数は以下の性質をもつことが望ましい．

されている．一般のNCPやVIPに対しても，逐次線形化法，射影法などが提案されているが［11］，最近，NCP

やVIPを等価な制約なしあるいは制約つき最適化問
題や方程式系に再定式化して解く方法が注目を集め，◇ メリット関数は微分可能である．
◇ メリット関数の停留点が問題の解となる．
◇ メリット関数は問題のエラーバウンドとなる．
◇ メリット関数のレベル集合が有界となる．

活発な研究が行われてレアる［外本稿では，著者たちの最近の研究を中心に，そのようなアプローチに関するメリット関数が微分可能であることは，アルゴリズム

研究の流れを概観する．

の構成上非常に重要な性質である．また，最適化アルゴリズムによって得られる解は一般に問題の停留点ま2．NCPとⅤIP

たは局所的最適解である．したがって，適当な条件のNCPやⅤIPを数学的に定式化すると以下のようにもとで停留点が大域的最適解となることが保証され表せる．NCPは次式をみたすべクトルご∈Rnを求めていることが望ましい．エラーバウンドとは，与えらる問題である．

れた点と問題の解集合との距離をある定数倍で上か【NCP］（∬，ダ（ご））＝0，￡∈月ユ，ダ（ご）∈軍
ダは月nから月nへの連続関数，（・，・）は月れ上の内積，

埠＝（ご∈Rnlごi≧0，i＝1，…，乃）である・ダがアフィン関数のとき，この間題は線形相補性問題（Lim−ear Complementarity Problem，LCP）と呼ばれる．NCPに関連した問題として，ⅤIPがある．ⅤIPはらおさえることができる関数のことであり，アルゴリ
ズムの大域的，局所的収束率を解析する上で重要な役割を果たす．また，メリット関数のレベル集合が有界となれば，降下法によって生成される点列が集積点をもつことが保証される．

♭ 最適化問題に対しては，目的関数や（制約つき問題の場合は）ペナルティ関数を自然なメリット関数として用いることができますが，NCPやVIPにはそのような関数がふくしま まさお，やました のぶお 京都大学工学研究科〒606京都市左京区吉田本町
1997年6 月号

最初から備わっている訳ではありません．しかし，NCPやVIPを実際に解こうとすれば，解を定量的に評価するための関数が不可欠です．したがって，上に述べたような好まし© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（31）423

い性質をもつ関数を構成し，さらにそのような関数をうまく利用した効率的な手法を開発することは，実際的観点からも非常に重要な研究課題です【4，9】・（福島）q

4．種々のメリット関数

ここで，αは正の定数である．このメリット関数を用いた次の制約つき最小化問題はⅤIPと等価になる．
min fc，（r）s・t・X∈S

NCPやⅤIPを構成する関数ダのヤコピ行列∇ダ（ご）が対称ならば，任意のご0∈月れを用いて，実数値関数（1）

正則化ギャップ関数は，ギャップ関数に比べて多くの長所を備えている．とくに，ダが微分可能であれば，んも微分可能であり，任意の集合∫に対して関数値は必

J（ご）＝

、（−

（ダ（∬0＋t（エー￡0）），エー∬0）df

ず有限となる．さらに，（1）の停留点ご＊は，∇ダ（ごりがが定義でき，この関数は微分可能なメリット関数とな

正定植であれば，ⅤIPの解であることが保証されていることが知られている［11】．しかし，一般のNCPやる［7】．また，ダが強単調であれば，んは5上でVIP

ⅤIPでは，ダのヤコピ行列が対称となるとは限らない．

のエラーバウンドになる［23】．正則化ギャップ関数をそのため，∇ダ（ご）が非対称な問題に対する様々なメリ用いたニュートン法［23】や正則化ギャップ関数の拡張

ット関数が提案されてきた【町［24，25】も提案されている・

VIPに対する最初のメリット関数はAuslender［2】が提案した次のギャップ関数と呼ばれる関数である．

♭正則化ギャップ関数を点いついたのは，Auslender【2】を読んでいたときでした．そこでは集合5が 強凸 集合であればギャップ関数ダは微分可能になることが指摘されて

g（g）＝Sup（ダ（∬），エーy〉
y∈5

定義から容易にわかるように，関数gを制約集合5上で最小化する問題は，ⅤIPと等価になる．この関数は後で述べる多くのメリット関数の基礎となるが，いく
つかの欠点をもっている．まず，ギャップ関数gは一般に微分不可能である．また，∫が有界な集合でないとき，g（∬）は必ずしも有界な値をとるとは限らない．このため，5＝埠の場合に対応するNCPに直接適用することは困難である．
P ギャップ関数という名前は1982年のHearnの論文【12】で初めて使われました．そこでは凸計画問題の最適性条件
に対して上記の関数ダを定義しており，それ以前の研究で，より一般的であるAuslender［2］は引用されていません．文献【2】は仏語のせいか，それほど広く知られていませんが，これ以外にも興味深い結果がいろいろ書かれており，1976
年に出た本であることを考えると，非常に先見性豊かな書物ということができます．（福島）d
VIPと等価な制約なし最小化問題を構成するメリッいました．しかし，経済均衡問題や交通流均衡問題など実際の応用ではgは凸多面体になる場合が多く，
強凸 性
は成立しません．そこで思いついたのが，集合のかわりに関数の方が 強凸 になるようにしてやっても同様の性質が導けるのではないかということで，それがギャップ関数の定義式に2次の項を付け加えるアイデアです．そのように定義された関数んはギャップ関数にはない様々な良い性質をもつことが確かめられたため，論文にまとめ，Mathematical
Programmingに投稿したのが1989年のことです．2年余りしてその論文【71が出版された後のある日J・−S・Pangから「こんな論文が出ているが知っているか」と送らてきたのがAuchmutyの論文［1］です．その論文は少なくとも数理計画の世界でVIPを研究している人たちの間ではほとんど知られていなかったものですが，なんと正則化ギャップ関数と実質的に同じメリット関数が提案されていました．また，
それが1989年に出版されていることにも驚きましたが，論文投稿の日付を見ると【7】よりわずか一週間余りですが遅かったのです．それを見て安堵するとともに，研究は時間との勝負でもあることを改めて実感しました．（福島）q

これまでに紹介したメリ？ト関数を用いた最適化問
題は，微分不可能な制約なし問題であるか，または，微分可能な制約つき問題であり，微分可能な制約なし

ト関数として，次の標準残差関数がある．

最小化問題を構成できるメリット関数があるかどうか
r（ご）＝順一【∬−ダ（∬）】51l2

は，未解決問題として残されていた．この間題の一つ

ここで，抽は集合gへの直交射影を表す・この関数の解答として，山下・福島［31］は正則化ギャップ関数

はダが強単調でリブシソソ連続のとき，ⅤIPに対するをさらに正則化した関数を提案した．しかし，このメエラーバウンドとなることが知られている．しかしな

リット関数は関数値の評価に要する計算量が大きいとがら，この標準残差関数γは微分可能ではない．

いう問題があった．それに対して，最近，Peng【21】は，

福島［71は，ギャップ関数gの微分可能性に関する欠点を改良した次の正則化ギャップ関数んを提案し2つの正則化ギャップ関数の差で定義される関数を用いれば，微分可能で制約なし最小化問題を構成できるている．なお，この関数は，Auchmuty［1］によって，同ことを示した．山下・田地・福島［34］はこの結果をさ時期に独立に提案されている．

らに発展させることにより，次の関数鮎βがⅤIPに対ん（ご）＝Supyぴ（（ダ（ご），ご一再一号順一洲2）するメリット関数として様々な好ましい性質をもつこ
オペレーションズ・リサーチ

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

●

とを示した．

表1：ⅤIPに対するメリット関数
メリット関数 微分 制約 停留点 エラーバウンド

鮎β（∬）＝ん（ご）−わ（ご）ここで，0＜α＜βであり，α＝左の特別な場合が
Peng［21】が考察した関数に対応している．関数恥βをD−ギャップ関数と呼ぶ．Dは difkrence を表して

ギャップ

不可 5

標準残差

不可 なし

Lip．，強単調

正則化ギャップ 可能 5 正走値 5上で強単調
D＿ギャップ
可能 なし 正定借 Lip．，強単調いる．この関数は，後で紹介するNCPに対するメリット関数である陰ラグランジュ関数のⅤIPへの拡張に

勘月（ご）＝0，㌫≧0，彗（ご）≧0，f＝1，2，…，m

なっており，陰ラグランジュ関数の多くの性質を引き

このNCP特有の構造を利用して，ⅤIPとは異なるメ継いでいる・例えば，関数鮎βの停留点ご＊は∇F（￡ヰ）

リット関数を構成することができる．

が正走値であればⅤIPの解となり，また，ダが強単調
でリプシソソ連続のとき，恥βはⅤIPのエラーバウン

ドとなる［34］．D−ギャップ関数を目的関数とする最小次の性質をみたす関数￠：月2→月をNCP関数と呼ぶ［6】．

￠（α，♭）＝0⇔αゐ＝0，α≧0，ゐ≧0

化問題の解法として，一般化ニュートン法を拡張した
任意のα，みに対して￠（α，b）≧0であるような非負の手法が提案されている【15，22］．

NCP関数を用いれば，NCPに対するメリット関数中♭ 正則化ギャップ関数の後，NCPに対しては後で紹介する陰ラグランジュ関数や2乗Fischer−Burmeister関数など，
もとの問題と等価な微分可能制約なし最適化問題を構成するメリット関数が次々と知られてきましたが，VIPに対しを次のように構成することができる．
Il吋）＝∑￠（ご ，月（ご））i＝1てはそのようなメリット関数はなかなか見つかりませんでした．その最初の試みとして，私たちは二重の正則化を施し

NCP関数の定義より明らかに，関数中を目的関数とたギャップ関数を考えてみましたが［31］，そうして得られたメリット関数はとくにエラーバウンドに関して非常に好まする制約なし最小化問題はNCPと等価である．制約

しい理論的性質をもつものの，実際の計算に用いるには特殊な場合を除いてそれほど便利とはいえませんでした．そうこうしているうちに，中国を訪問したとき北京の中国科
学院で講演をする機会がありました．その講演後，一人の若者がこれを読んでほしいといって自分の論文をもってきました．その論文（Peng【21］）を読むと，そこに私たちが探していたものが書かれているではありませんか．ただ，Pengの発想はNCPに対する陰ラグランジュ関数を拡張するというところからきており，議論が複雑で，あまり読みやすい

ものではありませんでした．その後，よく考えてみると，話はもっと簡単で，値の異なるパラメータをもつ2つめ正則化
ギャップ関数の差を考えるだけで同様のメリット関数が定義できることがわかり，その関数の様々な性質も明らかになりつき最小化問題を構成するための制約つきNCP関数
については【29］で考察されている．ここでは，非負のNCP関数の例として，次の4つを紹介しよう．
（i）￠〃月（α，占）＝min（α，り2（ii）￠〟5（α，ム）＝αゐ＋去（max（0，d−αり2−α2＋max（0，ぁーαα）2一み2），（α＞1は定数）（iii）￠ダβ（α，あ）＝喜（仰一也−り2（iY）山（α，り＝去max（0，扉）4＋喜（J才子扉−α−り2
これらの関数のうち両用は微分不可能であるが，そました［34】．私たちはこの関数を D−ギャップ関数と名付けの他は微分可能である．よって，関数￠〃5，￠ダβ，￠A

ましたが，これはⅤIPに対する微分可能かつ無制約の最適化問題を構成できるメリット関数として現在知られている最良のものと考えられます．（福島）dを用いて構成したメリット関数は，ダが微分可能であ

これまで述べてきたⅤIPに対するいくつかのメリット関数の性質をまとめると表1のようになる．ここで， 停留点 はそのメリット関数の停留点ごがⅤIPの解になるための∇ダ（ご）の条件を表し， エラーバウン
ド はそのメリット関数がエラーバウンドになるためのダの条件を表している．また， Lip． はダがリブれば微分可能となる．以下では，これらの関数で構成される各メリット関数の性質について述べる．
関数￠〃月を用いたメリット関数は，ⅤIPに対する標準残差関数rを特殊化したものに他ならない．
関数￠〃5を用いれば次の陰ラグランジュ関数〟。
を構成することができる．
n〟。（ご）＝∑￠〃5（勘十R（ご））i＝1

シッツ連続であることを表している．

次にNCPに対するメリット関数を紹介しよう．まず，NCPが次のように成分ごとに分解した形で表されることに注意する．
1997年6 月号

MangasarianとSolodov［20］は，NCPと等価な制約つ
き最小化問題min（c，F（r））s・t・X≧0，F（r）≧0© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（33）425

の拡張ラグランジュ関数を変形することによって，陰ラグランジュ関数を導き出した．この関数を目白勺関数とする制約なし最小化問題はNCPと等価であり，微分可竃馴生などの好ましい性質を有している．とくに，爪先の停留点￡は∇ダ（ご）が正定借であればNCPの解り扱うのに大変つごうがよいので，これを利用したニュートン型の解法もいろいろ提案されています．それらの方法
はある意味で内点法に似た振る舞いをするのですが，内点法のようにα＞0，占＞0を満たす必要はないという点が大きく異なっています．Fischer−Burmeister関数についてはFischerによるサーベイ論文【6］があります．（福島）q
メリット関数γ，〟α，βに対して次の不等式をみたすであることが保証される【30］．また，NCPに対する陰正の定数cl，C2，C3，C4が存在する［26，18】．

ラグランジュ関数は，一般化相補性問題やⅤIPにも拡

Clr（∬）≦脆（￡）≦c2r（∬）brall￡∈月m

張されている［28，2叶C3r（影）≦♂（￡）≦c4γ（ご） brallご∈月れ♭ 奈良先端大の修士課程に入学したばかりの山下にしたがって，これらのメリット関数のひとつがエラー

Mangasarian−Solodov［20］の原稿を読んでみてはどうかといって渡しておいたところ，しばらくして，論文中で今後のバウンド性またはレベル集合の有界性をもてば，他の課題とされていた 関数〟。の停留点が解になるための条

メリット関数もエラーバウンド性またはレベル集合の件 がわかったという報告がありました．早速検討したと有界性をもつことがわかる．これまでに知られている

ころ，正しいことが確認されましたので，論文［叫にまとめ，MangasarianがAsso9iateEditorをしているJOTAにところでは，これらのメリット関数がエラーバウンド

投稿しました．これについても，別の研究者が同様の結果をになるための十分条件はダが強単調かつリプシソソ

得てMangasarianに送りましたが，僅かの差で私たちに先連続であることであり，レベル集合が有界となるためを越されたいう話があります．また，陰ラグランジュ関数がVIPに対する正則化ギャップ関数と関連があることは文献【20］で指摘されていますが，その後のTsengと私たちの論
文［28］でもより明確な形で議論しています．しかし，その当時は，私たちにも陰ラグランジュ関数は相補性問題の構造に依存する関数という認識があったため，VIPに拡張するまでには至りませんでした・その衡Peng［21］によるD−
ギャップ関数の発見によって陰ラグランジュ関数がVIPに直接拡張できることが明らかにされたのです．（福島）d

関数毎βを用いて構成される次の関数が，最近，注の十分条件はダが強単調であることである．
NCP関数￠Aを用いたメリット関数は，n

弘（ご）＝∑去max（0，ご五月（瑚4＋β（ご）i＝1となり，2乗F−B関数の多くの性質を引き継いでいる【33］・例えば，βAの停留点ごは，∇ダ（ご）が半正走値であればNCPの解となる．さらに，関数♂Aはいくつかの好ましい性質をもっている．まず，♂Aがエラーバウン

目を集めている2乗Fischer−Burmeister（F−B）関ドとなるための十分条件はダが強単調であることで数である［5j．

あり，ダの・リブシソソ連続性は必要としない．また，レベル集合が有界となるための十分条件は，ダが単調関

nβ（㌶）＝∑毎β（ごi，瑚

数でNCPが狭義実行可乾すなわちご＞0，ダ（ご）＞0Ⅰ、＝l

この関数の長所のひとつは，βの停留点ごがNCPのとなる点が存在することである．なお，関数βに似た解となる十分条件が∇ダ（ご）が半正定借であることで関数のクラスが［16］で考察されている．

奉り，これは正則化ギャップ関数や陰ラグランジュ関

最後に，メリット関数〟。，β，βAの性質を表2にま数の停留点が解となる条件よりも弱い．そのためト2

とめる．ここで， 停留点 はメリット関数の停留点ご

乗F−B関数は，陰ラグランジュ関数よりも応用範囲ががNCPの解になるための∇F（ご）の条件を表し， エ広い．例えば，2次計画問題をLCPに定式化すると，ラーバウンド はメリット関数がエラーバウンドにな

そのLCPにおいては関数ダのヤコピ行列∇ダ（ご）はるためのダの条件を， レベル集合 はメリット関数の半正定借となるので，関数♂の停留点に関する上記のレベル集合が有界になるための条件を表している．ま条件が満たされる．2乗F−B関数の一般化相補性問題

た， 狭実 はNCPが狭義実行可能であることを表しへの拡張や［14］，2乗F−B関数の最小化に対する一般ている．

化ニュートン法も提案されている［13，32］．

♭ 2変数関数￠ト，わ）＝仰一α−わはFischerの論文【5］において初めて示されました．Fischerによれば，この関数は1985年頃に彼の同僚であるBurmeisterという人と何かの問題について議論していたときに，Burmeisterが発見したものだということです．このことから，関数￠はFischeトBurrneister関数あるいは単にFischer関数と呼ばれています．上にも述べたように，この関数はNCPを取

5．今後の研究指針
前節で紹介したように，これまでにⅤIPやNCPに対する様々なメリット関数が提案され，それらの関数
1表2の 正定借 ， 半正定借 はそれぞれ ア行列 ， 尾行
列 というより弱い条件でおきかえることができる．
オペレーションズ・リサーチ

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

●

提案されているが［10】，このような研究はまだ始まっ

表2：NCPに対するメリット関数たばかりであり，多くの研究課題が残されている．

停留点 エラーバウンド レベル集合

SDCPは，Sを対称行列の集合としたとき，次の条几オα 正走値1

強単調，Lip．

強単調

β 半正定値1

強単調，Lip．

強単調♂A 半正定借1

強単調

単調，狭実

件をみたす￡∈5を求める問題である．
［SDCP］（r，F（x）〉＝0，X∈K，F（x）∈K
ここで，〟⊂∫は半正走値対称行列の集合であり，ダの性質が示されてきた．研究のポイントは，適用可能な問題のクラスが広く，さらに関数値や勾配の計算量は5から∫への関数である・また，∫の内積（・，・〉は（ご，y〉‥＝traCe（ごTy）が少なくてすむといった好ましい性質をできるだけ多で定義される．最近，NCPに対する陰ラグランジュ関

くもつメリット関数を構成し，その理論的性質を解明

数や標準残差関数，2乗F−B関数がSDCPに拡張でするとともに，効率的なアルゴリズムを開発することきることが示されている［27］．しかし，それらのメリッにあった．このような観点から見れば，まだ次のようト関数の性質はまだ十分に解明されておらず，興味深な未解決な問題が残されており，それらを調べること

い研究課題として残されている．

が今後の研究課題となる．

♭研究においては，独自のアイデアを暖め発展させていくと同時に，他の人たちがどのようなことを考え，どのような成果を発表しているかという情報を早く入手し，それによって自分のアイデアの客観的な評価をすることも大切なことです・しかし，論文誌に論文が掲載されるまでには，投稿してから少なくとも1年から2年かかることも珍しくありま

ロ標準残差関数はダの強単調性の仮定だけでエラーバウンドになるか？

現在，標準残差関数のエラーバウンド性の証明には，ダの強単調性とリブシソソ連続性が必要とされている．

せんから，論文が正式に出版されたときには，すでに新鮮さ

しかし，リブシソソ連続性を満たさず，かつエラーバ

はかなり失われていると考えられます．そこで，論文の原稿の段階でそれを手に入れる必要がありますが，昔は著者

ウンドとならない具体例は知られていない．

に直接ハードコピーを郵送してもらうしか方法がありませ□ⅤIPにおいて，ダが単調関数のとき，停留点が解となるようなメリット関数は存在するか？

NCPに対しては，2乗FTB関数がそのような性質をもっている．しかし，2乗F−B関数はNCPの特性である成分ごとの分離可能性に依存しており，ⅤIPに拡張することができない．ⅤIPに対して，このような性質をもつメリット関数を構成できるであろうか．
ログが単調関数であるとき，凸関数となるメリット
関数は存在するか？

陰ラグランジュ関数など，NCPに対するメリット関数のいくつかは，ダが強単調なアフィン関数という条件のもとで，凸関数となることが知られている．その条
件よりも緩い，例えばダが単調関数という条件のもとで，凸関数となるメリット関数を構成できるであろうか．

んでした．しかし，最近は多くの研究者がWWWのホームページをもっていて，そこから新しい論文をダウンロードできるようにしています．あるいは，新しい論文のリストを公開していて，請求してきた人に論文を送るようにしている人もいます．例えば，本稿の参考文献にあげた私たちの最近の論文のpsファイルはhttp‥／／www．kuamp．kyoto−u．aC．jp／
1abs／optipla／member／staq／fuku／recent−WOrk・htmlから自由にダウンロードしていただくことができます．また，本稿のテーマであるNCPやVIPに関連する事柄についてはComplementarityProblemNET（http：／／www・CS・wisc．edu／

cpnet／），より広く最適化・数理計画関係についてはNet−
WOrkEnabledOptimizationSystem（NEOS）（http‥／／www．
mcs・anl・gOV／home／otc／index．html）などを通して情報を検索することができます．（福島）q

最後になりましたが，本稿の執筆を勧めていただいた水野真治先生と原稿を読んで適切なコメントを頂戴したお二人の編集委員に感謝します．

参考文献［1］Auchmuty，G．， Variationalprinciplesfor variational
inequalities， Numer・Funct・Anal・Opt・10（1989），Pp．
863−874．

さらに，今後の研究指針として，NCPやVIPに対する等価な再定式化の方法を，均衡条件を制約にもつ［2］Auslender，A・，Optimisation：M6thodes NtLm6riqtLeS，Masson，Paris，1976．

［3］Cottle，R・W．，Pang，，：S．and Stone，R．E．，The Lin

数理計画問題（MPEC）や半正定借相補性問題（SDCP）

earComplemenLar・iLy Problem，Academic Press，Newに活用することが挙げられる．

York，NY，1992．

制約条件が線形相補性条件を含むMPEC［19］に対しては，LCPの再定式化の手法を応用した反復解法が1997年6 月号［4］Ferris，M・C・arLd Pang，］．−S．， Engineering and eco−nomic applications of complementarity problems，刀SL4MReview，tOaPpear．

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

（35）427

［5］Fischer，A．，く A specialNewton−type Optimization
method， Optimization24（1992），pp・269L284＝・［6］Fischer，A．，く AnNCP−functionanditsuseforthesolu−［21］Peng，J・M・， Equivalence of variationalinequal−
ity problernS tO unCOnStrained optimization，

Math．

Prog．，tOaPpear．

［22］Sun，D・，Fukushima，M・and Qi，L・， A com−
RecentAdvances
inNonsmooth Optimization，D．−Z．Du，L．QiandR．S． PutablegeneralizedHessianoftheD−gaPfllnCtionand
Newton−typemethodsforvariationalirLequalityprob−
Womersley（eds・），World Scienti航c Publishers，1995，
tion ofcomplementarity problems，

1ems，

pp．88−105．

Com〆emer血「軸αndlんrねfior柑JPro封em5ごState qfthe Art，M．C．Ferris a・ndJ・−S・Pang（eds・），［7］Fukushima，M．， くEquivalent differentiable optimiza−tion problems and descent methods for a．symnlet−

SIAM，Philadelphia，1997，pp．452−472．

ric variationalinequality problems， Math．Prog．53 ［23］Taji，K・，Fukushima，M・andIbaraki，T・， Aglobally

COnVergentNewtonmethodforsoIvingstronglymono−（1992），pp・99−110・

tonevariationalihequalities， Math・Prog・58（1993），［8］Fukushima，M．， Merit functions for variationalinT
equality a．nd complementarity problems，

pp．369−383．

Nonlinear

Optimization andApplications，G．DiPilloandF．Gi−【24］Taji，K．and Fukusllima，M．， A globally conver−annessi（eds・），Plenum Press，New York，1996，pP・

gent Newton method for soIving variatiorLalinequa・l−

155−170．

ity problems withinequalityconstraints， RecentAd一川IICeSiTINonsmo（一th OpE＝li＝atio‖．D、−Z．Du，Ⅰ，．Qi［9］福島雅夫， 均衡モデル：相補性問題への招待 ，オペレ

andR・S・Womersley（eds・），WorldScienti6cPublish−

リサーチ41（1996），pp．33ト336．

ーションズ・［10］Fukushima，M・，Luo，Z．−Q．and Pang，J．S．， Aglob−

a11yconvergentsequentialquadraticprogrammingaト

ers，1995，pp，405−417．

［25】Taji，K・andFukushima，M・， Aneweritfunction
and a successive quadratic programmlng algorithm

gorithm for mathematicalprograms withlinearcom−

plementarity constraints， Comp．Opt．Appl．，tO ap−
pear・【11］Harker，P・T．and Pang，］．−S．， Finite−dimensional
Variationalinequality and nonlinearcomplementarlty

for variationalinequality problems，

SIAMJ．Opt．6（1996），pp・704−713・［26］Tseng，P・， Growthbehaviorofaclassofmeritfunc−
tioIISfor tlle nOnlinearcomplementarlty prOblem，

J．

Opf・rんeoryAp〆・89（1996），pp・17−37・
problems‥Asurveyoftheory，algorithmsandapplica−［27］Tseng，P・，くくMeritfunctionsfor semi−de負nitecomple−
tions， 〝o亡ん・Prog・48（1990），pp・161−220・［12］Hearn，D．W．， Thegapfunctionofaconvexprogram，Oper．月eβ．上eは1，pp．67−71．

mentarity problems，Working paper，Depa・rtmentOf

Mathematics，UniversltyOfWashington，Seattle，WA，
1996．

［13］Jiang，H．，Fukushima，M．，Qi，L．a．ndSun，D．，
Atrust［28］Tseng，P・，Yamashita，N・andFukushima，M・，
Eq11iv−
reglOn method for soIvinggeneralized complementaト
1typrOblems， SIAMJ．Opt．，tOappear．

alence ofcomplementarlty prOblems to difFerentiable
minimization：A uni航ed approach，

SIAMJ．Opt．6［14］KaLnZOW，C．and Fukushima，M．，

Equivalenceofthe （1996），pp・446−460・generalizedcomplementarltyPrOblemtodi什erentiable［29］Yamashita，N・， Some properties of the restrictedunconstrainedminimization，

J．Opt．TheoryAppl．90（1996），pp・581−603・

NCP−functions for the nonlinear complementa．rlty
PrOblem，Workingpaper，Dept・OfAppl・Math・and［15］Kanzow，C．and Fukushima，M．，

TheoreticalandPhys．，KyotoUniversity，Kyoto，Japa・n，1996．
numericalinvestigation of the D−gap function for［30］Yamashita，N．arLd Fukushima，M・， On stationary
boxconstrainedvariationalinequalities，Math．Prog．，

pointsoftheimplicitLagranglanfornonlinearcomple−

mentarityproblems， J．Opt・TheoryAppl・84（1995），［16】Kanzow，C．，Yamashita，N．andFukushima，M．， Newpp．653−663．
NCP−functions and their properties， J．Opt．Theory［31］Yamashita，N・and Fukushima，M・， Equivalent un−
s11bmitted．

COnStrainedminimizationandglobalerrorboundsfor

Appl．，tO aPpear．

Variationalinequality problems，［17］Kojima，M．，Megiddo，N．，Nomi，T．andYoshise，A．，

SIAMJ．CoTltrOL

Opf・35（1997），pp・273−284・

A 打n漬edAppro（lCわーoJnferior Poi円上AJダOr鵡mβわrLineor Compteme一雨rity Problems，Springer−Verlag， ［32】Yamashita，N・and Fukushima，M・，

ModiRed New−ton methods for soIving semismooth reformulations

Berlin，1991．

Ofmonotonecomplementarityproblems， Math．Prog．
【18］Luo，Z：Q．，Mangasarian，0．L，Ren，J．and Solodov，
M．V．，

New error bo1111ds for thelinear complemen−76（1997），pp・469−491・［33］山下信雄，福島雅夫，非線形相補性問題に対する新しいメリット関数，1996年度日本オペレーションズ・リサ
ーチ学会秋期研究発表会アブストラクト集，1996，pp．
［19］Luo，Z，−Q．，Pang，J．−S．and Ralph，D．，MathematicaL

tarityproblem， Math・Oper・Res・19（1994），pp・880q
892．

124−125．

Programs with Equilibrium Constraints，Cambridge
UniversityPress，Cambridge，UK，1996．

［20］Mangasarian，0．L．and Solodov，M．V．，［34］Yamashita，N・，Taji，K・and Fukushima，MJ Uncon−
Nonlinearstrainedoptlmizationreformulationsofvariationalin−

COmplementarity as unconstrained and constrained

equalityproblems，

J・Opt・TheoryAppL・，tOaPPear・

minimization， Math・Prog・62（1993），pp・277−297．
オペレーションズ・リサーチ

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

●