VladimirDobrovolsky611/Алгоритм SDDP: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
| Строка 22: | Строка 22: | ||
<math> | <math> | ||
\left\{\begin{matrix} | \left\{\begin{matrix} | ||
| − | min \ c_1x_1 + \sum_{i=1}^{ | + | min \ c_1x_1 + \sum_{i=1}^{N_1}p_1^iQ_2(x_1,\xi_i^2) |
\\subject \ to | \\subject \ to | ||
\\A_1x_1\geqslant b_1 | \\A_1x_1\geqslant b_1 | ||
| Строка 30: | Строка 30: | ||
где | где | ||
| + | |||
| + | <math> | ||
| + | Q_1(x_1,\xi_i^2) = | ||
| + | \left\{\begin{matrix} | ||
| + | min \ c_2x_2 + \sum_{i=1}^{N_2}p_2^iQ_3(x_2,\xi_i^3) | ||
| + | \\subject \ to | ||
| + | \\A_2x_2 + B_2x_1\geqslant b_1 | ||
| + | \\x_2 \geqslant 0 | ||
| + | |||
| + | \end{matrix}\right.</math> | ||
== Вычислительное ядро алгоритма== | == Вычислительное ядро алгоритма== | ||
Версия 14:50, 6 февраля 2017
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Стохастическое двойственное динамическое программирование (SDDP) – это метод оптимизации, предназначенный для решения динамических задач в условиях неопределенности, то есть в случае, когда некоторые параметры задачи не являются детерминированными. В силу фундаментальности постановки задачи, данный алгоритм может быть применен в самых различных прикладных областях. Например, на сегодняшний день, стохастическое двойственное динамическое программирование активно используется для управления ГЭС в Норвегии, а также вводится в банках для управления рыночными рисками. На сегодняшний день также широко распространены альтернативные динамические методы поиска решений в условиях неопределенности, например, методы, работающие на принципах построения дерева возможных исходов, или методы, работающие на принципах управляющих правил. Однако, методы, работающие по принципу построения дерева, неизбежно сталкиваются с широко известным «проклятием размерности» (curse of dimensionality), а методы, построенные на принципах управляющих правил, как правило, требуют серьезные ограничения на тип управляющих правил, а также на свойства стохастических параметров задачи. Также, в задачах динамического управления присутствует проблема тайм-консистентности решения (time-consistence solution).
Алгоритм SDDP (Stochastic dual dynamic programming) впервые был предложен в статье M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied to energy planning" в 1991 году. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", Теперь под аббревиатурой SDDP подразумевается целое семейство алгоритмов.
1.2 Математическое описание алгоритма
Исходные данные:
1. Количество этапов T, количество состояний на каждом этапе [math]N_t[/math], [math]t = 1,...,T[/math] 2. Размерность задачи N (размерность управляющего правила) 3. Вероятности переходов [math]p_{nt}; t = 1,...,T; n = 1,...,N_t[/math] 4. матрицы состояний [math]A_i^t, B_i^t, b_i^t, c_i^t[/math]
Совокупность входных параметров в пунктах 1 - 4 формируют сценарную решетку задачи (см. рис. 1)
Вычисляемые данные: Матрица управляющих действий [math]X[/math] (элементы [math]x_{it}; t \in 1,...,T; i \in 1,...,N[/math] - управления для i-го элемента на шаге t)
Постановка задачи:
[math] \left\{\begin{matrix} min \ c_1x_1 + \sum_{i=1}^{N_1}p_1^iQ_2(x_1,\xi_i^2) \\subject \ to \\A_1x_1\geqslant b_1 \\x_1 \geqslant 0 \end{matrix}\right.[/math]
где
[math] Q_1(x_1,\xi_i^2) = \left\{\begin{matrix} min \ c_2x_2 + \sum_{i=1}^{N_2}p_2^iQ_3(x_2,\xi_i^3) \\subject \ to \\A_2x_2 + B_2x_1\geqslant b_1 \\x_2 \geqslant 0 \end{matrix}\right.[/math]
