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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 64: Строка 64:
 
\end{matrix}\right.
 
\end{matrix}\right.
 
</math>
 
</math>
 +
 +
Данная постановка задачи позволяет решать задачи стохастического программирования, где в качестве метрики взято мат. ожидание по состояниям системы.
 +
Существуют также и другие расширения данного алгоритма, где в качестве метрики взято значение Value at Risk или Expected Shortfall, широко используемые в оценки рисков финансовых потерь.
 +
 +
Существует несколько прикладных задач, для которых используется данный алгоритм:
 +
 +
1. Управление ГЭС
 +
 +
Моделируется следующая ситуация:
 +
 +
Существует водохранилище с ограниченным объемом воды. водохранилище наполняется за счет осадков, а опустошается с помощью шлюзов ГЭС. Также существует населенный пункт, потребляющий электроэнергию. ГЭС может генерировать электричество 2-мя способами: спускать воду из водохранилища или использовать топливные генераторы. Себестоимость электроэнергия, полученная ГЭС за счет спуска воды можно считать нулевой, в то время, как электроэнергия, выработанная за счет топливных генераторов имеет значительную себестоимость.
 +
 +
Считается, что количество энергии, потребляемой населенным пунктом, а также объем осадков - случайные процессы, распределения которых можно получить с помощью исторических данных. Объем водохранилища и себестоимость производства электричества тем или иным способом - известны и фиксированы.
 +
В данных условиях стоит задача минимизировать финансовые потери ГЭС на несколько лет вперед.
 +
 +
2. Управление портфелем ценных бумаг.
 +
 +
Инвестор обладает некоторым стартовым капиталом, который можно инвестировать в заданный набор ценных бумаг. Инвестор формирует финансовый портфель на несколько лет, но внутри данного периода возможны ребалансировки портфеля, проводимые, однако, без вывода и без привлечения дополнительных средств. Прирост цен активов портфеля, а также величина дивидендных выплат - случайны. При этом, транзакционные издержки, начальный капитал инвестора, а также набор возможных активов для вложения - фиксированные величины.
 +
В данных условиях стоит задача минимизировать финансовые потери инвестора.
  
 
== Вычислительное ядро алгоритма==
 
== Вычислительное ядро алгоритма==

Версия 15:41, 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]m_t[/math], [math]t = 1,...,T[/math]

2. Размерность задачи N (размерность управляющего правила)

3. Вероятности переходов [math]p_{nt}; t = 1,...,T; n = 1,...,m_t[/math]

4. матрицы и векторы, характеризующие каждое состояние системы [math] \xi_i^t=(A_i^t, \ B_i^t, \ b_i^t, \ c_i^t) [/math]

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

Считается, что на 1-м этапе задача детерминирована. Здесь присутствует всего одно состояние [math] \xi_1 =(A_1, \ b_1, \ c_1) [/math].

рис.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}^{m_2}p_{1i}^1Q_2(x_1,\xi_i^2) \\subject \ to \\A_1x_1\geqslant b_1 \\x_1 \geqslant 0 \end{matrix}\right.[/math]

где

[math] Q_t(x_{t-1},\xi_i^t) = \left\{\begin{matrix} min \ c_t^ix_t + \sum_{j=1}^{m_{t+1}}p_{ji}^tQ_{t+1}(x_t,\xi_j^{t+1}) \\subject \ to \\A_t^ix_t + B_t^ix_{t-1}\geqslant b_t^i \\x_t \geqslant 0 \end{matrix}\right. t=2,...,T-1 [/math]

...

[math] Q_T(x_{T-1},\xi_i^T) = \left\{\begin{matrix} min \ c_T^ix_T \\subject \ to \\A_T^ix_T + B_T^ix_{T-1}\geqslant b_T^i \\x_t \geqslant 0 \end{matrix}\right. [/math]

Данная постановка задачи позволяет решать задачи стохастического программирования, где в качестве метрики взято мат. ожидание по состояниям системы. Существуют также и другие расширения данного алгоритма, где в качестве метрики взято значение Value at Risk или Expected Shortfall, широко используемые в оценки рисков финансовых потерь.

Существует несколько прикладных задач, для которых используется данный алгоритм:

1. Управление ГЭС

Моделируется следующая ситуация:

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

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

2. Управление портфелем ценных бумаг.

Инвестор обладает некоторым стартовым капиталом, который можно инвестировать в заданный набор ценных бумаг. Инвестор формирует финансовый портфель на несколько лет, но внутри данного периода возможны ребалансировки портфеля, проводимые, однако, без вывода и без привлечения дополнительных средств. Прирост цен активов портфеля, а также величина дивидендных выплат - случайны. При этом, транзакционные издержки, начальный капитал инвестора, а также набор возможных активов для вложения - фиксированные величины. В данных условиях стоит задача минимизировать финансовые потери инвестора.

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

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

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

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

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

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

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

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