ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2012, том 52, № 1, с. 153-163
УДК 519.7
НОВАЯ МОДИФИКАЦИЯ МЕТОДА ДВОЙНОГО ОПИСАНИЯ ДЛЯ ПОСТРОЕНИЯ ОСТОВА МНОГОГРАННОГО КОНУСА1)
© 2012 г. Н. Ю. Золотых
(603950Нижний Новгород, пр-т Гагарина, 23, Нижегородский гос. ун-т) e-mail: Nikolai.Zolotykh@gmail.com Поступила в редакцию 01.03.2011 г. Переработанный вариант 27.07.2011 г.
Предлагается новая модификация метода двойного описания для построения остова многогранного конуса. Теоретические результаты и вычислительный эксперимент показывают значительное превосходство в быстродействии предлагаемых модификаций по сравнению с исходным алгоритмом. Библ. 18. Табл. 3.
Ключевые слова: полиэдр, многогранный конус, остов конуса, выпуклая оболочка, метод двойного описания.
ВВЕДЕНИЕ
Известно, что каждый полиэдр в [ можно представить любым из следующих двух способов:
1) как множество решений некоторой системы линейных неравенств;
2) как сумму (по Минковскому) конической оболочки некоторой системы векторов u1, u2,..., un и выпуклой оболочки некоторой системы точек v1, v2, ..., vkв [ .
Если полиэдр телесен, то неприводимая система линейных неравенств для этого полиэдра определяется единственным образом с точностью до умножения каждого неравенства на положительные константы, при этом каждому неравенству соответствует фасета (грань максимальной размерности). Далее, если полиэдр не содержит ненулевых аффинных подпространств, то неприводимые порождающие системы векторов u1, u2, ., un и точек v1, v2, ., vk определяются единственным образом с точностью до умножения векторов u1, u2, ..., un на положительные скаляры. При этом v1, v2, ..., vk суть вершины полиэдра, а u1, u2, ..., un — его экстремальные рецессивные лучи. Задача построения неприводимого представления способом (2) по представлению способа (1) называется, допуская некоторую вольность речи, задачей нахождения вершинного описания. Обратная задача — задачей нахождения фасетного описания или задачей построения выпуклой оболочки. Согласно классической теореме Вейля, любая из этих двух задач не более чем за линейное время сводится к обратной (двойственной).
Аналогично, каждый полиэдральный конус в [ можно представить любым из следующих двух способов:
1) как множество решений некоторой однородной системы линейных неравенств;
2) как множество всех неотрицательных комбинаций некоторой системы векторов
Неприводимая система векторов, множество неотрицательных комбинаций которой есть заданный конус, называется остовом. Если конус острый (т.е. не содержит ненулевых подпространств), то остов конуса определяется единственным образом с точностью до умножения векторов на положительные скаляры и образует множество экстремальных лучей конуса.
Существует стандартный способ свести задачу построения вершинного/фасетного описания для полиэдров к соответствующей задаче для полиэдральных конусов. Например, для нахожде-
Работа выполнена при финансовой поддержке РФФИ (код проекта 09-01-00545-а).
ния вершинного описания полиэдра {х е К : Ах > Ь} достаточно решить аналогичную задачу для конуса {(х, хл +1) е К : Ах — Ьхл +1 > 0, хл +1 > 0} и затем положить хл +1 = 1.
Указанные задачи возникают во многих приложениях: компьютерной графике, физической симуляции, обработке изображений, картографии, вычислительной биологии, теоретической физике и многих других. К построению фасетного описания (выпуклой оболочки) могут быть сведены задачи построения триангуляции Делоне и диаграммы Вороного (см. [1]).
В настоящее время не известно, существуют ли алгоритмы, решающие поставленные задачи, время работы которых было бы ограничено полиномом от суммарной длины входа и выхода. Более того, ни один из известных алгоритмов таковым не является (см. [2]). С другой стороны, данные задачи возникают во многих приложениях и необходимы быстрые практические алгоритмы их решения.
В работе рассматривается классический метод "двойного описания" (см. [3]) (другое распространенное название — алгоритм Моцкина—Бургера), решающий поставленные задачи. Разными авторами предлагались различные улучшения этого метода (см., например, [4]—[13]).
Метод двойного описания относится к классу "инкрементных" и основная его идея заключается в следующем. Пусть рассматривается задача построения вершинного описания полиэдра {х : Ах < Ь}. Вначале задача решается для некоторой подсистемы системы Ах < Ь (например, для одного неравенства или подсистемы ранга d). Далее в эту подсистему добавляются одно за другим все неравенства исходной системы, при этом вершинное описание каждый раз пересчиты-вается. Название метода "двойного описания" объясняется следующим образом. На каждой итерации поддерживаются два описания текущего полиэдра: вершинное и фасетное, — и вся другая необходимая информация вычисляется по ним, в частности вычисляется множество всех ребер текущего полиэдра. Пусть на текущей итерации добавляется неравенство ах < р. Множество вершин нового полиэдра состоит из вершин текущего полиэдра, координаты которых удовлетворяют этому неравенству, а также из точек пересечения его ребер с гиперплоскостью ах = р.
В отличие от других инкрементных алгоритмов, метод двойного описания не пересчитывает полную решетку граней текущего полиэдра, как, например, метод "под—над" (см. [1]), или метод Шевченко—Чиркова (см. [12]), а также не использует триангуляций, как, например в [13]—[15]) и др. Заметим, что размер полной решетки граней и размер триангуляции может суперполиномиально зависеть от суммарного размера входа и выхода (см. [2]), поэтому метод двойного описания часто опережает по скорости работы другие алгоритмы, в частности, на крайне вырожденных задачах. (Задача нахождения вершинного описания вырождена, если существует вершина, инцидентная более, чем d фасетам.)
Одним из "узких мест" метода является вызываемая на каждой итерации процедура нахождения множества ребер текущего полиэдра. Для этого обычно для каждой пары его вершин проверяется какое-либо необходимое и достаточное условие их смежности. Известны два из них: алгебраический и комбинаторный тесты. Как правило, на практике комбинаторный тест работает значительно быстрее алгебраического. Мы предлагаем новую ускоренную модификацию комбинаторного теста, названную нами "графовой". Другое улучшение связано с уменьшением количества рассматриваемых пар вершин при проверке их на смежность. В [11] замечено, что не все ребра текущего полиэдра приводят на поздних итерациях к порождению новых вершин и показано, как на этой основе можно существенно снизить объем используемой памяти и время работы. Мы развиваем эту идею и применяем ее для модификации метода двойного описания с динамическим порядком добавления неравенств. Теоретические результаты и вычислительный эксперимент показывают значительное превосходство в быстродействии предлагаемых модификаций по сравнению с исходным алгоритмом и другими модификациями, например, [11].
Для определенности будем рассматривать задачу построения остова многогранного конуса, заданного однородной системой линейных неравенств Ах > 0. Ограничимся случаем острого конуса. Задача для произвольного конуса легко сводится к данной путем перехода из исходного
пространства [ в ортогональное дополнение к подпространству {х е [ : Ах = 0}.
Необходимые определения и обозначения мы вводим в разд. 1. Схема метода двойного описания представлена в разд. 2. В разд. 3 мы рассматриваем ряд известных способов добавления не-
равенств исходной системы. Разд. 4 и 5 посвящены двум важным процедурам в методе двойного описания. В разд. 4 рассматриваются известные способы проверки смежности экстремальных лучей многогранного конуса и предлагается новая, графовая, модификация этого теста. В разд. 5 описаны некоторые способы уменьшения количества генерируемых пар смежных экстремальных лучей и предлагаются новые методы для решения этой задачи. В разд. 6 кратко описывается программа SKELETON, в которой реализованы предлагаемые модификации, и приводятся результаты вычислительных экспериментов.
1. ОБОЗНАЧЕНИЯ И ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
Ниже используются результаты из [7], [16]. Многогранным конусом в пространстве Кй (далее просто конусом) называется множество
С = {х е К : Ах > 0},
п~ът х й
где А е К — вещественная матрица размера т х а. Говорят, что система линейных неравенств Ах > 0 определяет конус С. Конус называется острым, если он не содержит ненулевых подпространств. Известно, что для того, чтобы конус С был острым, необходимо и достаточно, чтобы гапкА = а, где гапкА обозначает ранг матрицы А. Любой многогранный конус С может быть задан
в виде конической оболочки некоторой конечной системы векторов и1, и2,..., иппространства К , т.е. С = {х = а1и1 + а2и2 + ... + апип : а;-> 0,1 = 1, 2, ..., п}.
Говорят, что система векторов и1, и2, ..., ип порождает конус С.
Ненулевой вектор и е С назовем лучом конуса С. Два луча и и V будем называть равными и записывать и — V, если для некоторого а > 0 верно и = а^ Луч и е С называется экстремальным, если из условий и = аv + р^, а > 0, р > 0, V, w с С, следует и — V — w. Множество экстремальных лучей острого конуса является его минимальной порождающей системой и называется остовом
конуса. Пусть Р — выпуклое подмножество в К и для некоторых а е К , а е К верно, что Р с с {х : ах < а}, тогда Р п {х : ах = а} называется гранью множества Р. Два экстремальных луча и и V острого конуса С называются смежными, если минимальная грань, содержащая оба луча, не содержит никаких других экстремальных лучей конуса. Остов конуса С будем обозначать через и(С), а множество всех пар {и, V} смежных экстремальных лучей — через Е(С).
Если А е К'" , г е {1, 2, ..., т}, К с {1, 2, ..., т}, то через аг обозначена г-я строка матрицы А, а через АК — подматрица матрицы А, составленная из строк аг, где г е К. В выражениях вида ах, где
а е К , х е К , вектор а следует интерпретировать как вектор-строку, а х — как вектор-столбец.
2. МЕТОД ДВОЙНОГО ОПИСАНИЯ
Основная идея метода двойного описания (см. [3]) для построения остова многогранного ко-
п~т>а х п
н
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.