Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах

The approach for improvement of dual lagrangian bounds in quadratic optimization problems with binary (±1) and boolean (0 −1) variables is considered. It is based on use of families superfluous constraints in form of equality, which for these problems can be constructed as a result of introduction n...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Теорія оптимальних рішень
Datum:	2006
Hauptverfasser:	Стецюк, П.И., Пардалос, П.М.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2006
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/84966
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:	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах / П.И. Стецюк, П.М. Пардалос // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 145-153. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-84966
record_format	dspace
spelling	Стецюк, П.И. Пардалос, П.М. 2015-07-17T17:13:13Z 2015-07-17T17:13:13Z 2006 Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах / П.И. Стецюк, П.М. Пардалос // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 145-153. — Бібліогр.: 4 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84966 519.8 The approach for improvement of dual lagrangian bounds in quadratic optimization problems with binary (±1) and boolean (0 −1) variables is considered. It is based on use of families superfluous constraints in form of equality, which for these problems can be constructed as a result of introduction new variable in the form of products already existing variable. Is shown, that the introduction of these constraints improves accuracy of lagrangian dual bounds problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах On improving of lagrangian dual bounds in binary and boolean quadratic problems Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах
spellingShingle	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах Стецюк, П.И. Пардалос, П.М.
title_short	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах
title_full	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах
title_fullStr	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах
title_full_unstemmed	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах
title_sort	об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах
author	Стецюк, П.И. Пардалос, П.М.
author_facet	Стецюк, П.И. Пардалос, П.М.
publishDate	2006
language	Russian
container_title	Теорія оптимальних рішень
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	On improving of lagrangian dual bounds in binary and boolean quadratic problems
description	The approach for improvement of dual lagrangian bounds in quadratic optimization problems with binary (±1) and boolean (0 −1) variables is considered. It is based on use of families superfluous constraints in form of equality, which for these problems can be constructed as a result of introduction new variable in the form of products already existing variable. Is shown, that the introduction of these constraints improves accuracy of lagrangian dual bounds problem.
issn	XXXX-0013
url	https://nasplib.isofts.kiev.ua/handle/123456789/84966
citation_txt	Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах / П.И. Стецюк, П.М. Пардалос // Теорія оптимальних рішень: Зб. наук. пр. — 2006. — № 5. — С. 145-153. — Бібліогр.: 4 назв. — рос.
work_keys_str_mv	AT stecûkpi obutočneniilagranževyhdvoistvennyhocenokvbinarnyhibulevyhkvadratičnyhzadačah AT pardalospm obutočneniilagranževyhdvoistvennyhocenokvbinarnyhibulevyhkvadratičnyhzadačah AT stecûkpi onimprovingoflagrangiandualboundsinbinaryandbooleanquadraticproblems AT pardalospm onimprovingoflagrangiandualboundsinbinaryandbooleanquadraticproblems
first_indexed	2025-11-25T23:26:45Z
last_indexed	2025-11-25T23:26:45Z
_version_	1850578085339987968
fulltext	145 Теорія оптимальних рішень. 2006, № 5 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассмотрен подход для улучшения лагранжевых двойственных оце- нок в квадратичных оптимизаци- онных задачах с бинарными )1(± и булевыми )10( − переменными. Он базируется на использовании семейств функционально избы- точных квадратичных ограниче- ний-равенств, которые для этих задач можно построить при вве- дении новых переменных в форме произведений уже существующих переменных. Показано, что введе- ние этих ограничений улучшает точность лагранжевых двойст- венных оценок.  П.И. Стецюк, П.М. Пардалос, 2006 ÓÄÊ 519.8 Ï.È. ÑÒÅÖÞÊ, Ï.Ì. ÏÀÐÄÀËÎÑ ÎÁ ÓÒÎ×ÍÅÍÈÈ ËÀÃÐÀÍÆÅÂÛÕ ÄÂÎÉÑÒÂÅÍÍÛÕ ÎÖÅÍÎÊ Â ÁÈÍÀÐÍÛÕ È ÁÓËÅÂÛÕ ÊÂÀÄÐÀÒÈ×ÍÛÕ ÇÀÄÀ×ÀÕ Многие из NP-трудных экстремальных задач на графах (максимальное устойчивое множе- ство вершин графа, максимальный разрез графа, оптимальная бисекция графа, макси- мальная клика графа и ряд других) формули- руются с помощью оптимизационных квад- ратичных задач на максимум, используя ли- бо бинарные )1(± , либо булевые )10( − пе- ременные. Верхнюю оценку для глобального максимума целевой функции в этих задачах позволяет находить разработанная Н.З. Шо- ром техника нахождения оптимальных ла- гранжевых двойственных оценок [1, 2], ко- торая базируется на решении задачи мини- мизации выпуклой недифференцируемой функции, определенной на параметрическом семействе неотрицательно определенных симметричных матриц. Для уточнения лагранжевых двойственных верхних оценок очень важную роль играют функционально избыточные ограничения [1,2], которые являются нетривиальными следствиями из уже имеющихся ограниче- ний, но в то же время не являются линейны- ми комбинациями уже существующих огра- ничений. Такие ограничения не изменяют оптимального значения исходной квадратич- ной задачи. Но их добавление к исходной квадратичной задаче приводит к новой функции Лагранжа и может оказаться, что новая лагранжева двойственная оценка – бо- лее точная верхняя оценка, чем лагранжева двойственная оценка, которая соответствует исходной задаче. П.И. СТЕЦЮК, П.М. ПАРДАЛОС 146 Теорія оптимальних рішень. 2006, № 5 Строить функционально избыточные ограничения можно по разному. Так, например, в [1–3] для экстремальных задач на графах (максимальное устойчи- вое множество вершин графа, максимальный разрез графа и др.) исследованы различные семейства функционально избыточных квадратичных ограничений. Большинство из них ориентированы на учет специфических особенностей каж- дой конкретной задачи для того или иного семейства графов. Оказывается, этого неудобства можно избежать, используя простой прием "расширения" множества бинарных (булевых) переменных. Он дает возможность генерировать функцио- нально избыточные квадратичные ограничения-равенства, не обращая внимая на специфику задачи, для которой была сформулирована оптимизационная квадратичная модель. Такой "автомат" для генерации функционально-избыточных ограничений в бинарных и булевых квадратичных задачах обсудим в данной работе. Сделаем это на примере простейших квадратичных задач, которые связаны с максимиза- цией квадратичной функции от n бинарных переменных nyy ,,1 K , каждая из которых может принимать значение либо +1, либо –1, либо n булевых перемен- ных nxx ,,1 K , каждая из которых может принимать значение либо 0, либо 1. Заметим, что ничего не изменится, если рассмотреть квадратичную задачу от бинарных (булевых) переменных в общем виде, т.е. при наличии квадратичных ограничений равенств или неравенств. 1. Простейшие бинарная и булевая квадратичные задачи. Простейшую бинарную квадратичную задачу рассмотрим в следующей формулировке:         ++=== ∑∑∑ = − = > 00 1 0 1 1 )(max)( qyqyyqyQyQQ n i ii n i n ij jiijy (1) при ограничениях 12 =iy , ni ,,1 K= , (2) а простейшую булевую квадратичную задачу – в формулировке:         ++=== ∑∑∑ = − = > 00 1 0 1 1 )(max)( qxqxxqxQxQQ n i ii n i n ij jiijx (1') при ограничениях 02 =− ii xx , ni ,,1 K= . (2') Пусть * yΨ и * xΨ – наилучшие лагранжевые двойственные оценки, соответ- ствующие задачам (1)–(2) и (1')–(2'). Их можно найти с помощью решения зада- чи минимизации выпуклой недифференцируемой функции, определенной на па- раметрическом семействе неотрицательно определенных симметричных матриц [1]. Здесь не будем обсуждать алгоритмы нахождения оценок * yΨ и * xΨ , а отме- ОБ УТОЧНЕНИИ ЛАГРАНЖЕВЫХ ДВОЙСТВЕННЫХ ОЦЕНОК… Теорія оптимальних рішень. 2006, № 5 147 тим лишь, что эти оценки служат оценками сверху для глобального максимума * yQ и * xQ , т.е. yy Q≥Ψ и xx Q≥Ψ . Оценки * yΨ и * xΨ не всегда есть достаточно хорошими верхними оценками для * yQ и * xQ . Так, например, для функций от двух переменных имеем 2121)( yyyyyQ −−−= ⇒ 1* =yQ , 5.1* =Ψy , 2121 2)( yyyyyQ −−−= ⇒ 2* =yQ , 25.2* =Ψy , 2121 232)( xxxxyQ ++−= ⇒ 3* =xQ , 125.3* =Ψx , 2121)( xxxxyQ ++−= ⇒ 1* =xQ , 125.1* =Ψx , и, следовательно, для всех указанных примеров они являются неточными. Более того, в первом примере имеем наихудшую относительную точность оценки * yΨ , которая составляет 50%. Поэтому оценки * yΨ и * xΨ нуждаются в уточнении. Сделать это можно за счет использования функционально избыточных ограничений. Далее рассмот- рим получение новых более точных верхних оценок, чем оценки * yΨ и * xΨ . Но- вые оценки получены благодаря использованию фунционально избыточных ог- раничений, которые можно построить, если для задач (1)–(2) и (1')–(2') опреде- ленным образом расширить множество бинарных и булевых переменных. 2. Расширенные бинарная и булевая квадратичные задачи. Для задачи (1)–(2) множество бинарных переменных расширим введением новых бинарных переменных jiij yyy = для всех njiji ≤<≤1:, . В результате получим "расши- ренную" формулировку квадратичной задачи (1)–(2):         ++=== ∑∑∑ = − = > 00 1 0 1 1 )(max)( qyqyyqyQyQQ n i ii n i n ij jiijy (3) при ограничениях 12 =iy , ni ,,1 K= , (4)     = = ,1 , 2 ij jiij y yyy njiji ≤<≤∀ 1:, . (5) Множество булевых переменных для задачи (1')–(2') расширим за счет введения новых булевых переменных jiij xxx = для всех njiji ≤<≤1:, . В результате получим "расширенную" формулировку булевой квадратичной задачи (1')–(2'): П.И. СТЕЦЮК, П.М. ПАРДАЛОС 148 Теорія оптимальних рішень. 2006, № 5         ++=== ∑∑∑ = − = > 00 1 0 1 1 )(max)( qxqxxqxQxQQ n i ii n i n ij jiijx (3') при ограничениях 02 =− ii xx , ni ,,1 K= . (4')     =− = ,0 , 2 ijij jiij xx xxx njiji ≤<≤∀ 1:, . (5') Справедлива следующая теорема. Теорема 1. Расширенным квадратичным задачам (3)–(5) и (3')–(5') соответ- ствуют точно такие же наилучшие лагранжевые двойственные оценки как и квадратичным задачам (1)–(2) и (1')–(2'), т.е. (i) лагранжева двойственная оценка для задачи (3)–(5) равна * yΨ , (ii) лагранжева двойственная оценка для задачи (3')–(5') равна * xΨ . Итак, расширение множества переменных не дает никаких улучшений ла- гранжевых двойственных оценок. Зато "расширенные" формулировки квадра- тичных задач позволяют описывать семейства функционально избыточных ог- раничений в форме квадратичных ограничений-равенств [4], добавление кото- рых к задачам (3)–(5) и (3')–(5') может способствовать уточнению лагранжевых двойственных оценок. Содержательный смысл этих семейств ограничений со- стоит в отражении различных видов "избыточных" квадратичных зависимостей между новыми переменными ijy и старыми переменными iy для бинарной квадратичной задачи, и между новыми переменными ijx и старыми переменны- ми ix для булевой квадратичной задачи. 3. Семейства функционально избыточных ограничений для расширен- ных бинарной и булевой задач. Для бинарных переменных имеем следующие семейства функционально избыточных ограничений. Для каждой двойки бинарных переменных iy , jy имеем два ограничения 0=− iiji yyy , 0=− jijj yyy , (6) которые являются следствием очевидных равенств jijjjijii yyyyyyyy === )(2 , iijijiijj yyyyyyyy === )(2 и справедливы при любых i и j , таких, что nji ≤<≤1 . Для каждой тройки бинарных переменных iy , jy и ky имеем пять функ- ционально избыточных ограничений. Первые три из них такие 0=− jkikij yyy , 0=− jkijik yyy , 0=− ikijjk yyy (7) ОБ УТОЧНЕНИИ ЛАГРАНЖЕВЫХ ДВОЙСТВЕННЫХ ОЦЕНОК… Теорія оптимальних рішень. 2006, № 5 149 и являются следствием очевидных равенств jkikkjkikjijiij yyyyyyyyyyyy ==== ))((2 , jkijkjjijkikiik yyyyyyyyyyyy ==== ))((2 , ikijkijiikjkjjk yyyyyyyyyyyy ==== ))((2 , которые, учитывая (2), справедливы при любых индексах i , j и k . Три ограни- чения (7) дополняются двумя ограничениями: 0=− jikkij yyyy , 0=− ijkkij yyyy , (8) которые следуют из неоднозначности представления произведения kji yyy , т.е. ijkikjjikjkikijkjikji yyyyyyyyyyyyyyyyyy ====== )()()( . Заметим, что из неоднозначного представления kji yyy следует три ограниче- ния. Но одно из них – линейно зависимо от двух оставшихся ограничений, и не будет влиять на точность лагранжевой двойственной оценки. Для каждой четверки бинарных переменных iy , jy , ky и ly имеем два ог- раничения: 0=− jlikklij yyyy , 0=− jkilklij yyyy , (9) которые линейно независимы и следуют из неоднозначности представления произведения всех четырех переменных jkiljlikklijlkji yyyyyyyyyy === . По аналогичной схеме для булевых переменных имеем следующие семейст- ва функционально избыточных ограничений. Для каждой двойки булевых переменных ix , jx имеем два ограничения: 0=− ijiij xxx , 0=− ijjij xxx , (6') которые являются следствием равенств: 0)()(0 22 =−=−=−=−= ijijijijiijiiii xxxxxxxxxxxxx , 0)()(0 22 =−=−=−=−= ijijjjijijijjjj xxxxxxxxxxxxx , и справедливы при любых i и j , таких что nji ≤<≤1 . Для каждой тройки булевых переменных ix , jx и kx имеем пять ограниче- ний. Первые три ограничения: 0=− jkiikij xxxx , 0=− ikjjkij xxxx , 0=− ijkjkik xxxjx , (7') являются следствием таких очевидных равенств: 0)())(()(0 2 =−=−=−= jkiikijkjikijikjii xxxxxxxxxxxxxxx , 0)())(()(0 2 =−=−=−= ikjjkijkijkjjikijj xxxxxxxxxxxxxxx , 0)())(()(0 2 =−=−=−= ijkjkikjikkjkijikk xxxxxxxxxxxxxxx , П.И. СТЕЦЮК, П.М. ПАРДАЛОС 150 Теорія оптимальних рішень. 2006, № 5 которые, учитывая (2'), справедливы при любых индексах i , j и k . Они точно также, как и в случае бинарных переменных дополняются еще двумя ограниче- ниями 0=− jikkij xxxx , 0=− ijkkij xxxx , (8') которые следуют из неоднозначного представления ijkikjjikjkikijkjikji xxxxxxxxxxxxxxxxxx ====== )()()( . Для каждой четверки булевых переменных ix , jx , kx и lx имеем два огра- ничения: 0=− jlikklij xxxx , 0=− jkilklij xxxx , (9') которые линейно независимы и следуют из неоднозначности представления произведения четырех переменных: jkiljlikklijlkji xxxxxxxxxx === . Семейства функционально избыточных ограничений (6)–(9) и (6')–(9') дают возможность построить новые улучшенные бинарные и булевые квадратичные задачи, которым в ряде случаев будут соответствовать более точные оценки, чем оценки * yΨ и * xΨ . 4. Улучшенные бинарная и булевая квадратичные задачи. Eсли квадра- тичную задачу (3)–(5) дополнить группами функционально избыточных ограни- чений (6), (7), (8) и (9), то получим новую квадратичную задачу в бинарных пе- ременных:         ++== ∑∑∑ = − = > 00 1 0 1 1 * )(max qyqyyqyQQ n i ii n i n ij jiijy (10) при ограничениях 012 =−iy , ni ,,1 K= , (11)        =− =− =− =− ,0 ,0 ,0 ,012 ijij jiij ijji ij yyy yyy yyy y njiji ≤<≤∀ 1:, , (12) ОБ УТОЧНЕНИИ ЛАГРАНЖЕВЫХ ДВОЙСТВЕННЫХ ОЦЕНОК… Теорія оптимальних рішень. 2006, № 5 151          =− =− =− =− =− ,0 ,0 ,0 ,0 ,0 jkikij ikjkij ijjkik ijkkij jikkij yyy yyy yyy yyyy yyyy nkjikji ≤<<≤∀ 1:,, , (13)     =− =− ,0 ,0 jkilklij jlikklij yyyy yyyy nlkjilkji ≤<<<≤∀ 1:,,, . (14) Пусть * yψ – наилучшая лагранжевая двойственная оценка для задачи (10)– (14). Она всегда будет не хуже, чем оценка * yΨ , а в ряде случаев будет более точной верхней оценкой для * yQ . Аналогично, если квадратичную задачу (3')–(5') дополнить группами функ- ционально избыточных ограничений (6'), (7'), (8') и (9'), то получим новую квад- ратичную задачу в булевых переменных:         ++== ∑∑∑ = − = > 00 1 0 1 1 * )(max qxqxxqxQQ n i ii n i n ij jiijx (10') при ограничениях 02 =− ii xx , ni ,,1 K= . (11')        =− =− =− =− ,0 ,0 ,0 ,012 jijij ijiij ijji ij xxx xxx xxx x njiji ≤<≤∀ 1:, , (12')          =− =− =− =− =− ,0 ,0 ,0 ,0 ,0 ijkikij jikjkij kijjkik ijkkij jikkij xxxx xxxx xxxx xxxx xxxx nkjikji ≤<<≤∀ 1:,, , (13')     =− =− ,0 ,0 jkilklij jlikklij xxxx xxxx nlkjilkji ≤<<<≤∀ 1:,,, . (14') П.И. СТЕЦЮК, П.М. ПАРДАЛОС 152 Теорія оптимальних рішень. 2006, № 5 Пусть * xψ – наилучшая лагранжевая двойственная оценка для задачи (10')– (14'). Она всегда будет не хуже, чем оценка * xΨ , а в ряде случаев будет более точной верхней оценкой для * xQ . Итак, новые квадратичные задачи в (10)–(14) и (10')–(14') получены допол- нением простейших квадратичных задач (1)–(2) и (1')–(2') полными семействами функционально избыточных ограничений, которые рассмотрены выше. Ограни- чения (12) и (12') описывают связи внутри каждой двойки булевых и бинарных переменных. Их количество равно )1(2 −nn . Ограничения (13) и (13') описыва- ют дополнительные связи внутри каждой тройки булевых и бинарных перемен- ных и их количество равно 6/)2)(1(5 −− nnn . Количество ограничений (14) и (14') равно 12/)3)(2)(1( −−− nnnn и они описывают дополнительные связи для переменных внутри каждой четверки булевых и бинарных переменных. Справедлива следующая теорема. Теорема 2. Оценки * yψ и * xψ (при произвольном 4≥n ) удовлетворяют следующим неравенствам: * yyyQ Ψ≤ψ≤ , * xxxQ Ψ≤ψ≤ . В заключение отметим, что точность оценок * yψ и * xψ требует детального исследования. Так, неравенства в теореме 2 – очень грубые и рассчитаны на наихудшие случаи бинарной и булевой квадратичных задач. Конечно в ряде случаев оценки * yψ и * xψ будут более точными, чем оценки * yΨ и * xΨ . Так, на- пример, для бинарной квадратичной задачи с 4=n , где −−−−= 2121)( yyyyyQ 4343 yyyy −−− , имеем 2* =yQ , 3* =Ψy , 2* =ψ y . Для булевой квадратичной за- дачи с 4=n , где 43432121)( xxxxxxxxxQ ++−++−= , имеем 2* =xQ , 25.2* =Ψx , 2* =ψ x . П.І. Стецюк, П.М. Пардалос ПРО УТОЧНЕННЯ ЛАГРАНЖЕВИХ ДВОЇСТИХ ОЦІНОК У БІНАРНИХ ТА БУЛЕВИХ КВАДРАТИЧНИХ ЗАДАЧАХ Розглянуто підхід для покращення лагранжевих двоїстих оцінок у квадратичних оптимізацій- них задачах з бінарними )1(± та булевими )10( − змінними. Він базується на використанні сімейств функціонально надлишкових квадратичних обмежень-рівностей, які для цих задач можно побудувати при введенні нових змінних у формі добутків вже існуючих змінних. По- казано, що введення цих обмежень покращує точність лагранжевих двоїстих оцінок. ОБ УТОЧНЕНИИ ЛАГРАНЖЕВЫХ ДВОЙСТВЕННЫХ ОЦЕНОК… Теорія оптимальних рішень. 2006, № 5 153 P.I. Stetsyuk, P.M. Pardalos ON IMPROVING OF LAGRANGIAN DUAL BOUNDS IN BINARY AND BOOLEAN QUADRATIC PROBLEMS The approach for improvement of dual lagrangian bounds in quadratic optimization problems with binary )1(± and boolean )10( − variables is considered. It is based on use of families superfluous constraints in form of equality, which for these problems can be constructed as a result of introduc- tion new variable in the form of products already existing variable. Is shown, that the introduction of these constraints improves accuracy of lagrangian dual bounds problem. 1. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Dordrecht, Kluwer, 1998. – 394 p. 2. Шор Н.З. Роль избыточных ограничений в улучшении двойственных оценок для по- линомиальных оптимизационных задач // Кибернетика и системный анализ. – 1998. – № 4. – С. 106–121. 3. Shor N.Z., Stetsyuk P.I. Lagrangian bounds in multiextremal polynomial and discrete optimization problems // J. of Global Optimization. – 2002. – № 23. – P. 1–41. 4. Стецюк П.И. О функционально избыточных ограничениях для булевых оптимиза- ционных задач квадратичного типа // Кибернетика и системный анализ. – 2005. – № 6. – С. 168–172. Получено 17.07.2006

Об уточнении лагранжевых двойственных оценок в бинарных и булевых квадратичных задачах

Institution

Ähnliche Einträge