Задача типа LP - LP-type problem

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

Определение

Задачи типа LP были определены Шарир и Вельцль (1992) как задачи, в которых на входе задано конечное множество S элементов, а функция ж который отображает подмножества S к значениям из полностью упорядоченного набора. Функция должна удовлетворять двум ключевым свойствам:

  • Монотонность: на каждые два комплекта А ⊆ B ⊆ S, ж(А) ≤ ж(B) ≤ ж(S).
  • Населенный пункт: за каждые два комплекта А ⊆ B ⊆ S и каждый элемент Икс в S, если ж(А) = ж(B) = ж(А ∪ {Икс}), тогда ж(А) = ж(B ∪ {Икс}).

А основа задачи типа LP - это множество B ⊆ S со свойством, что каждое собственное подмножество B имеет меньшее значение ж чем B сам, и измерение (или же комбинаторная размерность) задачи типа LP определяется как максимальное мощность основы.

Предполагается, что алгоритм оптимизации может оценивать функцию ж только на наборах, которые сами по себе являются базами или которые сформированы путем добавления одного элемента к основе. В качестве альтернативы алгоритм может быть ограничен двумя примитивными операциями: тест на нарушение что определяет, за основу B и элемент Икс ли ж(B) = ж(B ∪ {Икс}), а базисное вычисление который (с теми же входами) находит основу B ∪ {Икс}. Задача алгоритма - оценить ж(S) используя только эти ограниченные оценки или примитивы.

Примеры и приложения

Lp шары

А линейная программа может быть определена системой d неотрицательный реальные переменные, при условии п ограничения линейного неравенства вместе с неотрицательной линейной целевой функцией, которую необходимо минимизировать. Это можно поместить в рамки задач LP-типа, если S быть набором ограничений, а определение ж(А) (для подмножества А ограничений) как минимальное значение целевой функции меньшей линейной программы, определяемой А. При подходящих допущениях общего положения (во избежание того, чтобы несколько точек решения имели одинаковое оптимальное значение целевой функции), это удовлетворяет требованиям монотонности и локальности задачи типа LP и имеет комбинаторную размерность, равную числу d переменных.[1] Точно так же целочисленная программа (состоящий из набора линейных ограничений и линейной целевой функции, как в линейной программе, но с дополнительным ограничением, что переменные должны принимать только целые значения) удовлетворяет как свойствам монотонности, так и локальности задачи типа LP, с те же предположения об общем положении, что и для линейных программ. Теоремы Белл (1977) и Шарф (1977) покажите, что для целочисленной программы с d переменных комбинаторная размерность не более2d.[1]

Многие проблемы естественной оптимизации в вычислительная геометрия LP-типа:

Задача наименьшего круга
  • В задача наименьшего круга проблема нахождения минимального радиуса круга, содержащего заданный набор п точки в плоскости. Он удовлетворяет монотонности (добавление дополнительных точек может только сделать круг больше) и локальности (если наименьший круг для набора А содержит B и Икс, то в этом же круге B ∪ {Икс}). Поскольку наименьший круг всегда определяется некоторыми тремя точками, задача наименьшего круга имеет комбинаторную размерность три, даже если она определяется с использованием двухмерной евклидовой геометрии.[2] В более общем смысле, наименьший охватывающий шар точек в d размерности формируют задачу комбинаторной размерности типа LP d + 1. Задача о наименьшем круге может быть обобщена на наименьший шар, охватывающий набор шаров,[3] на наименьший шар, который касается или окружает каждый из множества шаров,[4] взвешенным 1-центровая проблема,[5] или аналогичным меньшим задачам с охватывающим мячом в неевклидовых пространствах, таких как пространство с расстояниями, определяемыми Расхождение Брегмана.[6] Связанная с этим проблема поиска наименьшего ограждающего эллипсоид также является задачей LP-типа, но с большей комбинаторной размерностью, d(d + 3)/2.[7]
  • Позволять K0, K1, ... быть последовательностью п выпуклые множества в d-мерное евклидово пространство, и предположим, что мы хотим найти самое длинное префикс этой последовательности, имеющей общую точку пересечения. Это может быть выражено как проблема типа LP, в которой ж(А) = −я куда Kя первый член А который не принадлежит пересекающемуся префиксу А, и где ж(А) = −п если такого участника нет. Комбинаторная размерность этой системы равна d + 1.[8]
  • Предположим, нам дан набор выровненных по осям прямоугольных ящиков в трехмерном пространстве, и мы хотим найти линию, направленную в положительный октант пространства, которая пересекает все ящики. Это можно выразить как задачу типа LP с комбинаторной размерностью 4.[9]
  • Проблема поиска ближайшего расстояния между двумя выпуклые многогранники, заданные своими наборами вершин, можно представить как задачу типа LP. В этой постановке множество S - множество всех вершин в обоих многогранниках, а значение функции ж(А) это отрицание наименьшего расстояния между выпуклые оболочки из двух подмножеств А вершин в двух многогранниках. Комбинаторная размерность задачи равна d + 1 если два многогранника не пересекаются, или d + 2 если у них есть непустое пересечение.[1]
  • Позволять S = {ж0, ж1, ...} быть набором квазивыпуклые функции. Тогда поточечный максимум Максимумя жя сам квазивыпуклый, и задача нахождения минимального значения Максимумя жя является проблемой типа LP. Он имеет комбинаторную размерность не более 2d + 1, куда d - размерность области определения функций, но для достаточно гладких функций комбинаторная размерность меньше, не более d + 1. Таким же образом можно выразить с помощью квазивыпуклых функций и многие другие проблемы типа LP; например, задача наименьшего окружающего круга - это проблема минимизации Максимумя жя где каждая из функций жя измеряет евклидово расстояние от одной из заданных точек.[10]

Задачи типа LP также использовались для определения оптимальных исходов некоторых игр в алгоритмическая теория игр,[11] улучшить размещение вершин в метод конечных элементов сетки[12] решать расположение объекта проблемы,[13] анализировать временную сложность некоторых алгоритмов экспоненциального поиска,[14] и реконструировать трехмерное положение объектов по их двумерным изображениям.[15]

Алгоритмы

Зайдель

Зайдель (1991) предоставил алгоритм низкоразмерного линейного программирования, который может быть адаптирован к структуре задач типа LP. Алгоритм Зейделя принимает в качестве входных данных набор S и отдельный набор Икс (изначально пустые) элементов, о которых известно, что они принадлежат оптимальному базису. Затем он рассматривает оставшиеся элементы один за другим в случайном порядке, выполняя тесты на нарушение для каждого из них и, в зависимости от результата, выполняет рекурсивный вызов того же алгоритма с большим набором известных базовых элементов. Это может быть выражено следующим псевдокодом:

функция Зейдель (S, ж, Икс) является    р : = пустой набор B := Икс    за Икс в случайной перестановке S:        если ж(B) ≠ ж(B ∪ {Икс}):            B : = seidel (р, ж, основа (Икс ∪ {Икс}))        р := р ∪ {Икс}    возвращаться B

В задаче с комбинаторной размерностью d, тест на нарушение в яитерация алгоритма терпит неудачу только тогда, когда Икс один из d − |Икс| оставшиеся базовые элементы, что происходит с вероятностью не более (d − |Икс|)/я. На основании этого расчета можно показать, что в целом ожидаемое количество проверок нарушений, выполняемых алгоритмом, равно O (d! п), линейный по п но хуже экспоненциального в d.

Кларксон

Кларксон (1995) определяет два алгоритма, рекурсивный алгоритм и итерационный алгоритм, для линейного программирования, основанного на методах случайной выборки, и предлагает их комбинацию, которая вызывает итерационный алгоритм из рекурсивного алгоритма. Рекурсивный алгоритм многократно выбирает случайные выборки, размер которых приблизительно равен квадратному корню из входного размера, рекурсивно решает выбранную проблему, а затем использует тесты на нарушение, чтобы найти подмножество оставшихся элементов, которые должны включать хотя бы один базовый элемент:

функция рекурсивный (S, ж) является    Икс : = пустой набор повторение        р : = случайное подмножество S размером d√n B : = основа для р ∪ Икс, вычисляется рекурсивно V := {Икс | ж(B) ≠ ж(B ∪ {Икс})}        Икс := Икс ∪ V    до того как V пусто возвращаться B

На каждой итерации ожидаемый размер V является O (√п),[16] и когда V непусто, оно включает по крайней мере один новый элемент возможной основы S. Следовательно, алгоритм выполняет не более d итераций, каждая из которых выполняет п проверяет нарушение и выполняет один рекурсивный вызов подзадачи размера O (d√п).

Итерационный алгоритм Кларксона присваивает веса каждому элементу S, изначально все они равны. Затем он выбирает набор р из 9d2 элементы из S случайным образом и вычисляет множества B и V как в предыдущем алгоритме. Если общий вес V самое большее 2/(9d − 1) раз больше общего веса S (что происходит с постоянной вероятностью), тогда алгоритм удваивает веса каждого элемента V, и, как прежде, он повторяет этот процесс до тех пор, пока V становится пустым. Можно показать, что на каждой итерации вес оптимального базиса увеличивается с большей скоростью, чем общий вес S, из чего следует, что алгоритм должен завершиться в течение O (журнал п) итераций.

Используя рекурсивный алгоритм для решения данной проблемы, переключаясь на итерационный алгоритм для его рекурсивных вызовов, а затем снова переключаясь на алгоритм Зейделя для вызовов, сделанных итерационным алгоритмом, можно решить данную задачу типа LP, используя O (дн + d! dО (1) бревно п) тесты на нарушение.

Применительно к линейной программе этот алгоритм можно интерпретировать как двойственный симплексный метод.[17] С некоторыми дополнительными вычислительными примитивами помимо примитивов проверки нарушений и базисных вычислений, этот метод можно сделать детерминированным.[18]

Матушек, Шарир и Вельцль

Матушек, Шарир и Вельцль (1996) описать алгоритм, который использует дополнительное свойство линейных программ, которое не всегда поддерживается другими задачами LP-типа, что все базы имеют одинаковую мощность друг друга. Если проблема LP-типа не имеет этого свойства, ее можно сделать, добавив d новые фиктивные элементы и путем изменения функции ж вернуть упорядоченная пара старой ценности ж(А) и числа мин (d,|А|), упорядоченный лексикографически.

Вместо того, чтобы добавлять элементы S по одному или находя образцы элементов, Матушек, Шарир и Вельцль (1996) описать алгоритм, который удаляет элементы по одному. На каждом этапе он поддерживает основу C изначально это может быть набор фиктивных элементов. Это можно описать следующим псевдокодом:

функция MSW (S, ж, C) является    если S = C тогда        возвращаться C    выбрать случайный элемент x из S \ C    B = msw (S \ Икс, ж, C)    если ж(B) ≠ f (B ∪ {x}) тогда        B : = основа (B ∪ {Икс})        B : = msw (S, ж, B)    возвращаться B

В большинстве рекурсивных вызовов алгоритма проверка нарушения проходит успешно, а оператор if пропускается. Однако с небольшой вероятностью проверка на нарушение не выполняется, и алгоритм выполняет дополнительное базовое вычисление, а затем дополнительный рекурсивный вызов. Как показывают авторы, ожидаемое время работы алгоритма линейно по п и экспонента в квадратном корне из d бревно п. Комбинируя этот метод с рекурсивными и итеративными процедурами Кларксона, эти две формы временной зависимости могут быть отделены друг от друга, в результате чего получается алгоритм, выполняющий O (дн) тестов на нарушение во внешнем рекурсивном алгоритме и число, являющееся экспоненциальным в квадратном корне из d бревно d на нижних уровнях алгоритма.[19]

Вариации

Оптимизация с выбросами

Матушек (1995) рассматривает вариант задач оптимизации типа LP, в котором вместе с множеством S и целевая функция ж, число k; задача убрать k элементы из S чтобы сделать целевую функцию на оставшемся наборе как можно меньше. Например, применительно к задаче наименьшего круга это даст наименьший круг, содержащий все, кроме k заданного набора плоских точек. Он показывает, что для всех невырожденных задач типа LP (то есть задач, в которых все базы имеют разные значения) эта проблема может быть решена за время O (нкd), решая набор O (kd) Задачи LP-типа, определяемые подмножествами S.

Неявные проблемы

Некоторые задачи геометрической оптимизации могут быть выражены как задачи LP-типа, в которых количество элементов в формулировке LP-типа значительно превышает количество значений входных данных для задачи оптимизации. В качестве примера рассмотрим набор п точки на плоскости, каждая из которых движется с постоянной скоростью. В любой момент времени диаметр этой системы - максимальное расстояние между двумя ее точками. Задача нахождения времени минимизации диаметра может быть сформулирована как минимизация поточечного максимума O (п2) квазивыпуклые функции, по одной для каждой пары точек, измеряющие евклидово расстояние между парой как функцию времени. Таким образом, ее можно решить как задачу ЛП-типа комбинаторной размерности два на множестве O (п2) элементов, но этот набор значительно больше, чем количество входных точек.[20]

Чан (2004) описывает алгоритм для решения неявно определенных проблем типа LP, таких как эта, в котором каждый элемент типа LP определяется k-набор входных значений для некоторой константы k. Чтобы применить его подход, должен существовать алгоритм решения которая может определить для данного базиса типа LP B и установить S из п входные значения, будь то B лежит в основе задачи ЛП-типа, определяемой S.

Алгоритм Чана выполняет следующие шаги:

  • Если количество входных значений ниже некоторого порогового значения, найдите набор элементов LP-типа, который он определяет, и решите полученную явную проблему LP-типа.
  • В противном случае разделите входные значения на подходящее число больше, чем k равных подмножеств Sя.
  • Если ж является целевой функцией для неявно определенной задачи типа LP, которая должна быть решена, затем определите функцию грамм который отображает коллекции подмножеств Sя к стоимости ж о объединении коллекции. Тогда набор подмножеств Sя и целевая функция грамм сам определяет проблему LP-типа того же размера, что и неявная проблема, которую нужно решить.
  • Решите (явную) задачу типа LP, определенную формулой грамм с использованием алгоритма Кларксона, который выполняет линейное количество тестов на нарушение и полилогарифмическое количество оценок базиса. Базовые оценки для грамм могут выполняться рекурсивными вызовами алгоритма Чана, а тесты на нарушение могут выполняться вызовами алгоритма принятия решения.

Если предположить, что алгоритм принятия решения занимает некоторое время O (Т(п)) который растет как минимум полиномиально в зависимости от размера входных данных п, Chan показывает, что порог для перехода к явной формулировке LP и количество подмножеств в разделе можно выбрать таким образом, чтобы неявный алгоритм оптимизации типа LP также работал во времени O (Т(п)).

Например, для минимального диаметра движущихся точек алгоритму решения необходимо только вычислить диаметр набора точек в фиксированное время, и эта проблема может быть решена за O (п бревно п) время, используя вращающиеся суппорты техника. Следовательно, алгоритм Чана для определения времени минимизации диаметра также требует времени O (п бревно п).Chan использует этот метод, чтобы найти точку максимального Глубина Тьюки среди данной коллекции п указывает в d-мерное евклидово пространство во времени O (пd − 1 + п бревно п). Похожую технику использовали Брасс, Генрих-Литан и Морин (2003) найти точку максимальной глубины Тьюки для равномерного распределения на выпуклом многоугольнике.

История и связанные с ней проблемы

Открытие алгоритмов линейного времени для линейного программирования и наблюдение, что одни и те же алгоритмы во многих случаях могут использоваться для решения задач геометрической оптимизации, которые не были линейными программами, восходит, по крайней мере, к Мегиддо (1983, 1984 ), который дал алгоритм линейного ожидаемого времени как для линейных программ с тремя переменными, так и для задачи наименьшего круга. Однако Мегиддо сформулировал обобщение линейного программирования скорее геометрически, чем комбинаторно, как выпуклая оптимизация проблема, а не как абстрактная проблема о системах множеств. По аналогии, Дайер (1986) и Кларксон (в версии конференции 1988 г. Кларксон 1995 ) заметил, что их методы могут применяться как к выпуклым программам, так и к линейным программам. Дайер (1992) показал, что задача минимального охватывающего эллипсоида также может быть сформулирована как задача выпуклой оптимизации путем добавления небольшого количества нелинейных ограничений. Использование рандомизации для улучшения временных рамок для низкоразмерного линейного программирования и связанных задач было впервые предложено Кларксоном и Красильщик и Фриз (1989).

Определение задач типа LP в терминах функций, удовлетворяющих аксиомам локальности и монотонности, взято из Шарир и Вельцль (1992), но другие авторы в те же сроки сформулировали альтернативные комбинаторные обобщения линейных программ. Например, в рамках, разработанных Гертнер (1995), функция ж заменяется полным порядком на подмножествах S. Можно разорвать связи в задаче типа LP, чтобы создать полный порядок, но только за счет увеличения комбинаторной размерности.[21]Кроме того, как и в задачах типа LP, Гертнер определяет некоторые примитивы для выполнения вычислений над подмножествами элементов; однако его формализация не имеет аналога комбинаторной размерности.

Еще одно абстрактное обобщение как линейных программ, так и задачи линейной дополнительности, сформулированный Стикни и Ватсон (1978) и позже изученный несколькими другими авторами, касается ориентации краев гиперкуб со свойством, что каждая грань гиперкуба (включая весь гиперкуб как грань) имеет уникальная раковина, вершина без исходящих ребер. Ориентация этого типа может быть сформирована из задачи типа LP путем сопоставления подмножеств S с вершинами гиперкуба таким образом, что два подмножества отличаются одним элементом тогда и только тогда, когда соответствующие вершины смежны, и ориентируя ребро между соседними множествами А ⊆ B к B если ж(А) ≠ ж(B) и к А иначе. Полученная ориентация обладает дополнительным свойством: она образует ориентированный ациклический граф, из которого можно показать, что рандомизированный алгоритм может найти единственный сток для всего гиперкуба (оптимальный базис задачи типа LP) за несколько шагов, экспоненциальных от квадратного корня изп.[22]

Недавно разработанная структура места для нарушителей обобщает проблемы LP-типа в том смысле, что каждая проблема LP-типа может быть смоделирована пространством нарушителей, но не обязательно наоборот. Пространства нарушителей определяются аналогично задачам LP-типа функцией ж который отображает множества в значения целевой функции, но значения ж не заказываются. Несмотря на отсутствие заказа, каждый комплект S имеет четко определенный набор баз (минимальные множества с тем же значением, что и весь набор), которые могут быть найдены вариациями алгоритмов Кларксона для задач типа LP. Действительно, было показано, что пространства нарушителей точно характеризуют системы, которые могут быть решены с помощью алгоритмов Кларксона.[23]

Примечания

  1. ^ а б c Матушек, Шарир и Вельцль (1996).
  2. ^ Хотя задача наименьшего круга была впервые названа проблемой LP-типа Матушек, Шарир и Вельцль (1996), в нескольких более ранних работах описывались алгоритмы решения этой проблемы, основанные на идеях низкоразмерного линейного программирования, в том числе Мегиддо (1983) и Вельцль (1991).
  3. ^ Фишер и Гертнер (2004).
  4. ^ Леффлер и ван Кревельд (2010).
  5. ^ Дайер (1986).
  6. ^ Нильсен и Нок (2008).
  7. ^ Матушек, Шарир и Вельцль (1996); Вельцль (1991).
  8. ^ Чан (2004).
  9. ^ Амента (1994).
  10. ^ Амента, Берн и Эпштейн (1999); Эппштейн (2005).
  11. ^ Хэлман (2007).
  12. ^ Амента, Берн и Эпштейн (1999).
  13. ^ Пуэрто, Родригес-Чиа и Тамир (2010).
  14. ^ Эппштейн (2006).
  15. ^ Ли (2007).
  16. ^ Ограничения на размер V также известны: см. Гертнер и Вельцль (2001).
  17. ^ Калаи (1992).
  18. ^ Шазель и Матушек (1996).
  19. ^ Матушек, Шарир и Вельцль (1996). Очень похожая временная граница для линейного программирования была также дана Калаи (1992).
  20. ^ ЛВ-формулировка этой задачи была дана формулой Чан (2004), но ранее он изучался другими алгоритмическими методами Гупта, Джанардан и Смид (1996). Чан также цитирует неопубликованную рукопись Кларксона для O (п бревно п) алгоритм времени, согласовывающий время, которое может быть достигнуто с помощью неявного подхода типа LP.
  21. ^ Матушек (2009).
  22. ^ Сабо и Вельцль (2001).
  23. ^ Gärtner et al. (2008); Бриз и Гертнер (2011).

Рекомендации