Градиентный алгоритм для систем независимости с
отрицательными весами
И.В. Оффенбах, Омский государственный университет,
кафедра прикладной и вычислительной математики
1. Основные понятия
Пусть
E - конечное множество, - непустое
семейство его подмножеств. Семейство называется
системой независимости, если
Множества
семейства называются
независимыми множествами, а подмножества E, не вошедшие в семейство , -
зависимыми. Базой множества называется
любое максимальное по включению независимое подмножество F. Базы множества E
называются базами системы независимости. Множество всех баз будем обозначать . Введем
обозначения:
Числа
lr(F), ur(F) называются соответственно нижним и верхним рангом множества F.
Величина
называется
кривизной системы независимости (минимум
берется по всем ). Очевидно,
что для любой системы независимости .
Рассмотрим
задачу максимизации на системе независимости:
где
- семейство
баз системы независимости , а - аддитивная
весовая функция.
Для
решения задачи (1) применим следующий Алгоритм A:
Шаг
0: Упорядочить множество по
невозрастанию весов; ;
Шаг
i: . Если , то ; если i
Договоримся
далее через SA обозначать результат работы алгоритма A на системе независимости
, а через S0 -
базу максимального веса
Алгоритм
A в общем случае не находит оптимального решения и может рассматриваться лишь
как приближенный метод решения задачи (1). В связи с этим большой интерес
представляет получение оценок погрешности градиентного алгоритма.
В
работе [1] (см. также [2]) получена следующая нижняя оценка погрешности
градиентного алгоритма решения задачи (1).
Теорема
1 (Корте и Хаусманн). Пусть - произвольная
система независимости. Тогда для любой неотрицательной аддитивной весовой
функции задачи
максимизации (1) имеет место достижимая оценка
где
k - кривизна системы .
Cистема
независимости называется матроидом, если семейство ее баз
обладает следующим свойством:
В
дальнейшем нам понадобится следующая
Лемма
1.
Доказательство.
При lr(E)=ur(E) лемма, очевидно, следует из определения матроида.
Рассмотрим
случай lr(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|.
Если
не матроид, то
по лемме 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.
Для
подготовки данной работы были использованы материалы с сайта http://www.omsu.omskreg.ru/