Framework for modeling optimization problems that involve uncertainty
数理最適化 の分野において 、 確率計画法は 不確実性を 伴う 最適化問題 をモデル化する ための枠組みである 。 確率計画法とは、問題パラメータの一部またはすべてが不確実であるものの、既知の 確率分布 に従う最適化問題である 。 [1] [2] この枠組みは、すべての問題パラメータが正確に既知であると仮定する決定論的最適化とは対照的である。確率計画法の目的は、意思決定者が選択したいくつかの基準を最適化し、かつ問題パラメータの不確実性を適切に考慮した決定を見つけることである。現実世界の多くの意思決定には不確実性が含まれるため、確率計画法は 金融 から 輸送 、エネルギー最適化に至るまで幅広い分野で応用されている。 [3] [4]
方法 いくつかの確率的計画法が開発されています。
2段階の問題定義 2段階確率計画法の基本的な考え方は、（最適な）決定は、決定が行われる時点で利用可能なデータに基づいて行われ、将来の観測値に依存してはならないというものです。この2段階定式化は、確率計画法において広く用いられています。2段階確率計画法の問題の一般的な定式化は、以下の式で与えられます。 ここで 、は第2段階の問題の最適値です。 min x ∈ X { g ( x ) = f ( x ) + E ξ [ Q ( x , ξ ) ] } {\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}} Q ( x , ξ ) {\displaystyle Q(x,\xi )} min y { q ( y , ξ ) | T ( ξ ) x + W ( ξ ) y = h ( ξ ) } . {\displaystyle \min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.}
古典的な2段階線形確率計画問題は次のように定式化できる。 min x ∈ R n g ( x ) = c T x + E ξ [ Q ( x , ξ ) ] subject to A x = b x ≥ 0 {\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}}}
第2段階の問題の最適値は どこにあるか Q ( x , ξ ) {\displaystyle Q(x,\xi )} min y ∈ R m q ( ξ ) T y subject to T ( ξ ) x + W ( ξ ) y = h ( ξ ) y ≥ 0 {\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}}}
このような定式化では 、 は第一段階の決定変数ベクトル、 は第二段階の決定変数ベクトル、 は 第二段階の問題のデータを含みます。この定式化では、第一段階では、 不確実なデータ （ランダムベクトルとして捉えられる）の実現値が判明する前に、「今ここで」の決定を下す必要があります。第二段階では、 の実現値が判明した後 、適切な最適化問題を解くことで行動を最適化します。 x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} y ∈ R m {\displaystyle y\in \mathbb {R} ^{m}} ξ ( q , T , W , h ) {\displaystyle \xi (q,T,W,h)} x {\displaystyle x} ξ {\displaystyle \xi } ξ {\displaystyle \xi }
第一段階では、第一段階の意思決定のコスト と、（最適な）第二段階の意思決定の期待コストを加算して最適化（上記の定式化では最小化）します。第二段階の問題は、不確実なデータが明らかになった際に想定される最適な行動を記述する最適化問題として単純に捉えることもできますし、その解決策を、 システムの潜在的な不整合を補償する項 と、 この項のコストをリコースアクションとして捉えることもできます。 c T x {\displaystyle c^{T}x} W y {\displaystyle Wy} T x ≤ h {\displaystyle Tx\leq h} q T y {\displaystyle q^{T}y}
検討されている二段階問題は、目的関数と制約が線形であるため 線形 である。概念的にはこれは本質的ではなく、より一般的な二段階確率計画問題を考えることもできる。例えば、第一段階の問題が整数問題である場合、第一段階の問題に整数性制約を追加することで、実行可能集合が離散的になるようにすることができる。必要に応じて、非線形の目的関数と制約も組み込むことができる。 [5]
分配仮定 上記の2段階問題の定式化では、第2段階のデータが 既知の 確率分布 を持つランダムベクトルとしてモデル化されていると仮定しています。これは多くの状況で正当化されます。例えば、 分布が対象期間にわたって大きく変化しないと仮定すれば、 の分布は履歴データから推測できます。また、サンプルの経験分布は、 の将来値の分布の近似値として使用できます 。 の事前モデルがあれば 、ベイズ更新によって事後分布を取得できます。 ξ {\displaystyle \xi } ξ {\displaystyle \xi } ξ {\displaystyle \xi } ξ {\displaystyle \xi }
シナリオベースのアプローチ
離散化 2段階確率問題を数値的に解くには、ランダムベクトルには、 それぞれの確率質量がである、 シナリオ と呼ばれる有限個の可能な実現値（ 例えば）が存在すると仮定することがしばしば必要と なる。この場合、第1段階問題の目的関数における期待値は、次の和として表すことができる。 さらに、2段階問題は1つの大きな線形計画問題として定式化することができる（これは元の問題の決定論的等価問題と呼ばれる。「確率問題の決定論的等価問題」のセクションを参照）。 ξ {\displaystyle \xi } ξ 1 , … , ξ K {\displaystyle \xi _{1},\dots ,\xi _{K}} p 1 , … , p K {\displaystyle p_{1},\dots ,p_{K}} E [ Q ( x , ξ ) ] = ∑ k = 1 K p k Q ( x , ξ k ) {\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}
に無限（あるいは非常に多数）の実現可能な可能性がある 場合、標準的なアプローチは、この分布をシナリオで表現することです。このアプローチは、以下の3つの疑問を提起します。 ξ {\displaystyle \xi }
シナリオの構築方法については、§ シナリオの構築を参照してください。 決定論的等価問題の解き方。CPLEX や GLPKなどの最適化ツールは 、 大規模な線形/非線形問題を解くことができます。 ウィスコンシン大学マディソン校 がホストするNEOSサーバー [6]では、多くの最新ソルバーに無料でアクセスできます。決定論的等価問題の構造は、 ベンダーズ分解 やシナリオ分解 などの分解法 [7] の適用に特に適しています。 得られたソリューションの品質を「真の」最適値と比較して測定する方法。 これらの問題は独立ではありません。例えば、構築されるシナリオの数は、決定論的等価物の扱いやすさと得られる解の質の両方に影響を与えます。
確率線形計画法 確率 線形計画法は 、古典的な2段階確率計画法の特殊な例です。確率線形計画法は、それぞれ同じ構造を持ちながら多少異なるデータを持つ、複数期間の線形計画法（LP）の集合から構築されます。シナリオ を表す2期間のLPは、 以下の形式を持つと考えられます。 k t h {\displaystyle k^{th}} k t h {\displaystyle k^{th}}
Minimize f T x + g T y + h k T z k subject to T x + U y = r V k y + W k z k = s k x , y , z k ≥ 0 {\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}}}
ベクトルとに は、 第1期の変数が含まれており、その値は直ちに選択する必要があります。ベクトル には、後続期のすべての変数が含まれています。制約条件は 第1期の変数のみに関係し、すべてのシナリオで同じです。その他の制約条件は、後続期の変数に関係し、シナリオごとにいくつかの点で異なり、将来の不確実性を反映しています。 x {\displaystyle x} y {\displaystyle y} z k {\displaystyle z_{k}} T x + U y = r {\displaystyle Tx+Uy=r}
2期間のLP を解くことは、 第2期間のシナリオを不確実性なしに仮定することと等価であることに注意してください。第2段階で不確実性を組み込むには、異なるシナリオに確率を割り当て、対応する決定論的等価物を解く必要があります。 k t h {\displaystyle k^{th}} k t h {\displaystyle k^{th}}
確率的問題の決定論的等価物 有限個のシナリオを用いると、2段階確率線形計画問題は大規模線形計画問題としてモデル化できます。この定式化は、しばしば決定論的等価線形計画問題、または略して決定論的等価問題と呼ばれます。（厳密に言えば、決定論的等価問題とは、最適な第1段階の決定を計算するために使用できる任意の数学的プログラムであり、第2段階のコストを何らかの閉じた形で表現できる場合、連続確率分布にも存在します。）例えば、上記の確率線形計画問題の決定論的等価問題を作成するには、 各シナリオに確率を割り当てます 。すると、すべてのシナリオからの制約条件の下で、目的関数の期待値を最小化できます。 p k {\displaystyle p_{k}} k = 1 , … , K {\displaystyle k=1,\dots ,K}
Minimize f ⊤ x + g ⊤ y + p 1 h 1 ⊤ z 1 + p 2 h 2 T z 2 + ⋯ + p K h K ⊤ z K subject to T x + U y = r V 1 y + W 1 z 1 = s 1 V 2 y + W 2 z 2 = s 2 ⋮ ⋱ ⋮ V K y + W K z K = s K x , y , z 1 , z 2 , … , z K ≥ 0 {\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期について決定を下す必要があるため、すべてのシナリオで同じです。したがって、とのみに関する制約は 一 度だけ指定すればよく、残りの制約はシナリオごとに個別に指定する必要があります。 z k {\displaystyle z_{k}} k {\displaystyle k} x {\displaystyle x} y {\displaystyle y} x {\displaystyle x} y {\displaystyle y}
シナリオ構築 実際には、専門家から将来に関する意見を聞き出すことでシナリオを構築できる可能性があります。構築するシナリオの数は比較的少なく、得られる決定論的等価シナリオを妥当な計算量で解くことができるようにする必要があります。少数のシナリオのみを用いた最適な解は、単一のシナリオのみを想定する解よりも、より適応性の高い計画を提供するとよく言われます。場合によっては、このような主張はシミュレーションによって検証できます。理論的には、得られた解が元の問題を妥当な精度で解くことを保証するいくつかの手段があります。通常、応用においては、 最初の段階の 最適解のみ が実用的な価値を持ちます。なぜなら、ランダムデータの「真の」実現は、構築（生成）されたシナリオの集合とはほぼ常に異なるからです。 x ∗ {\displaystyle x^{*}}
に独立したランダム成分が含まれており 、それぞれが3つの実現可能性を持つと 仮定すると（例えば、各ランダムパラメータの将来の実現可能性は低、中、高に分類される）、シナリオの総数は となります 。 シナリオ数がこのように指数 関数的に増加すると、 たとえ妥当なサイズであっても、専門家の意見を用いたモデル開発は非常に困難になります。 のランダム成分の一部が連続分布を持つ 場合、状況はさらに悪化します。 ξ {\displaystyle \xi } d {\displaystyle d} K = 3 d {\displaystyle K=3^{d}} d {\displaystyle d} ξ {\displaystyle \xi }
モンテカルロサンプリングとサンプル平均近似（SAA）法 シナリオセットを扱いやすいサイズに縮小する一般的な方法は、モンテカルロシミュレーションを用いることです。シナリオの総数が非常に多い、あるいは無限大であると仮定します。さらに、 ランダムベクトル の実現値 の標本を生成できると仮定します 。通常、標本は 独立かつ同一分布 に従うと仮定されます（iid標本）。標本が与えられた場合、期待値関数 は標本平均によって近似されます。 ξ 1 , ξ 2 , … , ξ N {\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}} N {\displaystyle N} ξ {\displaystyle \xi } q ( x ) = E [ Q ( x , ξ ) ] {\displaystyle q(x)=E[Q(x,\xi )]}
q ^ N ( x ) = 1 N ∑ j = 1 N Q ( x , ξ j ) {\displaystyle {\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})}
したがって、第一段階の問題は次のように与えられる。
g ^ N ( x ) = min x ∈ R n c T x + 1 N ∑ j = 1 N Q ( x , ξ j ) subject to A x = b x ≥ 0 {\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段階確率線形計画問題と同じ形式です 。 ξ 1 , ξ 2 , … , ξ N {\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}} ξ j {\displaystyle \xi ^{j}} j = 1 , … , N {\displaystyle j=1,\dots ,N} p j = 1 N {\displaystyle p_{j}={\frac {1}{N}}}
統計的推論 次の確率計画問題を考えてみましょう
min x ∈ X { g ( x ) = f ( x ) + E [ Q ( x , ξ ) ] } {\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}} ここで は の空でない閉部分集合であり 、は確率分布が 集合 上でサポートされる ランダムベクトルであり 、 である 。2段階確率計画法の枠組みにおいて、 は対応する第2段階問題の最適値によって与えられる。 X {\displaystyle X} R n {\displaystyle \mathbb {R} ^{n}} ξ {\displaystyle \xi } P {\displaystyle P} Ξ ⊂ R d {\displaystyle \Xi \subset \mathbb {R} ^{d}} Q : X × Ξ → R {\displaystyle Q:X\times \Xi \rightarrow \mathbb {R} } Q ( x , ξ ) {\displaystyle Q(x,\xi )}
が明確に定義され、 すべての に対して 有限値で あると仮定する 。これは、任意の に対して、 その値が ほぼ確実に有限であることを意味する。 g ( x ) {\displaystyle g(x)} x ∈ X {\displaystyle x\in X} x ∈ X {\displaystyle x\in X} Q ( x , ξ ) {\displaystyle Q(x,\xi )}
ランダムベクトル の実現値 の 標本があるとする。このランダム標本は の観測値 の履歴データとみなすこともできるし、モンテカルロサンプリング法によって生成することもできる。そして、対応する 標本平均近似 を定式化することができる。 ξ 1 , … , ξ N {\displaystyle \xi ^{1},\dots ,\xi ^{N}} N {\displaystyle N} ξ {\displaystyle \xi } N {\displaystyle N} ξ {\displaystyle \xi }
min x ∈ X { g ^ N ( x ) = f ( x ) + 1 N ∑ j = 1 N Q ( x , ξ j ) } {\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問題の最適値と最適解は、真の問題のそれぞれの最適値と最適解に として収束すると期待するのは当然です 。 1 N ∑ j = 1 N Q ( x , ξ j ) {\displaystyle {\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})} E [ Q ( x , ξ ) ] {\displaystyle E[Q(x,\xi )]} N → ∞ {\displaystyle N\rightarrow \infty } E [ g ^ N ( x ) ] = g ( x ) {\displaystyle E[{\hat {g}}_{N}(x)]=g(x)} g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} g ( x ) {\displaystyle g(x)} N → ∞ {\displaystyle N\rightarrow \infty }
SAA推定値の一貫性 SAA問題の実行可能集合 が固定されている、つまり標本に依存しないと仮定する。 真の問題の最適値と最適解の集合をそれぞれ と とし、 SAA問題の最適値と最適解の集合をそれぞれ と とする。 X {\displaystyle X} ϑ ∗ {\displaystyle \vartheta ^{*}} S ∗ {\displaystyle S^{*}} ϑ ^ N {\displaystyle {\hat {\vartheta }}_{N}} S ^ N {\displaystyle {\hat {S}}_{N}}
と を （決定論的な）実数値関数の列とする。以下の2つの性質は同値である。 g : X → R {\displaystyle g:X\rightarrow \mathbb {R} } g ^ N : X → R {\displaystyle {\hat {g}}_{N}:X\rightarrow \mathbb {R} } 任意の列 に対して、 収束する任意の列 は、 収束する x ¯ ∈ X {\displaystyle {\overline {x}}\in X} { x N } ⊂ X {\displaystyle \{x_{N}\}\subset X} x ¯ {\displaystyle {\overline {x}}} g ^ N ( x N ) {\displaystyle {\hat {g}}_{N}(x_{N})} g ( x ¯ ) {\displaystyle g({\overline {x}})} 関数は 連続であり 、 任意のコンパクト部分集合上で一様 収束する。 g ( ⋅ ) {\displaystyle g(\cdot )} X {\displaystyle X} g ^ N ( ⋅ ) {\displaystyle {\hat {g}}_{N}(\cdot )} g ( ⋅ ) {\displaystyle g(\cdot )} X {\displaystyle X} SAA問題の目的関数が、 実行可能集合 上で一様 に、確率1で 真の問題の目的関数に収束するとします 。すると、 は、 確率1で に収束します 。 g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} g ( x ) {\displaystyle g(x)} N → ∞ {\displaystyle N\rightarrow \infty } X {\displaystyle X} ϑ ^ N {\displaystyle {\hat {\vartheta }}_{N}} ϑ ∗ {\displaystyle \vartheta ^{*}} N → ∞ {\displaystyle N\rightarrow \infty } 次のような コンパクト集合が存在すると仮定する。 C ⊂ R n {\displaystyle C\subset \mathbb {R} ^{n}} 真の問題の最適解の 集合は空ではなく、以下に含まれる。 S {\displaystyle S} C {\displaystyle C} 関数 は有限値であり、連続である。 g ( x ) {\displaystyle g(x)} C {\displaystyle C} 関数列は 確率1で に収束し 、一様に g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} g ( x ) {\displaystyle g(x)} N → ∞ {\displaystyle N\rightarrow \infty } x ∈ C {\displaystyle x\in C} 十分に大きい場合、 集合 は空ではなく、 確率1で N {\displaystyle N} S ^ N {\displaystyle {\hat {S}}_{N}} S ^ N ⊂ C {\displaystyle {\hat {S}}_{N}\subset C} すると 、 確率1で となる 。 は 集合 から 集合 への偏差 を表し 、次のように定義される。 ϑ ^ N → ϑ ∗ {\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}} D ( S ∗ , S ^ N ) → 0 {\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0} N → ∞ {\displaystyle N\rightarrow \infty } D ( A , B ) {\displaystyle \mathbb {D} (A,B)} A {\displaystyle A} B {\displaystyle B} D ( A , B ) := sup x ∈ A { inf x ′ ∈ B ‖ x − x ′ ‖ } {\displaystyle \mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}} いくつかの状況では、SAA問題の 実行可能集合が推定され、対応するSAA問題は次の形式をとる。 X {\displaystyle X}
min x ∈ X N g ^ N ( x ) {\displaystyle \min _{x\in X_{N}}{\hat {g}}_{N}(x)} ここで、は 標本に依存する の部分集合であり、したがってランダムである。しかしながら、SAA推定値の一貫性の結果は、いくつかの追加の仮定の下でも導き出すことができる。 X N {\displaystyle X_{N}} R n {\displaystyle \mathbb {R} ^{n}}
次のような コンパクト集合が存在すると仮定する。 C ⊂ R n {\displaystyle C\subset \mathbb {R} ^{n}} 真の問題の最適解の 集合は空ではなく、以下に含まれる。 S {\displaystyle S} C {\displaystyle C} 関数 は有限値であり、連続である。 g ( x ) {\displaystyle g(x)} C {\displaystyle C} 関数列は 確率1で に収束し 、一様に g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} g ( x ) {\displaystyle g(x)} N → ∞ {\displaystyle N\rightarrow \infty } x ∈ C {\displaystyle x\in C} 十分に大きい場合、 集合 は空ではなく、 確率1で N {\displaystyle N} S ^ N {\displaystyle {\hat {S}}_{N}} S ^ N ⊂ C {\displaystyle {\hat {S}}_{N}\subset C} とが 確率1で点 に収束する 場合 、 x N ∈ X N {\displaystyle x_{N}\in X_{N}} x N {\displaystyle x_{N}} x {\displaystyle x} x ∈ X {\displaystyle x\in X} ある点において、 確率 1 で 次の 数列が存在します。 x ∈ S ∗ {\displaystyle x\in S^{*}} x N ∈ X N {\displaystyle x_{N}\in X_{N}} x N → x {\displaystyle x_{N}\rightarrow x} すると 、 確率 1 で となります 。 ϑ ^ N → ϑ ∗ {\displaystyle {\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}} D ( S ∗ , S ^ N ) → 0 {\displaystyle \mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0} N → ∞ {\displaystyle N\rightarrow \infty }
SAA最適値の漸近解析 標本 が独立同値で、点 を固定すると仮定する。すると、 の 標本平均推定値 は不偏かつ分散 を持つ。 ここで は有限であると仮定する。さらに、 中心 極限定理より、 ξ 1 , … , ξ N {\displaystyle \xi ^{1},\dots ,\xi ^{N}} x ∈ X {\displaystyle x\in X} g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} g ( x ) {\displaystyle g(x)} 1 N σ 2 ( x ) {\displaystyle {\frac {1}{N}}\sigma ^{2}(x)} σ 2 ( x ) := V a r [ Q ( x , ξ ) ] {\displaystyle \sigma ^{2}(x):=Var[Q(x,\xi )]}
N [ g ^ N − g ( x ) ] → D Y x {\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]{\xrightarrow {\mathcal {D}}}Y_{x}} ここで、は 分布 の収束を表し 、は 平均 と分散 の 正規分布 を持ち 、 と表記されます 。 → D {\displaystyle {\xrightarrow {\mathcal {D}}}} Y x {\displaystyle Y_{x}} 0 {\displaystyle 0} σ 2 ( x ) {\displaystyle \sigma ^{2}(x)} N ( 0 , σ 2 ( x ) ) {\displaystyle {\mathcal {N}}(0,\sigma ^{2}(x))}
言い換えれば、は 漸近的に正規 分布に従う 、すなわち が大きい場合 、 は平均 、分散の近似正規分布に従う 。このことから、 の（近似的な） % 信頼区間は 次のようになる 。 g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} N {\displaystyle N} g ^ N ( x ) {\displaystyle {\hat {g}}_{N}(x)} g ( x ) {\displaystyle g(x)} 1 N σ 2 ( x ) {\displaystyle {\frac {1}{N}}\sigma ^{2}(x)} 100 ( 1 − α ) {\displaystyle 100(1-\alpha )} f ( x ) {\displaystyle f(x)}
[ g ^ N ( x ) − z α / 2 σ ^ ( x ) N , g ^ N ( x ) + z α / 2 σ ^ ( x ) N ] {\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]} ここで （ここでは 標準正規分布の累積分布関数を表す）および z α / 2 := Φ − 1 ( 1 − α / 2 ) {\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)} Φ ( ⋅ ) {\displaystyle \Phi (\cdot )}
σ ^ 2 ( x ) := 1 N − 1 ∑ j = 1 N [ Q ( x , ξ j ) − 1 N ∑ j = 1 N Q ( x , ξ j ) ] 2 {\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}} は の標本分散推定値です 。つまり、 の推定値の誤差は （確率的に） のオーダーです 。 σ 2 ( x ) {\displaystyle \sigma ^{2}(x)} g ( x ) {\displaystyle g(x)} O ( N ) {\displaystyle O({\sqrt {N}})}
アプリケーションと例
生物学的応用 確率的動的計画法は、 行動生態学 などの分野において、 動物行動の モデル化に頻繁に用いられている 。 [8] [9] 最適採餌行動 、 鳥類の巣立ちや 寄生 蜂の産卵 といった 生活史 遷移のモデルに関する実証的検証は、 このモデリング手法が行動意思決定の進化を説明する上で有用であることを示している。これらのモデルは、通常、2段階ではなく多段階で構成される。
経済的応用 確率動的計画法は 、不確実性下における意思決定を理解する上で有用なツールです。不確実性下における資本ストックの蓄積はその一例であり、資源経済学者は 天候など不確実性が関与する 生物経済学の問題 [10]を分析するために、この手法を用いることが多いです。
例: 多段階ポートフォリオ最適化 以下は、ファイナンスにおける多段階確率計画法の例です。ある時点において、資産 に投資するための 初期資本があるとします 。さらに、ポートフォリオを随時リバランスすることは可能です が、追加資金の投入は行わないものとします。各時点において、現在の資産を資産 間で 再分配する決定を下します 。n個の資産に投資された初期額をnとします。各nは 非負であり、バランス方程式が成立することを 条件とします 。 t = 0 {\displaystyle t=0} W 0 {\displaystyle W_{0}} n {\displaystyle n} t = 1 , … , T − 1 {\displaystyle t=1,\dots ,T-1} t {\displaystyle t} W t {\displaystyle W_{t}} n {\displaystyle n} x 0 = ( x 10 , … , x n 0 ) {\displaystyle x_{0}=(x_{10},\dots ,x_{n0})} x i 0 {\displaystyle x_{i0}} ∑ i = 1 n x i 0 = W 0 {\displaystyle \sum _{i=1}^{n}x_{i0}=W_{0}}
各期間 の 総収益について考えてみましょう 。これはベクトル値のランダムプロセス を形成します 。 期間 に 、各資産に投資された金額を指定してポートフォリオを再調整できます 。 その時点では、第 1 期間の収益が実現されているため、再調整の決定にこの情報を使用するのは合理的です。したがって、時間 における第 2 段階の決定は、 実際にはランダムベクトル の実現の関数 、つまり です 。同様に、時間 における 決定は、 時間 までのランダムプロセスの履歴 によって提供される利用可能な情報の 関数です。 が 定数 である 一連の関数 、は、決定プロセスの 実装可能なポリシー を定義します。このようなポリシーは、 確率 1 でモデル制約、つまり非負制約 、、、 および資産残高制約
を満たす場合に 実行可能 であると言えます。 ξ t = ( ξ 1 t , … , ξ n t ) {\displaystyle \xi _{t}=(\xi _{1t},\dots ,\xi _{nt})} t = 1 , … , T {\displaystyle t=1,\dots ,T} ξ 1 , … , ξ T {\displaystyle \xi _{1},\dots ,\xi _{T}} t = 1 {\displaystyle t=1} x 1 = ( x 11 , … , x n 1 ) {\displaystyle x_{1}=(x_{11},\dots ,x_{n1})} t = 1 {\displaystyle t=1} ξ 1 {\displaystyle \xi _{1}} x 1 = x 1 ( ξ 1 ) {\displaystyle x_{1}=x_{1}(\xi _{1})} t {\displaystyle t} x t = ( x 1 t , … , x n t ) {\displaystyle x_{t}=(x_{1t},\dots ,x_{nt})} x t = x t ( ξ [ t ] ) {\displaystyle x_{t}=x_{t}(\xi _{[t]})} ξ [ t ] = ( ξ 1 , … , ξ t ) {\displaystyle \xi _{[t]}=(\xi _{1},\dots ,\xi _{t})} t {\displaystyle t} x t = x t ( ξ [ t ] ) {\displaystyle x_{t}=x_{t}(\xi _{[t]})} t = 0 , … , T − 1 {\displaystyle t=0,\dots ,T-1} x 0 {\displaystyle x_{0}} x i t ( ξ [ t ] ) ≥ 0 {\displaystyle x_{it}(\xi _{[t]})\geq 0} i = 1 , … , n {\displaystyle i=1,\dots ,n} t = 0 , … , T − 1 {\displaystyle t=0,\dots ,T-1}
∑ i = 1 n x i t ( ξ [ t ] ) = W t , {\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},} 期間中に 富 は t = 1 , … , T {\displaystyle t=1,\dots ,T} W t {\displaystyle W_{t}}
W t = ∑ i = 1 n ξ i t x i , t − 1 ( ξ [ t − 1 ] ) , {\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),} それはランダムプロセスの実現と時間までの決定に依存します 。 t {\displaystyle t}
最終期におけるこの富の期待効用を最大化することが目的だと仮定すると、つまり、次のような問題を考える。
max E [ U ( W T ) ] . {\displaystyle \max E[U(W_{T})].} これは多段階確率計画問題であり、各段階は から まで番号が付けられています 。最適化は、実装可能かつ実行可能なすべての方策について行われます。問題の説明を完了するには、ランダムプロセス の確率分布を定義する必要があります 。これはさまざまな方法で行うことができます。例えば、プロセスの時間発展を定義する特定のシナリオツリーを構築することができます。各段階において、各資産のランダムリターンが他の資産とは独立して2つの継続を持つことが許容される場合、シナリオの総数は t = 0 {\displaystyle t=0} t = T − 1 {\displaystyle t=T-1} ξ 1 , … , ξ T {\displaystyle \xi _{1},\dots ,\xi _{T}} 2 n T . {\displaystyle 2^{nT}.}
動的計画 法の方程式を書くには 、上記の多段階問題を時間的に遡って考えてみましょう。最終段階では、 ランダム過程の 実現方法が既知であり、 選択されています。したがって、次の問題を解く必要があります。 t = T − 1 {\displaystyle t=T-1} ξ [ T − 1 ] = ( ξ 1 , … , ξ T − 1 ) {\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})} x T − 2 {\displaystyle x_{T-2}}
max x T − 1 E [ U ( W T ) | ξ [ T − 1 ] ] subject to W T = ∑ i = 1 n ξ i T x i , T − 1 ∑ i = 1 n x i , T − 1 = W T − 1 x T − 1 ≥ 0 {\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}}} ここで、 は 与えられた の条件付き期待値を表します 。上記の問題の最適値は と に依存し 、 は と表されます 。 E [ U ( W T ) | ξ [ T − 1 ] ] {\displaystyle E[U(W_{T})|\xi _{[T-1]}]} U ( W T ) {\displaystyle U(W_{T})} ξ [ T − 1 ] {\displaystyle \xi _{[T-1]}} W T − 1 {\displaystyle W_{T-1}} ξ [ T − 1 ] {\displaystyle \xi _{[T-1]}} Q T − 1 ( W T − 1 , ξ [ T − 1 ] ) {\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}
同様に、段階ごとに 問題を解決する必要がある。 t = T − 2 , … , 1 {\displaystyle t=T-2,\dots ,1}
max x t E [ Q t + 1 ( W t + 1 , ξ [ t + 1 ] ) | ξ [ t ] ] subject to W t + 1 = ∑ i = 1 n ξ i , t + 1 x i , t ∑ i = 1 n x i , t = W t x t ≥ 0 {\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}}} その最適値は で表されます 。最終的に、 段階では 、問題 Q t ( W t , ξ [ t ] ) {\displaystyle Q_{t}(W_{t},\xi _{[t]})} t = 0 {\displaystyle t=0}
max x 0 E [ Q 1 ( W 1 , ξ [ 1 ] ) ] subject to W 1 = ∑ i = 1 n ξ i , 1 x i 0 ∑ i = 1 n x i 0 = W 0 x 0 ≥ 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}}}
段階的に独立したランダムプロセス プロセス の一般的な分布では 、これらの動的計画法方程式を解くのは困難かもしれません。プロセスが 段階的に独立している場合、 つまり が に対して（確率的に） 独立である場合、状況は劇的に単純化されます 。この場合、対応する条件付き期待値は無条件期待値になり、関数 は に 依存しません 。つまり、 は問題の最適値です。 ξ t {\displaystyle \xi _{t}} ξ t {\displaystyle \xi _{t}} ξ t {\displaystyle \xi _{t}} ξ 1 , … , ξ t − 1 {\displaystyle \xi _{1},\dots ,\xi _{t-1}} t = 2 , … , T {\displaystyle t=2,\dots ,T} Q t ( W t ) {\displaystyle Q_{t}(W_{t})} t = 1 , … , T − 1 {\displaystyle t=1,\dots ,T-1} ξ [ t ] {\displaystyle \xi _{[t]}} Q T − 1 ( W T − 1 ) {\displaystyle Q_{T-1}(W_{T-1})}
max x T − 1 E [ U ( W T ) ] subject to W T = ∑ i = 1 n ξ i T x i , T − 1 ∑ i = 1 n x i , T − 1 = W T − 1 x T − 1 ≥ 0 {\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}}} そして、 最適値は Q t ( W t ) {\displaystyle Q_{t}(W_{t})}
max x t E [ Q t + 1 ( W t + 1 ) ] subject to W t + 1 = ∑ i = 1 n ξ i , t + 1 x i , t ∑ i = 1 n x i , t = W t x t ≥ 0 {\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}}} のために 。 t = T − 2 , … , 1 {\displaystyle t=T-2,\dots ,1}
モデリング言語 離散確率計画問題はすべて、任意の代数モデリング言語 で表現できます 。明示的または暗黙的な非予測性を手動で実装することで、結果のモデルが各段階で利用可能な情報の構造を尊重するようにします。一般的なモデリング言語によって生成されるSP問題のインスタンスは、（シナリオ数に比例して）非常に大きくなる傾向があり、その行列はこのクラスの問題に固有の構造を失います。この構造は、本来であれば特定の分解アルゴリズムによって解を求める際に活用できるものです。SP向けに特別に設計されたモデリング言語の拡張機能が登場し始めています。以下を参照してください。
どちらも、問題の構造を冗長性のない形式でソルバーに伝える SMPS インスタンス レベル形式を生成できます。
参照
参考文献 ^ Shapiro, Alexander; Dentcheva, Darinka ; Ruszczyński, Andrzej (2009). Lectures on stochastic programming: Modeling and theory (PDF) . MPS/SIAM Series on Optimization. Vol. 9. Philadelphia, PA: Society for Industrial and Applied Mathematics and the Mathematical Programming Society. pp. xvi+436. ISBN 978-0-89871-687-0 . MR 2562798. オリジナル （PDF） から2020年3月24日にアーカイブ 。 2010年9月22日 閲覧。 ^ Birge, John R.; Louveaux, François (2011). 確率計画法入門. Springer Series in Operations Research and Financial Engineering. doi :10.1007/978-1-4614-0237-4. ISBN 978-1-4614-0236-7 . ISSN 1431-8598. ^
Stein W. Wallace、William T. Ziemba（編）. 確率的計画法の応用 . MPS-SIAM最適化ブックシリーズ5、2005年。 ^ 確率的計画法の応用については、次の Web サイト Stochastic Programming Community で説明されています。 ^ Shapiro, Alexander; Philpott, Andy. 確率的計画法のチュートリアル (PDF) . ^ 「最適化のためのNEOSサーバー」。 ^ Ruszczyński, Andrzej ; Shapiro, Alexander (2003). 確率的計画法 . オペレーションズ・リサーチとマネジメント・サイエンスのハンドブック. 第10巻. フィラデルフィア: Elsevier . p. 700. ISBN 978-0444508546 。 ^ Mangel, M. & Clark, CW 1988. 行動生態学における動的モデリング. プリンストン大学出版局 ISBN 0-691-08506-4 ^ Houston, A. I & McNamara, JM 1999. 適応行動モデル：状態に基づくアプローチ ケンブリッジ大学出版局 ISBN 0-521-65539-0 ^ Howitt, R., Msangi, S., Reynaud, A, K. Knapp. 2002. 「多項式近似を用いた確率的動的計画問題の解決：あるいはSDPへの「ベティ・クロッカー」アプローチ」カリフォルニア大学デービス校、農業資源経済学部ワーキングペーパー。
さらに読む John R. Birge、François V. Louveaux著 『確率計画法入門 』Springer Verlag、ニューヨーク、1997年。 カール、ピーター; ウォレス、スタイン W. (1994). 確率的計画法. Wiley-Interscience Series in Systems and Optimization. チチェスター: John Wiley & Sons, Ltd. pp. xii+307. ISBN 0-471-95158-7 . MR 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 and the Mathematical Programming Society. pp. xvi+436. ISBN 978-0-89871-687-0 . MR 2562798. オリジナル （PDF） から2020年3月24日にアーカイブ 。 2010年9月22日 閲覧。 Stein W. WallaceとWilliam T. Ziemba（編）（2005） 確率的計画法の応用 。MPS-SIAM最適化ブックシリーズ5 キング、アラン・J.; ウォレス、スタイン・W. (2012). 確率計画法によるモデリング. シュプリンガー・オペレーションズ・リサーチ・アンド・ファイナンシャル・エンジニアリング・シリーズ. ニューヨーク: シュプリンガー. ISBN 978-0-387-87816-4 。
外部リンク
![{\displaystyle \min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b8be5f17858f12985b6377724d3166c14be6bcb)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9a9b30c8d4ed6c4d9d0cb92169848f118761480)
![{\displaystyle E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6965b6869757dbc1d6965f9dea796cf48a67288)
![{\displaystyle q(x)=E[Q(x,\xi )]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b800a7fbfbddea6252c4c00a7170d77aa6d1746)
![{\displaystyle \min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/161c2b7f54a3e783d3b8edc45b2ab66a62fc4671)
![{\displaystyle E[Q(x,\xi)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8de948ea64600cb9e6bb7c1b536f5a74813719b4)
![{\displaystyle E[{\hat {g}}_{N}(x)]=g(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20be6eddd812ab84d9689fe9f2797bf6d625b9e0)
![{\displaystyle \sigma^{2}(x):=Var[Q(x,\xi)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f306057a735880a5f769821dd74c4266aa3dafd)
![{\displaystyle {\sqrt {N}}[{\hat {g}}_{N}-g(x)]\xrightarrow {\mathcal {D}} Y_{x}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1a4d7c91c6049a45acde5a55fce8d68a308a659)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8143acc88a78ea0cf121b6ffca33de816eaff11)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bf6be623be9a7f985827a018cfc97291dfc2e14)
![{\displaystyle x_{t}=x_{t}(\xi _{[t]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c4c87e8bd03667ddfc859878c222f768760b157)
![{\displaystyle \xi_{[t]}=(\xi_{1},\dots,\xi_{t})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbec2e91abeb7c2dff6418ab77d4a739f92ccb5b)
![{\displaystyle x_{it}(\xi _{[t]})\geq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a2f628c30ae0cbeb6617b84e714e2fd9ca62b90)
![{\displaystyle \sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f273b99affc7b38b95f0db5290329905ae724664)
![{\displaystyle W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/766e52fd0bfcd1c129158bbb0cef9c9a2b043924)
![{\displaystyle \max E[U(W_{T})].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/361eb1dabb6fb57c8a84cf434c36129aa8b9c400)
![{\displaystyle \xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9472da7b1985654e2ad2a1aa942251bfe031dec9)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4aff6e1cb7b24da4b7bee1482954018e2f129836)
![{\displaystyle E[U(W_{T})|\xi _{[T-1]}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9b3328b09ec5c8b5b9d6ef577852f05e28d1a94)
![{\displaystyle \xi _{[T-1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/973805509f7259ed072bbe78e8a29b09f887cff2)
![{\displaystyle Q_{T-1}(W_{T-1},\xi _{[T-1]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bb7df5a0d50efd9c8aaca2842518fc0a1564f9a6)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00c8656a01a165dbeaa35dd136f739edb20e4cec)
![{\displaystyle Q_{t}(W_{t},\xi _{[t]})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b9b9ff8951ab2abc4d648f0b4492d2e8f56121e1)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e4040e2ebece795d1d8e32ecec1f64e9e76fab1)
![{\displaystyle \xi _{[t]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae8e25ef1d2db3fd3d4f5d8977b4d94bfbcdfe50)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb205a5bb173c2ad39e924817211d59bacdc9ac1)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/183777e5365e288ed829121af98dda49d9fda57f)
