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

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

Двухэтапные задачи [ править ]

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

где - оптимальное значение задачи второго этапа${\ Displaystyle Q (х, \ xi)}$

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

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

В такой формулировке это вектор переменной решения первого этапа, вектор переменной решения второго этапа и содержит данные задачи второго этапа. В этой формулировке на первом этапе мы должны принять решение «здесь и сейчас» до того , как станет известна реализация неопределенных данных , рассматриваемых как случайный вектор. На втором этапе, когда реализация становится доступной, мы оптимизируем свое поведение, решая соответствующую задачу оптимизации.${\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 _{1},\dots ,\xi _{K}}$${\displaystyle p_{1},\dots ,p_{K}}$

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

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

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

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

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

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

Выборка Монте-Карло и метод приближения среднего значения выборки (SAA) [ править ]

Распространенным подходом к уменьшению набора сценариев до приемлемого размера является использование моделирования Монте-Карло. Предположим, общее количество сценариев очень велико или даже бесконечно. Предположим далее , что мы можем создать образец из репликаций случайного вектора . Обычно предполагается, что выборка является независимой и одинаково распределенной (iid sample). Для данной выборки функция ожидания аппроксимируется средним значением выборки.${\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 является функцией рассматриваемой выборки и в этом смысле случайна. Для данного образца проблема ССА имеет тот же вид , как двухступенчатый стохастическую задача линейного программирования со сценариями ., , Взятая с той же вероятностью .${\displaystyle \xi ^{1},\xi ^{2},\dots ,\xi ^{N}}$${\displaystyle \xi ^{j}}$${\displaystyle j=1,\dots ,N}$${\displaystyle p_{j}={\frac {1}{N}}}$

Статистический вывод [ править ]

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

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

По закону больших чисел имеем, что при некоторых условиях регулярности поточечно сходится с вероятностью 1 к as . Более того, при мягких дополнительных условиях сходимость равномерная. У нас также есть , то есть, является несмещенной оценкой . Следовательно, естественно ожидать, что оптимальное значение и оптимальные решения задачи 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 фиксирован, т. Е. Не зависит от выборки. Пусть и будет оптимальным значением и набором оптимальных решений, соответственно, истинной проблемы, и пусть и будет оптимальным значением и набором оптимальных решений, соответственно, проблемы 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}$

В некоторых ситуациях оценивается допустимый набор задач SAA, затем соответствующая задача SAA принимает вид${\displaystyle 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 }$

Асимптотика оптимального значения SAA [ править ]

Предположим, что образец 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 {\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)}$

где (здесь обозначает cdf стандартного нормального распределения) и${\displaystyle z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)}$${\displaystyle \Phi (\cdot )}$

- выборочная оценка дисперсии . То есть ошибка оценки (стохастически) порядка .${\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}}$

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

Поэтапный независимый случайный процесс [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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