Stochastic programming — 確率的計画法

確率的計画法（かくりつてきけいかくほう、英語: stochastic programming）は、数理計画法の一分野であり、モデルの一部のパラメータが正確には分からず、既知または推定された確率分布を持つ確率変数として表現されるような、不確実性の条件下における最適化問題を解くためのモデルと手法を扱う。

全てのデータが定数として与えられる決定論的な問題とは異なり、確率的計画法は、ある統計的な意味で最適となる解（または意思決定ポリシー）を見つけることを目的とする。最も一般的には、これは目的関数の期待値を最小化または最大化することを意味する。その中心的な考え方は、確率的パラメータのすべての可能な実現値に対して「平均的に」最良となるような意思決定ポリシーを見つけることであり、これは特に在庫管理やエネルギーシステムのように、類似した条件下で繰り返し意思決定が行われる問題において重要となる。

数理的な問題設定

一般的に、確率的計画問題は次のように定式化できる: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ ここで:

• $x$ — 決定すべき制御変数（決定）のベクトル。
• $X$ — $x$に対する許容解の集合であり、決定論的な制約によって定義される。
• $\xi$ — 問題の不確実なパラメータ（例：需要、価格、天候条件）を表す確率ベクトル。
• $f(x,\xi )$ — その値が決定$x$と確率ベクトル$\xi$の実現値の両方に依存する目的関数。
• $\mathbb{𝔼}[\cdot ]$ — 確率ベクトル$\xi$の確率分布に基づいて計算される期待値演算子。

多段階確率モデルの基礎となる最も重要な原則は、非予測性原則（英語: non-anticipativity principle）である。この原則は、どの段階で行われる決定も、その時点までに利用可能な情報にのみ依存することができ、未来を「先読み」することはできないというものである。

リコース付き2段階問題

最も一般的なモデルは、リコース付き2段階確率計画問題（英語: two-stage stochastic program with recourse）である。この意思決定プロセスは2つの段階に分かれている:

1. 第1段階: 「今ここで」（here-and-now）の決定、すなわちベクトル$x$が決定される。この決定は、確率ベクトル$\xi$の具体的な実現値が判明する前に行われなければならない。
2. 第2段階: 確率的な事象が発生した後、第1段階の決定$x$と結果$\xi$の組み合わせによって生じた悪影響を最小化したり、好機を活用したりするための修正的または補償的な決定（recourse decision）、すなわちベクトル$y(\xi )$が下される。

数理的には、2段階確率的線形計画問題は次のように定式化される: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ 第1段階の制約: $Ax=b,x\ge 0$。 ここで $Q(x,\xi )$はリコース関数（recourse function）であり、第2段階問題の最適値を表す: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ ここで$\xi$はパラメータ$q(\xi ),T(\xi )$, $h(\xi )$を含む確率ベクトルであり、$c,A,b$, $W$は決定論的なパラメータである。

主な特性と定理

• 凸性: この理論の基本的な結果の一つは、2段階確率的線形計画問題において、期待リコース関数$Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$が凸関数であるということである。この特性は非常に重要である。なぜなら、これにより第1段階の全体問題が凸計画問題となり、効率的な解法が存在し、局所最適解が大域最適解と一致することが保証されるからである。
• 確定的等価問題: 確率ベクトル$\xi$が有限個の可能な実現値（シナリオ）${\xi }_1,\dots ,{\xi }_K$を確率$p_1,\dots ,p_K$でとる場合、確率的計画問題は一つの大規模な決定論的最適化問題として再定式化できる。この場合、期待値はすべてのシナリオにわたる加重和に置き換えられる。しかし、この問題の規模はシナリオ数に比例して増大するため、「次元の呪い」を引き起こし、シナリオ数が非常に多い場合にはこのアプローチは計算上実行不可能となる。

ロバスト最適化との比較

確率的計画法は、不確実性の下での最適化に対する複数のアプローチの一つである。ロバスト最適化との主な違いは、不確実性のモデル化手法と最適性の基準にある。

不確実性の下での最適化アプローチの比較

基準	確率的最適化	ロバスト最適化
不確実性の表現	パラメータは既知の確率分布を持つ確率変数	パラメータは所定の不確実性集合に属し、分布は不要
最適性基準	目的関数の期待値の最適化	最悪シナリオでの最適化（ミニマックス）
解の特性	「平均的に」最適なポリシーであり、稀なシナリオでは実行不可能となる可能性がある	全ての実現値に対して実行可能であることが保証される解。保守的になることがある

例

• 新聞売り子問題（英語: newsvendor problem）: 在庫管理の古典的な問題。売り手は将来の正確な需要が分からない状況で、どれだけの商品を仕入れるかを決定しなければならない。この決定は、過剰在庫による損失リスクと、品切れによる機会損失リスクとの間のバランスをとるものである。
• 農家の問題: 農家は、収穫量に影響を与える将来の天候が分からない状況で、総面積の中から異なる作物にどれだけの土地を割り当てるかを決定する。天候が判明した後、農家は修正措置（例えば、余剰分を売却したり、市場で不足分を買い足したりする）をとることができる。

関連項目

• 数理計画法
• オペレーションズ・リサーチ
• ロバスト最適化
• 動的計画法
• 制御理論

脚注

Category:Decision making