Срединные решения линейных программ

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

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

Минимизировать $\epsilon$ при условии $f_i(\bar x) \leq \epsilon < 0$ с $f_i$ линейный и $x_i > 0$ для всех $i$ а также $\sum_i x_i = 1$ ,

Конечно, мы никогда не получили бы никакого подобного центральности свойства из симплексного алгоритма. Хотя какой-нибудь из обычных алгоритмов внутренних точек обладает такими свойствами? Есть ли гарантия, что они будут избегать вершин или граней меньшего размера, когда это возможно?

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

Обновление: я сократил основную проблему до простой ограниченной задачи минимизации, решаемой с помощью множителей Лагранжа, но вопрос выше остается интересным в любом случае.

ds.algorithms linear-algebra linear-programming Джефф Берджес
источник

не совсем твой вопрос, но: вычисление центроида # P-hard; я не уверен, что является наилучшим приближением, но для некоторых применений достаточно поместить многогранник в изотропное положение и взять среднее для полиномиально большого числа однородных выборок из (преобразованного) многогранника. см. эту заметку, например, лемму 15: cc.gatech.edu/~vempala/acg/notes.pdf

Сашо Николов

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

анонимно

Ответы:

У меня есть несколько замечаний, которые слишком длинны для комментариев. Вот краткое изложение.

Любой алгоритм для точного решения вашей проблемы может быть использован для точного решения линейных программ (т. Е. «Сильное линейное программирование», которое используется в решении Сариэля и в настоящее время не имеет алгоритма полиномиального времени).
Естественным продолжением является то, что приближенные решения (т. Е. «Слабое линейное программирование») могут обеспечить решение. Хотя ответ «да», похоже, что условие остановки для этой процедуры требует величин, которые, насколько мне известно, не могут быть вычислены за полиномиальное время. (т. е. алгоритм находит что-то хорошее, но подтвердить это сложно.) Мое главное предложение состоит в том, чтобы дать осмысленное определение « $\epsilon$ «оптимальное решение» для вашей проблемы, и в этом случае этот подход поддается лечению. (Эта стратегия эффективно выбрасывает крошечные грани многогранника.)

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

(1.) Предположим, у нас есть алгоритм, который точно решает вашу проблему. Обратите внимание, что любая открытая точка любого грани, содержащая предоставленную среднюю точку, будет точным решением исходной линейной программы. Так что действуйте следующим образом. Добавьте новое линейное ограничение, говорящее, что исходное значение цели должно быть равно оптимальному (которое мы теперь знаем), и установите новую цель, сказав, чтобы максимизировать первую координату решения. Повторите эту процедуру один раз для каждого измерения, каждый раз добавляя ограничение и выбирая новую координату для максимизации. Этот процесс будет уменьшать размер решения каждый раз; обязательно, когда процесс завершится, у нас будет 0-мерное аффинное множество, означающее одну точку. Таким образом, с $\mathcal O(d)$ итерации вашего алгоритма решения средней точки (и только увеличение описания проблемы на полином $d$ каждый раз) решается сильное линейное программирование. Это показывает, что, хотя решение Сариэля требует сильного линейного программирования, точное решение вашего вопроса не может этого избежать. ( Изменить : обратите внимание, что мое доказательство предполагает компактный многогранник (многогранник) в качестве входных данных; в противном случае он должен работать немного сложнее, чтобы найти вершины.)

(2.) Вот итерационная схема, использующая выпуклый выпуклый решатель на каждой итерации, решения которой будут сходиться к мягкому представлению о решении средней точки. Выберите положительную, но убывающую последовательность штрафных параметров $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ ; разумно, чтобы они шли вниз геометрически, т.е. $\lambda_i = 2^{-i}$ , Теперь для каждого $i$ примерно минимизировать выпуклую функцию

⟨ c, x ⟩ - λ_{i} \sum_{j = 1}^{m} \ln (⟨ a_{j}, x ⟩ - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

где $\langle c,x\rangle$ ваша первоначальная цель, и $j$ колеблется над $m$ исходные ограничения, теперь помещенные в цель с помощью логарифмических барьеров (обратите внимание, это стандартно). Теперь, если мы думаем о минимизирующей грани (самого большого измерения) вашего многогранника, обратите внимание, что для достаточно малого $\lambda_i$ и терпимость $\tau$ к вашему выпуклому черному ящику, ваш приблизительный оптимум будет близок к этому лицу, однако барьеры будут отталкивать его как можно дальше от других ограничений. Сказал по-другому, как $\lambda_i$ уменьшается, первоначальная линейная цель в конечном итоге будет доминировать над некоторыми причудливыми барьерами, которые удерживали вас от соответствующего лица, но не будут влиять на барьеры, удерживающие вас от других границ, в частности, от границ лица цели.

В идеальном мире мы садимся и аналитически определяем идеальную ценность $\lambda$ или хотя бы время остановки, чтобы вам не приходилось решать бесконечно много проблем. К сожалению, это кажется сложным. Одна идея, скажем, определить наименьшую ширину любой грани, имеющей размерность больше 0; это хорошо определенная проблема минимизации с положительным оптимумом, потому что существует конечное число граней (и ширина вычисляется относительно каждой). С этим мы можем установить $\lambda$ достаточно маленький, чтобы влияние барьеров было крошечным в центре каждого лица. К сожалению, может быть экспоненциально много граней, поэтому вычисление этой величины бессмысленно.

У всех условий остановки, которые я мог придумать, были подобные вычислительные трудности. (Более того, многие могут снова быть использованы, чтобы превратить это в сильный решатель линейного программирования.)

По этой причине моя рекомендация состоит в том, чтобы построить понятие `` $\epsilon$ - выберите оптимальную среднюю точку '' и решите ее, выбрав $\lambda$ и ваш допуск выпуклого черного ящика $\tau$ соответственно. Я думаю, что это разумный выбор, потому что вы действительно можете не заботиться о лицах, которые имеют наибольшую ширину максимум $\epsilon$ ,

(Некоторые заключительные комментарии.) Кажется, что понятие «середина» имеет решающее значение; Комментарий Сашо указывает на то, что центроид (центр масс?) Является чрезвычайно сложной проблемой, тогда как найти, скажем, самый большой вписанный шар очень просто. Логарифмические барьеры, которые я предложил выше, в общем случае не будут соответствовать ни одному из этих понятий средней точки. С другой стороны, для барьеров и мяча вы можете получить нижнюю границу на расстоянии от вашего центроида до относительной границы лица; может это тебе полезнее?

Наконец, из вашего описания, я полагаю, вы имели в виду, что «целевое лицо» должно иметь как можно более высокое измерение? Это хорошо определено, однако есть также грани решения для всех возможных меньших размеров. В любом случае, подход Сариэля и вышеописанный барьерный подход будут работать с гранью самого большого измерения.

Матус
источник

Да, я рассматривал подобные трюки, но в конечном итоге я пошел на минимизацию

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$ при условии

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$ используя множители Лагранжа. Это дает слабое свойство центральности для

x

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

ϵ

$\epsilon$ , В конечном итоге не было необходимости держать

ϵ

$\epsilon$ сведены к минимуму, чтобы помочь ограничения развиваться быстрее. Спасибо хоть! :)

Джефф Берджес

Аааа # 2 выглядит интересно, не то, что я изначально думал, что это было. милый! Как я уже сказал, я прощаю

x

$x$ для того, чтобы не приземлиться на минимизирующее лицо, пока оно идет куда-то разумно быстро. Я поиграю с этим в какой-то момент. На самом деле, мне все равно придется читать выпуклую оптимизацию, так как я нашел причину сделать мою цель билинейной, а не линейной.

Джефф Берджес

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

Сашо Николов

@SashoNikolov, вот мое настоящее понимание. Любой существующий (слабый поли-тайм) решатель будет терпеть

τ

$\tau$ в качестве ввода и вернуть

τ

$\tau$ -Оптимальным решением. Между тем, решение Сариэль в решающей степени зависит от точного решения: в частности, метод внутренней точки вернет относительно внутренний приблизительный оптимум, что означает, что шаг, идентифицирующий аффинную оболочку желаемой оптимальной грани, фактически выберет оболочку всего выполнимого набор. Я согласен с тем, что мне следует пересмотреть то, что я написал о сильных / слабых, где ключевой вопрос заключается в получении точных решений любым способом.

Матус

@SashoNikolov, теперь, когда я об этом думаю, то же самое понятие оптимальности (с теми же проблемами) может быть использовано в решении Сариэля, например, путем обработки ограничений, которые находятся в пределах некоторого крошечного допуска, чтобы фактически быть жесткими, и соответствующей настройки этого значения. Я обновлю свое решение сегодня вечером.

Матус

Сначала найдите оптимальное решение, затем добавьте линейное ограничение, что решение должно иметь значение, равное оптимальному, которое вы хотите, и переформулируйте ваш LP как тот, который ищет самый большой шар внутри допустимой области. Решите этот модный LP, и вы получите то, что хотите.

Почему вторая проблема может быть решена с помощью LP - это милая проблема в вычислительной геометрии ...

==============

Более формально, вы найдете аффинное подпространство, охватывающее возможные точки, содержащие оптимальное решение. Итак, предположим, что оптимальное решение лежит на гиперплоскости $h \equiv cx = \alpha$ (То есть, $\min c x$ была оригинальная целевая функция LP). Если - допустимая область исходного LP, мы ищем самый большой шар в . Для этого нам нужно вычислить наименьшее размерное аффинное подпространство, содержащее этот набор. Найдя это подпространство, измените переменные так, чтобы вы учитывали только этот аффинный подпапс. Теперь ваш многогранник полноразмерен, и вы можете использовать второй LP, как я описал выше. $P$ $P \cap h$

Итак, пусть будет вершина, вычисленная первым LP. Учитывая все соседние вершины . Рассмотрим аффинное подпространство вместе со всеми его соседями, которые имеют одинаковое целевое значение (т. ). Нетрудно видеть, что это аффинное подпространство является искомым подпространством. $v$ $v$ $v$ $\alpha$

Итак, подведем итог: (A) решить LP, чтобы найти оптимальное значение. (B) Вычислить наименьшее размерное подпространство, содержащее допустимое решение с оптимальным значением. (C) Перепишите исходную LP в этом аффинном подпространстве (то есть, отбросив все несущественные измерения), добавьте переменную и превратите ее в LP для нахождения наибольшего шара внутри этого многогранника.

Сариэль Хар-Пелед
источник

Что подразумевается под «самым большим шаром» в многограннике не полной размерности?

Кристоффер Арнсфельт Хансен

@KristofferArnsfeltHansen многогранник, безусловно, является выпуклым множеством, лежащим в аффинном подпространстве некоторого измерения.

Сашо Николов

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

Суреш Венкат

Есть ли способ сделать шаги после начальной оптимизации за полиномиальное время? Как написано, кажется, что необходимо рассмотреть все вершины в целевой грани, которых может быть экспоненциально много.

Матус

Это проще - вам нужно учитывать только вершины, смежные с оптимальной вершиной, - к ней не более , и вы можете вычислить их за полиномиальное время .... Чтобы понять, почему это так, рассмотрите многогранник на аффинное подпространство - оно охватывает соседи которые лежат в этом аффинном подпространстве, но это подмножество вершин, смежных с v в исходном многограннике. И да - мне потребовалось совсем немного времени, чтобы увидеть это.

d

$d$

v

$v$

Сариэль Хар-Пелед