О динамической задаче построения остова полиэдрального конуса

Основные понятия и обозначения

Любой выпуклый полиэдр (многогранник) в Q d может быть представлен в двух видах:

Вершинное описание - как сумма по-Минковскому выпуклой и конической оболочек конечных систем векторов:

P = conv{ v i , v 2 , ..., V k } + cone{ u 1 , u 2 , ..., U p }, V i e Q d , i = 1, 2, ..., k , U j e Q d , j = 1, 2, ..., p.

Фасетное описание - как множество решений конечной системы линейных неравенств:

P = { x e Q d : Ax >  b }, A e Q m ^x d , b e Q m .

Ограниченный выпуклый полиэдр называется политопом.

Частным случаем выпуклого полиэдра является полиэдральный (многогранный) конус, который может быть представлен как коническая оболочка конечной системы векторов и как множество решений конечной однородной системы линейных неравенств. Неприводимая порождающая система векторов многогранного конуса называется его остовом. Обозначим U ( C ) остов конуса C .

Задача перехода между вершинным и фасетным описаниями выпуклого полиэдра (построение одного описания по заданному другому описанию) называется задачей построения двойственного описания полиэдра. Частным случаем данной задачи являются задачи построения выпуклой оболочки и нахождения общего решения системы линейных неравенств. Задача построения двойственного описания полиэдра является одной из центральных в теории систем линейных неравенств [1-4]. Известно множество алгоритмов решения данной задачи [5-10] и близких к ней задач, включая вопросы трудоемкости и организации параллельных вычислений [11-14]. Задача построения двойственного описания выпуклого полиэдра в Q ^d сводится к аналогичной задаче для полиэдрального конуса в Q d ⁺¹ (см., например, [4]). В дальнейшем изложении для краткости под полиэдрами и конусами понимаются, соответственно, выпуклые полиэдры и полиэдральные конусы.

Пусть A e Q m ^x d . Обозначим A ( I) , где I c {1, 2, „., m }, подматрицу матрицы A , составленную из строк с номерами из I .

Постановка задачи

В работе рассматривается следующая задача, тесно связанная с задачей построения двойственного описания. Заданы неприводимые вершинное и фасетное описания полиэдрального конуса C 0 в Q d :

C 0 = { x ∈ ℚ ^d : Ax ≥ 0} = cone{ u 1 , u 2 , …, u p }, A ∈ ℚ ^{m × d} , u i ∈ ℚ ^d , i = 1, 2, …, p .

Требуется выполнить последовательность из N операций над конусом C 0 , обозначим C k конус, полученный в результате выполнения операции с номером k ( k = 1, 2, …, N ). Рассматриваются операции двух типов:

• 1.    Пересечение текущего конуса с заданным полупространством:

• 2.    Удаление неравенства из фасетного описания текущего конуса [15]. Пусть C k– 1 = { x ∈ ℚ ^d : A k– 1 x ≥ 0}, где матрица A k– 1 имеет m k строк. Задается номер удаляемого неравенства i k (1 ≤ i k ≤ m k ). Результатом операции является конус

C k = { x ∈ C k– 1 : a k x ≥ 0}. (1)

C k = { x ∈ ℚ ^d : A k x ≥ 0}, A k = A k– 1 ({1, 2, …, m k } \ { i k }), ⁽²⁾ где матрица A k состоит из всех строк матрицы A k– 1 , за исключением строки с номером i k .

В результате выполнения каждой из указанных операций требуется получить неприводимые вершинное и фасетное описания конуса C_k . Таким образом, операция (1) соответствует добавлению неравенства к фасетному описанию конуса, а операция (2) – удалению неравенства из фасетного описания, в обоих случаях производится перестройка остова. Отметим, что требование неприводимости описаний конуса может быть ослаблено для операции (1), однако является существенно важным для операции (2), как показано в [15]. Предполагается, что порядок выполнения операций фиксирован.

Необходимость выполнения подобных операций может возникать в некоторых задачах автоматического анализа и верификации программ для ЭВМ с использованием полиэдральных подходов [15–17]. При этом отметим, что в настоящей работе задача исследуется только с теоретической точки зрения.

Аналогичная задача для выпуклого полиэдра в ℚ ^d сводится к случаю конуса в ℚ ^{d +1}. Рассматриваемая задача построения остова конуса в дальнейшем называется динамической по аналогии с динамической задачей построения выпуклой оболочки точек, множество которых может меняться путем добавления или удаления точек в процессе работы. Дальнейшее изложение производится для случая конуса. Для простоты предполагается, что исходный конус и все промежуточные конусы являются острыми: rank( A_k ) = d , k = 1, 2, …, N , в этом случае векторы остова определяются единственным образом с точностью до умножения на положительные скаляры (см., например, [4]).

В разделе 2 рассматривается операция добавления неравенства к фасетному описанию конуса с помощью метода двойного описания, приводятся оценки трудоемкости. Раздел 3 посвящен операции удаления неравенства из фасетного описания и анализу зависимости размера выхода от размера входа.

Операция добавления неравенства к фасетному описанию конуса

Рассмотрим выполнение операции (1), состоящей в добавлении нового неравенства к фасетному описанию многогранного конуса с перестройкой остова. Данная операция возникает в инкрементных (по классификации [18]) алгоритмах построения двойственного описания полиэдра. В связи с тем, что для всех промежуточных конусов известны неприводимые вершинное и фасетное описания, целесообразным представляется использование метода двойного описания [5], иногда также называемого алгоритмом Моцкина–Бургера [19] или алгоритмом Черниковой [6]. Существует множество модификаций метода, например, [20–22]. В настоящем разделе приводится краткое описание метода в контексте выполнения операции добавления неравенства. В связи с этим не рассматривается начальный шаг метода, а также порядок обработки неравенств, который может существенно влиять на трудоемкость метода двойного описания в общем случае (см., например, [18, 20]).

На каждом шаге метода двойного описания выполняется пересечение текущего конуса с полупространством, определяемым очередным обрабатываемым неравенством. В начале шага известны вершинное и фасетное описания текущего конуса C k– 1 , а также множество E ( C k– 1 ) пар смежных векторов его остова. В конце шага те же данные определяются для конуса C k . Таким образом, шаг метода двойного описания соответствует операции (1).

Рассмотрим выполнение одного шага метода. Остов конуса C_k- 1 разбивается на три подмножества в зависимости от того, выполняется ли для них добавляемое неравенство:

U + = { u e U ( C_k- 1 ): a_k u > 0}, U 0 = { u e U ( C_k- 1 ): a_k u = 0}, U - = { u e U ( C_k- 1 ): a_k u < 0}. Строятся комбинации пар смежных векторов из U + х U - :

U ± = {( au ) v + ( -av ) u : u e U + , v e U - , { u , v } e E ( C_k- 1 )}.                  (3)

Искомый остов конуса С определяется следующим образом:

U(C k ) = U + и U 0 и U ± .                              (4)

Информация о смежности векторов остова конуса C_k определяется следующим образом. Все пары векторов из множества U + , являющиеся смежными в конусе C_k- 1 , являются смежными и в конусе C_k . Таким образом, смежность необходимо определить для векторов из множества U ₀ и U ± . Для каждого вектора u хранится множество Inc ( u ) номеров неравенств, определяющих конус, которые удовлетворяются этим вектором как равенства.

Известны несколько критериев того, является ли пара векторов остова { u , v } смежной:

• 1.    Алгебраический критерий [5]: rank(A( Inc ( u ) n Inc ( v ))) = d - 2.

• 2.    Комбинаторный критерий [17]:

• 3.    Графовый критерий (графовая модификация комбинаторного критерия) [22]. Определим неориентированный граф G = ( V , E ) следующим образом: V = U ₀ и U ± , E = {{ u , v }: u , v e V , |Inc ( u ) n Inc ( v )| >  d - 2}. Тогда критерий смежности пары имеет вид:

$ w e U ₀ и U ± : w + u , w ^ v , Inc ( u ) n Inc ( v ) c Inc ( w ).

• $ w e U ₀ и U ± : w # u , w ^ v , { u , w } e E , { v , w } e E , Inc ( u ) n Inc ( v ) c Inc ( w ).

• 4.    Критерий на основе k -мерных деревьев [21].

Условие | Inc ( u ) n Inc ( v )| >  d - 2 является необходимым (но в общем случае не достаточным) для смежности пары { u , v }.

Обозначим T _add( C_k- 1 ) трудоемкость выполнения шага метода двойного описания для текущего конуса C_k- 1 . В качестве меры трудоемкости будем использовать количество арифметических операций над целыми числами, вопросы о битовой сложности и росте коэффициентов рассматриваются, например, в [3]. Для изложенного алгоритма справедливы следующие верхние оценки трудоемкости.

Утверждение 1 [23]. Трудоемкость шага метода двойного описания для текущего острого конуса C_k- 1 составляет:

• •    T add ( C k -i ) e O (| U ( C_k _1 )p(| U ( C_k _i )| + d ) + | U ( C_k 1 )² m_{k —1} d ²) при использовании алгебраиче

ского критерия смежности;

• •     T add ( C k -1 ) e O (| U ( C k -1 )p(| U ( C k -1 )| + d ) + I U ( C k -1 )h m k -r (| U ( C k -1 )|² + d )) при использовании

комбинаторного и графового критериев смежности.

Как показывает утверждение 1, зависимость верхней оценки трудоемкости шага метода двойного описания от размера остова текущего конуса квадратичная при использовании алгебраического критерия и кубическая при использовании комбинаторного и графового критериев смежности. Отметим, что максимальный размер выхода шага метода двойного описания асимптотически ограничен сверху величиной | U ( C_k- 1 )².

Для анализа трудоемкости в следующих разделах введем также обозначение для общей трудоемкости метода двойного описания. Обозначим T _DDM( m, d) трудоемкость метода двойного описания для построения остова конуса в Q ^d , заданного системой из m неравенств. Для описываемого варианта метода двойного описания справедливы следующие оценки:

Утверждение 2 [23]. Трудоемкость метода двойного описания для построения остова острого конуса при любом фиксированном d составляет:

• •    T _DDM( m, d) e O ( m^{d+ 2}) при использовании алгебраического критерия смежности;

• •    T o _DM( m, d) e O ( m ^{3 d/2+} 1 ) при использовании комбинаторного и графового критериев смежности.

Операция удаления неравенства из фасетного описания конуса

Настоящий раздел посвящен операции (2) удаления неравенства из фасетного описания конуса. Отметим, что «наивным» способом решения задачи является прямое построение остова конуса C_k по системе неравенств, без использования информации о конусе C_k- 1 . В этом случае, при использовании метода двойного описания, трудоемкость составляет T _DDM( m_k- 1 -1 , d ).

В [15] предложен алгоритм удаления неравенств из фасетного описания, названный авторами инкрементным. Обозначим F фасету, соответствующую удаляемому неравенству. Строится множество фасет F adj , смежных с F . С помощью метода двойного описания вычисляется остов конуса C adj , определяемого неравенствами, соответствующими фасетами из F adj . В остове конуса C adj находится подмножество векторов U _new, которые не принадлежат конусу C_{k– 1}. Множество векторов U ( C k– 1 ) ∪ U new порождает конус C k– 1 , однако не обязательно является неприводимым. Для завершения операции достаточно удалить избыточные элементы из множества U ( C k– 1 ) ∪ U new . Таким образом, трудоемкость инкрементного алгоритма удаления неравенства составляет T remove ( C k– 1 ) ∈ O ( T DDM ( |F adj |, d )). При этом в худшем случае полученная оценка совпадает с оценкой трудоемкости «наивного» алгоритма. Оценка в терминах количества фасет конуса C k– 1 может быть получена с помощью утверждения 2.

Отметим, что алгоритм [15] позволяет одновременное удаление нескольких неравенств, отличие от случая одного неравенства состоит лишь в том, что в F adj добавляются фасеты, смежные хотя бы с одной из удаляемых.

В общем случае задача удаления неравенства из фасетного описания является существенно более трудной по сравнению с задачей добавления неравенства, как показывает следующий пример. Рассмотрим семейство политопов CC 2δ ( s ), являющихся произведением δ циклических политопов C _{2 δ} ( s ), конструкция и некоторые свойства данного семейства приведены в [18, 24]. Как показано в [24], при удалении любой вершины v политопа P = CC 2δ ( s ) количество фасет многогранника conv( P \ { v }), не являющихся фасетами P , составляет Θ( s ^{( δ – 1) δ} ). Таким образом, удаление любой вершины такого политопа приводит к образованию очень большого количества новых фасет. При сведении к случаю удаления неравенства из фасетного описания конуса, из этого вытекает следующее утверждение:

Утверждение 3 . Размер выхода задачи удаления одного неравенства из фасетного описания конуса не ограничен полиномом от длины входа.

Следующая теорема устанавливает один из подклассов, для которых размер выхода полиномиален от длины входа.

Теорема 1 . Пусть острый конус C k получен путем удаления неравенства ax ≥ 0 из фасетного описания острого конуса C_{k– 1} и выполнено условие

∀ u ∈ U ( C k ) ∃ v ∈ U ( C k– 1 ): { u , v } ∈ E ( C k ), av > 0.                      (5)

Тогда справедливо неравенство

| U ( C k )| ≤ | U ( C k– 1 )| + | E ( C k– 1 )|.

Доказательство . Рассмотрим обратную операцию: конус C k– 1 может быть получен из C k путем добавления неравенства ax ≥ 0 с помощью метода двойного описания, рассмотренного в разделе 2. При этом, ввиду соотношения (4), векторы из U ( C k ), лежащие в полупространстве ax ≥ 0, присутствуют и в U ( C k– 1 ). Таким образом, справедливо неравенство

U ( C k )| ≤ | U ( C k– 1 )| + | U ( C k ) \ U ( C k– 1 )|.                                 (6)

Для оценки величины | U ( C_k ) \ U ( C_{k– 1})| отметим, что векторы из этого множества создают комбинации со смежными им векторами из открытого полупространства ax > 0, согласно (3). Из условия (5) следует, что каждый вектор из U ( C k ) \ U ( C k– 1 ) создаст хотя бы одну комбинацию. Таким образом, каждый вектор из этого множества лежит на пересечении продолжения ребра конуса C_{k– 1}, составленного парой векторов из U ( C_{k– 1}), один из которых являлся его «парой» при комбинировании, а другой – результатом комбинирования. Таким образом, количество ребер конуса C k– 1 дает верхнюю оценку величины | U ( C k ) \ U ( C k– 1 )|. Подстановка этой оценки в соотношение (6) и дает доказываемое неравенство.

Так как величина | E ( C_{k– 1})| ограничена количеством (неупорядоченных) пар векторов остова и всегда меньше, чем | U ( C k– 1 )|² / 2, справедливо следующее

Следствие 1 . В условиях теоремы справедливо неравенство

| U ( C k )| < | U ( C k– 1 )| + | U ( C k– 1 )|² / 2.

Таким образом, в условиях теоремы 1 зависимость размера выхода от размера входа не более, чем квадратичная. Отметим, что доказательство теоремы дает полиномиальный от длины входа (в условиях теоремы) алгоритм построения U(Ck) с помощью продолжения ребер конуса Ck–1, составленных их пары векторов, один из которых лежит в удаляемой фасете, а другой – нет, до пересечения с фасетами. Смежность векторов может быть определена с помощью одного из критериев, описанных в разделе 2. Принимая во внимание то, что оценки утверждения 1 также являются полиномиальными от длины входа, справедлива следующая теорема:

Теорема 2 . Пусть выполняется последовательность операций добавления и удаления неравенств вида (1), (2) и для каждой операции удаления выполнено условие (5). Тогда существует алгоритм выполнения последовательности операций с трудоемкостью, ограниченной полиномом от длины входа при любом фиксированном числе операций.

Заключение

В статье рассматривается задача построения остова полиэдрального конуса, множество неравенств которого динамически изменяется путем добавления новых и удаления существующих неравенств. Рассматривается применение метода двойного описания для операции добавления нового неравенства, соответствующей итерации метода, приводятся оценки трудоемкости. Для задачи удаления неравенства из фасетного описания конуса рассматривается «наивный» и инкрементный алгоритмы, приводятся оценки трудоемкости. Приводится пример, показывающий, что размер выхода при удалении неравенства в общем случае не ограничен полиномом от длины входа. Выделяется подкласс задач, для него доказывается, что размер выхода ограничен квадратом от размера входа. Показано, что для данного класса существует алгоритм выполнения последовательного выполнения операций с трудоемкостью, ограниченной полиномом от длины входа при любом фиксированном числе операций.

Авторы благодарят В.Н. Шевченко и А.Н. Максименко за полезные обсуждения.