Каковы преимущества / недостатки методов внутренних точек по сравнению с симплексным методом для линейной оптимизации?

Насколько я понимаю, поскольку решение линейной программы всегда происходит в вершине ее многогранного выполнимого множества (если решение существует и оптимальное значение целевой функции ограничено снизу, предполагая задачу минимизации), как можно выполнить поиск через интерьер возможного региона будет лучше? Это сходится быстрее? При каких обстоятельствах было бы выгодно использовать симплекс-метод по сравнению с методами внутренней точки? Проще ли реализовать в коде, чем другой?

convex-optimization linear-programming Пол
источник

min_{x \in [- 1, 1]} x^{2}

$\min_{x \in [-1, 1]} x^{2}$

x = 0

$x = 0$

Было бы уместнее сказать «линейная оптимизация» вместо «выпуклая оптимизация»?

Павел

Да, тогда ваше утверждение верно. Спасибо за редактирование вашего вопроса.

Джефф Оксберри

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

Ответы:

Исходя из личного опыта, я бы сказал, что симплекс-методы немного легче понять, как реализовать, чем методы внутренних точек, основываясь на личном опыте реализации как основного симплексного метода, так и базового метода внутренних точек в MATLAB в рамках изучения линейного программирования. , Основными препятствиями в простейшем симплексе являются правильная реализация Фазы I и Фазы II, а также правильное выполнение правила антициклирования. Основные препятствия в реализации метода внутренних точек для линейного программирования, как правило, заключаются в правильной реализации итерационного метода и соответствующем масштабировании параметра барьера.

Вы можете найти более полное обсуждение плюсов и минусов каждого алгоритма в учебнике по линейному программированию, таких как Введение в линейную оптимизацию Берцимаса и Цициклиса. ( Отказ от ответственности: я изучил линейное программирование из этого учебника и взял линейное программирование в Массачусетском технологическом институте от жены Берцимаса.) Вот некоторые из основ:

Плюсы симплекса:

Учитывая переменных решения, обычно сходится в операциях с осями. $n$ $O(n)$ $O(n)$
Использует преимущества геометрии задачи: посещает вершины допустимого множества и проверяет оптимальность для каждой посещенной вершины. (В простом симплексе для этой проверки можно использовать уменьшенную стоимость.)
Хорошо для небольших проблем.

Минусы симплекса:

$n$ $O(2^{n})$
Не так хорошо для больших проблем, потому что операции поворота становятся дорогими. Алгоритмы отсечения или алгоритмы генерации отложенных столбцов, такие как Dantzig-Wolfe, могут иногда компенсировать этот недостаток.

Плюсы методов интерьерной точки:

$O(n^{3.5}L^2\log{L}\log\log{L})$ $L$
Лучше для больших, разреженных задач, потому что линейная алгебра, требуемая для алгоритма, быстрее.

Минусы методов внутренней точки:

Это не так интуитивно удовлетворяет, потому что вы правы, эти методы не посещают вершины. Они бродят по внутренней области, сходясь к решению в случае успеха.
Для небольших задач симплекс, вероятно, будет быстрее. (Вы можете построить патологические случаи, как куб Кли-Минти.)

Джефф Оксберри
источник

Хорошее резюме. На самом деле, похоже, что Клее-Минти создан для того, чтобы смешивать симплексные методы LP ...

@JM Да, в этом и заключается суть - это явная конструкция, показывающая, что симплекс-методы не являются полиномиальными (хотя есть варианты, которые также заставляют плакать методы внутренней точки).

Кристиан Клэйсон

Спасибо за этот информативный пост. Интересно, сколько переменных делают проблему большой? Десятки? Сотни? Тысячи?

KjMag

5^{D}

$5^D$

A

$A$

x^{*}

$x^*$

Ответ прост. Они оба (симплекс и методы внутренней точки) являются зрелой областью с алгоритмической точки зрения. Они оба работают очень хорошо на практике. Хорошая репутация IPM (методы внутренней точки зрения) обусловлена его полиномиальной сложностью в худшем случае. Это не относится к симплексу, который имеет комбинаторную сложность. Тем не менее комбинаторные линейные программы практически никогда не встречаются на практике. Для очень больших задач IP кажется немного быстрее, но это правило не является обязательным. По моему мнению, ИС может быть легко понять и реализовать, но наверняка кто-то еще может не согласиться, и это нормально. Теперь, в LP, если решение уникально, оно определенно будет в вершине (и IP, и Simplex также преуспевают здесь). Решение также может быть на поверхности многогранника или на ребре, в этом случае, смежная вершина (или вершины) также является решением (опять же, IP и симплекс преуспевают). Так что они в значительной степени одинаковы.

Карлос Рамирес
источник

Я понимаю, что приведенный мной пример не был линейной программой; Если вы посмотрите историю изменений, то в более ранней версии этого вопроса предлагалось сравнить методы симплекс-метода и метода внутренних точек для задач выпуклой оптимизации. Я привел контрпример, чтобы оправдать внесенные мною изменения и призвать автора плаката исправить свой вопрос, что он и сделал.

Джефф Оксберри