Оракул разделения

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

Определение

Пусть K — выпуклое и компактное множество в R ^н . Оракул сильного разделения для K — это оракул ( черный ящик ), который по заданному вектору y в R ^н , возвращает одно из следующих значений:

• Утвердите, что y находится в K .
• Найдите гиперплоскость, отделяющую y от K : вектор a в R ^н , такой, что $a\cdot y>a\cdot x$ для x в K. всех

Прогноз сильного разделения абсолютно точен, и поэтому его может быть сложно построить. По практическим соображениям рассматривается более слабая версия, допускающая небольшие ошибки в границах K и неравенствах. Учитывая небольшую допуск на ошибку d > 0, мы говорим, что:

• Вектор y является d-близким к K , если его евклидово расстояние от K не превышает d ;
• Вектор y d -глубок в K , если он находится в K и его евклидово расстояние от любой точки вне K не менее d .

Слабая версия также рассматривает рациональные числа, которые имеют представление конечной длины, а не произвольные действительные числа. Оракул слабого разделения для K — это оракул, который по вектору y из Q ^н и рациональное число d >0, возвращает одно из следующих значений:

• Утверждаем, что d y - близок к K ;
• Найдите вектор a в Q ^н , нормализованный так, что его максимальный элемент равен 1, такой, что $a\cdot y+d\geq a\cdot x$ для всех x, которые d -глубоки в K .

Выполнение

Частным случаем выпуклого множества является множество, представленное линейными неравенствами: $K=\{x|Ax\leq b\}$. Такое множество называется выпуклым многогранником . Можно реализовать оракул сильного разделения для выпуклого многогранника, но время его выполнения зависит от входного формата.

Представление неравенствами

Если матрица A и вектор b заданы в качестве входных данных, так что $K=\{x|Ax\leq b\}$, то оракул сильного разделения можно реализовать следующим образом. Учитывая точку y , вычислите $Ay$:

• Если результат не более $b$, то y принадлежит K ; по определению
• В противном случае существует хотя бы одна строка $c$ A , такой , что $c\cdot y$ больше соответствующего значения в $b$; эта строка $c$ дает нам разделяющую гиперплоскость, как $c\cdot y>b\geq c\cdot x$ для x в K. всех

Этот оракул работает за полиномиальное время, пока количество ограничений полиномиально.

Представление вершинами

Предположим, что набор вершин K задан в качестве входных данных, так что $K={\text{conv}}(v_{1},\ldots ,v_{k})=$ выпуклая оболочка его вершин. Затем для принятия решения о том, находится ли y в K, необходимо проверить, является ли y выпуклой комбинацией входных векторов, то есть существуют ли коэффициенты z ₁ ,..., z _k такие, что:

• $z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y$;
• $0\leq z_{i}\leq 1$ для всех i в 1,..., k .

Это линейная программа с k переменными и n ограничениями равенства (по одному на каждый элемент y ). Если y не находится в K , то приведенная выше программа не имеет решения, и оракулу разделения необходимо найти вектор c такой, что

• $c\cdot y>c\cdot v_{i}$ для всех i в 1,..., k .

Обратите внимание, что два приведенных выше представления могут сильно различаться по размеру: возможно, что многогранник может быть представлен небольшим количеством неравенств, но имеет экспоненциально много вершин (например, n -мерный куб). И наоборот, возможно, что многогранник имеет небольшое количество вершин, но требует экспоненциально большого числа неравенств (например, выпуклая оболочка 2 n векторов вида (0,...,±1,...,0 ).

Представление конкретной проблемы

В некоторых задачах линейной оптимизации, даже несмотря на то, что количество ограничений является экспоненциальным, все равно можно написать собственный оракул разделения, который работает за полиномиальное время. Некоторые примеры:

• Задача об древовидности минимальной стоимости : по взвешенному ориентированному графу и вершине r в нем найти подграф минимальной стоимости, содержащий направленный путь от r до любой другой вершины. Задачу можно представить в виде ЛП с ограничением для каждого подмножества вершин, которое представляет собой экспоненциальное число ограничений. Однако оракул разделения может быть реализован с использованием n -1 применений процедуры минимального разреза .
• Задача о максимальном независимом множестве . Его можно аппроксимировать ЛП с ограничением для каждого цикла нечетной длины. Хотя таких циклов экспоненциально много, оракул разделения, работающий за полиномиальное время, можно реализовать, просто найдя нечетный цикл минимальной длины, что можно сделать за полиномиальное время.
• Двойственная конфигурация линейной программы для задачи упаковки контейнеров . Его можно аппроксимировать ЛП с ограничением для каждой допустимой конфигурации. Хотя таких циклов экспоненциально много, оракул разделения, работающий за псевдополиномиальное время, может быть реализован путем решения задачи о рюкзаке . Это используется алгоритмами упаковки бинов Кармаркара-Карпа .

Нелинейные множества

Пусть f — на выпуклая функция R ^н . Набор $K=\{(x,t)|f(x)\leq t\}$ — выпуклое множество в R ^{п +1} . Имея оракул оценки f (черный ящик, который возвращает значение f для каждой заданной точки), можно легко проверить, находится ли вектор ( y , t ) в K . Чтобы получить оракул разделения, нам также нужен оракул для субградиента f оценки . Предположим, некоторый вектор ( y , s ) не принадлежит K , поэтому f ( y )> s . Пусть g — субградиент f в точке y ( g — вектор в R ^н ) . Обозначим $c:=(g,-1)$.Затем, $c\cdot (y,s)=g\cdot y-s>g\cdot y-f(y)$и для всех ( x , t ) в K : $c\cdot (x,t)=g\cdot x-t\leq g\cdot x-f(x)$. По определению субградиента: $f(x)\geq f(y)+g\cdot (x-y)$ для всех x в R ^н . Поэтому, $g\cdot y-f(y)\geq g\cdot x-f(x)$, так $c\cdot (y,s)>c\cdot (x,t)$ , а c представляет собой разделяющую гиперплоскость.

Использование

Оракул сильного разделения можно использовать в качестве входных данных для метода эллипсоидов для решения линейной программы. Рассмотрим линейную программу ${\text{maximize}}~~c\cdot x~~{\text{subject to}}~~Ax\leq b,x\geq 0$. Метод эллипсоида поддерживает эллипсоид, который изначально содержит всю допустимую область. $Ax\leq b$. На каждой итерации t он берет центр $x_{t}$ текущего эллипсоида и отправляет его оракулу разделения:

• Если оракул говорит это $x_{t}$ допустима (т. е. содержится в множестве $Ax\leq b$), то мы делаем «оптимальный разрез» в $x_{t}$: вырезаем из эллипсоида все точки x, для которых $c\cdot x<c\cdot x_{t}$. Эти точки определенно не являются оптимальными.
• Если оракул говорит это $x_{t}$ невозможно, то он обычно возвращает конкретное ограничение, которое нарушается $x_{t}$, то есть ряд $a_{j}$ в матрице A такой, что $a_{j}\cdot x_{t}>b_{j}$. С $a_{j}\cdot x\leq b_{j}$ для всех возможных x это означает, что $a_{j}\cdot x_{t}>a_{j}\cdot x$ для всех возможных x . Затем мы делаем «обоснование технико-экономического обоснования» в $x_{t}$: вырезаем из эллипсоида все точки y, для которых $a_{j}\cdot y>a_{j}\cdot x_{t}$. Эти пункты определенно невыполнимы.

Сделав разрез, мы строим новый, меньший эллипсоид, содержащий оставшуюся область. Можно показать, что этот процесс сходится к приближенному решению, полиномиальному по времени требуемой точности.

Превращение слабого оракула в сильного оракула

Учитывая слабый оракул разделения для многогранника , можно построить сильный оракул разделения с помощью тщательного метода округления или диофантовых приближений .

См. также

• Алгоритмические задачи на выпуклых множествах