Стохастическое двойственное динамическое программирование (SDDP) - История изменений

ASA в 13:42, 20 июля 2022

2022-07-20T13:42:38Z

← Предыдущая версия		Версия от 13:42, 20 июля 2022
Строка 432:		Строка 432:
	</math>		</math>

	= Программная реализация алгоритма =		== Программная реализация алгоритма ==

	=== Особенности реализации последовательного алгоритма ===		=== Особенности реализации последовательного алгоритма ===

ASA в 13:41, 20 июля 2022

2022-07-20T13:41:50Z

← Предыдущая версия		Версия от 13:41, 20 июля 2022
Строка 456:		Строка 456:
	== Литература ==		== Литература ==

	<references \>		<references />

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[en:Stochastic dual dynamic programming (SDDP)]]		[[en:Stochastic dual dynamic programming (SDDP)]]

ASA в 13:40, 20 июля 2022

2022-07-20T13:40:57Z

Внесённые изменения

ASA в 13:37, 20 июля 2022

2022-07-20T13:37:35Z

@@ Строка 437: / Строка 437: @@
 Важной особенностью реализации последовательного алгоритма SDDP является выбор количества пробных сценариев на каждой итерации. С одной стороны, увеличив количество пробных сценариев на каждой итерации, задача быстрее усложняется с вычислительной точки зрения от итерации к итерации. С другой стороны, увеличивается и вероятность нахождения оптимального решения на более ранних итерациях. До сих пор нет единого мнения о том, какое количество пробных сценариев - оптимальное. Авторы первых статей об SDDP применяли всего 1 пробный сценарий на итерацию, аргументировав это тем, что каждое следующее вычисление новой гиперплоскости использует уже все существующие, тем самым повышая скорость сходимости.
 ==Возможные способы и особенности параллельной реализации алгоритма ==
@@ Строка 452: / Строка 446: @@
 Возможно ускорение также при параллельной реализации задач ЛП, однако как показывают реальные опыты, задачи ЛП решаются за незначительное время и не время их выполнения на одном процессоре сопоставимо с обменом данными между несколькими при параллельной реализации.
-==Масштабируемость алгоритма и его реализации ==
+На данный момент существует пакет Fast в Матлабе, который позволяет запускать алгоритм SDDP с математическим ожиданием в качестве метрики на скалярном компьютере.
-Ввиду того, что существуют реализации алгоритма только на языке R и Matlab, которые не установлены ни на Blue gene (установить невозможно), ни на Lomonosov(в процессе установки) Результаты расчетов были проведены лишь для количества задействованных ядер многоядерного домашнего компьютера.
+Также в разработке находится проект, написанный на R, позволяющий использовать в качестве метрики как мат.ожидание, так и VaR, и CVaR. Разрабатывается также параллельный алгоритм вычисления с помощью пакета Rmpi.
 == Выводы для классов архитектур ==
 К сожалению, ввиду того, что не существует универсальных реализаций на низкоуровневых языках программирования, трудно дать какие либо рекомендации касательно того, какие архитектуры лучше подходят для данного алгоритма.
 = Литература =

ASA в 14:23, 14 марта 2018

2018-03-14T14:23:42Z

← Предыдущая версия		Версия от 14:23, 14 марта 2018
Строка 508:		Строка 508:

	<references \>		<references \>

			[[Категория:Статьи в работе]]

			[[en:Stochastic dual dynamic programming (SDDP)]]

Konshin в 14:17, 16 января 2018

2018-01-16T14:17:00Z

← Предыдущая версия		Версия от 14:17, 16 января 2018
Строка 4:		Строка 4:
	\| name = SDDP		\| name = SDDP
	\| serial_complexity = <math>O(\overline{S}^{2T}\cdot(M^3+N^3))</math>		\| serial_complexity = <math>O(\overline{S}^{2T}\cdot(M^3+N^3))</math>
	\| input_data = размерность задачи <math>N</math>, ~~количеством~~ ограничений <math>M</math>, количество этапов <math>T</math>, среднее количество состояний <math>\overline{S}</math>		\| input_data = размерность задачи <math>N</math>, количество ограничений <math>M</math>, количество этапов <math>T</math>, среднее количество состояний <math>\overline{S}</math>
	}}		}}

	= Свойства и структура алгоритма =		= Свойства и структура алгоритма =

	== Общее описание алгоритма==		== Общее описание алгоритма ==

	Стохастическое двойственное динамическое программирование (SDDP) – это метод оптимизации, предназначенный для решения динамических задач в условиях неопределенности, то есть в случае, когда некоторые параметры задачи не являются детерминированными. В силу фундаментальности постановки задачи, данный алгоритм может быть применен в самых различных прикладных областях. Например, на сегодняшний день, стохастическое двойственное динамическое программирование активно используется для управления ГЭС в Норвегии, а также вводится в банках для управления рыночными рисками. На сегодняшний день также широко распространены альтернативные динамические методы поиска решений в условиях неопределенности, например, методы, работающие на принципах построения дерева возможных исходов, или методы, работающие на принципах управляющих правил. Однако, методы, работающие по принципу построения дерева, неизбежно сталкиваются с широко известным «проклятием размерности» (curse of dimensionality), а методы, построенные на принципах управляющих правил, как правило, требуют серьезные ограничения на тип управляющих правил, а также на свойства стохастических параметров задачи. Также, в задачах динамического управления присутствует проблема тайм-консистентности решения (time-consistence solution).		Стохастическое двойственное динамическое программирование (SDDP) – это метод оптимизации, предназначенный для решения динамических задач в условиях неопределенности, то есть в случае, когда некоторые параметры задачи не являются детерминированными. В силу фундаментальности постановки задачи, данный алгоритм может быть применен в самых различных прикладных областях. Например, на сегодняшний день, стохастическое двойственное динамическое программирование активно используется для управления ГЭС в Норвегии, а также вводится в банках для управления рыночными рисками. На сегодняшний день также широко распространены альтернативные динамические методы поиска решений в условиях неопределенности, например, методы, работающие на принципах построения дерева возможных исходов, или методы, работающие на принципах управляющих правил. Однако, методы, работающие по принципу построения дерева, неизбежно сталкиваются с широко известным «проклятием размерности» (curse of dimensionality), а методы, построенные на принципах управляющих правил, как правило, требуют серьезные ограничения на тип управляющих правил, а также на свойства стохастических параметров задачи. Также, в задачах динамического управления присутствует проблема тайм-консистентности решения (time-consistence solution).

	Алгоритм SDDP (Stochastic ~~dual dynamic programming~~) впервые был предложен в 1991 году в статье <ref>M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied		Алгоритм SDDP (Stochastic Dual Dynamic Programming) впервые был предложен в 1991 году в статье <ref>M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied
	to energy planning", Programming 52 (1991) 359-375</ref>. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде <ref>Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", SIAM, 2014</ref>. В настоящее время под аббревиатурой SDDP подразумевается целое семейство алгоритмов.		to energy planning", Programming 52 (1991) 359-375</ref>. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде <ref>Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", SIAM, 2014</ref>. В настоящее время под аббревиатурой SDDP подразумевается целое семейство алгоритмов.

Konshin в 14:15, 16 января 2018

2018-01-16T14:15:54Z

← Предыдущая версия		Версия от 14:15, 16 января 2018
Строка 3:		Строка 3:
	{{algorithm		{{algorithm
	\| name = SDDP		\| name = SDDP
	\| serial_complexity = <math>O(\overline{S}^{2T}*(M^3+N^3))</math>		\| serial_complexity = <math>O(\overline{S}^{2T}\cdot(M^3+N^3))</math>
	\| input_data = размерность задачи <math>N</math>, количеством ограничений <math>M</math>, количество этапов <math>T</math>, среднее количество состояний <math>\overline{S}</math>		\| input_data = размерность задачи <math>N</math>, количеством ограничений <math>M</math>, количество этапов <math>T</math>, среднее количество состояний <math>\overline{S}</math>
	}}		}}

Konshin в 14:15, 16 января 2018

2018-01-16T14:15:13Z

← Предыдущая версия		Версия от 14:15, 16 января 2018
Строка 1:		Строка 1:
	Автор описания: [https://algowiki-project.org/ru/Участник:VladimirDobrovolsky611<b>В.М.Добровольский</b>]		Автор описания: [https://algowiki-project.org/ru/Участник:VladimirDobrovolsky611<b>В.М.Добровольский</b>]

			{{algorithm
			\| name = SDDP
			\| serial_complexity = <math>O(\overline{S}^{2T}*(M^3+N^3))</math>
			\| input_data = размерность задачи <math>N</math>, количеством ограничений <math>M</math>, количество этапов <math>T</math>, среднее количество состояний <math>\overline{S}</math>
			}}

	= Свойства и структура алгоритма =		= Свойства и структура алгоритма =

Konshin: /* Общее описание алгоритма */

2018-01-16T14:03:27Z

Общее описание алгоритма

← Предыдущая версия		Версия от 14:03, 16 января 2018
Строка 7:		Строка 7:
	Стохастическое двойственное динамическое программирование (SDDP) – это метод оптимизации, предназначенный для решения динамических задач в условиях неопределенности, то есть в случае, когда некоторые параметры задачи не являются детерминированными. В силу фундаментальности постановки задачи, данный алгоритм может быть применен в самых различных прикладных областях. Например, на сегодняшний день, стохастическое двойственное динамическое программирование активно используется для управления ГЭС в Норвегии, а также вводится в банках для управления рыночными рисками. На сегодняшний день также широко распространены альтернативные динамические методы поиска решений в условиях неопределенности, например, методы, работающие на принципах построения дерева возможных исходов, или методы, работающие на принципах управляющих правил. Однако, методы, работающие по принципу построения дерева, неизбежно сталкиваются с широко известным «проклятием размерности» (curse of dimensionality), а методы, построенные на принципах управляющих правил, как правило, требуют серьезные ограничения на тип управляющих правил, а также на свойства стохастических параметров задачи. Также, в задачах динамического управления присутствует проблема тайм-консистентности решения (time-consistence solution).		Стохастическое двойственное динамическое программирование (SDDP) – это метод оптимизации, предназначенный для решения динамических задач в условиях неопределенности, то есть в случае, когда некоторые параметры задачи не являются детерминированными. В силу фундаментальности постановки задачи, данный алгоритм может быть применен в самых различных прикладных областях. Например, на сегодняшний день, стохастическое двойственное динамическое программирование активно используется для управления ГЭС в Норвегии, а также вводится в банках для управления рыночными рисками. На сегодняшний день также широко распространены альтернативные динамические методы поиска решений в условиях неопределенности, например, методы, работающие на принципах построения дерева возможных исходов, или методы, работающие на принципах управляющих правил. Однако, методы, работающие по принципу построения дерева, неизбежно сталкиваются с широко известным «проклятием размерности» (curse of dimensionality), а методы, построенные на принципах управляющих правил, как правило, требуют серьезные ограничения на тип управляющих правил, а также на свойства стохастических параметров задачи. Также, в задачах динамического управления присутствует проблема тайм-консистентности решения (time-consistence solution).

	Алгоритм SDDP (Stochastic dual dynamic programming) впервые был предложен в статье <ref>M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied		Алгоритм SDDP (Stochastic dual dynamic programming) впервые был предложен в 1991 году в статье <ref>M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied
	to energy planning", Programming 52 (1991) 359-375</ref>. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде <ref>Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", SIAM, 2014</ref>. В настоящее время под аббревиатурой SDDP подразумевается целое семейство алгоритмов.		to energy planning", Programming 52 (1991) 359-375</ref>. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде <ref>Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", SIAM, 2014</ref>. В настоящее время под аббревиатурой SDDP подразумевается целое семейство алгоритмов.

Konshin: /* Общее описание алгоритма */

2018-01-16T14:02:43Z

Общее описание алгоритма

← Предыдущая версия		Версия от 14:02, 16 января 2018
Строка 8:		Строка 8:

	Алгоритм SDDP (Stochastic dual dynamic programming) впервые был предложен в статье <ref>M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied		Алгоритм SDDP (Stochastic dual dynamic programming) впервые был предложен в статье <ref>M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied
	to energy planning", Programming 52 (1991) 359-375</ref>. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде <ref>Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory, SIAM, 2014"</ref>. В настоящее время под аббревиатурой SDDP подразумевается целое семейство алгоритмов.		to energy planning", Programming 52 (1991) 359-375</ref>. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде <ref>Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", SIAM, 2014</ref>. В настоящее время под аббревиатурой SDDP подразумевается целое семейство алгоритмов.

	== Математическое описание алгоритма ==		== Математическое описание алгоритма ==