離散最適化に於ける弱双対定理
スポンサーリンク
概要
- 論文の詳細を見る
数理計画 (Mathematical Programming) はミクロ経済理論の最小化・最大化問題を扱う静学分析の基盤を与えるものであり近年ではポートフォリオ理論の様に理論・解法の両面に数理計画が用いられている例もある。数理計画の最近の発展は、理論面では非滑関数の最適化や半正定値 計画等一般化の方向に進んできているが、線形計画に対する多項式時間の解法が発見されて以来、理論・解法の両面から変数の連続性、離散性の境界を究明しようとする研究方向が活発になってきている。 ところで数理計画でも変数が離散の整数計画では、整数線形計画でさえ双対ギャップが存在して、双対理論が作られていないのが現状である。代理(surrogate)双対緩和の理論的性質もまだ十分に述べられておらず、Ram and Karwan にも混合整数計画問題に於いて代理双対ギャップの存在が示されたに過ぎない。 本稿では整数計画に既に代理双対ギャップが存在することと、著者に依る代理双対ギャップやラグランジュ双対ギャップが存在しない為の必要十分条件の導出、及び混合整数計画への拡張結果について述べる。最後に一般の離散計画に対する双対理論を中心とした最近の話題や展望について述べる。
- 北海道大学の論文
- 2001-12-11
著者
関連論文
- Nash 均衡の計算複雑度について
- Farkasの補題について
- 現代暗号の数理
- Farkasの補題再考
- ダンツィークの統計学への貢献
- 生産理論に関する或る考察
- 一般均衡と数理計画 (経済学部50周年記念号)
- 混合整数計画に対する弱双対定理 (最適化の数理とアルゴリズム)
- 離散最適化に於ける弱双対定理
- 準凹計画とその応用 (最適化のための連続と離散数理)
- 3Y-1 野球の評価モデルについて
- 半無限計画に対する信頼領域法の拡張について(最適化の数理における離散と連続構造)
- 区間方程式の解について(数理計画モデルにおける最適化理論)
- 「ORの計算環境」研究部会終了報告(部会報告)
- マルチメディアと現代解析 : 画像圧縮の話題から
- 静学モデルの或る一般化について
- 2集団マッチングについて : メカニズム・デザイン
- 生産理論に於ける安定性 (最適化の基礎理論と応用)