Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 34
Текст из файла (страница 34)
Теорема 8,3. Пусть Вс — положительно определенная матрицп, 1 ~Я" и а — произвольный ненугевой и-вектор. Пусть В,ь, и 1 ~,. вычисляются согласно шагу 3 алгоритма эллипсоидов. Тогда справедливы следуюсцие утверждения. а) Матрица В лс положительно определена (или, что эквивалентно, множество Е,+,— — (хек": (х — (г„)'Вс+сс(х — 1 лс)<1) являепсся зллипсоидом). б) Пол узллипсоид (112) Е [а1=(хелло: (х — 1,)'В,'(х — 1,) <1, а'(х — Сз) <О) являепсся подлсножеством множгства Е „..
в) Объемы эллипсоидов Ел и Ел с удовлетворяют неравенству чо! (Ес с)/чо!(Е ) < 2-'с'со"с. Для доказательства теоремы 8.3 нам потребуются две вспомогательные леммы. Лемма 8.12. Рассмопсрим саар З„и множество Е= (х ~ Рос (х — 1)'В '(х — С)<1), где с=( — 1'(и+1), О, ..., О)' и В=с!!ай(п'I (и+1)', пЧ(по — !), ..., пЧ(п' — 1)). Тогда а) мптрицп В положительно определена ('и, следовптельно, Š— эллипсоид); б) полушар (1~2)Во — -- (х ~ Во: х'х<! и хс<0) является подмножеством множествп Е; в) объемы З„и Е удовлетворяют неравенству чо1 (Е)счо) (5„) < < 2-1Со Сол1) Доказательсспво.
а) В=Оссг, где З.Ч. Алгоритм вллипвоидов 1ВВ б) Пусть хб(1,'2) 5„. Тогда (х — 1)' В ' (х — !) = —, ~ х, + — ) -1- (п+ 1)в ! ! и пв — 1, пв — 1, 2п+2 в 2п 1-2 1 ~~'х,'=, х'х+ —,, х,'+ ., х,+ — пв( !=г (1+ —.. (х:+х1)< 2п+ 2 (поскольку Х~5„) поскольку Х ~ 2 5п) . 1 <1 лемме 8.9 чо! (Е)/чо! (5„)= де1 !г, где матрица !) та же, что Поскольку Д вЂ” диагональная матрица, то де1 (;! = „+п ! ( ~., ! ) в) По в и. а).
1+х<в", 1 — х <е " для всех х) О, то — =1 — — <е-а!ив*1, +1 п 1-1 и" — ! пв — ! Так как Поэтому де1!! <ехр( ', — — ) < 2-'!'1" *!., () 1,2 (ив — !) п-1-1) Доказательство. По условию матрица В! положительно определена н, следовательно, В1=!г!гг дЛЯ НЕКОтОРой невыРожденной матрицы 9. По лемме 8.10 су'ществует такое вращение Рг, что Рт!!та=(Ига!1, О, ..., 0)'. Определим преобразованне Т формулой Т(х)=11+ЯРХ.
Проверим все трн условия. а) Т (5„) = ( Т (х): х 'х < 1) = = (х: (Т '(х))' Т '(х) <1) = = (х: (х — ! )' Я ')гРРгО. '(х — ! )<1)= - ('! (х 1',) В; (, 1,) < 1). Лемма 8.13. Пусть  — положительно определенная матрица, 1л Е Р" и а — произвольный ненулевой п-вектор. П уыпь 1,„, и В ов вычисляются по формулам шага 3 алгоритма зллипсоидов, и пусть 1125„и Е определяются так же, как в предыдущей лемме. Тогда суи(ествует такое аффинное преобразование Т, что а) Т (5„) = (х Е Р": (х — 1 )' В,' (х — ! ) < 1); б) Т (Е)=(хб Р": (х — 1,,)' Вф (х — 1;о,) < 1)! в) Т (1125„) = (х с Р"' (х — !2)' В,. ' (х — 1 ) <!, а' (х — 1 ) < О) 186 Гл.
8. Алгоритма и сложность б) Вначале заметим, что гге ( 2 дД!1тдтаа дРРтдт~ аг — 1 ( г а-1-! а'ор1гтг)то (поскольку ВтЯта=(!1!'„!та!1, О, ..., О)') ггч — 1 ( Г а+1 ~в. гге ! В 01~ о!аа ((! От 1г О О) ктс)т 1дта)г — ~ В 2 (тхг 1)(аьо (1 0 0) Ртдт ае та — 1 цр(ВВтцт где В определяется так же, как в лемме 8.12. Кроме того, длит!)та х — (+,— — !х — 1,+ (а + 1) )Г но ь 11 т ге та / =(-'+ ' ' /= / 11+ ( +1!1!от /= =ДЯ (Т '(х) — 1). Поэтому Т (Е) = (Т (х) ! (х — 1)' В " (х — !) ( 1) = = (х: (т-'(х) — 1)' В- (т- (х) — 1) =а1) = = (х' (Х 1уьг) ((сг ) ЯВ Й гсг (Х 1гьг) » (1)= =(ы (Х вЂ” 1~ь,)' Вф (х — (у,) (1). в) Условие в) теперь легко следует из условия а) и леммы 8.8, если заметить, что Т ((х Е Ьа! х, (О)) = (х Е йа! а' (х — 1 ) ( О). () Доказательство тпеоремы 8.3, а)Согласно условию б) леммы 8ЛЗ, Т(Е)=Е,„;, кроме того, из утверждения а) леммы 8.12 следует, что Е=Т'($„) для некоторого аффинного преобразования Т'.
Поэтому Е!ь,=т Т'(Ва) — эллипсоид (композиция двух аффинных преобразований также является аффннным преобразованием). Г 1 б! Согласно условию в) леммы 8.13, Е [а1=Т! — 5„), и, согласно утверждению б) леммы 8.13, 1)25„= Е. Отсюда Е 1п1~ а т(е) =е„,.
в) В соответствии с леммой 8.9 и утверждением в) леммы 8.12 чо! (Е1ьг! чо1 (Т !Е)! де!(Яй) чо1 (Е) -Ые „+!) 6~г \ 6~г (Б В гц (ойдо " 3(ял Можно доказать также следующую лемму. 8.7. Алаэритм эллипсоид«э !87 Лемма 8.14. Если система СЛН размера Е имеет Ьаешение, то множество решений, лежащих внутри шара (х((п2, имеет объем, не меныиий чем 2 м+мс, Доказательапво. Мы знаем, что если неравенство Ах<Ь имеет решение, то имеется решение и для систе.лы неравенств Ах<Ь, х;<2с, 1=1, ..., и, Следовательно, в многограннике Ах<Ь, имеется внутренняя точка.
Тогда по лемме 8.11 он содержит и+1 линейно независимых вершин (с„, с„..., оэ ). Все внутренние точки выпуклой оболочки этих вершин являются решениями неравенства Ах Ь, лежащими внутри шара 11х1(п2с. Объем выпуклой оболочки равен —,(д!( ' ' ) ~0. Каждое с, можно записать в виде и«7Р«, где и, — целочисленный вектор и Р, — определитель, абсолютная величина которого не превосходит 2с. Поэтому объем выпуклой оболочки не меньше чем (п)П««1Р,()-«~2-мэ»)У (-) Теорема 8.4. Алгоритм зллипсоидов корректно распознает, имеет ли решение система СЛН.
Доказательство. Если алгоритм выдает некоторую точку 17 на шаге 2, тогда, очевидно, эта точка является решением. Предположим теперь, что алгоритм выдает «нет», а система имеет решение. По лемме 8.14 внутри шара Е,= (х Е 1«": х'В„'х<1) имеется множество Я решений, объем которого не меньше чем 2 '"+ 1«. По теореме 8.3 (п. 6)) 5 остается подмножеством Еэ для всех 1=0, ..., К.
Однако по теореме 8.3 (п.' в)) чо!(Е Др чо1(Е,)2 «/м"+м = <(2«п»2»с)" 2 «"с<2 ш'"с, поэтому 5 не может содержаться в Ек — противоречие. 8.7.4. Арифметическая точность. Остается последний вопрос, который нужно разрешить прежде, чем можно будет утверждать, что алгоритм эллипсоидов является полиномиальным алгоритмом для задачи о строгих линейных неравенствах и, следовательно, согласно теореме 8.2 и лемме 8.7, для ЛП. В отличие от всех остальных вычислений, обсуждавшихся в этой книге, алгоритм эллипсо- 188 Гл.
8. Алгоритмы и сложность идов нельзя выполнить с помощью арифметики целых или рациональных чисел. На это явно указывает квадратный корень в алгоритме на рис. 8.5. Следовательно, при любой реализации этого алгоритма на вычислительной машине нам придется приближать все променсуточные результаты рациональными числами, Это можно делать по следующей простой схеме. Любое действительное число х представляется двоичным целым числом с Р разрядами, умноженным на некоторую степень числа 2 (возможно, с отрицательным показателем); ближайшее к х рапиональное число такого вида обозначае1ся х. Пусть, например, Р=4.
Если 8=37, то х=9х2'= =36; если к=3.156, то х= !3 х2 '=3.25. Мы будем говорить, что наше вычисление производится с точностью Р. Допустим, что точность Р фиксированна. Легко видеть, что !х — хЯх((2 Р для любого действительного числа х; это условие можно записать следующим образом: х=х(1+02 ') для некоторого — 1 < 0 ( 1, или просто х = х (1 + 02 Р), (8.9) опуская явное задание границ для О.
В дальнейшем представление (8.9) будет использоваться очень часто. В тех случаях, когда оно будет записываться для вектора или матрицы, мы допускаем, чтобы 0 выбиралось различным для различных компонент. Будем выполнять алгоритм эллипсоидов с точностью Р. Произвольная арифметическая операция, вообще говоря, будет давать не точный результат г (сумму, произведение, квадратный корень и т, д.), а г — приближение г с точностью Р, Выполнение таких операций в том случае, когда аргуменгами являются приближения действительных чисел с точностью Р, состоит из двух шагов: выполнение операций (сложения, вычитания или сравнения) над двумя показателями степеней двойки и выполнение операции над двумя Р-разрядними целыми числами.
Например, сложение 9 х2'+ +13х2 '- выполняется следующим образом. Вначале сравниваем и вычитаем показатели степеней и обнаруживаем, что второй из них меньше на 4. Находим целое число, ближайшее к 13124, а именно 1. Прибавляем ! к 9 и получаем ответ г=!Ох2'. Проверяем условие 10)16, т. е. «переполнилось» ли наше Р-разрядное число, и, поскольку это условие не выполнено, выдаем !Ох 2'=40 в качестве результата.
Г1ервый шаг, т. е. сравнение, сложение или вычитание показателей, легко выполнйм. Показатель степени любого числа, появляющегося в алгоритме эллипсоидов, не превосходит экспоненты от Е. (Это следуег из того, что у нас полиномиальное (общее) число операций, и при каждой операции показатель увеличивается не более чем вдвое.) Поэтому если показатели также хранить в двоичном представлении, то первый шаг любой арифметической операции мож- В.7.
Алгор»тн ылипс»ив»в 189 но выполнить за время, полиномиальное относительно Е. Вь>волнение арифметических операций над двоичными целыми числами с Р разрядами на втором шаге можно произвести за 0(Р') элементарных двоичных операций с помощью хорошо известных методов, изучаемых в начальной школе. Возникаег вопрос, насколько большйм должно быть Р, чтобы алгоритм эллипсоидов оставался корректным. Если Р можно ограничить некоторым полиномом ог Е размера данной задачи, то окончательно можно утверждать, что алгоритм эллипсоидов полииомиален Вспомним алгоритм эллипсоидов. Он строит последовательность эллипсоидов Е,=(1„ В,), Е,=(1о В,), ...
для 1=0, 1, .... Величины 1>э, и В>э, вычисляются через 1> и В; по правилам = Р (1, В ), Вг~, =- О (1, В ), где Р и 6 — преобразования, заданные явно на рис. 8.5. Модифицированный алгоритм эллипсоидов для заданной точности Р также порождает последовательность эллипсоидов Е„'= Е„ Е;=(1;, В;" (1+6)'), ... и т. д., где 6) 0 нам нужно будет определить, а 1;„и В;„вычисляются по формулам 1';„, =Р(1;, В), В;„=6(1а В;). Крышки над Р и б указывают, что в производимых вычислениях все промежуточные результаты приближаются с точностью Р. Заметим, что 1;„и В;„вычисляются гак же, как в исходном алгоритме эллипсоидов; единственное отличие состои г в том, что в наше определение Е; мы добавляем дополнительный множитель (!+6) на каждом шаге, и поэтому наша оценка объема будет умножаться на каждом шаге иа (! +6)".
Грубо говыря, этот дополнительный множитель будет гарантировать, что е«ли Е; содержит множество 5 решений неравенства Ах(Ь, то э>о же справедливо и для Еп о и теорема 8.4 остается справедливой, несмотря на ошибки округления, порожденные вычислением с конечной точностью Заметим, что множители (1+6) не участвуют иа самом деле в вычислении; они используются просто в определении эллипсоидов Е;, участвующих в наших рассуждениях. Это можно сделать, поскольку формула для вычисления В„, через В> (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
