確率的計画法

数学的最適化の分野において、確率的計画法は不確実性を伴う最適化問題をモデル化する ための枠組みである。確率的計画法は、一部またはすべての問題パラメータが不確実であるが、既知の確率分布に従う最適化問題である。^{[1] [2]}この枠組みは、すべての問題パラメータが正確に既知であると想定される決定論的最適化とは対照的である。確率的計画法の目標は、意思決定者が選択したいくつかの基準を最適化し、問題パラメータの不確実性を適切に考慮した決定を見つけることである。現実世界の多くの決定には不確実性を伴うため、確率的計画法は金融から輸送、エネルギー最適化まで幅広い分野で応用されている。^{[3] [4]}

いくつかの確率的計画法が開発されています。

• サンプル平均近似を含むシナリオベースの方法
• いくつかの変数が整数でなければならない問題に対する確率的整数計画法
• 与えられた確率で満たされなければならない制約を扱うチャンス制約プログラミング
• 確率動的計画法
• マルコフ決定過程
• ベンダーの分解

2段階確率計画法の基本的な考え方は、（最適な）決定は、決定が下された時点で利用可能なデータに基づいて行われ、将来の観測には依存しないというものです。2段階定式化は、確率計画法で広く使用されています。2段階確率計画法の問題の一般的な定式化は、次のようになります。 ここで、は第2段階の問題の最適値です。 $${\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}$$${\displaystyle Q(x,\xi )}$$${\displaystyle \min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}。}$$

古典的な2段階線形確率計画問題は次のように定式化できる。 $${\displaystyle {\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E_{\xi }[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}}$$

第二段階の問題の最適値は どこにあるか${\displaystyle Q(x,\xi )}$$${\displaystyle {\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}}$$

このような定式化では、は第 1 段階の決定変数ベクトル、は第 2 段階の決定変数ベクトル、 には第 2 段階の問題のデータが含まれます。この定式化では、第 1 段階では、ランダム ベクトルとして表示される不確実なデータの実現が判明する前に、 「今ここで」の決定を行う必要があります。第 2 段階では、 の実現が利用可能になった後、適切な最適化問題を解くことで動作を最適化します。 ${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle y\in \mathbb {R} ^{m}}$${\displaystyle \xi (q,T,W,h)}$${\displaystyle x}$${\displaystyle \xi }$${\displaystyle \xi }$

最初の段階では、最初の段階の決定のコストと、(最適な) 2 段階目の決定の予想コストを合わせて最適化 (上記の式で最小化) します。2 段階目の問題は、不確実なデータが明らかになったときの想定される最適な動作を記述する最適化問題として単純に考えることができます。または、その解決策を、システムの起こりうる不整合を補償する項がこのリコース アクションのコストであるリコース アクションと見なすこともできます。 ${\displaystyle c^{T}x}$${\displaystyle Wy}$${\displaystyle Tx\leq h}$${\displaystyle q^{T}y}$

検討した2段階の問題は、目的関数と制約が線形であるため線形である。概念的にはこれは必須ではなく、より一般的な2段階確率計画を検討することもできる。たとえば、第1段階の問題が整数の場合、第1段階の問題に整数制約を追加して、実行可能集合が離散的になるようにすることができる。必要に応じて、非線形の目的関数と制約も組み込むことができる。^[5]

上記の 2 段階の問題の定式化では、第 2 段階のデータが既知の確率分布を持つランダム ベクトルとしてモデル化されていると想定しています。これは多くの状況で正当化されます。たとえば、分布が対象期間にわたって大きく変化しないと想定すると、 の分布は履歴データから推測できます。また、サンプルの経験的分布は、 の将来の値の分布の近似値として使用できます。 の事前モデルがある場合は、ベイズ更新によって事後分布を取得できます。 ${\displaystyle \xi }$${\displaystyle \xi }$${\displaystyle \xi }$${\displaystyle \xi }$

2 段階の確率問題を数値的に解くには、ランダム ベクトルには、それぞれの確率質量 を持つシナリオと呼ばれる有限個の可能な実現があると仮定する必要があります。この場合、第 1 段階の問題の目的関数の期待値は、次のように合計して表すことができます。 さらに、2 段階の問題は、1 つの大きな線形計画問題として定式化できます (これは、元の問題の決定論的等価問題と呼ばれます。セクション「確率問題の決定論的等価問題」を参照してください)。 ${\displaystyle \xi }$${\displaystyle \xi _{1},\dots ,\xi _{K}}$${\displaystyle p_{1},\dots ,p_{K}}$$${\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}$$

実現可能な数が無限（または非常に多い）である 場合、標準的なアプローチは、この分布をシナリオで表すことです。このアプローチでは、次の 3 つの疑問が生じます。${\displaystyle \xi }$

1. シナリオの構築方法については、§ シナリオの構築を参照してください。
2. 決定論的等価物を解く方法。CPLEXやGLPKなどの最適化ツールは、大規模な線形/非線形問題を解くことができます。ウィスコンシン大学マディソン校がホストするNEOSサーバー^{[6]では、多くの最新のソルバーに無料でアクセスできます。決定論的等価物の構造は、}ベンダーズ分解やシナリオ分解などの分解法^[7]を適用するのに特に適しています。
3. 得られたソリューションの品質を「真の」最適値と比較して測定する方法。

これらの質問は独立ではありません。たとえば、構築されたシナリオの数は、決定論的等価物の扱いやすさと、得られたソリューションの品質の両方に影響します。

確率線形計画法は、古典的な 2 段階確率計画法の特定のインスタンスです。確率線形計画法は、それぞれ同じ構造を持ちながら多少異なるデータを持つ複数期間の線形計画法 (LP) の集合から構築されます。シナリオを表す 2 期間の LP は、次の形式を持つと考えられます。 ${\displaystyle k^{th}}$${\displaystyle k^{th}}$

${\displaystyle {\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}}$

ベクトルとには、最初の期間の変数が含まれており、その値はすぐに選択する必要があります。ベクトルには、後続の期間のすべての変数が含まれます。制約には最初の期間の変数のみが含まれ、すべてのシナリオで同じです。その他の制約には、後の期間の変数が含まれ、シナリオごとにいくつかの点で異なり、将来に関する不確実性を反映しています。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle z_{k}}$${\displaystyle Tx+Uy=r}$

2 期間の LP を解くことは、第 2 期間のシナリオを不確実性なしで想定することと同じであることに注意してください。第 2 段階で不確実性を組み込むには、さまざまなシナリオに確率を割り当て、対応する決定論的同等物を解く必要があります。 ${\displaystyle k^{th}}$${\displaystyle k^{th}}$

シナリオの数が有限の場合、2 段階の確率的線形計画法は大規模な線形計画問題としてモデル化できます。この定式化は、決定論的等価線形計画法、または決定論的等価と略されることがよくあります。(厳密に言えば、決定論的等価とは、最適な第 1 段階の決定を計算するために使用できる任意の数学的プログラムであるため、第 2 段階のコストを何らかの閉じた形式で表すことができる場合は、連続確率分布に対しても決定論的等価プログラムが存在します。) たとえば、上記の確率的線形計画法の決定論的等価を作成するには、各シナリオに確率を割り当てます。次に、すべてのシナリオの制約に従って、目的の期待値を最小化できます。 ${\displaystyle p_{k}}$${\displaystyle k=1,\dots ,K}$

${\displaystyle {\begin{array}{lccccccccccccc}{\text{Minimize}}&f^{\top }x&+&g^{\top }y&+&p_{1}h_{1}^{\top }z_{1}&+&p_{2}h_{2}^{T}z_{2}&+&\cdots &+&p_{K}h_{K}^{\top }z_{K}&&\\{\text{subject to}}&Tx&+&Uy&&&&&&&&&=&r\\&&&V_{1}y&+&W_{1}z_{1}&&&&&&&=&s_{1}\\&&&V_{2}y&&&+&W_{2}z_{2}&&&&&=&s_{2}\\&&&\vdots &&&&&&\ddots &&&&\vdots \\&&&V_{K}y&&&&&&&+&W_{K}z_{K}&=&s_{K}\\&x&,&y&,&z_{1}&,&z_{2}&,&\ldots &,&z_{K}&\geq &0\\\end{array}}}$

後期の変数のベクトルはシナリオごとに異なります。ただし、第 1 期の変数と はどのシナリオでも同じです。これは、どのシナリオが実現するかを知る前に、第 1 期の決定を下す必要があるためです。結果として、とのみを含む制約は1回指定するだけで済みますが、残りの制約はシナリオごとに個別に指定する必要があります。 ${\displaystyle z_{k}}$${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

実際には、将来に関する専門家の意見を引き出すことでシナリオを構築できる可能性があります。構築するシナリオの数は比較的少なくする必要があります。そうすれば、得られる決定論的等価物を妥当な計算量で解決できます。少数のシナリオのみを使用して最適なソリューションを実現すると、単一のシナリオのみを想定するソリューションよりも適応性の高いプランが提供されるとよく​​言われます。場合によっては、このような主張はシミュレーションによって検証できます。理論的には、得られたソリューションが元の問題を妥当な精度で解決することを保証する手段がいくつかあります。通常、アプリケーションでは、ランダム データの「真の」実現は、構築された (生成された) シナリオのセットとはほとんど常に異なるため、最初の段階の最適なソリューションのみが実用的な価値があります。 ${\displaystyle x^{*}}$

に独立したランダム成分が含まれており、各成分に 3 つの実現可能性（たとえば、各ランダムパラメータの将来の実現が低、中、高に分類される）がある場合、シナリオの総数は です。シナリオ数がこのように指数関数的に増加すると、妥当なサイズの であっても専門家の意見を使用したモデル開発が非常に困難になります。 のランダム成分の一部が連続分布を持つ場合、状況はさらに悪化します。 ${\displaystyle \xi }$${\displaystyle d}$${\displaystyle K=3^{d}}$${\displaystyle d}$${\displaystyle \xi }$

シナリオセットを扱いやすいサイズに縮小する一般的な方法は、モンテカルロシミュレーションを使用することです。シナリオの総数が非常に多いか、無限であると仮定します。さらに、ランダムベクトルの複製のサンプルを生成できると仮定します。通常、サンプルは独立かつ同一に分布していると想定されます（iidサンプル）。サンプルが与えられた場合、期待関数はサンプル平均によって近似されます。 ${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$${\displaystyle N}$${\displaystyle \xi }$${\displaystyle q(x)=E[Q(x,\xi )]}$

${\displaystyle {\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$

したがって、第一段階の問題は次のように与えられる。

${\displaystyle {\begin{array}{rlrrr}{\hat {g}}_{N}(x)=&\min \limits _{x\in \mathbb {R} ^{n}}&c^{T}x+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})&\\&{\text{subject to}}&Ax&=&b\\&&x&\geq &0\end{array}}}$

この定式化はサンプル平均近似法として知られています。SAA 問題は、検討対象のサンプルの関数であり、その意味ではランダムです。特定のサンプルの場合、 SAA 問題は、シナリオ.、がそれぞれ同じ確率 で実行される2 段階の確率的線形計画問題と同じ形式です。 ${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$${\displaystyle \xi ^{j}}$${\displaystyle j=1,\dots ,N}$${\displaystyle p_{j}={\frac {1}{N}}}$

次の確率計画問題を考えてみましょう

${\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}}$

ここで はの空でない閉部分集合、は確率分布が集合 上でサポートされるランダムベクトル、です。2 段階確率計画法の枠組みでは、 は対応する第 2 段階の問題の最適値によって与えられます。 ${\displaystyle X}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \xi }$${\displaystyle P}$${\displaystyle \Xi \subset \mathbb {R} ^{d}}$${\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} }$${\displaystyle Q(x,\xi )}$

は明確に定義されており、すべての に対して有限の値であると仮定します。これは、すべての に対して値がほぼ確実に有限であることを意味します。 ${\displaystyle g(x)}$${\displaystyle x\in X}$${\displaystyle x\in X}$${\displaystyle Q(x,\xi )}$

ランダムベクトル の実現のサンプルがあるとします。このランダムサンプルはの観測の履歴データとして見ることができます。また、モンテカルロサンプリング技術によって生成することもできます。次に、対応するサンプル平均近似を定式化できます。${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$${\displaystyle N}$${\displaystyle \xi }$${\displaystyle N}$${\displaystyle \xi }$

${\displaystyle \min \limits _{x\in X}\{{\hat {g}}_{N}(x)=f(x)+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\}}$

大数の法則により、いくつかの規則性条件下では、は確率 1 で に点ごとに収束することが分かります。さらに、軽度の付加条件下では、収束は一様です。また、 、つまり はの不偏推定量です。したがって、SAA 問題の最適値と最適解は、 として真の問題の対応するものに収束すると予想するのは自然なことです。 ${\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}$${\displaystyle E[Q(x,\xi )]}$${\displaystyle N\rightarrow \infty }$${\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}$${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle g(x)}$${\displaystyle N\rightarrow \infty }$

SAA 問題の実行可能集合が固定されている、つまりサンプルに依存しないと仮定します。および をそれぞれ真の問題の最適値と最適解の集合とし、および をそれぞれ SAA 問題の最適値と最適解の集合とします 。${\displaystyle X}$${\displaystyle \vartheta ^{*}}$${\displaystyle S^{*}}$${\displaystyle {\hat {\vartheta }}_{N}}$${\displaystyle {\hat {S}}_{N}}$

1. およびを（決定論的な）実数値関数の列 とします。次の 2 つの特性は同等です。${\displaystyle g:X\rightarrow \mathbb {R} }$${\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} }$
   • 任意の列に対して、収束する任意の列は、収束する${\displaystyle {\overline {x}}\in X}$${\displaystyle \{x_{N}\}\subset X}$${\displaystyle {\overline {x}}}$${\displaystyle {\hat {g}}_{N}(x_{N})}$${\displaystyle g({\overline {x}})}$
   • 関数は連続であり、任意のコンパクトな部分集合上で一様に収束する。${\displaystyle g(\cdot )}$${\displaystyle X}$${\displaystyle {\hat {g}}_{N}(\cdot )}$${\displaystyle g(\cdot )}$${\displaystyle X}$
2. SAA 問題の目的関数が、実行可能集合 上で一様に、確率 1 で真の問題の目的関数に収束する場合、 は、確率 1 でに収束します。${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle g(x)}$${\displaystyle N\rightarrow \infty }$${\displaystyle X}$${\displaystyle {\hat {\vartheta }}_{N}}$${\displaystyle \vartheta ^{*}}$${\displaystyle N\rightarrow \infty }$
3. 次のような コンパクト集合が存在すると仮定する。${\displaystyle C\subset \mathbb {R} ^{n}}$
   • 真の問題の最適解の集合は空ではなく、${\displaystyle S}$${\displaystyle C}$
   • 関数は有限値であり、連続的である。${\displaystyle g(x)}$${\displaystyle C}$
   • 関数列は確率1でに収束し、${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle g(x)}$${\displaystyle N\rightarrow \infty }$${\displaystyle x\in C}$
   • 十分に大きい場合、集合は空ではなく、確率1で${\displaystyle N}$${\displaystyle {\hat {S}}_{N}}$${\displaystyle {\hat {S}}_{N}\subset C}$

となり、確率1で となります。 は集合 から集合 への偏差を表し、次のように定義されます。${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$${\displaystyle N\rightarrow \infty }$${\displaystyle \mathbb {D} (A,B)}$${\displaystyle A}$${\displaystyle B}$

${\displaystyle \mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}}$

いくつかの状況では、SAA問題の実行可能集合が推定され、対応するSAA問題は次の形式をとる。 ${\displaystyle X}$

${\displaystyle \min _{x\in X_{N}}{\hat {g}}_{N}(x)}$

ここで、はサンプルに依存する のサブセットであり、したがってランダムです。ただし、SAA 推定値の一貫性の結果は、いくつかの追加の仮定の下でも導き出すことができます。${\displaystyle X_{N}}$${\displaystyle \mathbb {R} ^{n}}$

1. 次のような コンパクト集合が存在すると仮定する。${\displaystyle C\subset \mathbb {R} ^{n}}$
   • 真の問題の最適解の集合は空ではなく、${\displaystyle S}$${\displaystyle C}$
   • 関数は有限値であり、連続的である。${\displaystyle g(x)}$${\displaystyle C}$
   • 関数列は確率1でに収束し、${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle g(x)}$${\displaystyle N\rightarrow \infty }$${\displaystyle x\in C}$
   • 十分に大きい場合、集合は空ではなく、確率1で${\displaystyle N}$${\displaystyle {\hat {S}}_{N}}$${\displaystyle {\hat {S}}_{N}\subset C}$
   • とが確率1で点 に収束する場合、${\displaystyle x_{N}\in X_{N}}$${\displaystyle x_{N}}$${\displaystyle x}$${\displaystyle x\in X}$
   • ある点に対して、確率 1 となるようなシーケンスが存在します。${\displaystyle x\in S^{*}}$${\displaystyle x_{N}\in X_{N}}$${\displaystyle x_{N}\rightarrow x}$

すると、確率 1 で となります。${\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}}$${\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0}$${\displaystyle N\rightarrow \infty }$

標本が iid で、点 を固定すると仮定します。すると、 の標本平均推定量は不偏で、分散 を持ちます。ここで、は有限であると想定されます 。さらに、中心極限定理により、${\displaystyle \xi ^{1},\dots ,\xi ^{N}}$${\displaystyle x\in X}$${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle g(x)}$${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$${\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}$

${\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]{\xrightarrow {\mathcal {D}}}Y_{x}}$

ここで、 は分布の収束を表し、 は平均と分散の正規分布を持ち、 と表記されます。 ${\displaystyle {\xrightarrow {\mathcal {D}}}}$${\displaystyle Y_{x}}$${\displaystyle 0}$${\displaystyle \sigma ^{2}(x)}$${\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}$

言い換えると、は漸近的に正規分布します。つまり、 が大きい場合、は平均と分散を持つ近似的に正規分布します。これにより、 の次の (近似) % 信頼区間が導かれます。 ${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle N}$${\displaystyle {\hat {g}}_{N}(x)}$${\displaystyle g(x)}$${\displaystyle {\frac {1}{N}}\sigma ^{2}(x)}$${\displaystyle 100(1-\alpha )}$${\displaystyle f(x)}$

${\displaystyle \left[{\hat {g}}_{N}(x)-z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}},{\hat {g}}_{N}(x)+z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}}\right]}$

ここで（ここでは標準正規分布の累積分布関数を表す）および ${\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}$${\displaystyle \Phi (\cdot )}$

${\displaystyle {\hat {\sigma }}^{2}(x):={\frac {1}{N-1}}\sum _{j=1}^{N}\left[Q(x,\xi ^{j})-{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\right]^{2}}$

は のサンプル分散推定値です。つまり、 の推定値の誤差は（確率的に） のオーダーです。 ${\displaystyle \sigma ^{2}(x)}$${\displaystyle g(x)}$${\displaystyle O({\sqrt {N}})}$

確率的動的計画法は、行動生態学などの分野で動物の行動をモデル化するために頻繁に使用されます。^{[8] [9]}最適な採餌、鳥の巣立ちや寄生蜂の産卵などの生活史の遷移 のモデルの経験的テストにより、行動上の意思決定の進化を説明する上でこのモデリング手法の価値が示されました。これらのモデルは通常、2段階ではなく多段階です。

確率的動的計画法は、不確実性の下での意思決定を理解する上で有用なツールです。不確実性の下での資本ストックの蓄積はその一例であり、資源経済学者は天候などの不確実性が入り込む 生物経済学の問題^{[10]を分析するためによく使用します。}

以下は、多段階確率計画法の金融の例です。ある時点で、資産に投資するための初期資本があるとします。さらに、ポートフォリオを随時再調整することはできますが、追加の現金を注入することはできないものとします。各期間で、現在の富を資産間で再分配するかどうかを決定します。n 個の資産に投資された初期額を とします。それぞれが負でなく、バ​​ランス方程式が成り立つ ことを要求します。${\displaystyle t=0}$${\displaystyle W_{0}}$${\displaystyle n}$${\displaystyle t=1,\dots ,T-1}$${\displaystyle t}$${\displaystyle W_{t}}$${\displaystyle n}$${\displaystyle x_{0}=(x_{10},\dots ,x_{n0})}$${\displaystyle x_{i0}}$${\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}$

各期間 の総収益について考えてみましょう。これはベクトル値のランダムプロセス を形成します。 期間 に、それぞれの資産に投資した金額を指定してポートフォリオを再調整できます。 その時点では、最初の期間の収益が実現されているため、この情報を再調整の決定に使用するのは妥当です。 したがって、時間 における第 2 段階の決定は、実際にはランダムベクトル の実現の関数、つまり です。同様に、時間 における決定は、時間 までのランダムプロセスの履歴によって提供される利用可能な情報の関数です。 が定数である関数のシーケンス、は、決定プロセスの実装可能なポリシーを定義します。 このようなポリシーは、確率 1 でモデル制約、つまり非負制約、、、および富のバランス制約 を満たす場合に実行可能であると言われています。${\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})}$${\displaystyle t=1,\dots ,T}$${\displaystyle \xi _{1},\dots ,\xi _{T}}$${\displaystyle t=1}$${\displaystyle x_{1}=(x_{11},\dots ,x_{n1})}$${\displaystyle t=1}$${\displaystyle \xi _{1}}$${\displaystyle x_{1}=x_{1}(\xi _{1})}$${\displaystyle t}$${\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})}$${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$${\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})}$${\displaystyle t}$${\displaystyle x_{t}=x_{t}(\xi _{[t]})}$${\displaystyle t=0,\dots ,T-1}$${\displaystyle x_{0}}$${\displaystyle x_{it}(\xi _{[t]})\geq 0}$${\displaystyle i=1,\dots ,n}$${\displaystyle t=0,\dots ,T-1}$

${\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},}$

期間中の富は ${\displaystyle t=1,\dots ,T}$${\displaystyle W_{t}}$

${\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),}$

これはランダムプロセスの実現と時点までの決定に依存します。 ${\displaystyle t}$

最終期間におけるこの富の期待効用を最大化することが目的であると仮定すると、つまり、問題を考える。

${\displaystyle \max E[U(W_{T})].}$

これは多段階の確率的計画問題であり、段階は から まで番号が付けられています。最適化は、実装可能で実行可能なすべてのポリシーに対して実行されます。問題の説明を完了するには、ランダム プロセスの確率分布も定義する必要があります。これはさまざまな方法で実行できます。たとえば、プロセスの時間的変化を定義する特定のシナリオ ツリーを構築できます。各段階で、各資産のランダム リターンが他の資産とは独立して 2 つの継続を持つことが許される場合、シナリオの総数は${\displaystyle t=0}$${\displaystyle t=T-1}$${\displaystyle \xi _{1},\dots ,\xi _{T}}$${\displaystyle 2^{nT}.}$

動的計画法の方程式を書くには、上記の多段階問題を時間的に遡って考えます。最終段階では、 ランダムプロセスの実現がわかっており、選択されています。したがって、次の問題を解く必要があります。 ${\displaystyle t=T-1}$${\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}$${\displaystyle x_{T-2}}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})|\xi _{[T-1]}]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}$

ここで、 は与えられたの条件付き期待値を表します。上記の問題の最適値は と に依存し、と表されます。 ${\displaystyle E[U(W_{T})|\xi _{[T-1]}]}$${\displaystyle U(W_{T})}$${\displaystyle \xi _{[T-1]}}$${\displaystyle W_{T-1}}$${\displaystyle \xi _{[T-1]}}$${\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}$

同様に、段階ごとに、問題を解決する必要があります ${\displaystyle t=T-2,\dots ,1}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1},\xi _{[t+1]})|\xi _{[t]}]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}$

その最適値は で表されます。最後に、ステージ で、問題を解きます。 ${\displaystyle Q_{t}(W_{t},\xi _{[t]})}$${\displaystyle t=0}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{0}}&E[Q_{1}(W_{1},\xi _{[1]})]&\\{\text{subject to}}&W_{1}&=&\sum _{i=1}^{n}\xi _{i,1}x_{i0}\\&\sum _{i=1}^{n}x_{i0}&=&W_{0}\\&x_{0}&\geq &0\end{array}}}$

プロセス の一般的な分布では、これらの動的計画法方程式を解くのは難しいかもしれません。プロセス が段階的に独立している場合、つまり がに対して(確率的に) 独立している場合、状況は劇的に単純化されます。この場合、対応する条件付き期待値は無条件期待値になり、関数 はに依存しません。つまり、は問題の最適値です 。${\displaystyle \xi _{t}}$${\displaystyle \xi _{t}}$${\displaystyle \xi _{t}}$${\displaystyle \xi _{1},\dots ,\xi _{t-1}}$${\displaystyle t=2,\dots ,T}$${\displaystyle Q_{t}(W_{t})}$${\displaystyle t=1,\dots ,T-1}$${\displaystyle \xi _{[t]}}$${\displaystyle Q_{T-1}(W_{T-1})}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}}$

そして最適値は ${\displaystyle Q_{t}(W_{t})}$

${\displaystyle {\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1})]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}}$

のために。 ${\displaystyle t=T-2,\dots ,1}$

すべての離散確率計画問題は、任意の代数モデリング言語で表現できます。明示的または暗黙的な非予測性を手動で実装して、結果のモデルが各段階で利用できる情報の構造を尊重するようにします。一般的なモデリング言語によって生成される SP 問題のインスタンスは、非常に大きくなる傾向があり (シナリオの数に比例して)、そのマトリックスはこのクラスの問題に固有の構造を失います。この構造は、そうでなければ、特定の分解アルゴリズムによって解決時に活用できます。SP 用に特別に設計されたモデリング言語の拡張機能が登場し始めています。以下を参照してください。

• AIMMS - SP問題の定義をサポート
• EMP SP (確率的計画のための拡張数理計画法) -確率的計画法を容易にするために作成されたGAMSのモジュール (パラメトリック分布、確率制約、およびValue at Riskや Expected shortfallなどのリスク測定のキーワードが含まれています )。
• SAMPL - 確率的プログラムを表現するために特別に設計されたAMPLの拡張機能のセット(確率制約、統合確率制約、ロバスト最適化問題の構文を含む)

どちらも SMPS インスタンス レベル形式を生成でき、問題の構造を冗長性のない形式でソルバーに伝えます。

• チャンス制約ポートフォリオ選択
• 相関ギャップ
• 確率的計画法のための EMP
• エントロピー値が危険にさらされている
• フォートSP
• SAMPL代数モデリング言語
• シナリオ最適化
• 確率的最適化

• John R. Birge および François V. Louveaux。確率的計画法入門。Springer Verlag、ニューヨーク、1997 年。
• Kall, Peter; Wallace, Stein W. (1994)。確率的計画法。Wiley-Interscience シリーズ システムと最適化。チチェスター: John Wiley & Sons, Ltd. pp. xii+307。ISBN 0-471-95158-7MR  1315300 。
• G. Ch. Pflug: 確率モデルの最適化。シミュレーションと最適化のインターフェイス。Kluwer、ドルドレヒト、1996 年。
• アンドラス・プレコパ確率的プログラミング。 Kluwer Academic Publishers、ドルドレヒト、1995 年。
• Andrzej Ruszczynskiおよび Alexander Shapiro (編) (2003)確率的計画法. オペレーションズ・リサーチおよびマネジメント・サイエンスのハンドブック、第 10 巻、Elsevier。
• Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009)。確率的計画法に関する講義: モデリングと理論(PDF)。MPS/SIAM 最適化シリーズ。第 9 巻。フィラデルフィア、ペンシルバニア州: Society for Industrial and Applied Mathematics (SIAM)。pp. xvi+ 436。ISBN 978-0-89871-687-0. MR 2562798. 2020年3月24日時点の オリジナル（PDF）からアーカイブ。2010年9月22日閲覧。 {{cite book}}:不明なパラメータ|agency=は無視されました (ヘルプ)
• Stein W. Wallace および William T. Ziemba (編) (2005)確率的計画法の応用。MPS-SIAM 最適化ブックシリーズ 5
• King, Alan J.; Wallace, Stein W. (2012)。確率的計画法によるモデリング。Springer オペレーションズ リサーチおよび金融工学シリーズ。ニューヨーク: Springer。ISBN 978-0-387-87816-4。

• 確率的プログラミング コミュニティ ホームページ