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

Для контекста теории управления см. Стохастическое управление .

В области математической оптимизации стохастическое программирование представляет собой основу для моделирования задач оптимизации , связанных с неопределенностью . Стохастическая программа — это задача оптимизации, в которой некоторые или все параметры задачи неопределенны, но подчиняются известным распределениям вероятностей . Эта концепция контрастирует с детерминированной оптимизацией, в которой предполагается, что все параметры задачи точно известны. Цель стохастического программирования — найти решение, которое одновременно оптимизирует некоторые критерии, выбранные лицом, принимающим решение, и соответствующим образом учитывает неопределенность параметров задачи. Поскольку многие решения в реальном мире связаны с неопределенностью, стохастическое программирование нашло применение в широком спектре областей: от финансов до транспорта и оптимизации энергетики.

Двухэтапные задачи

Основная идея двухэтапного стохастического программирования заключается в том, что (оптимальные) решения должны основываться на данных, доступных на момент принятия решений, и не могут зависеть от будущих наблюдений. Двухэтапная формулировка широко используется в стохастическом программировании. Общая формулировка двухэтапной задачи стохастического программирования имеет вид:

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

где $Q(x,\xi )$ – оптимальное значение задачи второго этапа

$$\min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.$$

Классические двухэтапные задачи линейного стохастического программирования можно сформулировать как

$${\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}}$$

где $Q(x,\xi )$ – оптимальное значение задачи второго этапа

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

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

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

Предположение

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

Дискретизация

Для численного решения двухэтапной стохастической задачи часто приходится предполагать, что случайный вектор $\xi$ имеет конечное число возможных реализаций, называемых сценариями , скажем $\xi _{1},\dots ,\xi _{K}$, с соответствующими вероятностными массами $p_{1},\dots ,p_{K}$. Тогда математическое ожидание целевой функции задачи первого этапа можно записать в виде суммирования:

$$E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})$$

и, более того, двухэтапную задачу можно сформулировать как одну большую задачу линейного программирования (это называется детерминистическим эквивалентом исходной задачи, см. раздел § Детерминированный эквивалент стохастической задачи ).

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

1. Как строить сценарии, см. § Построение сценариев ;
2. Как решить детерминированный эквивалент. Оптимизаторы, такие как CPLEX и GLPK, могут решать большие линейные/нелинейные задачи. Сервер НЕОС, размещенный в Университете Висконсина, Мэдисон , обеспечивает свободный доступ ко многим современным решателям. Структура детерминированного эквивалента особенно удобна для применения методов декомпозиции. такие как декомпозиция Бендерса или декомпозиция сценариев;
3. Как измерить качество полученного решения относительно «истинного» оптимума.

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

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

Стохастическая линейная программа — это частный случай классической двухэтапной стохастической программы. Стохастическая ЛП строится из набора многопериодных линейных программ (ЛП), каждая из которых имеет одинаковую структуру, но несколько разные данные. $k^{th}$ двухпериодная LP, представляющая $k^{th}$ сценарий можно рассматривать как имеющий следующий вид:

${\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}}$

Векторы $x$ и $y$ содержат переменные первого периода, значения которых необходимо выбрать немедленно. Вектор $z_{k}$ содержит все переменные для последующих периодов. Ограничения $Tx+Uy=r$ включают только переменные первого периода и одинаковы в каждом сценарии. Другие ограничения включают переменные более поздних периодов и в некоторых отношениях различаются от сценария к сценарию, отражая неопределенность относительно будущего.

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

задачи

При ограниченном числе сценариев двухэтапные стохастические линейные программы можно моделировать как большие задачи линейного программирования. Эту формулировку часто называют детерминированной эквивалентной линейной программой или сокращенно детерминированный эквивалент. (Строго говоря, детерминистическим эквивалентом является любая математическая программа, которую можно использовать для вычисления оптимального решения на первом этапе, поэтому они будут существовать и для непрерывных распределений вероятностей, когда можно представить затраты на втором этапе в некоторой замкнутой форме.)Например, чтобы сформировать детерминированный эквивалент вышеупомянутой стохастической линейной программы, мы присваиваем вероятность $p_{k}$ к каждому сценарию $k=1,\dots ,K$. Тогда мы можем минимизировать ожидаемое значение цели с учетом ограничений всех сценариев:

${\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}}$

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

Построение сценария

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

Предполагать $\xi$ содержит $d$ независимые случайные компоненты, каждая из которых имеет три возможных реализации (например, будущие реализации каждого случайного параметра классифицируются как низкие, средние и высокие), тогда общее количество сценариев равно $K=3^{d}$. Такой экспоненциальный рост количества сценариев делает разработку моделей с использованием экспертного мнения очень сложной задачей даже для разумных размеров. $d$. Ситуация становится еще хуже, если некоторые случайные компоненты $\xi$ имеют непрерывные распределения.

SAA

Распространенным подходом к уменьшению набора сценариев до приемлемого размера является использование моделирования Монте-Карло. Предположим, что общее количество сценариев очень велико или даже бесконечно. Предположим далее, что мы можем сгенерировать выборку $\xi ^{1},\xi ^{2},\dots ,\xi ^{N}$ из $N$ репликации случайного вектора $\xi$. Обычно предполагается, что выборка независима и одинаково распределена (iid выборка). Учитывая выборку, функция ожидания $q(x)=E[Q(x,\xi )]$ аппроксимируется выборочным средним

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

и, следовательно, задача первого этапа имеет вид

${\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 является функцией рассматриваемой выборки и в этом смысле является случайной. Для данного образца $\xi ^{1},\xi ^{2},\dots ,\xi ^{N}$ задача SAA имеет тот же вид, что и двухэтапная задача стохастического линейного программирования со сценариями $\xi ^{j}$., $j=1,\dots ,N$, каждое взято с одинаковой вероятностью $p_{j}={\frac {1}{N}}$.

Статистический

Рассмотрим следующую задачу стохастического программирования.

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

Здесь $X$ является непустым замкнутым подмножеством $\mathbb {R} ^{n}$, $\xi$ — случайный вектор, распределение вероятностей которого $P$ поддерживается в наборе $\Xi \subset \mathbb {R} ^{d}$, и $Q:X\times \Xi \rightarrow \mathbb {R}$. В рамках двухэтапного стохастического программирования $Q(x,\xi )$ задается оптимальным значением соответствующей задачи второго этапа.

Предположим, что $g(x)$ корректно определен и имеет конечное значение для всех $x\in X$. Это означает, что для каждого $x\in X$ ценность $Q(x,\xi )$ конечен почти наверняка.

Предположим, что у нас есть образец $\xi ^{1},\dots ,\xi ^{N}$ из $N$реализации случайного вектора $\xi$. Эту случайную выборку можно рассматривать как исторические данные $N$ наблюдения за $\xi$, или его можно сгенерировать с помощью методов выборки Монте-Карло. Затем мы можем сформулировать соответствующую аппроксимацию выборочного среднего значения

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

По закону больших чисел мы имеем, что при некоторых условиях регулярности ${\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})$ сходится поточечно с вероятностью 1 к $E[Q(x,\xi )]$ как $N\rightarrow \infty$. При этом при мягких дополнительных условиях сходимость равномерная. У нас также есть $E[{\hat {g}}_{N}(x)]=g(x)$, то есть, ${\hat {g}}_{N}(x)$ является несмещенной оценкой $g(x)$. Поэтому естественно ожидать, что оптимальное значение и оптимальные решения проблемы SAA сходятся к своим аналогам истинной проблемы как $N\rightarrow \infty$.

Согласованность

Предположим, что допустимое множество $X$ задачи SAA фиксирована, т. е. не зависит от выборки. Позволять $\vartheta ^{*}$ и $S^{*}$ – оптимальное значение и множество оптимальных решений соответственно истинной задачи и пусть ${\hat {\vartheta }}_{N}$ и ${\hat {S}}_{N}$ – оптимальное значение и множество оптимальных решений соответственно задачи САА.

1. Позволять $g:X\rightarrow \mathbb {R}$ и ${\hat {g}}_{N}:X\rightarrow \mathbb {R}$ быть последовательностью (детерминированных) вещественных функций. Следующие два свойства эквивалентны:
   • для любого ${\overline {x}}\in X$ и любая последовательность $\{x_{N}\}\subset X$ сходящиеся к ${\overline {x}}$ отсюда следует, что ${\hat {g}}_{N}(x_{N})$ сходится к $g({\overline {x}})$
   • функция $g(\cdot )$ постоянно включен $X$ и ${\hat {g}}_{N}(\cdot )$ сходится к $g(\cdot )$ равномерно на любом компактном подмножестве $X$
2. Если цель проблемы SAA ${\hat {g}}_{N}(x)$ сходится к истинной цели проблемы $g(x)$ с вероятностью 1, так как $N\rightarrow \infty$, равномерно на допустимом множестве $X$. Затем ${\hat {\vartheta }}_{N}$ сходится к $\vartheta ^{*}$ с вероятностью 1 как $N\rightarrow \infty$.
3. Предположим, что существует компакт $C\subset \mathbb {R} ^{n}$ такой, что
   • набор $S$ оптимальных решений истинной задачи непусто и содержится в $C$
   • функция $g(x)$ конечнозначен и непрерывен на $C$
   • последовательность функций ${\hat {g}}_{N}(x)$ сходится к $g(x)$ с вероятностью 1, так как $N\rightarrow \infty$, равномерно в $x\in C$
   • для $N$ достаточно большой набор ${\hat {S}}_{N}$ непусто и ${\hat {S}}_{N}\subset C$ с вероятностью 1

затем ${\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}$ и $\mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0$ с вероятностью 1 как $N\rightarrow \infty$. Обратите внимание, что $\mathbb {D} (A,B)$ обозначает отклонение множества $A$ из набора $B$, определяемый как

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

В некоторых ситуациях допустимое множество $X$ задачи САА оценивается, то соответствующая задача САА принимает вид

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

где $X_{N}$ является подмножеством $\mathbb {R} ^{n}$ зависит от выборки и поэтому является случайным. Тем не менее, результаты согласованности для оценок SAA все же можно получить при некоторых дополнительных предположениях:

1. Предположим, что существует компакт $C\subset \mathbb {R} ^{n}$ такой, что
   • набор $S$ оптимальных решений истинной задачи непусто и содержится в $C$
   • функция $g(x)$ конечнозначен и непрерывен на $C$
   • последовательность функций ${\hat {g}}_{N}(x)$ сходится к $g(x)$ с вероятностью 1, так как $N\rightarrow \infty$, равномерно в $x\in C$
   • для $N$ достаточно большой набор ${\hat {S}}_{N}$ непусто и ${\hat {S}}_{N}\subset C$ с вероятностью 1
   • если $x_{N}\in X_{N}$ и $x_{N}$ сходится с вероятностью 1 к точке $x$, затем $x\in X$
   • в какой-то момент $x\in S^{*}$ существует последовательность $x_{N}\in X_{N}$ такой, что $x_{N}\rightarrow x$ с вероятностью 1.

затем ${\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}$ и $\mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0$ с вероятностью 1 как $N\rightarrow \infty$.

SAA

Предположим, образец $\xi ^{1},\dots ,\xi ^{N}$ это iid и исправить точку $x\in X$. Тогда выборочная средняя оценка ${\hat {g}}_{N}(x)$, из $g(x)$, является несмещенным и имеет дисперсию ${\frac {1}{N}}\sigma ^{2}(x)$, где $\sigma ^{2}(x):=Var[Q(x,\xi )]$ предполагается конечным. Более того, по центральной предельной теореме имеем, что

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

где ${\xrightarrow {\mathcal {D}}}$ обозначает сходимость в распределении и $Y_{x}$ имеет нормальное распределение со средним $0$ и дисперсия $\sigma ^{2}(x)$, записанный как ${\mathcal {N}}(0,\sigma ^{2}(x))$.

Другими словами, ${\hat {g}}_{N}(x)$ имеет асимптотически нормальное распределение, т. е. при больших $N$, ${\hat {g}}_{N}(x)$ имеет приблизительно нормальное распределение со средним $g(x)$ и дисперсия ${\frac {1}{N}}\sigma ^{2}(x)$. Это приводит к следующему (приблизительно) $100(1-\alpha )$% доверительный интервал для $f(x)$:

$\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_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)$ (здесь $\Phi (\cdot )$ обозначает CDF стандартного нормального распределения) и

${\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}$

это выборочная оценка дисперсии $\sigma ^{2}(x)$. То есть ошибка оценки $g(x)$ имеет (стохастический) порядок $O({\sqrt {N}})$.

Приложения и примеры

применения

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

приложения

Стохастическое динамическое программирование — полезный инструмент для понимания процесса принятия решений в условиях неопределенности. Одним из примеров является накопление основного капитала в условиях неопределенности; часто его используют экономисты-ресурсовики для анализа биоэкономических проблем. куда входит неопределенность, например, погода и т. д.

Пример: многоэтапная оптимизация портфеля

Основная статья: Выбор межвременного портфеля

Смотрите также: Проблема портфеля Мертона

Ниже приводится пример из области финансов многоэтапного стохастического программирования.Предположим, что в момент времени $t=0$ у нас есть первоначальный капитал $W_{0}$ инвестировать в $n$ ресурсы. Предположим далее, что нам разрешено время от времени ребалансировать наш портфель. $t=1,\dots ,T-1$ но без вливания в это дополнительных денег. В каждый период $t$ принимаем решение о перераспределении текущего богатства $W_{t}$ среди $n$ ресурсы. Позволять $x_{0}=(x_{10},\dots ,x_{n0})$ — первоначальные суммы, вложенные в n активов. Мы требуем, чтобы каждый $x_{i0}$ неотрицательен и что уравнение баланса $\sum _{i=1}^{n}x_{i0}=W_{0}$ должно держаться.

Рассмотрим общую прибыль $\xi _{t}=(\xi _{1t},\dots ,\xi _{nt})$ за каждый период $t=1,\dots ,T$. Это формирует векторный случайный процесс $\xi _{1},\dots ,\xi _{T}$. В период времени $t=1$, мы можем ребалансировать портфель, указав суммы $x_{1}=(x_{11},\dots ,x_{n1})$ вложены в соответствующие активы. К этому моменту прибыль за первый период уже реализована, поэтому разумно использовать эту информацию при принятии решения о ребалансировке. Таким образом, решения второго этапа, в свое время $t=1$, на самом деле являются функциями реализации случайного вектора $\xi _{1}$, то есть, $x_{1}=x_{1}(\xi _{1})$. Аналогично, во время $t$ решение $x_{t}=(x_{1t},\dots ,x_{nt})$ это функция $x_{t}=x_{t}(\xi _{[t]})$ доступной информации, предоставленной $\xi _{[t]}=(\xi _{1},\dots ,\xi _{t})$ история случайного процесса до момента времени $t$. Последовательность функций $x_{t}=x_{t}(\xi _{[t]})$, $t=0,\dots ,T-1$, с $x_{0}$ будучи константой, определяет реализуемую политику процесса принятия решений. Говорят, что такая политика осуществима , если она удовлетворяет ограничениям модели с вероятностью 1, т. е. ограничениям неотрицательности $x_{it}(\xi _{[t]})\geq 0$, $i=1,\dots ,n$, $t=0,\dots ,T-1$и баланс ограничений богатства,

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

где в период $t=1,\dots ,T$ богатство $W_{t}$ дается

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

которая зависит от реализации случайного процесса и решений, принятых до момента времени $t$.

Предположим, что цель состоит в том, чтобы максимизировать ожидаемую полезность этого богатства в последний период, то есть рассмотреть задачу

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

Это многоэтапная задача стохастического программирования, в которой этапы нумеруются от $t=0$ к $t=T-1$. Оптимизация выполняется по всем реализуемым и осуществимым политикам. Для завершения описания задачи необходимо также определить распределение вероятностей случайного процесса. $\xi _{1},\dots ,\xi _{T}$. Это можно сделать разными способами. Например, можно построить определенное дерево сценариев, определяющее временную эволюцию процесса. Если на каждом этапе случайному доходу каждого актива разрешено иметь два продолжения, независимых от других активов, то общее количество сценариев равно $2^{nT}.$

Чтобы написать уравнения динамического программирования , рассмотрим описанную выше многоэтапную задачу назад во времени. На последнем этапе $t=T-1$, реализация $\xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})$ случайного процесса известен и $x_{T-2}$ был выбран. Поэтому необходимо решить следующую задачу

${\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})|\xi _{[T-1]}]$ обозначает условное ожидание $U(W_{T})$ данный $\xi _{[T-1]}$. Оптимальное значение вышеуказанной задачи зависит от $W_{T-1}$ и $\xi _{[T-1]}$ и обозначается $Q_{T-1}(W_{T-1},\xi _{[T-1]})$.

Аналогично на этапах $t=T-2,\dots ,1$, надо решить проблему

${\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},\xi _{[t]})$. Наконец, на этапе $t=0$, человек решает проблему

${\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}}$

случайный

Для общего распространения процесса $\xi _{t}$, решить эти уравнения динамического программирования может быть сложно. Ситуация существенно упрощается, если процесс $\xi _{t}$ стадийно независима, т. е. $\xi _{t}$ (стохастически) не зависит от $\xi _{1},\dots ,\xi _{t-1}$ для $t=2,\dots ,T$. В этом случае соответствующие условные ожидания становятся безусловными ожиданиями, а функция $Q_{t}(W_{t})$, $t=1,\dots ,T-1$ не зависит от $\xi _{[t]}$. То есть, $Q_{T-1}(W_{T-1})$ оптимальная стоимость задачи

${\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})$ является оптимальным значением

${\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,\dots ,1$.

Программные инструменты

Языки моделирования

Все задачи дискретного стохастического программирования могут быть представлены с помощью любого языка алгебраического моделирования , вручную реализующего явную или неявную непредвиденность, чтобы гарантировать, что полученная модель соответствует структуре информации, доступной на каждом этапе. Экземпляр задачи SP, созданный с помощью общего языка моделирования, имеет тенденцию становиться довольно большим (линейно по числу сценариев), а его матрица теряет структуру, присущую этому классу задач, которую в противном случае можно было бы использовать во время решения с помощью специальные алгоритмы декомпозиции.Начинают появляться расширения языков моделирования, специально разработанных для SP, см.:

• AIMMS - поддерживает определение проблем SP
• EMP SP (Расширенное математическое программирование для стохастического программирования) — модуль GAMS, созданный для облегчения стохастического программирования (включает ключевые слова для параметрических распределений, случайных ограничений и мер риска, таких как «Ценность под риском» и «Ожидаемый дефицит» ).
• SAMPL — набор расширений AMPL, специально разработанных для выражения стохастических программ (включает синтаксис для случайных ограничений, интегрированных случайных ограничений и робастной оптимизации ). задач

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

См. также

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

Дальнейшее чтение

• Джон Р. Бирдж и Франсуа В. Луво. Введение в стохастическое программирование . Спрингер Верлаг, Нью-Йорк, 1997 г.
• Калл, Питер; Уоллес, Стейн В. (1994). Стохастическое программирование . Серия Wiley-Interscience по системам и оптимизации. Чичестер: John Wiley & Sons, Ltd., стр. xii+307. ISBN  0-471-95158-7 . МР   1315300 .
• Г. Ч. Пфлюг: Оптимизация стохастических моделей. Интерфейс между моделированием и оптимизацией . Клювер, Дордрехт, 1996 г.
• Андраш Прекопа . Стохастическое программирование. Kluwer Academic Publishers, Дордрехт, 1995.
• Анджей Рущинский и Александр Шапиро (ред.) (2003) Стохастическое программирование . Справочники по исследованию операций и науке управления, Vol. 10, Эльзевир.
• Шапиро, Александр; Денчева, Даринка ; Рущинский, Анджей (2009). Лекции по стохастическому программированию: Моделирование и теория (PDF) . Серия MPS/SIAM по оптимизации. Том. 9. Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM). стр. xvi+436. ISBN  978-0-89871-687-0 . МР   2562798 . Архивировано из оригинала (PDF) 24 марта 2020 г. Проверено 22 сентября 2010 г. {{cite book}}: Неизвестный параметр |agency= игнорируется ( помогите )
• Стейн В. Уоллес и Уильям Т. Зиемба (ред.) (2005) Приложения стохастического программирования . Серия книг MPS-SIAM по оптимизации 5
• Кинг, Алан Дж.; Уоллес, Стейн В. (2012). Моделирование с помощью стохастического программирования . Серия Springer по исследованию операций и финансовой инженерии. Нью-Йорк: Спрингер. ISBN  978-0-387-87816-4 .

Внешние ссылки

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