ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации

Рассматривается декомпозиция блочных задач выпуклого программирования со связывающими переменными. Исследуются свойства подзадач, полезные при вычислении ε-субградиентов целевых функций по связывающим переменным. Предлагаются некоторые алгоритмы решения рассматриваемой задачи....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2003
Автор:	Лаптин, Ю.П.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2003
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/84858
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 75-82. — Бібліогр.: 7 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-84858
record_format	dspace
spelling	irk-123456789-848582018-03-24T11:28:07Z ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации Лаптин, Ю.П. Рассматривается декомпозиция блочных задач выпуклого программирования со связывающими переменными. Исследуются свойства подзадач, полезные при вычислении ε-субградиентов целевых функций по связывающим переменным. Предлагаются некоторые алгоритмы решения рассматриваемой задачи. Розглядається декомпозиція блочних задач опуклого програмування зі зв’язуючими змінними. Досліджуються властивості підзадач, корисні при обчисленні ε-субградієнтів цільових функцій за зв’язуючими змінними. Пропонуються деякі алгоритми розв’язування задач, які розглядаються. Decomposition of block convex problems with linking variables is discussed. Block functions are defined on restricted sets. We analyze the subproblem properties which are useful for calculaiting ε -subgradient of the object function by linking variables. Some algorithms are proposed for solving such problems. Computational experiment results are discussed. 2003 Article ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 75-82. — Бібліогр.: 7 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/84858 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается декомпозиция блочных задач выпуклого программирования со связывающими переменными. Исследуются свойства подзадач, полезные при вычислении ε-субградиентов целевых функций по связывающим переменным. Предлагаются некоторые алгоритмы решения рассматриваемой задачи.
format	Article
author	Лаптин, Ю.П.
spellingShingle	Лаптин, Ю.П. ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации Теорія оптимальних рішень
author_facet	Лаптин, Ю.П.
author_sort	Лаптин, Ю.П.
title	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации
title_short	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации
title_full	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации
title_fullStr	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации
title_full_unstemmed	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации
title_sort	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2003
url	http://dspace.nbuv.gov.ua/handle/123456789/84858
citation_txt	ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации / Ю.П. Лаптин // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 75-82. — Бібліогр.: 7 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT laptinûp esubgradientyvmetodahdekompoziciipoperemennymdlânekotoryhzadačoptimizacii
first_indexed	2025-07-06T11:58:59Z
last_indexed	2025-07-06T11:58:59Z
_version_	1836898729354854400
fulltext	Теорія оптимальних рішень. 2003, №2 75 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается декомпозиция блочных задач выпуклого про- граммирования со связывающими переменными. Исследуются свой- ства подзадач, полезные при вы- числении ε-субградиентов целевых функций по связывающим пере- менным. Предлагаются некото- рые алгоритмы решения рас- сматриваемой задачи.  Ю.П. Лаптин, 2003 ÓÄÊ 519.8 Þ.Ï. ËÀÏÒÈÍ εεεε-ÑÓÁÃÐÀÄÈÅÍÒÛ Â ÌÅÒÎÄÀÕ ÄÅÊÎÌÏÎÇÈÖÈÈ ÏÎ ÏÅÐÅÌÅÍÍÛÌ ÄËß ÍÅÊÎÒÎÐÛÕ ÇÀÄÀ× ÎÏÒÈÌÈÇÀÖÈÈ При решении оптимизационных задач, воз- никающих в ходе моделирования сложных технических объектов, обычно приходится учитывать их особенности и структуру. Рас- сматриваемые объекты, как правило, состоят из совокупности связанных между собой блоков и подсистем, что отражается в струк- туре оптимизационных моделей [1]. В неко- торых случаях такие модели сводятся к блочным задачам выпуклого программиро- вания со связывающими переменными [2]. Эффективным подходом к решению таких задач в случае линейного программирования является применение схем декомпозиции по переменным. В случае нелинейного про- граммирования использование схем деком- позиции сопряжено с определенными труд- ностями. Преодолению некоторых из них посвящена настоящая работа. 1. Рассматривается блочная задача мате- матического программирования со связы- вающими переменными: ∑ = = Q q q q XyXy xyfXyF 1 0 ,, ),(min),(min (1) ,,...,1,,...,1,0),( QqIixyf q qi q ==≤ (2) где ),( qi q xyf - выпуклые собственные функции (L+Nq) – размерного вектора ),,( q xy L Ey ∈ , q N q Ex ∈ , i = 0,…, Iq , q = 1,…, Q , ),...,( 1 Q xxX = . Ю.П. ЛАПТИН 76 Теорія оптимальних рішень. 2003, № 2 Пусть переменные y зафиксированы, yy = , тогда задача (1), (2) распадается на подзадачи )( yPq следующего вида: { }q qi q Nqq q IixyfExxyf q ,...,1,0),(,:),(min 0 =≤∈ , Qq ,...,1= (3) Обозначим qW множество тех значений вектора y, для которых решение за- дачи )( yPq существует, и определим функцию )( y qΦ : { }     ∉∞+ ∈∈ =Φ ,, ,,)(:),(min )( 0 q qq qq qq Wy WyyDxxyf y (4) где )( yDq - множество всех q x , удовлетворяющих ограничениям задачи )( yP . Используя (4), задачу (1), (2) можно представить в виде следующей (коорди- нирующей): найти         ∈Φ∑ = L Q q q Eyy :)(min 1 , (5) В работе [2] показано, что если задача (1), (2) имеет решение, то Qqy q ,...,1),( =Φ являются собственными выпуклыми функциями, там же опре- делены правила вычисления субградиентов )( yg q Φ функций )( y qΦ . При этом каждая задача (3) должна решаться точно, субградиенты )( yg q Φ выражаются через субградиенты функций ),( xyf i q в оптимальной точке )(* yx q . Для не- дифференцируемых функций эти субградиенты должны выбираться специаль- ным образом. Поскольку для нелинейных задач алгоритмы оптимизации сходят- ся к оптимуму как к предельной точке, возникают значительные трудности в определении субградиентов )( ygΦ и применении схем декомпозиции к нели- нейным блочным задачам со связывающими переменными. В случае недиффе- ренцируемых функций возникают дополнительные трудности, поскольку отсут- ствуют процедуры формирования субдифференциалов функций (в точке может быть вычислен только некоторый субградиент функции). Преодолеть эти труд- ности можно переходя к использованию ε-субградиентов )( yg q Φ функций )( y qΦ . Способам вычисления таких ε-субградиентов посвящена основная часть настоящей работы. Задача (5) является задачей выпуклого программирования, однако непосред- ственное ее использование в вычислительных алгоритмах затруднительно в виду сложности описания подмножеств из EL , на которых функции )(y qΦ принимают конечные значения. В работе [2] для преодоления этих трудностей проводилась регуляризация задачи (5), позволяющая определить функции, аналогичные )( y qΦ , на всем пространстве E L . При этом предполагается, что функции ε-СУБГРАДИЕНТЫ В МЕТОДАХ ДЕКОМПОЗИЦИИ ПО ПЕРЕМЕННЫМ ДЛЯ НЕКОТОРЫХ … Теорія оптимальних рішень . 2003, № 2 77 ),( qi q xyf определены на всем пространстве q N L EE × . После регуляризации для решения задачи (5) могут использоваться известные ε- субградиентные ме- тоды [2 - 5]. 2. В дальнейшем будем рассматривать задачи вида (3), индекс q , если это не вызывает неоднозначности, будем опускать. Обозначим { }IixyfxyD i ,...,1,0),(:),( =≤= . Предполагается, что 1) D – замкнутое множество, i fD domint⊂ , Ii ,...,0= ; 2) множество D непусто и для него выполняется условие Слейтера; 3) в каждой точке области определения функции могут быть вычислены значе- ние и некоторый субградиент этой функции. Задача )( yP определяется соотношением (3), функция )( yΦ - соотношени- ем (4) (индекс q опущен), )( yD - допустимое множество задачи )( yP . Теорема 1. Пусть Iifxy i ,...,0,domint),( =∈ , Wy int∈ , для допустимого множества )( yD задачи )( yP выполняется условие Слейтера, заданы числа Iii ,...,1,0,0 =≥ε , в точке ),( xy вычислены iε - субградиенты ),( i x i y i ggg = функций i f такие, что для некоторых чисел Iiu i ,...,1, = , выполняются условия 0 1 0 =+∑ = I i i xix gug , (6) Iiu i ,...,1,0 =≥ . (7) Тогда 1) ε−≥Φ ),()( 0 xyfy ; 2) если )( yDx ∈ , то ε -субградиент функции Φ(y) в точке y = y может быть вычислен по формуле ,)( 1 0 ∑ = ε Φ += I i i yiy gugyg (8) где .)),(( 1 0 ∑ = −ε+ε=ε I i i ii xyfu (9) Доказательство. Рассмотрим первое утверждение. Используя теорему Куна - Таккера, имеем Ю.П. ЛАПТИН 78 Теорія оптимальних рішень. 2003, № 2 .)),(),((),(),(min ),(),(minmax)( 1 0 00 1 0 0       ε−−++ε−−+≥ ≥       +=Φ ∑ ∑ = = ≥ I i i i x i ix x I i i i xu xxgxyfuxxgxyf xyfuxyfy Откуда, с учетом (6), получаем утверждение теоремы. Докажем второе утверждение Пусть в некоторой точке Wy int∈ для допустимого множества )( yD задачи )( yP выполняется условие Слейтера. Обозначим x(y) – решение задачи )( yP , Iiyui ,...,1,0)( =≥ – значения множителей Лагранжа, таких, что .),(),(minmax),()(),(min ))(,()())(,())(,()( 1 0 0 1 0 1 0 )(       +=       += =+==Φ ∑∑ ∑ = ≥ = = I i i i xu I i i i I i i iyu xyfuxyfxyfyuxyf yxyfyuyxyfyxyLy x Такие множители существует в соответствии с теоремой Куна - Таккера. По условию теоремы в точке y для допустимого множества )( yD условие Слейтера выполняется. Рассмотрим точку Wy' int∈ , достаточно близкую к y , в которой для множества )( yD ′ также выполняется условие Слейтера (такая точка существует в силу непрерывности функций Iixyf i ,...,1),,( = ). Обозначим )( yxx ′=′ . Очевидно, ).,(),()( )( xyLxyLy uyu ′′≥′′=′Φ ′ Поскольку x - допустимая точка задачи )( yP , а )( yΦ - значение целевой функции в опти- мальной точке, то ),()( 0 xyfy ≤Φ . Откуда получаем [ ]≥+−′′+ +−′′=−′′≥Φ−′Φ ∑ = I i iii i u xyfxyfxyfu xyfxyfxyfxyLyy 1 000 ),(),(),( ),(),(),(),()()( [∑ = +ε−−′+−′+ε−−′+−′≥ I i i i y i xiyx gyygxxugyygxx 1 0 00 ),(),(),(),( ] [ ] .),(),(),( 1 0 1 0 ∑∑ == +ε−+ε−+−′=+ I i i ii I i i yiy i xyfugugyyxyf Последнее равенство выполняется в силу (6), т.е. ∑ = ε Φ += I i i yiy gugyg 1 0 )( . Теорема доказана. ε-СУБГРАДИЕНТЫ В МЕТОДАХ ДЕКОМПОЗИЦИИ ПО ПЕРЕМЕННЫМ ДЛЯ НЕКОТОРЫХ … Теорія оптимальних рішень . 2003, № 2 79 Рассмотрим сформулированный результат применительно к задаче линейно- го программирования. Пусть Iibyaxaxyf ii y i x i ,...,0,),( =++= , где i y i x aa , - вектор-строки соответствующих размерностей. Обозначим ,...,...,... 111           =           =           = II y y y I x x x b b b a a A a a A yabybyAbyb yy 000 )(,)( +=+= . Тогда задачу линейного программирования )( yP и двойственную к ней можно представить в виде { }0)(:)(min 00 ≤++ ybxAybxa xx x , (10) { }0,0:)()(max 00 ≥=++ uauAybuyb x T x T u . (11) Очевидно, что в условиях теоремы 1 можно положить Iii ,...,1,0,0 ==ε , а соотношения (6) , (7) есть условия допустимости двойственной задачи (11). Лемма 1. В условиях теоремы 1 для задачи (10) имеет место uybxa T x )(0 −=ε . Доказательство. =+−−=+−=−=ε ∑ = uybxAxaxauybxAxyfu T xxx I i T x i i ))(())((),( 00 1 −xax 0 uyb T)( . Лемма доказана. Сформулированная лемма определяет простое правило остановки при при- ближенном решении задач линейного программирования и вычислении ε - субградиентов функции )( yΦ . При этом должны использоваться алгоритмы решения задач линейного программирования, генерирующие на каждой итера- ции допустимые точки прямой и двойственной задач (см., например, [6]). Близ- кие результаты для задач линейного программирования получены в [5]. В общем случае для вычисления ε -субградиентов функции )( yΦ должны применяться специальные алгоритмы. Результаты, полезные для разработки та- ких алгоритмов, приводятся ниже. Пусть задана совокупность { }mxxx ,...,, 21 точек из N E , )(yDxm ∈ , в каж- дой точке ),( kxy вычислены значения ),( k iik xyff = и субградиенты ),( ik x ik y ik ggg = функций ,,...,0, Iif i = mk ,...,1= . Рассмотрим линейную аппроксимацию задачи (3) при фиксированном yy = , которая может быть представлена в виде: найти ξ ξ, min x (12) при ограничениях Ю.П. ЛАПТИН 80 Теорія оптимальних рішень. 2003, № 2 0,,...,1,),( ==ξ≤−+ imkxxgf k ik x ik , (13) Iimkxxgf k ik x ik ,...,1,,...,1,0),( ==≤−+ , (14) Пусть ikk uu ,0 - двойственные переменные, соответствующие ограничениям (13), (14), Iimk ,...,1,,...,1 == . Двойственная задача записывается следующим образом: найти ( )∑∑ = = − I i m k ikk ik x ik u uxgf 0 1 ),(max , (15) при ограничениях 1 1 0 =∑ = m k ku , (16) 0 0 1 =∑∑ = = I i m k ik xik gu , (17) .,...,1,,...,0,0 mkIiuik ==≥ (18) Обозначим ∗∗ ξmmx , - решение задачи (12)-(14), iku - оптимальные значения двойственных переменных, Iimk ,...,0,,...,1 == . Лемма 2. Пусть для некоторых i, k выполняется 0>iku , тогда ik есть εik g - субградиент функции i f в точке ),( mxy , где    =−+ξ− >−+ =ε ∗∗ ∗ .0),,( ,0),,( 00 ixxgf ixxgf mm k xm m mm ik x im ik (19) Доказательство. Легко видеть, что [ ] .),(),( ),(),( km ik x ik mm ik x im mmkm ik x ikim km ik x ikimik xxgfxxgf xxxxgffxxgff −+−−+= =−+−−−=−−−=ε ∗∗ ∗∗ Поскольку 0>iku , то соответствующее ограничение выполняется как равен- ство в оптимальной точке. Откуда следует утверждение леммы. Лемма доказана. Лемма 3. Пусть 0 1 >=∑ = m k iki uu . Тогда вектор         = ∑ = − m k ik iki i guug 1 1)( есть iε - субградиент функции i f в точке ),( mxy , где         ε=ε ∑ = − m k ik iki i uu 1 1)( , ikε оп- ределено в соответствии с леммой 2. Доказательство. В соответствии с леммой 2 имеем ,),(),( ik m ikimi xxgfxyf ε−−+≥ mk ,...,1= . Умножая неравенства на iku и суммируя по k, получаем утверждение леммы. Теорема 2. ε-СУБГРАДИЕНТЫ В МЕТОДАХ ДЕКОМПОЗИЦИИ ПО ПЕРЕМЕННЫМ ДЛЯ НЕКОТОРЫХ … Теорія оптимальних рішень . 2003, № 2 81 ,)( 1 0 ∑∑ = = ε Φ = m k I i ik yik guyg m (20) ∗ξ−=ε m m m f 0 . (21) Доказательство. Не трудно видеть, что векторы ),( i x i y i ggg = и числа iu , определенные в соответствии с леммой 3, удовлетворяют соотношениям (6), (7). Подставляя соответствующие выражения в (8), (9) и учитывая, что 1 1 0 =∑ = m k ku , получаем ∗∗ = = ∗ ξ−=        −+ξ−=ε ∑∑ m m mm m k I i ik xikm m m fxxguf 0 1 0 0 , . Последнее равен- ство следует из (17). Теорема доказана. Теорема 3 позволяет строить правила остановки в процессах приближенного решения задачи )( yP . Для этого необходимо, чтобы допустимые точки mx ге- нерировались некоторым процессом, сходящимся к решению задачи )( yP , и оптимальные значения линейных аппроксимаций также сходились к оптималь- ному значению задачи )( yP . Сформулированные условия выполняются, если ограничения задачи )( yP линейны, а для решения используется метод Келли [7]. Тогда все генерируемые точки являются допустимыми и оптимальные значения линейных аппроксима- ций сходятся к оптимальному значению задачи )( yP . Однако метод Келли име- ет медленную сходимость и сложный в программной реализации. В случае нелинейных ограничений необходимы дополнительные усилия для формирования допустимых точек и специальным образом построенные линей- ные аппроксимации, обеспечивающие сходимость оптимальных значений. При практическом формировании линейной аппроксимации в задачу (12)- (14) включаются только наиболее существенные ограничения. Правила, которые при этом используются, являются эвристическими, однако позволяют сущест- венно понизить размерность генерируемой задачи. 3. Представленные результаты могут быть полезны при разработке алгорит- мов декомпозиции для решения задач вида (1), (2). Применение таких алгорит- мов наиболее эффективно в случаях, когда исходная задача (1), (2) распадается на подзадачи, большинство из которых имеют специальную структуру и эффек- тивные алгоритмы решения, а подзадач общего вида немного и их размерность невелика. На основе предлагаемого подхода разрабатываются отдельные классы ре- курсивной объектно-ориентированной библиотеки RBL [1], предназначенной для оптимизационного моделирования задач, имеющих сложную структуру. При создании приложений прикладные классы должны порождаться от базовых классов библиотеки RBL. Для подзадач, имеющих специальную структуру, мо- гут разрабатываться соответствующие алгоритмы решения. Ю.П. ЛАПТИН 82 Теорія оптимальних рішень. 2003, № 2 Работа выполнена при финансовой поддержке Украинского научно- технологического центра (грант № 1625). Лаптін Ю.П. ε-СУБГРАДІЄНТИ В МЕТОДАХ ДЕКОМПОЗИЦІЇ ЗА ЗМІННИМИ ДЛЯ ДЕЯКИХ ЗАДАЧ ОПТИМІЗАЦІЇ Розглядається декомпозиція блочних задач опуклого програмування зі зв’язуючими змінними. Досліджуються властивості підзадач, корисні при обчисленні ε-субградієнтів цільових функцій за зв’язуючими змінними. Пропонуються деякі алгоритми розв’язування задач, які розглядаються. Laptin Y.P. ε -SUBGRADIENT IN DECOMPOSITION ALGORITMS ON VARIABLES FOR SOME OPTIMIZATION PROBLEMS Decomposition of block convex problems with linking variables is discussed. Block functions are defined on restricted sets. We analyze the subproblem properties which are useful for calculaiting ε -subgradient of the object function by linking variables. Some algorithms are proposed for solving such problems. Computational experiment results are discussed. 1. Лаптин Ю.П., Журбенко Н.Г. Разработка программных средств оптимизации сложных технических объектов // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М.Глушкова НАН України, 2002. – С. 3 - 12. 2. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – London: Kluwer Aca- demic Publishers, 1998. - 381 p. 3. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. – М.: Наука, 1981. – 384 с. 4. Ржевский С.В. Монотонные методы выпуклого программирования. – Киев: Наук. думка, 1993. – 316 с. 5. Condzio J., Vial J.-P. Warm Start and ε-Subgradients in a Cutting Plane Scheme for Block- Angular Linear Programs // Computational Optimization and Applications. – 1999. – N 14. – P. 17–36. 6. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория, методы и приложения. – М.: Наука, 1969. – 424 с. 7. Kelley J. The cutting plane method for solving convex programs // SIAM J. – 1960.- 8, N 4. - P.703 –712. Получено 17.09.2003

ε-субградиенты в методах декомпозиции по переменным для некоторых задач оптимизации

Репозитарії

Схожі ресурси