超立方体上での凸2次関数の最大化
スポンサーリンク
概要
- 論文の詳細を見る
この論文では、古くから難問とされている凸2次関数のn次元超立方体上での最大化問題を解くための新らしいアルゴリズムを取扱う。アルゴリズムの基本的な考え方は、まず問題を等価な双線形計画問題に変換し、最近この問題に対して開発された切除平面法を適用することであるが、本論文では問題の特殊構造を利用することにより・深い凸型カットがきわめて手軽に生成されること、またアルゴリズムの有限回収束性が凸型カットのみによって保証されることが示される。なお、この方法を超立方体の端点の総数え上げ法と比較した場合(I)早い段階で良い局所最適解が得られること(II)深いカットの効果により、最適解が早く求重る可能性があること(III)より大型の問題を取扱えることなどの長所がある一方、計算の途中で0-1整数線形計画問題を解かなくてはならないという短所を有するが、問題の特殊構造を利用することにより、この手間は大巾に軽減されることが示されている。