Метод канонических порядков в оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

р г 6а к аОЛе М И Я НАУК БЕЛАРУСИ Институт математики

на правах рукописи

ВАСИЛЬКОВ ДМИТРИЙ МИХАЙЛОВИЧ

МЕТОД КАНОНИЧЕСКИХ ПОРЯДКОВ В ОПТИМИЗАЦИИ Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

МИНСК - 1993

Работа выполнена в Белорусском государственном университете

Научный руководитель - доктор физико-математических наук,

доцент.Ковалев М.М.

Официальные оппоненты - доктор физико-математических наук,

профессор Танаев B.C., кандидат физико-математических наук, старший научный сотрудник Сарванов В.И.

Ведущая организация - Вычислительный Центр АН России.

Защита диссертации состоится "26" нсзТр-% 1993 г.

J Г

в 7 6 часов на заседании специализированного совета

К 006.19.01 при Институте математики АН Беларуси

(220072, Минск, ул.Сурганова, 11, конференц-зал)

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан •22 " Ok.T9.S~pA 1993 г.

Ученый секретарь

специализированного совета -Jtlii^-Urt— Астровский А.И.

к.ф.-м.н., старший научный сотрудник

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В диссертационной работе поставлена цель исследовать связь штода частичных порядков и традиционных методов выделения аассов. Основным объектом исследования язляется отношение <а ганонического частичного порядка и связанные с шил оптимизаци->нные задачи. Канонический порядок изучался ранее рядом автор-!в. В частности, описан класс-линейных функций, изотонных отно-штельно <а, исследовались обобщения канонического порядка и их ■вязь с оптимальными градиентными решениями на матроидных стру-:турах. Однако, открытой остается проблема полного описания :ласса непрерывно-дифференцируемых функций и функций дискрет-'ого аргумента, изотонных относительно <а. Требуют дальнейшего :зучения условия оптимальности градиентного решения для задач с ;елевими функциями из данного класса. Не изучены комбинаторные арактеристики целочисленных множеств, упорядоченных каноничес-1Ш порядком, позволяющие установить шенноновскую сложность ал-'оритмов вычисления локальных оптимумов.

Цель работы:

'- описать класс непрерывно-дифференцируемых функций, изо-онных относительно канонического порядка;

- исследовать условия оптимальности градиентных решений адач с целевыми функциями из этого класса;

- установить комбинаторные свойства подмножеств упоря-оченных отношением <а\

- исследовать задачу нахождения локальных оптимумов изотопных функций на (Z^,<a).

Научная новизна:

1) Полностью описан класс 5я нещэерывно-дифференцируемых функций, изотонных относительно канонического порядка <а.

2) Установлено, что r-тшшальность градиентного решения в задачах с целевой функцией из масса 501 определяется единственностью максимального элемента допустимого множества относительно порядка <а.

3) Получены критерии существования единственного максимального элемента' относительно <а для Bimyiuiux полиэдральных множеств.

4) Исследовано отношение вложимости канонических порядков. В частности, показано, что координатный и лексикографический порядки являвтся частными случаям! порядка <а.

Ь) Описано множество &(D) векторов а, определяющее семейство всех канонических порядков <а, относительно которых данный выпуклый полиэдр D обладает единственным максимальным элементом; тем самым описано максимальное по включению семейство классов ва, гарантирующих оптимальность градиентного решения любой задачи с целевой функцией из втого семейства.

6) Введено понятие обобщенного нелинейного канонического порядка и в его тор,чинах получены результаты, аналогичные доказанным ранее для порядка <а.

7) Установлена связь подмножеств (,z",4C£; с решетками раз-

т

биений и списаны их комбинаторные характеристики.

8) Описан эффективный алгоритм построения минимального цепного разлоаения множеств (Вп,<а), (Вп,т,<а) и (1™'т,<а) при некоторых а.

Практическое значение. Предложенные в диссертации подходы к решению оптимизационных задач реализованы в системе топографического проектирования и используются в ряде ВУЗов и предприятий J

Публикации и апробация работы. По теме диссертации опубликовано 7 работ. Основные результаты докладывались на школе-семинаре по дискретной оптимизации (Алушта 1990,1991), на международном семинаре "Discrete Optimization" (Магдебург 1992,

Минск 1993), на 4-й конференции математиков Беларуси (1992).

Структура и объеы работы. Диссертация состоит из введения, двух глав и списка цитируемой литературы из 82 наименований. Общий объем работы 101 страница машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается общая характеристика работы, сформулирована цель исследования и коротко изложено содержание глав диссертации.

В главе 1 с помощью-канонического порядка исследуются условия оптимальности градиентных решений задач с изотопными целевыми функциями. В §1 описан класс полиэдральных допустимых множеств в Шп, гарантирующих оптимальность градиентного решения для .задач с целевой функцией, изотонной относительно канонического порядка. Напомним, что фушшия / называется изотопной на множестве В относительно частичного порядка <, если "для любых точек х,уе!) выполнение а:<у влечет /(т)к/('у). Порядок < называется информацией о классе функций 5 на множестве В, если любая функция из 2 является изотонной, и полней иш^сфмацией, если из несравнимости векторов х,уеВ следует существование в 3 таких функций / и я, что /(х)</(у), а &(х)>ц(у). Множество максимальных влементов частично упорядоченного множества (В,<) называется иакмшальной базой и обозначается (В,<)тах.

На множестве ип введем отжмнение ■< канонического частичного порядка

за .

^лху ^ х,< Т у, \J8eln]. 1=1 1 1=1 1

Пусть 5 есть класс всех функций, изотопных относительно канонического порядка. Рассмотрим задачу

пох(Лх): кШ, /<=2- (Р1)

Назовем градиентным решением задачи (Р1) лексикографический максимум аР множества Б (если он существует).

Проблема 1: Описать ¡иасс множеств б К71, <Э.ш которых градиентное решение будет оптиплъных для задачи (Р1) при любой целевой функции из класса 2.

Теорема 1. Градиентное решение rc^eD является оптимальны.* решениел задачи. (Р1) для любой целевой функции /eg тогда и толысо тогда, когда множество (D,<) обладает единственных максимальным элелентол.

Проблема 2. Описать все выпуклые полиэдральные множества в R71, обладающие единственных максимальным, элементом относительно порядка <а.

Пусть D=(xen/l:Ar~b, х>0) - невырожденный поливдр, где А -невырожденная nxm-матрица, п>т. Обозначим В=(В(1),...,В(п)} множество индексов столбцов А^ базиса АВ матрицы А, и N=[nl\B.

Теорема 2. Градиентное решение является единственным максимальным, элементом множества (В,<) тогда и толысо mogda, когда существует такой базис ЛВ матрицы А, что

(AB)~1AJ > ek(J), WjeN (1)

где k(J) = mxikeCmJ: B(k)<J}.

Аналошчная теорема справедлива, если допустимое множество есть невырожденный полиэдр, заданный • системой неравенств: D-ixejf1: Ах<Ь), где А - невыроаденная ихп-матрица, т>п. Обозначим через А^ и bg, соответственно, подмножество базисных строк матрицы А и соответствующий подвектор вектора Ъ.

Теорема 3. Градиентное решение является единст-

венным максимальным элементом множества. (1),<) тогда и только тогда, когда

(0.....0) < (А~в1 )J Vjzinl. (2)

Описывается метод нахождения единственного максимального элемента для произвольной полиэдральной выпуклой области . в Rn на основе критериев (1) и (2). В качестве примера получены условия оптимальности градиентного решения для задачи с "рюкзачными" ограничениями

max (f(x)\ ах<Ъ, 0<x<h}, feg.

В §2 дано полное описание класса непрерывн07дифферешшруе--мых функций, изотонных относительно канонического порядка <.

Обозначим через С1 класс всех непрерывно-дифференцируемых

функций К, и пусть подкласс 5 с С

ко тех функций, которые удовлетворяют условию

состоит из тех и толь-

I£ (х) (х) > О УХ€К". (3)

1 1 п ■

Теореиа 4. Функция /сС изотонна относительно канонического порядка < тогда и только тогда; когда /ей- Более того, отношение < есть полная информация о классе 2. .

Аналогичная теорема справедлива и для функций целочисленного аргумента /:1п-> К. в качестве аналога частной производной для функций на 2п вводится градиент по £-му направлению: ^/(х) = /(х+еь) - /(х).

Пусть 5г есть класс функций на 2п, удовлетворяющих условию ^/(х) > ... > > О чхе1п

Теореиа 5. Фуюсция / на 1п изотонна относительно канонического порядка тогда и только тогда, когда Более того, отношение < есть полная информация о ¡массе

Следствием теорем 2, 3 и 4 является следующее утверждение, в котором дано решение проблемы 1.

Следствие 1. Градиентное решение задачи (Р1) с целевой функцией- /ей и полиэдральныл допустит.* жнохествол I) является оп-ти.тльннл тогда и только тогда, когда В удовлетворяет условиях (1)/(2).

В §3 на основе свойств обобщенных канонических порядков расширяется масс оптимизационных задач со свойством оптимальности градиентного решения. На к" рассматривается отноше!ше <а

канонического порядка с растяжением аеК":

я я

х< у £ а{а;{ < £ а\zsein]. (4)

1 1 = 1

В дальнейшем в (4) предполагаем . Если а=(1,...,1), то < есть отношеш1е < стандартного канонического порядка.

Обозначим через 5а класс непреривно-дифференцнруемых функций, удовлетворяющих условию

'%(*>»-к %<*> дА(х)>0 ^' (5)

7 2 2 п п

Теореиа 6. Функция /еС* изотонна относительно канонического порядка <а тогда и только тогда, когда /е2а.

Для двух различных отношений <? и <0 частичных порядков, заданных на Кп, будем говорить, что порядок <1 содерапгг порядок

<2 (пишем <2 s <1), если Ых,у^ из x<^¿) следует x<¿y. В частности, нетрудно показать, что лексикографический порядок « содержит стандартный канонический порядок <, а тот, в свою очередь, содержит координатный

«о <*¡,

Введем вектор 1.... ).

¿ а2 аП-1

Теорает 7. Пуахь Тогда следующе утверждения экви-

валентны:

1) порядок содержит порядок <а;

2) \(р)*\(а);

3) за.

Следствие 2.

1) Отпашете <а при 1(а) ■* (1,0,... ,0) эквивалентно отношению с лексшсографического порядка;

2) Отношение <а при \(а) -* (1эквивалентно отношению < координатного порядка.

Далее рассматривается проблема, двойственная к проблеме 1.

Проблема 3. Для данного полиэдрального допустимого тожества D описать лножеапво

&(D)=(aeIR^; \(D,<a)та*\=1}.

Peaeime проблемы 3 позволяет описать макш-шалышВ по включению класс Ъ(Ь) целевых непрерывпо-диффогенцгшруемых функций, заданных лишь соотношениями вида (5), который гарантирует оптимальность градиентного решения задачи (Р1) при фиксированных ограничениях.

Пусть допустимое множество есть невырожденный полиэдр вида D=f2reRn; Ах<Ь), где А - невырожденная ;лхп-матрица, т>п.

Tcopsua 8. Градиентное решение является единст-

пенныи жшсилалъныл элелентол лножества (D,<aj гсогЗа и только тогда, когда

(О....,О) <а {A~4)J yj^lnl. (6)

Обозначим через влемепты матрицы Á^ и, добавив к соотношениям (6) требование положительности а, запишем их в виде системы неравенств относительно а:

й Р

У а.а, ,>0

¿1 1 и (7)

<х{>0 чШп].

Следующая теорема устанавливает, что при условии существования градиентного решения множество решений системы (7) всегда непусто и совпадает с &(В).

Теорен'1 9. Выпуклый полиэдр Вей?1 содершп градиентное решение л^ тогда и только тогда, когда существует! положительной вектор а т/сой, что £ является единственный. жисси^альнш эле-ленто л .тожества (В,<а).

Следствие 3. Пусть В=(хФп: АхкЪ) - выпуклый полиэдр. Тогда следующе утверждения эквивалентны:

1)0 содержит градиектюе решение;

2) .тожество &(В) непусто и описывается системой нера-вечств (7); •

3) жтриир. А содержит невырохденный базис А^, соответствующий градиентнолу решения и обладающий следутрл свойствол: для любого его элемента Je[n], в А^ существует элемент а^хЭ, где Нц<р<,п.

Пусть 5„- и Но практике 3„ рассматривается как класс 0 «сИГ 0

неирэрыию-,Щ:ф|)еренш!ируемых функций, заданных лишь соотношениями для частных производных вида (5). Через 2(Д7£30 обозначим класс целевых функций задачи (Р1), оптимальное значение которых достигается в точке

Следствие 4. ?-(!)) = !) 5".

хг&(д)

В кпчестве примера описываются классы целевых функций в задачах целочисленной оптимизации, задаваемых соотношениями вида (5), для которые градиентное решение является оптимальным. Рассматриваются две задачи: задача о минимальней триангуляции и задача об упаковке.

Далее, вводится отношение обобщенного нелинейного канонического порядка. Обозначим через й класс еепарабельных строго

монотонных вогнутых функций на ¡к". Для функции Ь(х)= ^ Ь^х^еЗ!

гадололим отяс«лр!пге обобщенного канонического порядка

X <(П)У ^Ъ^х^ vзefnJ.

Если существует точка з&(г), ге{-1,1), допустимого-множества В задачи (Р1) такая, что

з^(г)=тах(г1х1: хеВ),

з^(г)=ш1х1г^х1: хей, х3=%3 чзеИ-Ш ч1-2,... ,п,

то назовем ее обобщенный градиентным решением задачи (Р1). Через ИЛСг) обозначим класс функций ТгеИ, компонента которых строго возрастает тогда и только тогда, когда г{=7. Если НеШСг), то будем говорить, что обобщенное градиентное решение и обобщенный канонический порядок -^^соответствуют друг другу. В дальнейшем рассматриваются только соответствующие градиентные решения и порядкц.

Обозначим через класс непрерывно-дифференцируемых

функций, удовлетворяющих условию

Теореиа 10. Функция /еС* является. изотопной относительно обобщенного канонического порока тогда и только тогда, когда №(1г).

Теореиа 11. Следующие утверждения эквивалентна:

■ 1) Порядок содержит порядок ;

2) < \8(х), где вектор \Р(х) определяется как

3) Ъ(&).

Теореиа 12. Обобщенное градиентное решение х^(г)еВ является оптилальныл решением задачи (Р1) для .тобой целевой функции /€3^, где Ь.ъЩг~), тогда и только тогда, когда зсР(г) является единственным, жшсимальныл элементах множества (В,<^). Для функции Ьсй и точки хеВ рассмотрим матрицу бЬ1(х)ЛП

В(х)=

. Ог^хшг ... Сй1п(х)/т

и пусть D есть невыровденный полиэдр D={xe$fl: Ах<Ъ).

Теореыа 13. Обобщенное градиетное решение яв-

ляется единственны», лаксижиьнил элелентол хножества )

тогда и только тогда, когда

Н(х?(г))А~в1 > 0пЖ . (8)

Через ЛС1),г) обозначим класс функций 1\сШ(г) таких, что множество ) обладает единственным максимальным элементом.

Теорема 14. Множество i\(D,r) непусто тогда и только тогда, когда V содержит соответствующее обобщенное градиентное решение х&(г). При этоя ft(D,r) состоит из тех и только тех функций heffi(r), для которых выполняются соотношения (8).

Пусть 5 (г) = U 5(Ю.

0 heWr)

Следствие 5. Целевая функция fe$o(r) задачи (Р1) достигает оппшлшьпого значения 6 тачке з@(г) тогда и только тогда, когда /еЪ(П), еде ПеЩд,г).

В главе 2 рассматривается задача

max f(x) Vf/.gjeЗ"хб, (Р2)

xzDcll z

где D - конечное множество допустимых решений, ge© - булева функция на z", называемая g-оракулоц или резольвентой и возвращающая О тогда и только тогда, когда xeD. Предполагается, что целевая функция / не задана аналитически и ее значения вычисляются посредством некоторой процедуры, называемой i-оракулои. Кроме того, предполагается, что функция / изотонна относительно канонического, порядка <п. Задача (Р2), таким образом, сводится к нахокдению всех элементов максимальной базы (1),<л)тах допустимого множества при минимальном числе обращений к f-оракулу.

В главе исследуются оптимальные алгоритмы построения максимальной базы множества (D,<a) для некоторых а на основе метода минимального ценного разложения. В §4 исследуются комбинаторные свойства множества для различных а, в частности, указан способ изоморфного вложения множества (Zr^,<) в решетку разбиений, что порьолило трансформировать характеристики хорошо ирученпыч решеток разбиений на упорядоченные каноническим поря-

дком множества.

Разбиение Л числа т есть мультимножество, заданное на множестве N и определяемое функцией кратности y^slN-HN, такой, что li>0mI)=т. ¡Значение V(t) есть число повторений слагаемого, равного I, в представлении чиела .. Частично-

улорядоченное множество (У,<) всех разбиений, является дистрибутивной решеткой, называемой решеткой Юига. Выделим подмножество Упс?У, содержащее разбиения, слагаемые которых не превосходят п.

Теореыа 15. Частично упорядоченные лножества (2^,<) и (У11,*.) изолорфны.

. Рассмотрено отношение канонического порядка на подмножествах (!"",<), в частности, на целых точек п-мерного параллелепипеда Z^rixcZ": 0<х<Н), на булеане (№>п,<), и на т-х слоях (®п,т,<) и (,<) соответственно булеана и. z". Показано, что множества (,Вп,<), ,<) и (*г"'т,<).рангово-унимодальны, ран-

гово-сишетричны и обладают сильным свойством 1Ш1ернера (говорят, что такие множества обладают свойством Peck). Кроме того, установлены изоморфизмы:

(гп+'т\о е (Впт~Г'т,<) с (Zr^1'n'1,<) и

(Впт~1'т,<), если О < т < \nh/2}, (Впш~1 'nh~mз<), если \nti/2\ + 1 < т < nh,

где обозначает т-й слой п-мерного куба со стороной И.

Далее, для получения верхних оценок слоааюсти построения максимальной базы изучаются комбинаторные свойства множества Сг",-<а; в случае, когда вектор « удовлетворяет условию

0<а1<...«хп ' (9)

Теореиа 16. При условии (9)

где ы(Р) есть шрйна частично [¡¡горядоченнго .тожества Р. Следствие б. При условии (9)

Установлено, что общем случае множество (2!},<а) при условии (9) не удовлетворяет условию Жордана-Дедекинда, т.е. к нему

не применимы такие характеристики, как симметричность, унимодальность , свойство Шернера и т.д.

В §5 исследуется метод минимального цепного разлозания для построения максимальной базы подмножеств (1^,<а) и описан эффективный алгоритм-построения минимального цепного разложения решеток (В?<), (Вп'т,<) и (Zn+'m,<).

Пусть V=(J>,<)c(2r^,<) есть конечное частично упорядоченное множество, содержащее допустимое множество (D,<). Очевидно, что в случае, когда целевая функция f и резольвента g изотонии на Р, то задача построения максимальной базы допустимого множества (Ь,<) становится эквивалентной задаче нахождения верхних пулей и нижних едшшц (т.е. задаче расзхгфрсвкн) функции g на множестве Р. Пусть Я-(Л) - множество всех алгоритмов, решзкгцяж эту задачу. Обозначим через ®(P,A,g) миш'.мяльнее число обращений к g-оракулу, достаточное для расшифровки функвди g алгоритмом Л. Введем функцию Шеннона

t?(P)= min max ffP.A.g).

Лей ge(5

Алгоритм А &Л, на котором достигается значение $(Р), называется оптимзльщы по Шеннону алгоритмом расшифровки.

С помощью метода минимального цепного разложения и свойств решетки установленных в §4, доказана

"oovmn 17. Upx условии (9)

Приводится оптимальный по Шеннону'алгоритм расшифровки булевой функции на при условии (9).

Как известно, сложность построения минимального цепного разложения не превосходит

Т(Р) = 0(К(Р)\Р\ЗУ2),

где K(P)=mxz(\п*(х)],\ъ~(х)\). В диссертации показано, что вта хеР

оценка может быть улучшена для решеток (а ,-<), (ЪГ' ,<) и (Ж™'т,<), и описан алгоритм построения минимального цепного разложения произвольного множества Р со свойством Peak за время, не превышающее

Т(п)

'л+h- ■Г 'п+К

h + h »

= о1к(Р) .

v 1ж) '

- 14 -

Teopeua 10. Нижиалъное цепное разложение ложно построить

1) для решетки ев",<) за вреля *(=gh1)/2(Ylat)3/2} ,

2) для решетки flB",т,<) за вреля ^~m)/2(Wbt)3/2J,

3) для решетки (1^,т,<) за вреля ^J^1 )/2(Wct)3/2j,

где !7а{, и 1<с{ - соответственно лощности слоев каждой из указанной решеток. «

Основные результаты диссертации опубликованы в работах:

1. Васильков Д.М., Ковалев Ь.М. О свойствах канонического по-

• рядка // Изв.АН Беларуси.- 1993.-'N 1.- С. 21-24.

2. Васильков Д.М. Геометрическое моделирование в геологии и экологии/ Экстремальные задачи оптимального планирования и проектирования. Сб.научных трудов ИТК.- Минск.- 1991.-С.22-31

3. Васильков Д.М. Расшифровка регулярной булевой функции/ 4 Конференция математиков Беларуси. Тезисы докладов. - Гродно.- 1992.- С.62

4. Vaeilkov D.M., Kovalev М.Ы. Canonical order in optimization/ Workshop on Discrete Optimisation. - Magdesprtmg.-

. 1992.- P.24.

5. Vasilkov D.Ii., Kovalev Ы.Ы. The Canonioal order and Greedy Algorithms/ Workshop on Discrete Optimization. - Minsk.-1993.- P.19.

Подписано к ппчатн форнат 60зг04/1б. Бумага тип (I 3.

Печать офсотная. Уал.пач.л. /,0 У а п. красно от. 0,0£ Уч.-изд.л. Тираж ню экз. Закал N 446

Белгосунирерситбт. 220050, Минск, пр.<Г.Скорины,4. Отпечатано на ротапринта Белгосуниверситвта. 220030. Нинок, Бобрунекая, 7.