Ускорение сходимости метода декомпозиции "Progressive Hedging’’

Ускорение сходимости метода декомпозиции "Progressive Hedging’’

Показано як метод розв'язку багатоетапних задач стохастичного програмування «Progressive Hedging» пов'язаний із методом декомпозиції по змінним першого рівня за допомогою множників Лагранжа на прикладі двоетапної задачі. Обговорюються питання регулювання швидкості збіжності методу та відно...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2018
Hauptverfasser: Бойко, В.В., Кузьменко, В.Н.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Schriftenreihe:Теорія оптимальних рішень
Schlagworte:
Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня.
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/144975
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Ускорение сходимости метода декомпозиции "Progressive Hedging’’ / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 79-84. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-144975
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-1449752025-02-09T16:02:10Z Ускорение сходимости метода декомпозиции "Progressive Hedging’’ Прискорення збіжності методу декомпозиції «Progressive Hedging» Increasing convergence rate of «Progressive Hedging» decomposition algorithm Бойко, В.В. Кузьменко, В.Н. Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня. Показано як метод розв'язку багатоетапних задач стохастичного програмування «Progressive Hedging» пов'язаний із методом декомпозиції по змінним першого рівня за допомогою множників Лагранжа на прикладі двоетапної задачі. Обговорюються питання регулювання швидкості збіжності методу та відновлення змінних першого рівня. It is shown relation between «Progressive Hedging» method for solving multistage stochastic optimization problems and decomposition method using Lagrangе multipliers in case of Two Stage stochastic problem. Adjusting of convergence rate and restoring of first stage variables are discussed. 2018 Article Ускорение сходимости метода декомпозиции "Progressive Hedging’’ / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 79-84. — Бібліогр.: 6 назв. — рос. 2616-5619 https://nasplib.isofts.kiev.ua/handle/123456789/144975 519.85 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня.
Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня.
spellingShingle Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня.
Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня.
Бойко, В.В.
Кузьменко, В.Н.
Ускорение сходимости метода декомпозиции "Progressive Hedging’’
Теорія оптимальних рішень
description Показано як метод розв'язку багатоетапних задач стохастичного програмування «Progressive Hedging» пов'язаний із методом декомпозиції по змінним першого рівня за допомогою множників Лагранжа на прикладі двоетапної задачі. Обговорюються питання регулювання швидкості збіжності методу та відновлення змінних першого рівня.
format Article
author Бойко, В.В.
Кузьменко, В.Н.
author_facet Бойко, В.В.
Кузьменко, В.Н.
author_sort Бойко, В.В.
title Ускорение сходимости метода декомпозиции "Progressive Hedging’’
title_short Ускорение сходимости метода декомпозиции "Progressive Hedging’’
title_full Ускорение сходимости метода декомпозиции "Progressive Hedging’’
title_fullStr Ускорение сходимости метода декомпозиции "Progressive Hedging’’
title_full_unstemmed Ускорение сходимости метода декомпозиции "Progressive Hedging’’
title_sort ускорение сходимости метода декомпозиции "progressive hedging’’
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2018
topic_facet Показано как метод решения многоэтапных задач стохастического программирования «Progressive Hedging» связан с методом декомпозиции по переменным первого уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулирования скорости сходимости метода и восстановления значений переменных первого уровня.
url https://nasplib.isofts.kiev.ua/handle/123456789/144975
citation_txt Ускорение сходимости метода декомпозиции "Progressive Hedging’’ / В.В. Бойко, В.Н. Кузьменко // Теорія оптимальних рішень: Зб. наук. пр. — 2018. — № 17. — С. 79-84. — Бібліогр.: 6 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT bojkovv uskorenieshodimostimetodadekompoziciiprogressivehedging
AT kuzʹmenkovn uskorenieshodimostimetodadekompoziciiprogressivehedging
AT bojkovv priskorennâzbížnostímetodudekompozicííprogressivehedging
AT kuzʹmenkovn priskorennâzbížnostímetodudekompozicííprogressivehedging
AT bojkovv increasingconvergencerateofprogressivehedgingdecompositionalgorithm
AT kuzʹmenkovn increasingconvergencerateofprogressivehedgingdecompositionalgorithm
first_indexed 2025-11-27T18:45:20Z
last_indexed 2025-11-27T18:45:20Z
_version_ 1849970262135537664
fulltext ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 79 ТЕОРІЯ ОПТИМАЛЬНИХ РІШЕНЬ Показано как метод решения мно- гоэтапных задач стохастическо- го программирования «Progressive Hedging» связан с методом де- композиции по переменным перво- го уровня с помощью множителей Лагранжа для двухэтапных задач. Обсуждаются вопросы регулиро- вания скорости сходимости ме- тода и восстановления значений переменных первого уровня.  В.В. Бойко, В.Н. Кузьменко, 2018 УДК 519.85 В.В. БОЙКО, В.Н. КУЗЬМЕНКО УСКОРЕНИЕ СХОДИМОСТИ МЕТОДА ДЕКОМПОЗИЦИИ «PROGRESSIVE HEDGING» Введение. В работе [1] предложен метод (называемый «Progressive hedging» (PH) ал- горитм) для решения многоэтапных задач стохастического программирования. Алго- ритм основан на рассмотрении случайных событий на всех этапах (уровнях) в едином пространстве и на декомпозиции исходной задачи на каждом уровне по связывающим переменным верхних уровней. PH алгоритм применяется не только для решения задач с непрерывными переменны- ми, но и для решения стохастических зада- чах с целочисленными переменными [2]. Несмотря на то, что сходимость алгоритма в выпуклом случае доказана, регулирование процесса сходимости осуществляется одним параметром. Этот параметр одновременно регулирует изменение и прямых, и двой- ственных переменных, должен обеспечить согласованность этих изменений и влияет на скорость сходимости в целом. При наличии дискретных переменных ал- горитм применяется как эвристика, поскольку вопрос сходимости здесь в общем не решен. Но и в непрерывном, и в дискретном случае вопросу выбора и изменения регули- рующего параметра уделяется достаточное внимание. Покажем как этот метод связан с другими методами декомпозиции, например, рас- сматриваемыми в работах Н.З. Шора [3], Н.Г. Журбенко [4], и как идеи, использован- ные в этих работах, можно использовать для ускорения сходимости PH алгоритма. В.В. БОЙКО, В.Н. КУЗЬМЕНКО 80 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 Рассмотрим двухэтапную задачу стохастического программирования, кото- рая может представлена в такой форме: min ( ) min [ ( , )] x X x X F x E Q x       , (1) где nX R ; [ ]E  – знак математического ожидания; ( , )Q x  целевая функция оптимального решения задачи второго этапа, условия которой зависят вектор x и случайной величины  , а именно: ( , ) ( , ) min ( , , ) y Y x Q x f x y      . (2) Предполагается, что функция ( , , )f x y  выпукла по переменным nx R и my R одновременно при любом фиксированном значении  . Далее будем рассматривать случайную величину с конечным дискретным распределением  1,..., r   и ненулевыми вероятностями 1,..., rp p . Реа- лизации такой случайной величины будем называть сценариями. В этом случае задачи (1) и (2) можно переписать так 1 min ( ) min ( ) r s ssx X x X F x p Q x     , где ( ) ( ) min ( , ) s s s y Y x Q x f x y   . (3) Для декомпозиции задачи введем дубли переменных первого этапа sx для каждого сценария, которые свяжем условием sx x . Получаем задачу   1 1,..., , min ( ) min ( ) | , r r s s s ssx X x x X x F x p Q x x x s      , (4) в которой переменные x можно не ограничивать множеством X . Поскольку эти переменные формально не используются в подзадачах, то можно избавиться от них, положив, например, rx x . В результате вместо блочной задачи (3) со связывающими переменными x получаем блочную задачу, с 1r  системами связывающих ограничений s rx x , а именно:   1 1,..., min ( ) min ( ) | , 1,..., 1 r r s s s s rsx X x x X F x p Q x x x s r       . (5) Для дальнейшей декомпозиции применим Лагранжеву релаксацию по связывающим ограничениям. Для этого введем вектора-строки s множителей Лагранжа для каждого блока и запишем такую минимаксную задачу:    11 1 1 1,...,,..., max min ( ) ( ) ( ) rr r s s s s s r r r rsx x X p Q x x x p Q x                 . (6) УСКОРЕНИЕ СХОДИМОСТИ МЕТОДА ДЕКОМПОЗИЦИИ «PROGRESSIVE HEDGING» ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 81 Задача минимизации в (6) разбивается на блоки  min ( ) ) , 1,..., 1 s s s s s s x X p Q x x s r      и  1 1 min ( ) r r r r r r ssx X p Q x x     . Чтобы сделать вид блоков одинаковым введем вектор множителей для бло- ка ,r положив 1 1 r r ss       . Отсюда следует условие 1 0 r ss   . Множители Лагранжа дальше будем называть двойственными переменными. Введем масштабирующие множители sb и сделаем замену двойственных переменных s s sb   . Тогда задача представима в виде 1 1,..., ( ) max ( ) r r s ss b         , (7) 1 0 r s ss b    , (8) , ( ) ( ) min ( , ) , 1,..., s s s s s s s s s s x X y Y x s p f x y x s r b            , (9) где 1( ,...,  ) nr r R     – вектор в объединенном пространстве двойственных переменных. Теперь опишем PH метод, так как он основан на предложенной декомпози- ции, но сначала укажем на достоинства и недостатки такой декомпозиции. Основное достоинство то, что если исходная задача (1) имеет решение, то все подзадачи минимизации (9) также имеют решения, независимо от значений двойственных переменных. Это важное свойство, так как при фиксированном векторе x в (2) множество ( , )Y x  может оказаться пустым, что требует специ- ального алгоритма формирования результата решения подзадачи. Такой резуль- тат должен быть согласован с алгоритмом решения задачи первого уровня, а это не всегда может оказаться простым [5]. Основной недостаток этой декомпози- ции – это значительное увеличение размерности задачи – количество перемен- ных увеличивается в 2r раза. Однако, при этом процесс решения легко распа- раллеливается, что дает возможность не рассматривать пропорционального уве- личения времени решения задачи. Задача максимизации (7) – (9) может решаться различными методами. При этом важным является вопрос ограничено или нет множество X ? Конкретизация метода зависит также от свойств подзадач (9). Если эти подзадачи линейны или В.В. БОЙКО, В.Н. КУЗЬМЕНКО 82 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 имеют неоднозначное оптимальное решение, то после получения оптимальных значений s возникает проблема восстановления оптимальных значений пере- менных sx и sy . В работах [3, 4] предлагаются разные варианты восстановле- ния этих переменных, так в [3] предлагается введение в подзадачи квадратичной регуляризирующей добавки. Рассмотрим далее детали PH алгоритма, связанные с решением задачи (7) – (9). А это четыре основных момента: выбор направления движения на ите- рации; сохранение ограничений (8); выбор квадратичной добавки для (9); выбор шага. Рассмотрим выбор направления и сохранения ограничений (8). Пусть в текущей точке 1( ,...,  )r    выполнено условие (8). Пусть есть некоторое направление nrd R изменения вектора двойственных переменных, которое может нарушать условие (8). Чтобы этого избежать введем коррекцию d направления ,d такую, чтобы ограничения (8) оставались выполненными. Вектора , ,d d как и вектор , разбиваются на вектора меньшей размерности, соответствующие блокам. Тогда условие для коррекции может быть записано как 1 ( ) 0 r s s ss b d d     или 1 1 r r s s s ss s b d b d      . Заметим, что такое усло- вие не определяет коррекцию однозначно. Она должна быть такой, чтобы обес- печить возрастание целевой функции или хотя бы приближение к максимуму при движении в скорректированном направлении. Рассмотрим такой вариант коррекции s sd b c  , где c – вектор размерности n . Тогда 2 1 1 r r s s ss s b d b c     и 2 1 1 r r s s ss s c b d b     . Такой вектор c делает коррекцию d вектором про- ектирования на подпространство, задаваемое (8), что непосредственно проверя- ется тем, что выполняется условие проектирования ( ) 0Td d d    (здесь T знак транспонирования, так как вектора , , ,d d c  – это строки. Таким образом, проекция произвольного направления d на подпростран- ство (8) задается так: 2 1 1 r r s sd b b d b       , 1,..., s r . Если в качестве d выбран градиент * * 1 1( ) ( ,..., )Tr rb x b x   , где * * 1 ,..., rx x вектора оптимальных значений sx блоков, то проекция получается такой: * 2 * 2 1 1 r rT T s s sb x b b x b       . Если 1sb  , 1,..., s r , имеем * * 1 rT T sx x r  , т. е. от * sx отнимается среднее *x . Для 1s sb p r  , 1,..., s r , получаем такое УСКОРЕНИЕ СХОДИМОСТИ МЕТОДА ДЕКОМПОЗИЦИИ «PROGRESSIVE HEDGING» ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 83 же направление  * *[ ] T sx E x r , где *[ ]E x математическое ожидание случай- ной величины *,x имеющей сценарии * sx . Если в качестве d выбрать вектор * * 1( ,..., )Trx x , а в качестве sb вероятности, то проекция выглядит так: * * 2 1 [ ] rT T s s s sd d x p E x p      . Если все вероят- ности равны, то снова получаем * *[ ]T T s s sd d x E x    . PH алгоритм предлагает использовать направление изменения двойствен- ных переменных * *( [ ]) ,T sx E x а множители sb полагают равными sp . Это на- правление, не совпадает с проекцией градиента, если вероятности не равны, тем не менее сохраняет условие (8) и имеет положительное скалярное произведение с градиентом, что непосредственно проверяется * * * * 1 1 1 ( [ ]) [ ] 0 T Tr r rT s s s s ss s s p x E x p x E x p          , (10) * * * *2 * 2 1 ( ) ( ) ( [ ]) [ ] [ ] 0 r T s s ss d d x E x p x E x E x           . (11) Равенство в (11) достигается только, если все * sx равны между собой. Работа PH алгоритма начинается из точки 0  , значения s sb p , 1,...,s r . Итерация k состоит в следующем. При заданных *k sx решить подза- дачи (9) с регуляризирующей добавкой и найти * 1k sx  2 * 1 * , ( ) argmin ( , ) [ ] , 1,..., 2 s k k k s s s x X y Y x x f x y x x E x s r             , (12) изменить двойственные переменные 1 * 1 * 1( [ ])k k k k T s s sx E x        , где  неко- торый коэффициент, который вначале полагается равным 1 и может регулиро- ваться. Алгоритм оканчивает работу, когда среднее изменение s становится небольшим. Тестовые расчеты показали, что PH алгоритм в описанном варианте имеет медленную скорость сходимости, а регулирование множителя  является ско- рее искусством, зависящим от задачи, чем правилом. Поскольку алгоритм проектирования на подпространство ограничений (8) прост, то задачу (7) – (9) по двойственным переменным можно решать любым методом безусловной оптимизации, например, PNK-методом [6], заменив гради- ент на его проекцию. Если точка минимума в задаче (9) определяется однознач- но при любом s и множество решений ограничено, то регуляризирующая до- В.В. БОЙКО, В.Н. КУЗЬМЕНКО 84 ISSN 2616-5619. Теорія оптимальних рішень. 2018, № 17 бавка может не применяться. В противном случае такая добавка может быть применена с небольшим весовым коэффициентом  к 2 x так, как это описано в [3], либо к 2 *[ ]kx E x так, как это описано в [6]. Вычислительные эксперименты показали, что использование других алго- ритмов решения задачи максимизации и других способов регуляризации позво- ляют существенно ускорить сходимость рассмотренного метода декомпозиции. В.В. Бойко, В.М. Кузьменко ПРИСКОРЕННЯ ЗБІЖНОСТІ МЕТОДУ ДЕКОМПОЗИЦІЇ «PROGRESSIVE HEDGING» Показано як метод розв'язку багатоетапних задач стохастичного програмування «Progressive Hedging» пов'язаний із методом декомпозиції по змінним першого рівня за допомогою множ- ників Лагранжа на прикладі двоетапної задачі. Обговорюються питання регулювання швид- кості збіжності методу та відновлення змінних першого рівня. V.V. Boyko, V.M. Kuzmenko INCREASING CONVERGENCE RATE OF «PROGRESSIVE HEDGING» DECOMPOSITION ALGORITHM It is shown relation between «Progressive Hedging» method for solving multistage stochastic opti- mization problems and decomposition method using Lagrangе multipliers in case of Two Stage sto- chastic problem. Adjusting of convergence rate and restoring of first stage variables are discussed. Список литературы 1. Rockafellar R.T., Wets R.J-B. Scenarios and policy aggregation in optimization under uncertainty. Mathematics of Operations Research. 16. 1991. P. 119 – 147. 2. Watson J.P., Woodruff D.L. Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Computational Management Science. 8. 2010. P. 355 – 370. 3. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно- транспортного планирования. М.: Наука, 1986. 264 с. 4. Беляева Л.В., Журбенко Н.Г., Шор Н.З. О методе решения одного класса динамических распределительных задач. Экономика и математические методы. 1978. Т. 14, Вып. 1. С. 137 – 146. 5. Лаптин Ю.П. Точные штрафные функции и выпуклые продолжения функций в схемах декомпозиции по переменным. Кибернетика и системный анализ. 2016. Т. 52, № 1. С. 93 – 104. 6. Кузьменко В.Н., Бойко В.В. Использование PNK-метода для решения невыпуклых задач оптимизации. Теорія оптимальних рішень. К.: Ін-т кібернетики імені В.М. Глушкова НАН України. 2012. С. 47 – 52. Получено 13.04.2018

Ähnliche Einträge