Н.М. Новикова - Дискретные и непрерывные задачи оптимизации, страница 6

имеет точное решение хе. Локязятелъотво. Обозначим через с' минимальное с, при котором система (1,) имеет решение (по условию с' < е~): с* =' пцп с. (ал): Я~5ВФае Попустнм, что утверждение теоремы не верно, тогда с* > О. Задача определения с' является (с учетом равенства тш() = — твл(- )) озЛП с пелевым вектором с = (О,...,О, — 1), п+1 переменными (х,с) н ограничениями Ах — се < 6. Следовательно, по теореме 1 с' может быть представлена в виде дроби со знаменателем, не превышавшим Ь((А] — е]) < (в+ 1)Ь(А), т.е. с* > 1Д(п+ 1)Ь(А)] > с~ — пришли к противоречию с определением с*. Аналогичное утверждение справедливо и для озЛП. Опгнднлкник 2. Точка х,' называется с-приближенным решением озЛП (2), если она является с-приближенным решением системы (1) н реализует максимум в (2) с с-точностью: (а;,х,') < 6;+с % = 1,пз в (с,х,') > Ы' — е.

ТеОРемА 2 ' (о мере вссоемссшиосши). Если озЛП (2) имеет сзприближенное решение для сз = 1/(2пзЬз(А)), то зта задача имеет точное решение х'. Локазаткльство см. в (3, с. 21]. 28 Ьб. Метод зллжпсоидов Полиномиальный алгоритпм округления ет-приближенного решения систпемы линейных нерввенстпв. Метпод эллипсоидов езприближенного решения оэЛЛ. Опенка сложности метпода эллипсоадов. По*иномиальностпь ЛП. 1. Имея е-приближенное решение (1) с е < еы можыо (на основании теоремы 2, $5) быть уверенным в существовании точного решения системы линейыых неравенств. Оказыватся, процедура получеыия хо из х" является полиномиальной.

Соответствующий алгоратпм округления ет-приближенного решения системы (1) до точного был указан Л. Г. Хачияном и состоит в следующем. Присвоим хт ох х" и подставим х' в (1). Разобьем множество М = (1,..., тп) индексов неравенств в системе на два подмножества М(х') =' (т: [(а;, х1) — Ьт[ < ет), М 1М(хт) =' (т: (апхт) — Ь; < — ет). Найдем решейие х" системы равенств Ам( т1х = Ьм(в 1 (существует по теореме 2). Пусть х" не является точным решением (1), т.е. в х" не выполнилось т-е неравенство для какого-либо т ф М(х').

Тогда введем множество индексов невыполненных неравенств М+ = (т[ (а;, х'т) ) Ь;) С М 1М(х') и рассмотрим ыа отрезке [х', х"] ближайшую к хт точку, в которой еще выполнены все неравенства для т' Е М+ (в х' онн выполнены с ет-запасом). А именно определим и прысвоим х оп (1 — г)х' + гх". Имеем М(х ) Э М(х') ~фМ+, ибо неравенства с индексами из М(х') ет-приближенно выполнялись как равенства на всем отрезке [х', х'т), а ыеравенства с индексами из М+, не выполненные в точке х", выполняются в х по построению.

Таким образом, М(хз) Э М(хт), но [М(х)) < нт, поэтому, повторяя указанную процедуру с заменой х' ыа хз и т.д., придем не более чем через шах(п, тп) шагов к тому, что решение х' соответствующей системы равенств окажется хо — решением (1). С учетом полиыомнальности решения систем уравнений предложенный алгоритм округления полиномиален. 29 Аналогичный алгоритм имеется и для округления сз-приближенного решения озЛП х,', до точного х' (см. (3, с. 21]). Поэтому для построения полиномиального алгоритма решения озЛП осталось указать полнномиальный алгоритм поиска сз-приближенного решения озЛП в шаре ОхО <»'7~А или удостоверения, что такого решения нет (по теоремам 1,2' из зб).

Требуемый алгоритм, основанный на мешодс элли»совдое, который предложили в 1976-77 гг. Д. Б. Юдин и А. С. Немировский и (независимо) Н. 3. Шор, приводится в следу'ющих пунктах. Здесь и далее Ь =' Ь(О), где матрица О задается таблицей (3). 2. Пусть Š— произвольный эллипсоид в Ва с центром с и ненулевого объема чо1 Е. Рассмотрим (» — 1)-мерную плоскость, заданную вектором у нормали и проходящую через центр с эллипсоида Е. Обозначим через Е (у) один из двух полуэллипсоидов, на которые разбивает Е данная плоскость, Е (д) = Е П (х~ (у, х — С) < 0). УтвеРжденне 1. Полуэллипсоид Е (у) эллипсоида Е можно целиком заключить в новый эллипсоид Е', имеющий объем, строго меньший Е, чо1Е' — <е 'Л "+1, (*) чо1Е и Е' можно вычислить по Е (у) за 0(»з) арифметических операций.

Доказатндьство. Пусть Š— единичный шар с центром в точке 0: Е = (х б Не: 'ОхО < 1), а Е (у) = Ей(х„> О). Поместим центр Е' в точку Е = (О,..., О, „+', ), тогда Е' = (х~ (х, +... + х„,)/ф + (х„— — ) /а < 1), »+1 где а =' 1 — 1/(»+ 1) < с ~Л"+11, 17з =' 1+ 1/(»з — 1) < е171" Отношение объемов равно произведению полуосей ар" ' < с 'Лз" +з1, отсюда получаем (ч), ибо любой зллипсояд можно превратить в шар афинным преобразованием координат, сохраняющим объем.

Действительно, будем представлять произвольный эллипсоид Е с помощью его центра с и матрицы Я (» х»), задающей укаэанное преобразование: Е = (х) х = С+ (~у, Оуй < 1). Обозначим и =' Я~у/О(~~уО, где верхний индекс — знак транспонирования. Тогдас' и Я', представляющие эллипсоид Е' минимального объема, описанный вокруг 30 полуэллипсоида Е (о), пересчитываются по формулам ( г+(, " 1 1)1) т) »+1 ' /( 3 — 1) у и+1 за О(»з) арйфметических операций. 3. Метод эллвпсовдое полученвя е-првблвженноео решенно озЛй. Положим е:= ез — — 1/(2»~Ь~). Введем мыожестео еприближенных решений озЛП в щаре радиуса В =' и'1зЬ с цеытром в О: Х; = (х/ (а;,х) < Ь;+е Ч1 = 1,гп, (сх) > Н' — е, ЦхЦ < В). Выберем указанный выше шар в качестве начальной итерации для эллипсоида Е Э Х;.

Рассмотрим произвольную итерапию. Проверяем, является ли центр б эллипсоида Е е-приближенным решением. Если да, то алгоритм закаычивает свою работу, в противном случае строим эллипсоид Е' для очередной итерации как минимальный по объему эллипсоид, содержащий полуэллипсоид Е (о) (см. п.2), где вектор у определяется следующим образом. Так как с ф Х;, то либо 1о) Лв': (а;, () > Ьс + е, и тогда о эп а;, либо 2 ) (с, б) < д" — е и о еп -с. Убедимся, что при этом Х," С Е'. Лействительно, для варианта 1е Ух б Х; (а;, х) < Ь; + е < (а;,с), т е.

Х; С Е П (х~ (а;, х — с) < О) = Е (а;) С Е', и аналогично получим для варианта 2о ~, > г,/' Х; С Е й (х~ (с, х — 4) > О) = Е ( — с) С Е'. з д Теперь с Е зв Е' возвращаемся к началу итерации (на новый шаг). Оценим число итерапий метода эллипсоидов. Покажем, что Х; содержит шар радиуса г/2, где г =' е/(Ьп'уз) < В, Ь > ~а;.~, ~су~ (Ь— оысогла задача).

Пусть х' — точное решение в Х;. Из Цх" — хЦ < г следует ~(апх) — (ачх')~ < Ца;Ц Цх' — хЦ < Ьп'~~г = е гэ б М и )(с, х) — (с,х')) < ЦсЦ Цх' — хЦ < Ьп'~~г, тегуквзанный выбор г гарантирует, что все такие х будут е-приближенными решениями. Поскольку Цх'Ц < В, то множество тех нз рассматриваемых х, для которых ЦхЦ < В (т.е. пересечение шаров радиуса г и В, включающее центр первого), содержит шар радиуса г/2. Этот шар и принадлежит Х;,.

Таким образом, объем Х; больше объема»-мерного 31 шара радиуса г/2. Значит, объем эллипсонда, построенного последним, например Еь для й-й итерации, не должен оказаться меньше объема этого шара. Отсюда и иэ утверждения 1 получаем для й соотношение ( — ") — — "." — — ",:" 2Я чо!Е' чо!Е' из которого й (по определейию г, Я, с, Ь н Ь) не превосходит 2вз 1п(ЛвЬ/с) < 2вз!п(2вз зЬз) < 10вз 1п(вЬ). УПРАЖНЕНИЕ 6. Одевать по поридку битовую длину Ь входа оэЛП: доказать, что Ь ) О(!п(вЬ)).

Следовательно, число итераций метода эллипсоидов й < О(в~)Ь, и с учетом 0(аз + ввз) арифметических операций для каждой итерации получим оценку О(вз(в+аз)Ь) для числа арифметических операций, достаточного методу эллипсоидов при поиске сз-приближенного решения озЛП. Алгоритм округления сз-приближенного решения до точного этой оценки не портит (см. (3, с. 21]). Можно также показать, что при реализации метода эллипсоидов и алгоритма округления все арифметические операции достаточно проводить с числами двоичной длины, ограниченной 0(Ь). При этом ошибки, возникающие за счет конечности числа разрядов (ошибки округлений), поглошаются путем некоторого дополнительного увеличения ("раздутия") описанного эллипсоида Е' на каждой итерации (3, с.

24), что не влияет на порядок оценки для обшего числа итераций. В результате временная сложность такой процедуры решения озЛП оказывается полиномом от длины входа и справедлива ТЕОРЕМА 3. Задача ЛП с целыми коэффициентами разрешима за полиномиальное от длины входа время. Следствием данной теоремы является Утнегжцение 2. ЛН 6 Р. Подчеркнем, что несмотря на доказанную полиномиальность, метод эллипсоидов не может конкурировать с симплекс-методом при практическом решении задач ЛП (реально он применяется в выпуклом квадратичном программировании), поскольку полученная оценка числа его итераций достигается на любых индивидуальных 32 задачах, даже если в качестве начального приближения взять решение.

Тогда как симплекс-метод для "хороших" (невырожденных) задач дает опенку 0(пз), на порядок меньшую, чем метод зллипсоидов, и за одну итерацию может подтвердить, что начальное приближение является решением. Тем не менее сам факт полиномиальности ЛП инициировал поиск новых методов ЛП, что привело к созданию целого класса эффективных методов математического программирования — методы впутргиигй точки — и пойволило построить конкурентоспособные полиномиальные алгоритмы ЛП. Идея их построения будет изложена в следующем параграфе, где также приводятся необходимые сведения по теории ЛП, начинал с ЛН.