ロバスト最適化

ロバスト最適化#

  • 読み: ろばすとさいてきか

  • 英名: Robust Optimization

ロバスト最適化とは,問題を定義するデータが不正確あるいは不確定な場合にも, 信頼できる結果を返すような最適化問題のモデリング技法およびその解法を指す. 最適化の結果が外部の擾乱について非常に不安定で,全く信頼できない解を返すケースが存在することが, この必要が叫ばれる背景となっている.

例えば [1] では,有名な線形計画問題のベンチマーク問題(NETLIB ライブラリ)を例として, 線形制約を定義する係数に対して微小な擾乱を加えた場合,「最適解」が大きく実行不可能になってしまう例を示している.

ロバスト最適化は,問題を定義するデータが存在する集合を仮定して,その中における最悪のケースの最適化という形で定式化する. データが存在する集合としては,二次錐の制約によって定義される集合, あるいは行列の半正定値性を定義する制約によって定義される集合が通常用いられる. このようにしておくと,ロバスト最適化の解が二次錐計画問題,半正定値計画問題を解くことにより, 多項式オーダーで求められるので,現実的なロバスト最適化問題の解を実際に導くことができる.

参考文献

[1]

Aharon Ben-Tal and Arkadi Nemirovski. Robust optimization - methodology and applications. Mathematical Programming, 92(3):453–480, may 2002. URL: http://link.springer.com/10.1007/s101070100286, doi:10.1007/s101070100286.