Клее – мятный кубик

Куб Кли Минти для симплексного метода теневых вершин.

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

В частности, многие алгоритмы линейной оптимизации демонстрируют низкую производительность при применении к кубу Кли-Минти. Данцига В 1973 году Кли и Минти показали, что симплексный алгоритм не является алгоритмом с полиномиальным временем при применении к их кубу. Позже модификации куба Кли-Минти показали плохое поведение как для других базисных алгоритмов поворота , так и для алгоритмов внутренней точки.

Описание

Куб Кли-Минти изначально был задан с помощью параметризованной системы линейных неравенств с размерностью в качестве параметра. Куб в двухмерном пространстве — это сплющенный квадрат , а «куб» в трёхмерном пространстве — это сплюснутый куб . Помимо алгебраических описаний появились иллюстрации «куба». Многогранник Кли – Минти имеет вид: $${\begin{aligned}x_{1}&\leq 5\\4x_{1}+x_{2}&\leq 25\\8x_{1}+4x_{2}+x_{3}&\leq 125\\&\vdots \\2^{D}x_{1}+2^{D-1}x_{2}+\dots +4x_{D-1}+x_{D}&\leq 5^{D}\\x_{1}\geq 0,\,\,\dots ,\,\,x_{D}&\geq 0.\end{aligned}}$$

Это имеет $D$ переменные, $D$ ограничения, кроме $D$ ограничения неотрицательности и $2^{D}$ вершины, так же, как $D$- мерный гиперкуб . Если целевая функция, которую необходимо максимизировать, равна $$2^{D-1}x_{1}+2^{D-2}x_{2}+\dots +2x_{D-1}+x_{D},$$ и если начальная вершина для симплексного алгоритма является началом координат, то алгоритм, сформулированный Данцигом, посещает все $2^{D}$ вершины, наконец достигая оптимальной вершины $(0,0,\dots ,5^{D})$.

Вычислительная сложность

Куб Кли-Минти использовался для анализа производительности многих алгоритмов как в худшем, так и в среднем случае. Временная сложность алгоритма достаточное подсчитывает количество арифметических операций, для того, чтобы алгоритм решил задачу. Например, исключение Гаусса требует порядка $D^{3}$ операций, поэтому говорят, что он имеет полиномиальную сложность по времени, поскольку его сложность ограничена кубическим полиномом . Существуют примеры алгоритмов, не обладающих полиномиальной сложностью. Например, обобщение метода исключения Гаусса, называемое алгоритмом Бухбергера, имеет по своей сложности экспоненциальную функцию данных задачи ( степени полиномов и количества переменных многомерных полиномов ). Поскольку экспоненциальные функции в конечном итоге растут намного быстрее, чем полиномиальные функции, экспоненциальная сложность означает, что алгоритм имеет низкую производительность при решении больших задач.

Худший случай

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

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

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

Алгоритмы следования по пути

Дальнейшие модификации куба Кли-Минти показали плохую производительность алгоритмов следования по центральному пути для линейной оптимизации, поскольку центральный путь подходит сколь угодно близко к каждому из углов куба. Такая производительность «преследования вершин» удивительна, поскольку такие алгоритмы отслеживания пути имеют полиномиальную сложность для линейной оптимизации.

Средний случай

Куб Кли-Минти также вдохновил на исследования сложности в среднем случае . Когда подходящие повороты выполняются случайным образом (а не по правилу наискорейшего спуска), симплексный алгоритм Данцига требует в среднем квадратично много шагов ( порядка $O(D^{2})$. Стандартные варианты симплексного алгоритма в среднем занимают $D$ шаги для куба. Однако, согласно Фукуде и Намики (1994) , когда он инициализируется в случайном углу куба, алгоритм крест-накрест посещает только $D$ дополнительные углы. Как симплекс-алгоритм, так и алгоритм крест-накрест посещают в среднем ровно 3 дополнительных угла трехмерного куба.

См. также

• Проективный алгоритм Кармаркара
• Эллипсоидальный алгоритм Хачияна

Ссылки

Библиография

• Бланд, Роберт Г. (май 1977 г.). «Новые конечные правила поворота для симплексного метода». Математика исследования операций . 2 (2): 103–107. дои : 10.1287/moor.2.2.103 . JSTOR   3689647 . МР   0459599 .
• Боргвардт, Карл-Хайнц (1987). Симплексный метод: Вероятностный анализ . Алгоритмы и комбинаторика (Учебные и исследовательские тексты). Том. 1. Берлин: Шпрингер-Верлаг. ISBN  978-3-540-17096-9 . МР   0868467 .
• Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренних точек? Кубы Кли – Минти ужесточают границы сложности итерации» (PDF) . Математическое программирование . 113 (1): 1–14. CiteSeerX   10.1.1.214.111 . дои : 10.1007/s10107-006-0044-x . МР   2367063 . S2CID   156325 .
• Фукуда, Комей ; Намики, Макото (март 1994 г.). «Об экстремальном поведении метода наименьшего индекса Мерти». Математическое программирование . 64 (1): 365–370. дои : 10.1007/BF01582581 . МР   1286455 . S2CID   21476636 .
• Гринберг, Харви Дж. (1997). «Многогранник Кли-Минти показывает экспоненциальную временную сложность симплексного метода» (PDF) . Университет Колорадо в Денвере.
• Фукуда, Комей ; Терлаки, Тамаш (1997). Либлинг, Томас М.; де Верра, Доминик (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. 79 (Документы 16-го Международного симпозиума по математическому программированию, проходившего в Лозанне, 1997 г.): 369–395. CiteSeerX   10.1.1.36.9373 . дои : 10.1007/BF02614325 . МР   1464775 . S2CID   2794181 . Препринт постскриптума .
• Гартнер, Б.; Зиглер, генеральный директор (1994). «Рандомизированные симплекс-алгоритмы на кубах Кли-Минти». Материалы 35-го ежегодного симпозиума по основам информатики . IEEE. стр. 502–510. CiteSeerX   10.1.1.24.1405 . дои : 10.1109/SFCS.1994.365741 . ISBN  978-0-8186-6580-6 . S2CID   8090478 .
• Клее, Виктор ; Минти, Джордж Дж. (1972). «Насколько хорош симплексный алгоритм?». В Шише, Овед (ред.). Неравенства III (Материалы третьего симпозиума по неравенствам, состоявшегося в Калифорнийском университете, Лос-Анджелес, Калифорния, 1–9 сентября 1969 г., посвященного памяти Теодора С. Моцкина) . Нью-Йорк-Лондон: Академическая пресса. стр. 159–175. МР   0332165 .
• Мегиддо, Нимрод ; Шуб, Майкл (февраль 1989 г.). «Граничное поведение алгоритмов внутренних точек в линейном программировании». Математика исследования операций . 14 (1): 97–146. CiteSeerX   10.1.1.80.184 . дои : 10.1287/moor.14.1.97 . JSTOR   3689840 . МР   0984561 .
• Мурти, Катта Г. (1983). Линейное программирование . Нью-Йорк: Джон Уайли и сыновья. стр. XIX+482. ISBN  978-0-471-09725-9 . МР   0720547 .
• Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование . Серия А. 46 (1): 79–84. дои : 10.1007/BF01585729 . МР   1045573 . S2CID   33463483 .
• Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Опорные правила линейного программирования: обзор последних теоретических разработок». Анналы исследования операций . 46 (Вырождение в задачах оптимизации, номер 1): 203–233. CiteSeerX   10.1.1.36.7658 . дои : 10.1007/BF02096264 . ISSN   0254-5330 . МР   1260019 . S2CID   6058077 .

Внешние ссылки

Алгебраическое описание с иллюстрацией

Первые две ссылки имеют как алгебраическую конструкцию, так и изображение трехмерного куба Кли–Минти:

• Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренних точек? Кубы Кли – Минти ужесточают границы сложности итерации» (PDF) . Математическое программирование . 113 (1): 1–14. CiteSeerX   10.1.1.214.111 . дои : 10.1007/s10107-006-0044-x . МР   2367063 . S2CID   156325 .
• Гартнер, Б.; Зиглер, генеральный директор (1994). «Рандомизированные симплекс-алгоритмы на кубах Кли-Минти». Материалы 35-го ежегодного симпозиума по основам информатики . IEEE. стр. 502–510. CiteSeerX   10.1.1.24.1405 . дои : 10.1109/SFCS.1994.365741 . ISBN  978-0-8186-6580-6 . S2CID   8090478 . IEEE неправильно пишет название «Gärnter» как «Gartner» (так в оригинале).

Картинки без линейной системы

• Статьи Э. Нематоллахи, в которых обсуждается кубик Клее-Минти, с иллюстрациями.
• Изображение куба Клее-Минти, показывающее путь симплекс-алгоритма (автоматический перевод немецкого языка ) Гюнтера Циглера . Картинка во второй половине страницы.