Алгоритмы решения некоторых задач субмодулярной оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕШЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи Р Е Д Д И Сварна Кумари

АЛГОРИТМЫ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ СУЕЫОДУЛЯРНОЯ ОПТИМИЗАЦИИ 01.01.09 - математическая кибернетика

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

МИНСК 1994

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

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

доцент ПИСАРУК Николай Николаевич.

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

член-корр. АН Беларуси, профессор, ТАНАЕВ Вячеслав Сергеевич. - кандидат физико-математических наук, Демиденко Виталий Михайлович.

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

Защита диссертации состоится " 29 " июня 1994- г. в_15_час. на заседании специализированного совета К 006.19.01 по присувдению ученой степени кандидата физико-математических наук в Институте математики АН Беларуси по адресу: 2206^4, г.Минск, ул. Сурганова, 11.

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

Автореферат разослан " июня 1994 г.

Ученый секретарь специализированного совета кандидат физ.-мат. наук

ДА Стл^ко; А.И.АСТрОВСКИЙ

Общая характеристика работы Актуальность теш. Роль субмодулярных функций в комбинаторной оптимизации сравнима с ролью выпуклых функций в непрерывной оптимизации. Многие классические комбинаторные проблемы могут быть сформулированы как задача поиска экстремума субмодулярной функции. Другой, еше более широкий класс зада"ч комбинаторной оптимизации, составляют задачи с так называемыми субмодулярными или полиматроидными ограничениями. Основная трудность решения таких задач связана о большим (экспоненциальным) количестом ограничений, которые определяют множество допустимых решений.

Основной целью работы является разработка новых численных методов решения некоторых задач субмодулярной оптимизации и их применение к решению ряда практических задач.

Методы исследования. В работе применяются методы выпуклого и линейного программирования, теории игр, комбинаторной оптимизации, теории матроидов.

Научная новизна и практическая ценность работы. Все полученные результаты является новыми. В работе введен и исследован новый класс полиэдральных лгр - матричные игры с зависимыми стратегиями. Предложены новые алгоритмы решения классических задач минимизации и макс.шизащш субмодулярной функции. Для двух классов целевых функций решены оптимизационные задачи на базовом многограннике субмодулярной функции. Субмодулярная задача упорядочения сведена к решению параметрической задачи линейного программирования. В диссертации приводится ряд практических задач, для решения которых можно использовать алгоритмы, разработанные в диссертации.

Аппробяния работ".. Основные результаты диссертации докладывались на межреспубликанских научно-практических конференция* творческой молодежи (Минск, 1990 г., Минск, 1992 г., Минск, 1994 г.). На научных семинарах: в Белорусском государственном университете и в Институте математики АН Беларуси.

Публикации. Основные результаты диссертации опубликованы в работах [1-4]-

Структура ц обьей работы. Диссертация состоит из введения, двух глав, и ,сщг$а литературы, включающего 91 наименование. Объем диссертации ад ртраниц машинописного текста, включая 15 рисунков.

Содержание дисрертационной работы.

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

В первом параграфе приводится ряд базовых результатов субмодулярной оптимизации и дается одно обобщение градиентного алгоритма для решения задачи линейного программирования на полиматроиде.

и

Напомни^, что функция /: 2 —> К называется субмодулярной, если субм.одулярное неравенство

хи + гы) г /а ЛJ) + /а и л (1)

выполняется для всех 1,1 с N. Если неравенство (1) выполняется как р^ерство, то / называется модулярной. Обычно предполагается, ч,тс> функция / доступна только через процедуру (оракул), которая вычисляв?; £(1) для каждого I с N. Временную сложность

этой процедуры обозначаем через Т^. Без ограничения общности рассмотрения будем предполагать, что f нормализована, т.е. /(а) = О. ' .

Многогранник

3(/):= {X е Ф-. x(I) s f(I) Vlcff, x(N) = r(N)) (2)

называ.;тся> базовым многогранником функции /. Здесь мы использовали обозначение х(1) для х{. Рассмотрим следующую задачу

шах ( ex: x(I) s f(I), I £ N; x(I) = f(I), I с С i (3) w

где семейство С с 2 является цепью (из I,J е С следует, что I с J или J's I), причем Ф, N е С.

Пусть a,b g N. Подмножество I s N называем а,5-множеством, если a е I, Ь й I.

Теорема 1.3. Для каждого с е IR^ максимум в задаче (3) достигается в точке где перестановка я удовлетворяет

следующим условиям:

Если í < J и с„ < с_ , то в С сущестует я,,я -множество. (4) Я1 1 J

Если в С существует я4 -множество, то I < J. (5)

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

Пусть * = (1,2,...,т) я Н = (1,2,...,п) есть множества стратегий первого и второго игроков, А - тжп матрица выгрышей первого игрока. Предположим, что также заданы две субыодулярные функции

р.г 2м-► К и р: 2я-► Я .

Г1 ♦ га ♦

Ыы можем интерпретировать р^си как вероятность применения &-м игроксы некоторой стратегии из множества I. В качестве допустимых смешанных стратегий соответственно первого и второго игроков рассматриваем множества ЗСр^ и В(рз). Как обычно, в качестве решения матричной игры рассматриваем пару допустимых стратегий р° с B(pi), с В(ря), которые" образуют седловую точку функции Щр.д) я рАц, т. е.

Щр.Я0) * Щр°.д°) * Е(р0,я) V ре В(р1), д с В(ря)

Теорема 2.1. Решение матричной игры о зависимыми стратегиями еквивалентно решению следующей пары задач линейного программирования:

похГи: V - р (Ад) л 0 у 9« ивггВ(ря), р с В(Р1), V е Ю (6) тШи: V.- (рА)д * 0 у'р « ьеггв(р1), д с В(р2), и с ю. (7)

Если Г1>°,р°; п (v0,q0) - оптимальные решения задач (6) и (7), то и0 есть цена игры, а р° и д° соответственно оптимальные стратегии первого и второго игроков.

Отметим, что каздая из задач (б) и (7) имеет экспоненциальное число ограничений. Сложность решения таких задач линейного программирования существенным образом зависит от сложности процедуры отделения, которая по заданной точке

должна проверить удовлетворяет ли она ограничениям задачи или найти ограничение, которое нарушается.

В диссертации приводится полиномиальный алгоритм, который для задачи ЛП (6) решает задачу об отделении. Это позволяет сформулировать следующий результат.

Теорема 2.2. Существует полиномиальный алгоритм решения матричной йгры о зависимыми стратегиями.

Несмотря на то, что теорема 2.2 устанавливает полиномиальную разрешимость задачи, она не указывает пути построения • алгоритма эффективного на . практике. Дело в тем, что полиномиальная разрешимость задачи (б) доказана о использованием метода -эллипсоидов. Из всех известных алгоритмов линейного программирования, доказавших свою эффективность на практике, к. задачам с экспоненциальным числом ограничений можно применять только двойственный симплекс-метод. В диссертации предлагается реализация двойственного симплекс-метода применительно к задаче '(б).

В третьем параграфе мы предлагаем два алгоритма поиска экстремумов субмодулярной функции. Сначала рассмотрим задачу минимизации субмодулярной функции

т1п(/(1): I с Я). (8)

Для решения задачи (8) существует сильно полиномиальный алгоритм. Несмотря на вто, проблема построения эффективного алгоритма минимизации субмодулярной функции все .еще очень далека от своего разрешения как с теоретичесской, так и с практической точки зрения.

Известно, что задача (8) эквивалентна следующей задаче

тШ(х.х): х е B(f)}, (9)

причем, если Xя - оптимальное решения (9), то N~(x*) = (I е N: х* < 0} - оптимальное решение задачи (8).

Для решения задачи (9) Фуджишге (Fujishige)11 предложил использовать алгоритм франка-Вольфа для минимизации дифференцируемой вшуклой функции на многогранном множестве. Мы предлагаем модификацию этого алгоритма, которая, начиная с произвольной точки х° е В(f), строит итерационную последовательность х*, г3,... по следующему правилу:

4

a*fi = а* + \tf, ■

где перестановка я определяется сортировкой компонент вектора г*2 по неубыванию: •

х% s a ...¡г х% ,

12 п

а

Ч - min{i; - ^ У' )

* V. Il/- 2TII ^

Алгоритм останавливается на итерации t после выполнения

»

следующего условия

хг(Г(хг)) >?(Я'(хг)) - 1, (10)

при этом N"(xt) - оптимальное решение задачи минимизации субмодулярной функции.

Проведенные вкспериментальные исследования показали, что

1'Pujishige S. Submodular functions and optimization.

Amsterdam : North Holand, 1991. p. 269.

предложенная версия алгоритма на большинстве примеров работает почти на порядок быстрее первоначальной версии Фудаошиге. Это объясняется тем, что сложность одной итерации нашего алгоритма почти на два порядка меньше сложности итерации в алгоритме Фудаишиге (нужно решать систему линейных уравнений в смысле наименьших квадратов). Кроме того, Фудамшиге использовал следующий критерий останова

(хг, J* - хг) г О. (11)

Можно показать, что условие (11) всегда влечет выполнение условия (10). Поэтому применение критерия останова (10) такие позволяет сократить и количество итераций алгоритма.

В отличие от задачи минимизации задача максимизации субмодулярной функциии является NP - трудной. Поэтому для нее остается актуальной проблемой .разработка эффективных эвристических процедур. Мы предлагаем для этой цели использовать эврютику Кернигана и Лина, которая доказала ■ свою -эффективность при решении задач разбиения и' размещения. Наш алгоритм базируется на следующем результате

Теорема 3.5. Для любого I с N

Tmxífd): I с Ю = max(g(X): я € у,

где g(ю = maxífd): I е R%), R^ = (I s. N: = f(I)) и

g(lí) можно вычислить за 0(n2mln(T^,n)) операций.

В четвергом параграфе мы рассматриваем один специальный случай задачи .максимизации выпуклой функции -а базовом многограннике

max{g(ax,bx): х е B(f) ) (12)

где в: В2—► 1* есть выпуклая функция, а, Ъ е К".

Так как в ~ выпуклая функция, то максимум в задаче (12) достигается в точке х е В(/), для которой двухмерная точка (ах, Ъх) является вершиной многогранника

В(/,а.Ь) -я сапи((ах,Ъх): х « В(/) ). (13)

Творша 4.1. Многогранник В(/,а,Ъ) имеет не более чем 2па вершин, которые, можно найти за время 0(п3тр.

Из теоремы 4.1 следует следующая очевидная стратегия решения задачи (12). Вычисляем вершины многогранника В(/,а,Ъ) и среда них выбираем ту, на которой достигается максимум функции В• Отметим, что алгоритм, который вычисляет вершины В(/,а,Ь), для каждой вершины (А,В) е В(/,а,Ъ) также находит точку х с В(/), что (А.В) я (са.Ъх).

Другой подход к решению задачи (12) применим только тогда, когда функция в удовлетворяет некоторым дополнительным условиям. Предполагаем, что в является строго выпуклой функцией, и для простоты изложения считаем, что векторы а и Ь удовлетворяют следующему предположению о невырожденности:

(а1.Ъ1) + (aJ,Ьj), и е N. I * J. (14)

Здесь мы иакже считаем, что функция / целочисленна. >

С каждой точкой (А,В) из К3 свяжем орграф 0(А,В) с множеством вершин N и множеством дуг Е(А,В), которое определяется следующим образом: пара (1,Л € Е(А.В), если ( * J и выполняется следующее неравенство

< ви * аг аВ гу > в(А,В) (15)

Орграф О = (Н,Е) называется битурниром, если для каждой

пары различных вершин {,/«)/ существует одна или две дуга из Е, соединяющие { и Если сушестует две такие дуги, то они противоположно направлены. Если (,/ - две вершины битурнира и сушестует дуга, ориентированная от 3 к {, то будем говорить, что ( доминирует ].

Теорема 4.2. Для каждой точки (А,В) с К3 орграф 0(А,8) является битурниром.

Пусть в=(И.Е) - битурнир. Рассмотрим произвольную точку х с В(/) и пусть у = х + е{- е^ (говорим, что у получена элементарной трансформацей из точки х). Будем говорить, что точка у улучшает точку х, если вершина I доминирует вершину / в битурнире О.

Точку х е В(/) называем О-оптимальной, еоли /ез* ■ ~(В(/), х; л Е(ах,Ъх) л В = ф. Такую точку, если она существует, будем обозначать Здесь /ез**~(0,х):= С,: с ,

для I С I) £ 2П.

Теорема 4.3. Для любого битурнира С=(К,Е) многогранник В(/,) имеет не более одной ^-оптимальной точки.

Теорема 4.4. Пусть х* е есть оптимальное решение

* * *

задачи (4.1). Тогда х является 0(ах ,Ьг ^-оптимальной точкой.

В качестве следствия из теорем 4.2 и 4.4 получаем следующую стратегию решения задачи (4.1). Сначала определяем всевозможные различные битурниры 0(ах,Ъх) (х с В(/)). После этого находим их ^-оптимальные точки и среди них находим ту, которая доставляет максимум функции £. Следуя этой стратегии, мы разбиваем К3 на конечное число классов эквивалентности. Две точки (А,В) и (С,Б) принадлежат одному классу эквивалентности, еоли С(А,В) = а(С,й). Пусть

Q* = Í(A.B) : (А,В) € R2. G(A,B) = Oli, t =1,..w(g). (16)

Так как число различных битурниров 0(то рассмотренный выше подход применим только для тех функций g, для которых ы(8) не слишком велико. Одним из таких классов являются полиномы. Известно11, что в этом случае последнее число имеет порядок 0(dsnl), где d есть степень полинома g.

В пятом параграфе рассматривается минимаксная задача на базовом многограннике субмодулярной функции, которая формулируется следующие образом:

min жа (g,(x,)), (17)

xeB(f) Ulan 1 1

где / есть целочисленная субмодулярная функция, а действительные функции gt(xi) (i = 1,..,п,) в целых числах принимают целые значения. Пусть g(x) = maxíg^x^: i - 1,..,п). Для x e Zn введем следующее обозначение:

l!g(x) = (i e N: gt(xty= g(x)}.

Для решения задачи (17) мы предлагаем алгоритм бикоординат-ного спуска, который строит следующую итерационную последовательность:

xT+í = - е, ,

't Jt

где (tt, Jt) € /<>з+'~(В(Г),хг) и g(xU1) < в(хг) или g(xt+1) = 8(хг) и \Ng(xt+111. < INgfxb I.

nWarrenH.E. Low ¡r bounds íor approximation on onllnear manifolds. Trana ¿mer Math Soo 1968. V. 133. p. 167-178.

Теорема 5.1. Если все функции gt (I = 1,...,п) являются строго неубывающими, то алгоритм бикоординатного спуска строит оптимальное решение задачи (17) не более чем за пФ итераций, где Ф = max(g(x): х е B(f)J - mtn(g(x): х е B(f)).

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

В заключительном шестом параграфе мы рассматриваем субмодулярную задачу упорядочения. Пусть /(I) и g(I) - субмодуляр-

«7

ные функции на 2 , причем f(N) = О, g($) = О. Также предполагаем, что f(I) - невозрастаюцая, a g(I) - неубывающая функция (f(I) г f(J), g(I) s g(J), если Is J). На множестве Sn всех перестановок элементов множества 11 определим следующую функцию:

Ш) : = tflZl0 fWU) (gWH-lJ) - g(*tU))}. (18)

Рассмотрим задачу

mln{<b(7i): я е Sn). (19)

В диссертации показано, что к задаче (19) сводится ряд задач из теории расписаний и теории матроидов, с реди которых имеются и труднорешаемые.

Задачу (19) можно записать в следующей эквивалентной форме: mini 4>ofCJ : с £ С ) (20)

где С - (ф = CQ s Ci е ...с с^ = N) есть цепь, С - множество

и

всех цепей из 2 , а функционал Фо задаётся следующие образом

Vе-" = t(Cl> (8(Ct + 1) - g(Ct)) (21)

Предлагаем аппроксимировать задачу (20) следующей задачей: тШ У(С) : С е С ), (22)

где

КС) : = Е 1%~'-<Г (/(Си1) + /(С^) (8(Си1) - 8(С1)) (23)

Теорема 6.1. Пусть С1 и С3 соответственно оптимальные решения задач (20) и (22). Тогда

Ф гс3;

Г * 2.

Теорема 6.2. Задача (22) еквивалентна следующей параметрической задаче линейного программирования

. т1п Ху + (24)

Д -!/ « о, 8а- 2 « О V а е Бп,

О 4 4 1, { = 1.....П,

где параметр X принадлежит отрезку 10,11.

Так как задача (24) имеет экспоненциальное число ограничений, то мы снова предлагаем её решать двойственным симплекс-методом.

Теорема 6.4. Двойственно допустимое базисное решение (х,у,2) задачи (24) оптимально тогда и только тогда, когда

У.

а

8 2.

О £ х* 1, I - 1 а перестановка < определяется сортировкой компонент вектора х по невозрастанш

о*.....* •

12 п

В работе так же показано, как выбрать начальное двойственно допустимое решение и дано детальное описание реализации двойственного симплекс-метода применительно к задаче (24).

Основные выводы по работе. В диссертации получены следующие основные результаты:

1) введён и изучен новых класс полиэдральных игр - матричные игры с зависимыми стратегиями;

2) предложена модификация алгоритма Фудмшиге для минимизации субмодулярной функции;

3) для решения задачи максимизации субмодулярной функции разработан новый приближенный алгоритм, в основе которого лежит эвристика Кернигана и Лина;

4) доказано, что алгоритм бикоординатного спуска строит точку оптимума в минимаксной задаче о неубыващими критериями на обобщенном полиматроиде;

5) предложены два метода решения задачи максимизации специальной выпуклой функции на базовом многограннике субмодулярной функции;

6) субмодулярная задача упорядочения сведена к решению параметрической задачи линейного программирования на базовом многограннике субмодулярной функции.

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

1. Редди С.К. Полиэдральный игры о зависимым стратегиями // Материалы межреспубликанской научно-практической конференции творческой молодежи. Минск, 1990 г. с.286-287.

2. Писарук H.H., Редци С.К. Матричные игры с зависимым стратегиями. Вестник БГУ. Серия 1, 1991. е.44-47.

3. Редди С.К. Локальный алгоритм максимизации оубмодулярнай функции // Материалы межреспубликанской научно-практической конференции творческой молодежи. Минск, 1992 г. 0.171-172.

4. Редди С.К. Минимизация субмодулярной функции // Материалы межреспубликанской научно практической - конференции творческой молодежи. Минск, 1994 г.

Подписано к печати " " Мм_1994г. Формат 60x84/16.

Обем 1 п.л. Тираж 100 экз. Заказ N371? . Бесплатно. Отпечатано на ротапринте БГУ: Минск, ул. Бобруйнская 7.