Tohazugatali Economic Review

2033：とはずがたり：2019/12/23(月) 10:56:09: >>2032

cオペレーションズ・リサーチ
離散凸解析のすすめ
室田一雄
http://www.orsj.or.jp/archive2/or58-06/or58_6_311.pdf

離散凸解析は，整数格子点の集合のうえで定義された関数を，凸解析と組合せ論の両方の視点から考察する理論であり，離散最適化，オペレーションズ・リサーチ，システム解析，ゲーム理論，数理経済学，離散幾何などへの応用がある（図1）．M凸関数，L凸関数の概念，共役性および双対性が理論の骨格であり，種々の問題に対してアルゴリズムが開発されている．

…

以上のように，1変数関数の場合には，式(1)で離散凸性の概念を定義することによって，凸拡張性，局所最適と大域最適の同値性，離散ルジャンドル変換，フェンシェル型双対定理，離散分離定理など，離散凸関数が持つべき性質が得られる．第2節で線形計画について列挙した定理(Conv, LocalOpt, DualPair, MinMax,Separ)に対応する定理がすべて揃っていることに注目されたい．このように，「1変数離散凸関数の最適化理論」は簡単にでき上がる．しかし，これを多変数関数に拡張することは自明でない．離散凸解析は，組合せ論的な考察に基づいてM凸関数とL凸関数という概念を定義し，この拡張を実現した理論体系である．

…

1980年代に，KelsoとCrawfordはゲーム理論の文脈で効用関数の粗代替性に着目し，この条件下である種のゲームに均衡が存在することを示した．2000年以降の研究により，粗代替性がM凸性と等価であることが明らかとなり，離散凸解析とゲーム理論（数理経済学）との交流が始まった

…

(M凸関数とL凸関数の説明→略ｗ)

…

M凸関数とL凸関数は，共役性や双対性といった数学的に美しい構造を持っているだけでなく，計算の観点からも扱いやすい対象である．

室田一雄，離散凸解析，共立出版，2001．

室田一雄，離散凸解析の考えかた，共立出版，2007．

室田一雄，塩浦昭義，離散凸解析と最適化アルゴリズム，朝倉書店，2013．

田村明久，離散凸解析とゲーム理論，朝倉書店，2009

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）