VladimirDobrovolsky611/Алгоритм SDDP: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 12: Строка 12:
 
  3. матрицы состояний <math>A_i^t, B_i^t, b_i^t, c_i^t</math>
 
  3. матрицы состояний <math>A_i^t, B_i^t, b_i^t, c_i^t</math>
 
Совокупность входных параметров в пунктах 1 - 3 формируют сценарную решетку задачи (см. рис. 1)
 
Совокупность входных параметров в пунктах 1 - 3 формируют сценарную решетку задачи (см. рис. 1)
File:Graph.png
+
[[File:Graph.png]]
  
 
== Вычислительное ядро алгоритма==
 
== Вычислительное ядро алгоритма==

Версия 13:38, 6 февраля 2017

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. Вероятности переходов [math]p_{nt}; t = 1,...,T; n = 1,...,N_t[/math] 
3. матрицы состояний [math]A_i^t, B_i^t, b_i^t, c_i^t[/math]

Совокупность входных параметров в пунктах 1 - 3 формируют сценарную решетку задачи (см. рис. 1) Graph.png

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма