Стохастическое программирование

В области математической оптимизации стохастическое программирование является структурой для моделирования задач оптимизации , которые включают неопределенность . Стохастическая программа является задачей оптимизации, в которой некоторые или все параметры задачи являются неопределенными, но следуют известным распределениям вероятностей . ^{[1] [2]} Эта структура контрастирует с детерминированной оптимизацией, в которой все параметры задачи считаются точно известными. Целью стохастического программирования является поиск решения, которое одновременно оптимизирует некоторые критерии, выбранные лицом, принимающим решения, и надлежащим образом учитывает неопределенность параметров задачи. Поскольку многие реальные решения включают неопределенность, стохастическое программирование нашло применение в широком спектре областей, начиная от финансов и заканчивая транспортом и оптимизацией энергетики. ^{[3] [4]}

Разработано несколько методов стохастического программирования:

• Методы, основанные на сценариях, включая аппроксимацию выборочного среднего
• Стохастическое целочисленное программирование для задач, в которых некоторые переменные должны быть целыми числами
• Программирование с ограничениями по вероятности для работы с ограничениями, которые должны быть удовлетворены с заданной вероятностью
• Стохастическое динамическое программирование
• Марковский процесс принятия решений
• Разложение Бендера

Основная идея двухэтапного стохастического программирования заключается в том, что (оптимальные) решения должны основываться на данных, доступных на момент принятия решений, и не могут зависеть от будущих наблюдений. Двухэтапная формулировка широко используется в стохастическом программировании. Общая формулировка двухэтапной задачи стохастического программирования имеет вид: где — оптимальное значение задачи второго этапа$${\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) \}.}$$

Классические двухэтапные задачи линейного стохастического программирования можно сформулировать как$${\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}}}$$

В такой формулировке — вектор переменных решения первого этапа, — вектор переменных решения второго этапа, и содержит данные задачи второго этапа. В этой формулировке на первом этапе мы должны принять решение «здесь и сейчас» до того, как станет известна реализация неопределенных данных , рассматриваемых как случайный вектор. На втором этапе, после того как реализация становится доступной, мы оптимизируем наше поведение, решая соответствующую задачу оптимизации.${\displaystyle x\in \mathbb {R} ^{n}}$${\displaystyle y\in \mathbb {R} ^{m}}$${\displaystyle \xi (q,T,W,h)}$${\displaystyle x}$${\displaystyle \xi }$${\displaystyle \xi }$

На первом этапе мы оптимизируем (минимизируем в приведенной выше формулировке) стоимость решения первого этапа плюс ожидаемую стоимость (оптимального) решения второго этапа. Мы можем рассматривать задачу второго этапа просто как задачу оптимизации, которая описывает наше предположительно оптимальное поведение при выявлении неопределенных данных, или мы можем рассматривать ее решение как регрессный иск, где член компенсирует возможную несогласованность системы и является стоимостью этого регрессного иска.${\displaystyle c^{T}x}$${\displaystyle Wy}$${\displaystyle Tx\leq h}$${\displaystyle q^{T}y}$

Рассматриваемая двухэтапная задача является линейной , поскольку целевые функции и ограничения линейны. Концептуально это не существенно, и можно рассмотреть более общие двухэтапные стохастические программы. Например, если задача первой стадии является целочисленной, можно добавить ограничения целочисленности к задаче первой стадии, чтобы допустимое множество было дискретным. Нелинейные цели и ограничения также могут быть включены, если необходимо. ^[5]

Формулировка вышеприведенной двухэтапной задачи предполагает, что данные второго этапа моделируются как случайный вектор с известным распределением вероятностей. Это было бы оправдано во многих ситуациях. Например, распределение может быть выведено из исторических данных, если предположить, что распределение не претерпевает существенных изменений за рассматриваемый период времени. Кроме того, эмпирическое распределение выборки может быть использовано в качестве приближения к распределению будущих значений . Если у вас есть априорная модель для , вы можете получить апостериорное распределение с помощью байесовского обновления.${\displaystyle \xi }$${\displaystyle \xi }$${\displaystyle \xi }$${\displaystyle \xi }$

Для численного решения двухэтапной стохастической задачи часто требуется предположить, что случайный вектор имеет конечное число возможных реализаций, называемых сценариями , скажем , с соответствующими вероятностными массами . Тогда ожидание в целевой функции задачи первого этапа можно записать в виде суммы: и, более того, двухэтапную задачу можно сформулировать как одну большую задачу линейного программирования (это называется детерминированным эквивалентом исходной задачи, см. раздел § Детерминированный эквивалент стохастической задачи).${\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})}$$

Когда существует бесконечное (или очень большое) число возможных реализаций, стандартный подход заключается в том, чтобы представить это распределение сценариями. Этот подход поднимает три вопроса, а именно:${\displaystyle \xi }$

1. Как строить сценарии, см. § Построение сценария;
2. Как решить детерминированный эквивалент. Такие оптимизаторы, как CPLEX и GLPK, могут решать большие линейные/нелинейные задачи. Сервер NEOS ^[6] , размещенный в Университете Висконсина, Мэдисон , предоставляет бесплатный доступ ко многим современным решателям. Структура детерминированного эквивалента особенно поддается применению методов декомпозиции ^[7] , таких как декомпозиция Бендерса или декомпозиция сценария;
3. Как измерить качество полученного решения относительно «истинного» оптимума.

Эти вопросы не являются независимыми. Например, количество построенных сценариев повлияет как на управляемость детерминированного эквивалента, так и на качество полученных решений.

Стохастическая линейная программа является частным случаем классической двухэтапной стохастической программы. Стохастическая LP строится из набора многопериодных линейных программ (LP), каждая из которых имеет одинаковую структуру, но несколько отличающиеся данные. Двухпериодная 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}$

Обратите внимание, что решение двухпериодного LP эквивалентно предположению сценария во втором периоде без неопределенности. Чтобы включить неопределенности на втором этапе, следует назначить вероятности различным сценариям и решить соответствующий детерминированный эквивалент.${\displaystyle k^{th}}$${\displaystyle k^{th}}$

При конечном числе сценариев двухэтапные стохастические линейные программы могут быть смоделированы как большие задачи линейного программирования. Эту формулировку часто называют детерминированным эквивалентом линейной программы или сокращенно детерминированным эквивалентом. (Строго говоря, детерминированный эквивалент — это любая математическая программа, которая может быть использована для вычисления оптимального решения на первом этапе, поэтому они будут существовать и для непрерывных распределений вероятностей, когда можно представить стоимость второго этапа в некоторой замкнутой форме.) Например, чтобы сформировать детерминированный эквивалент вышеприведенной стохастической линейной программы, мы назначаем вероятность каждому сценарию . Затем мы можем минимизировать ожидаемое значение цели с учетом ограничений из всех сценариев:${\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}}}$

У нас есть другой вектор переменных более позднего периода для каждого сценария . Однако переменные первого периода и одинаковы в каждом сценарии, поскольку мы должны принять решение для первого периода, прежде чем узнаем, какой сценарий будет реализован. В результате ограничения, включающие только и , нужно указать только один раз, в то время как остальные ограничения должны быть заданы отдельно для каждого сценария.${\displaystyle z_{k}}$${\displaystyle k}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

На практике может быть возможным построить сценарии, выявив мнения экспертов о будущем. Количество построенных сценариев должно быть относительно скромным, чтобы полученный детерминированный эквивалент мог быть решен с разумными вычислительными усилиями. Часто утверждается, что решение, которое является оптимальным с использованием только нескольких сценариев, обеспечивает более адаптируемые планы, чем решение, которое предполагает только один сценарий. В некоторых случаях такое утверждение может быть проверено с помощью моделирования. Теоретически некоторые меры гарантируют, что полученное решение решает исходную задачу с разумной точностью. Обычно в приложениях только оптимальное решение первого этапа имеет практическую ценность, поскольку почти всегда «истинная» реализация случайных данных будет отличаться от набора построенных (сгенерированных) сценариев.${\displaystyle x^{*}}$

Предположим, что содержит независимые случайные компоненты, каждый из которых имеет три возможных реализации (например, будущие реализации каждого случайного параметра классифицируются как низкие, средние и высокие), тогда общее число сценариев равно . Такой экспоненциальный рост числа сценариев делает разработку модели с использованием экспертного мнения очень сложной даже для разумного размера . Ситуация становится еще хуже, если некоторые случайные компоненты имеют непрерывные распределения.${\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 имеет ту же форму, что и двухэтапная задача стохастического линейного программирования со сценариями ., , каждый из которых взят с одинаковой вероятностью .${\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 )]\}}$

Здесь — непустое замкнутое подмножество , — случайный вектор, распределение вероятностей которого поддерживается на множестве , а . В рамках двухэтапного стохастического программирования задается оптимальным значением соответствующей задачи второго этапа.${\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. Пусть и будут последовательностью (детерминированных) вещественных функций. Следующие два свойства эквивалентны:${\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]} Эмпирические испытания моделей оптимального кормодобывания , переходов жизненного цикла , таких как оперение у птиц и откладывание яиц у паразитоидных ос, показали ценность этого метода моделирования в объяснении эволюции принятия поведенческих решений. Эти модели, как правило, многоэтапные, а не двухэтапные.

Стохастическое динамическое программирование является полезным инструментом для понимания принятия решений в условиях неопределенности. Накопление капитала в условиях неопределенности является одним из примеров; часто оно используется экономистами ресурсов для анализа биоэкономических проблем ^[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}}$

Рассмотрим общую доходность за каждый период . Это формирует векторный случайный процесс . В период времени мы можем перебалансировать портфель, указав суммы, инвестированные в соответствующие активы. В это время доходность в первом периоде была реализована, поэтому разумно использовать эту информацию в решении о перебалансировке. Таким образом, решения второго этапа в момент времени на самом деле являются функциями реализации случайного вектора , т. е . . Аналогично, в момент времени решение является функцией доступной информации, предоставленной историей случайного процесса до момента времени . Последовательность функций , , при этом будучи постоянной, определяет реализуемую политику процесса принятия решений. Говорят, что такая политика осуществима , если она удовлетворяет ограничениям модели с вероятностью 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})].}$

Это многоэтапная задача стохастического программирования, где этапы пронумерованы от до . Оптимизация выполняется по всем реализуемым и возможным политикам. Для завершения описания задачи также необходимо определить распределение вероятностей случайного процесса . Это можно сделать различными способами. Например, можно построить конкретное дерево сценариев, определяющее временную эволюцию процесса. Если на каждом этапе случайная доходность каждого актива может иметь два продолжения, независимо от других активов, то общее количество сценариев равно${\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, созданный для упрощения стохастического программирования (включает ключевые слова для параметрических распределений, ограничений вероятности и мер риска, таких как стоимость под риском и ожидаемый дефицит ).
• SAMPL — набор расширений AMPL, специально разработанных для выражения стохастических программ (включает синтаксис для ограничений вероятности, интегрированных ограничений вероятности и задач надежной оптимизации )

Они оба могут генерировать формат уровня экземпляра SMPS, который передает решателю структуру задачи в неизбыточной форме.

• Выбор портфеля с ограничениями по шансам
• Корреляционный разрыв
• EMP для стохастического программирования
• Энтропийная ценность под угрозой
• FortSP
• Язык алгебраического моделирования SAMPL
• Оптимизация сценария
• Стохастическая оптимизация

• Джон Р. Бирге и Франсуа В. Луво. Введение в стохастическое программирование . Springer Verlag, Нью-Йорк, 1997.
• Калл, Питер; Уоллес, Стайн В. (1994). Стохастическое программирование. Серия Wiley-Interscience по системам и оптимизации. Чичестер: John Wiley & Sons, Ltd. стр. xii+307. ISBN 0-471-95158-7. МР  1315300.
• Г. Ч. Пфлуг: Оптимизация стохастических моделей. Интерфейс между моделированием и оптимизацией . Kluwer, Дордрехт, 1996.
• Андраш Прекопа . Стохастическое программирование. Kluwer Academic Publishers, Дордрехт, 1995.
• Анджей Рущинский и Александр Шапиро (ред.) (2003) Стохастическое программирование . Справочники по исследованию операций и науке управления, т. 10, Elsevier.
• Шапиро, Александр; Денчева, Даринка ; Рущинский, Анджей (2009). Лекции по стохастическому программированию: Моделирование и теория (PDF) . Серия MPS/SIAM по оптимизации. Том 9. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). стр. xvi+436. ISBN 978-0-89871-687-0. MR  2562798. Архивировано из оригинала (PDF) 2020-03-24 . Получено 2010-09-22 . {{cite book}}: Неизвестный параметр |agency=проигнорирован ( помощь )
• Stein W. Wallace и William T. Ziemba (ред.) (2005) Applications of Stochastic Programming . Серия книг MPS-SIAM по оптимизации 5
• King, Alan J.; Wallace, Stein W. (2012). Моделирование с помощью стохастического программирования. Springer Series in Operations Research and Financial Engineering. New York: Springer. ISBN 978-0-387-87816-4.

• Домашняя страница сообщества стохастического программирования