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

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

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

1. Основні понятия

Пусть E — кінцеве безліч, — непорожнє сімейство його підмножин. Сімейство називається системою незалежності, якщо.

.

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

.

.

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

.

называется кривизною системи незалежності (мінімум з всім ). Вочевидь, що з будь-який системи незалежності .

Рассмотрим завдання максимізації на системі незалежності:

.

где — сімейство баз системи незалежності , а — аддитивная вагова функція.

Для виконання завдання (1) застосуємо наступний Алгоритм A:

Шаг 0: Впорядкувати безліч по невозрастанию терезів; ;

Шаг і: . Якщо , то ; якщо і < 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 — база. Крок і: . 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 містить «негативні «, то розглянемо підмножина його «неотрицательных «елементів З. З огляду на визначення ми можемо додавати до З «неотрицательные «елементи, доки одержимо базу, вагу якої суворо більше ваги S0). Отже, і .

Замечание. Заперечність не грає принципової ролі. Основний вона має сенс у цьому, що клас «негативних «елементів, вагу кожного з котрих значно менша ваги будь-якого «неотрицательного ». Приміром, теорему 4 можна інтерпретувати так: S0 і SA не містять жодного з найменших по вазі елементів.

3. Оцінки похибки градиентного алгоритма

Лемма 2. Нехай — довільна система незалежності, — вагова функція, яка припускає негативні ваги. Якщо за цьому ваги всіх елементів SA неотрицательны, то справедлива оцінка (2).

Доказательство. Розглянемо нове завдання, коли всі негативні ваги вихідної завдання зробимо нульовими, залишивши хоча б порядок елементів (для нового завдання використовуються позначення з ", P. S «A, P. S «0). Тоді P. S «A=SA, з «(P.S «A)=c (SA) і . Позаяк у новій завданню все ваги неотрицательны, то теорема 1 справедливою є.

.

Из теореми 4 і леми 2 безпосередньо слід.

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

.

Теперь розглянемо ситуацію, коли немає обмеження на число елементів негативного ваги.

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

Однако з такої теореми випливає, що й система незалежності відрізняється від матроида, то загальному разі неможливо отримати оцінку похибки градиентного алгоритму.

Теорема 6. Якщо цю систему незалежності відрізняється від матроида, то тут для довільних існує така вагова функція , що і . Причому, якщо , то існує з цим самим властивістю.

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

1) . Серед усіх баз, що є подмножествами виберемо максимальну за проектною потужністю базу З. Дамо всім елементам вагу, умовно кажучи, , елементам вагу , а елементу u вагу . Якщо S0 містить u, то , інакше, очевидно, . А т.к. , неважко зрозуміти, що .

2) . Серед усіх баз, що є подмножествами , виберемо базу З, на яку мінімальна. Нехай v довільний елемент . Дамо елементам вагу , елементу u вагу , елементу v вагу , а всім іншим елементам вагу 0 (у разі ). Т.к. мінімальна, то будь-яка база, ваги відмінного від і що містить u, містить v, тому .

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

Замечание. Завдання максимізації з вагами можна інтерпретувати як завдання мінімізації з вагами (ваговій функцією з «(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.

Для підготовки даної роботи було використані матеріали із сайту internet.