Градиентный алгоритм для систем независимости с отрицательными весами

И.В. Оффенбах, Омский государственный университет, кафедра прикладной и вычислительной математики

1. Основные понятия

Пусть E - конечное множество, - непустое семейство его подмножеств. Семейство называется системой независимости, если

Множества семейства называются независимыми множествами, а подмножества E, не вошедшие в семейство , - зависимыми. Базой множества называется любое максимальное по включению независимое подмножество F. Базы множества E называются базами системы независимости. Множество всех баз будем обозначать . Введем обозначения:

Числа lr(F), ur(F) называются соответственно нижним и верхним рангом множества F. Величина

называется кривизной системы независимости (минимум берется по всем ). Очевидно, что для любой системы независимости .

Рассмотрим задачу максимизации на системе независимости:

где - семейство баз системы независимости , а - аддитивная весовая функция.

Для решения задачи (1) применим следующий Алгоритм A:

Шаг 0: Упорядочить множество по невозрастанию весов; ;

Шаг i: . Если , то ; если i < n, то перейти на шаг i+1, иначе результат SA. Алгоритмы такого типа в англоязычной литературе имеют наименование greedy, что обычно переводится как жадный. Жадный алгоритм является дискретным аналогом градиентного алгоритма, поэтому его называют также градиентным алгоритмом.

Договоримся далее через SA обозначать результат работы алгоритма A на системе независимости , а через S0 - базу максимального веса

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

В работе [1] (см. также [2]) получена следующая нижняя оценка погрешности градиентного алгоритма решения задачи (1).

Теорема 1 (Корте и Хаусманн). Пусть - произвольная система независимости. Тогда для любой неотрицательной аддитивной весовой функции задачи максимизации (1) имеет место достижимая оценка

где k - кривизна системы .

Cистема независимости называется матроидом, если семейство ее баз обладает следующим свойством:

В дальнейшем нам понадобится следующая

Лемма 1.

Доказательство. При lr(E)=ur(E) лемма, очевидно, следует из определения матроида.

Рассмотрим случай lr(E)<ur(E). Пусть . Перенумеруем элементы и так, что если среди них есть одинаковые, то они имеют первые m номеров (), иначе m=0. Определим где r=ur(E).

Шаг 0: Am=A - база. Шаг i: . Am+i-1 - база, следовательно, множество независимо и не база. Если - не база, то мы нашли требуемые базы Am+i-1, B и элемент u=am+i. Иначе пусть - база. Переход на шаг i+1.

Учитывая, что A|B| зависимо (т.к. B - база и ), алгоритм завершится не позднее, чем на шаге |B|+1 доказательством леммы.

2. Характеристика и ее свойства

Фронтом данного независимого множества F назовем .

Fr(F) - это множество элементов, каждый из которых может быть добавлен к F без нарушения его независимости. Именно из этих элементов градиентный алгоритм выберет на очередном шаге самый "тяжелый" для добавления к F.

Введем новую характеристику системы независимости:

Она характеризует "узкое место" в работе градиентного алгоритма.

Будем называть предбазами максимальные по включению независимые множества, не являющиеся базами. Тогда определение (4) можно записать как

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

Теорема 2. 1) Для систем независимости , базы которых представляют собой все r-элементные подмножества (r-однородные матроиды),

где n=|E|, r=ur(E).

2) Для систем независимости, отличных от r-однородных матроидов,

Доказательство. 1) Очевидно, т.к. |Fr(F)|=n-|F|=n+1-ur(E) для любой предбазы F.

2) Если матроид (не r-однородный), то . Пусть F - база A. Т.к. |F|<|A|, то F не является базой матроида и .

Если не матроид, то по лемме 1 . Заметим, что .

Замечание. На различных системах независимости может принимать значения от 1 до n=|E| включительно, причем только в случае 1-однородного матроида.

Теорема 3 (оценка кривизны). Для любой системы независимости, отличной от 1-однородного матроида, имеет место оценка

Доказательство. Если система независимости представляет собой r-однороный матроид, , то k=1 и оценка (6) верна. Иначе , следовательно, и т.к. и (), то

Пусть дана система независимости , через (через ) обозначим такое минимальное число, что существует весовая функция , ровно () значений которой отрицательны, и SA (S0) содержит по крайней мере один элемент с отрицательным весом.

Теорема 4. для любой системы независимости .

Доказательство. Пусть . Присвоим элементам множества F0 вес |E|, элементам Fr(F0) вес -1, а остальным элементам вес 0. Тогда SA и S0 будут содержать элементы с отрицательным весом и, следовательно, и (всего отрицательных весов ).

Если число "отрицательных" элементов меньше , то SA и S0 не могут содержать элементов с отрицательным весом (для SA это очевидно. Если же S0 содержит "отрицательные", то рассмотрим подмножество его "неотрицательных" элементов C. В силу определения мы можем добавлять к C "неотрицательные" элементы, пока не получим базу, вес которой строго больше веса S0). Следовательно, и .

Замечание. Отрицательность здесь не играет принципиальной роли. Основной ее смысл в том, что выделяется класс "отрицательных" элементов, вес каждого из которых меньше веса любого "неотрицательного". К примеру, теорему 4 можно интерпретировать так: S0 и SA не содержат ни одного из наименьших по весу элементов.

3. Оценки погрешности градиентного алгоритма

Лемма 2. Пусть - произвольная система независимости, - весовая функция, допускающая отрицательные веса. Если при этом веса всех элементов SA неотрицательны, то справедлива оценка (2).

Доказательство. Рассмотрим новую задачу, в которой все отрицательные веса исходной задачи сделаем нулевыми, оставив тот же порядок элементов (для новой задачи используются обозначения c', S'A, S'0). Тогда S'A=SA, c'(S'A)=c(SA) и . А поскольку в новой задаче все веса неотрицательны, то теорема 1 справедлива и

Из теоремы 4 и леммы 2 непосредственно следует

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

Теперь рассмотрим ситуацию, когда нет ограничения на число элементов отрицательного веса.

Хорошо известна теорема Радо-Эдмондса, которая утверждает, что если система независимости является матроидом, то для произвольной неотрицательной весовой функции градиентный алгоритм всегда находит точное решение задачи (1). Нетрудно показать, что этот результат остается верным и для случая, когда допускаются отрицательные веса.

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

Теорема 6. Если система независимости отлична от матроида, то для произвольных существует такая весовая функция , что и . Причем, если , то существует с этим же свойством.

Доказательство. Так как отлична от матроида, то по лемме 1 , |B|=lr(E), и . Рассмотрим два случая:

1) . Среди всех баз, которые являются подмножествами выберем максимальную по мощности базу C. Присвоим всем элементам вес, условно говоря, , элементам вес , а элементу u вес . Если S0 содержит u, то , иначе, очевидно, . А т.к. , то нетрудно понять, что .

2) . Среди всех баз, которые являются подмножествами , выберем базу C, для которой минимальна. Пусть v произвольный элемент . Присвоим элементам вес , элементу u вес , элементу v вес , а всем остальным элементам вес 0 (в этом случае ). Т.к. минимальна, то любая база, веса отличного от и не содержащая u, содержит v, поэтому .

В обоих случаях можно так упорядочить элементы равного веса, что SA=A и .

Замечание. Задачу максимизации с весами можно интерпретировать как задачу минимизации с весами (весовой функцией c'(e)=-c(e)). Теорема 6 показывает, что для любой системы независимости, отличной от матроида, и задачи минимизации на ней (все веса неотрицательные) в принципе не может существовать гарантированной оценки погрешности градиентного алгоритма.

Списоклитературы

Hausmann D., Korte B. Lower bounds on the worst-case complexity of some oracle algorithms // Discrete Math. 1978. V.24. N 3. P.261-276.

Korte B. Approximative algorithms for discrete optimization problems // Annals of Discrete Math. Amsterdam: North-Holland. 1979. V.4. P.85-120.