ロバスト最適化 — 最悪ケース数理計画法
- 提唱者
- Ben-Tal, El Ghaoui & Nemirovski (seminal book, 2009); Bertsimas & Sim (tractable polyhedral formulation, 2004)
- 年
- 1970s theoretical roots; modern tractable form from late 1990s–2004
- 種類
- Mathematical programming framework
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
ロバスト最適化は、1990年代後半にベンタルとネミロフスキによって形式化され、ベルツィマスとシム(2004年)によって広く解可能にされた数理計画法のフレームワークであり、パラメータ値が正確にわかっていると仮定するのではなく、定義済みの不確実性集合内のあらゆるシナリオで許容可能な性能を発揮することが保証された決定を見つける。単一の期待される結果を最適化する代わりに、不確実なデータのすべての妥当な実現にわたる最悪ケースの目的関数を最小化する。
手法の背後にある直感
通常の最適化は、与えられた数値を信頼する。ロバスト最適化は、それらの数値が誤っていたらどうなるか、ある範囲内で、と問う。それは、その範囲内で最悪の入力が自然によって選ばれたときに最も損害が少ない決定を見つける。典型的なケースではわずかな性能コストを受け入れる代わりに、平均的な負荷ではなく、最も重い信頼できる負荷に耐える橋を設計すると考えてほしい。
歴史学
ロバスト最適化の理論的ルーツは、ソイスタ(1971年)とウォルド(1945年)のミニマックス決定理論にたどる。この分野は、1997年以降の一連の論文で、アルカディ・ネミロフスキとアハロン・ベンタルによって現代的で解可能な基盤が与えられ、エル・ガウィとの2009年のモノグラフで集大成された。ディミトリス・ベルツィマスとメルヴィン・シム(2004年)は、名目上の問題の線形性を維持する予算不確実性(多面体)定式化を導入し、ロバスト線形計画法を広く利用可能にした。それ以来、ロバスト最適化は、整数計画法、2段階定式化、および履歴観測から導出されたデータ駆動型不確実性集合をカバーするように拡張された。
使うべき場面
ロバスト最適化は、パラメータの不確実性が有界であるがその分布が未知または信頼できない場合、最悪ケースの保証が必要な場合(安全性クリティカルまたは規制上の文脈)、および確率計画法におけるポリシー分布ではなく、単一の実行可能な決定が必要な場合に適切である。連続決定変数で機能する。最小サンプルサイズ要件はない — 不確実性集合はデータから推定するのではなく、解析的に定義される。不確実性が有界でない場合、不確実なパラメータの確率分布が利用可能で正確である場合(代わりに確率的最適化を使用)、またはシナリオベースの検証で約1,000シナリオ評価未満が実行可能である場合には適さない。
限界と注意点
- 解は必然的に名目上の最適解よりも保守的になる;不確実性集合が大きい場合、ロバスト性の価格は大きくなる可能性がある。
- 現実的な不確実性集合を定義するにはドメイン知識が必要;不適切に選択された集合は、過度に保守的であるか、真の摂動をカバーしない可能性がある。
- 非凸問題または一般的な混合整数計画法の場合、ロバストな再定式化はNP困難であり、特殊な分解アルゴリズムが必要になる場合がある。
- ロバスト最適化は確率情報を含まない;信頼できる分布が利用可能な場合、確率計画法はより高い期待性能をもたらす可能性がある。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 不確実なパラメータの確率分布を必要とせずに、決定論的な最悪ケースの保証を提供する。
- 凸不確実性集合の再定式化は、名目上の問題と同程度に解可能であることが多い — 追加の計算爆発はない。
- 保守性のレベルは、不確実性集合のサイズと形状によって直接制御可能であり、ロバスト性と性能のトレードオフを明示的かつ透明にする。
- サプライチェーン、金融、工学設計、エネルギーシステムなど、有界なパラメータ不確実性が存在する多様なドメインに適用可能。
応用
- 不確実な需要とリードタイムの下でのサプライチェーンと物流ネットワーク設計。
- 資産リターンの不確実性下でのポートフォリオ最適化 — ロバストな平均・分散フロンティア。
- 製造公差がパラメータの不確実性を導入する工学設計(構造、機械、航空宇宙)。
- 不確実な再生可能エネルギー発電と燃料価格の下でのエネルギーシステム計画。
- 処理時間または移動時間が不正確にわかっているスケジューリングおよびルーティング問題。
使い方
使い方
アナリストは、名目上のパラメータ値の周りの妥当な摂動の領域である不確実性集合を指定する。一般的な形状には、ボックス(各パラメータが独立して区間内で変動する)、楕円体(摂動がユークリッドノルムで制限される)、多面体、および予算制約(ベルツィマス・シム)集合が含まれる。この選択は、不確実性がどの程度相関し、どの程度深刻になりうるかについての仮定をエンコードし、結果として得られる解の保守性を直接制御する。
最適化問題はミニマックス形式で定式化される:敵対的不確実性が課すことができる最大コストを、決定変数について最小化する。形式的には、目的関数は min_x max_{u in U} f(x, u) となり、制約は不確実性集合 U 内のすべての u に対して満たされなければならない。この内部最大化は、自然が不確実なパラメータの最悪の実現を選択することをモデル化する。
凸不確実性集合の場合、ミニマックス問題は解析的に決定論的凸計画問題に等価である — 楕円体集合の場合はしばしば二次錐計画問題、多面体集合の場合は線形計画問題となる。この解可能な再定式化は、ベンタルとネミロフスキの重要な洞察である:多くの古典的な問題のロバストな対応物は、名目上の問題よりも解くのが難しくない。非凸構造の場合、ベンダー分解は問題をマスター問題と敵対的サブ問題に分割し、反復的に解く。
再定式化された決定論的プログラムは、標準的な凸または混合整数ソルバーに渡される。再定式化は通常、錐計画または線形計画問題であるため、市販のソルバーが効率的に処理する。ソルバーは単一の決定ベクトル、すなわちロバスト最適解を返す。これは、不確実性集合内のすべてのシナリオに対して実行可能であり、ほぼ最適である。
アナリストは、ロバスト性の価格を調べる:名目上の最適目的値(不確実性なし)とロバスト最適値との差。タイトな不確実性集合は小さな差をもたらすが保証は弱くなる;大きな集合は、典型的なシナリオでの高い性能コストで強力な最悪ケース保護をもたらす。不確実性集合のサイズに関する感度分析は、保守性のレベルの最終的な選択をガイドする。
よくある落とし穴
- 過度に大きな不確実性集合を選択すると、実質的に役に立たないほど保守的な解が得られる — ドメイン知識または履歴変動性の境界に対して集合サイズを調整する。
- ロバスト最適化と確率的最適化の混同:不確実なパラメータの確率分布が確立され信頼されている場合、確率的最適化の方が適切である可能性が高い。
- 不確実性が真に有界でない場合にロバスト最適化を適用すると、最悪ケースの保証が無効になる — ロバスト最適化は有界な摂動を仮定する。
- 解決後にロバスト性の価格を調べないこと:名目上の目的とロバストな目的との間に大きな差がある場合、不確実性集合が非現実的に広い可能性があり、再検討する必要がある。
よくある質問
ロバスト最適化は確率的最適化とどう違うのか?
ロバスト最適化は、これらのシナリオに対する確率分布を仮定せずに、有界な不確実性集合内のすべてのシナリオに対して実行可能でほぼ最適な単一の決定を求める。確率的最適化は、既知の(または推定された)確率分布を使用して期待性能を最適化し、通常は1つの固定された解ではなく、ポリシーまたはリカバリーアクションを生成する。最悪ケースの保証が重要であり、信頼できる分布がない場合はロバスト最適化を選択する;良好な分布がわかっており、平均性能が主要な基準である場合は確率的最適化を選択する。
ロバスト性の価格とは何か?
ロバスト性の価格とは、不確実性を考慮せずに得られた名目上の最適解と比較して、目的関数の値が増加すること(最小化問題の場合)である。ベルツィマスとシム(2004年)は、彼らの予算不確実性定式化では、この価格が不確実なパラメータ数の平方根にしか比例して増加しないことを示しており、実際には控えめである。解決後にこの差を調べることは不可欠である:もしそれが非常に大きい場合、不確実性集合はおそらく過度に保守的である。
どの不確実性集合の形状を選択すべきか?
ボックス集合は最も単純で最も保守的 — 各パラメータは独立して変動する。楕円体集合(ベンタル&ネミロフスキ)は、ユークリッドノルムで制限された相関摂動をモデル化し、二次錐計画問題につながる。多面体/予算制約集合(ベルツィマス&シム)は、同時に偏差できるパラメータの数を制御し、線形性を維持し、保守性を低減する。摂動がどのように共起するかについてのドメイン知識と、利用可能なソルバークラスに基づいて選択する。
ロバスト最適化は整数決定変数を扱えるか?
はい、しかしロバストな整数計画法および混合整数計画法は大幅に難しい。混合整数線形計画法のロバストな対応物は、最悪の場合NP困難であることが多い。ベンダー分解および列・制約生成アルゴリズムは標準的なアプローチであるが、問題サイズと不確実性集合の複雑さは管理可能に保つ必要がある。
関連する手法
参考文献
Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009). Robust Optimization. Princeton University Press.
ISBN:9780691143682コピーしました。Bertsimas, D. & Sim, M. (2004). The Price of Robustness. Operations Research, 52(1), 35-53.
DOI 文献を開くコピーしました。