Куб Клее – Минти

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

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

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

• 1 Описание куба
• 2 Вычислительная сложность
  • 2.1 Худший случай
    • 2.1.1 Алгоритмы следования по пути
  • 2.2 Средний случай
• 3 См. Также
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки
  • 6.1 Алгебраическое описание с иллюстрацией
  • 6.2 Изображения без линейной системы

Куб Клее – Минти был изначально задан с параметризованной системой линейных неравенств с размерностью в качестве параметра. Когда размерность два, «куб» представляет собой сплющенный квадрат. Когда размерность равна трем, «куб» представляет собой сжатый куб. Помимо алгебраических описаний, появились иллюстрации «куба».

Многогранник Кли – Минти задается формулой

$x\; 1\; \le \; 5\; 4\; x\; 1\; +\; x\; 2\; \le \; 25\; 8\; x\; 1\; +\; 4\; x\; 2\; +\; x\; 3\; \le \; 125\; ⋮\; 2\; D\; x\; 1\; +\; 2\; D\; -\; 1\; x\; 2\; +\; \cdots \; +\; 4\; x\; D\; -\; 1\; +\; x\; D\; \le \; 5\; D\; x\; 1\; \ge \; 0,\dots ,\; x\; D\; \ge \; 0.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\_\; \{1\}\; \backslash \; leq\; 5\; \backslash \backslash \; 4x\_\; \{1\}\; +\; x\_\; \{2\}\; \backslash \; leq\; 25\; \backslash \backslash \; 8x\_\; \{1\}\; +\; 4x\_\; \{2\}\; +\; x\_\; \{3\}\; \backslash \; leq\; 125\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; 2\; ^\; \{D\; \}\; x\_\; \{1\}\; +\; 2\; ^\; \{D-1\}\; x\_\; \{2\}\; +\; \backslash \; dots\; +\; 4x\_\; \{D-1\}\; +\; x\_\; \{D\}\; \backslash \; leq\; 5\; ^\; \{D\}\; \backslash \backslash \; x\_\; \{1\}\; \backslash \; geq\; 0,\; \backslash ,\; \backslash ,\; \backslash \; dots,\; \backslash ,\; \backslash ,\; x\_\; \{D\}\; \backslash \; geq\; 0.\; \backslash \; end\; \{align\}\}\}$

У него есть переменные D, ограничения D, отличные от ограничений неотрицательности D, и 2 вершины, как и D-мерный гиперкуб делает. Если целевая функция, которую необходимо максимизировать, равна

$2\; D\; -\; 1\; x\; 1\; +\; 2\; D\; -\; 2\; x\; 2\; +\; \cdots \; +\; 2\; x\; D\; -\; 1\; +\; x\; D,\; \{\backslash \; displaystyle\; 2\; ^\; \{D-1\}\; x\_\; \{1\}\; +\; 2\; ^\; \{D-2\}\; x\_\; \{2\}\; +\; \backslash \; dots\; +\; 2x\_\; \{D-1\}\; +\; x\_\; \{D\},\}$

и если начальной вершиной симплексного алгоритма является начало координат, то алгоритм, как сформулировано Данциг посещает все 2 вершины, достигая, наконец, оптимальной вершины $(0,\; 0,\dots ,\; 5\; D).\; \{\backslash \; displaystyle\; (0,0,\; \backslash \; dots,\; 5\; ^\; \{D\}).\}$

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

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

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

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

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

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

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

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

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

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

1. ^ Клее и Минти (1972)
2. ^Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренней точки? Кубы Кли-Минти ужесточают границы сложности итераций». Математическое программирование. 113 (1): 1–14. CiteSeerX 10.1.1.214.111. doi : 10.1007 / с10 107-006-0044-х. MR 2367063. (требуется подписка). версия в формате pdf на домашней странице профессора Дезы. CS1 maint: ref = harv (ссылка )
3. ^ Deza, Nematollahi Terlaky (2008) ошибка harvtxt: несколько целей (3 ×) : CITEREFDezaNematollahiTerlaky2008 (help )
4. ^ Gartner Ziegler (1994) ошибка harvtxt: несколько целей (2 ×): CITEREFGartnerZiegler1994 (help )
5. ^Greenberg, Harvey J., Klee-Minty Exponential Временная сложность симплекс-метода Университет Колорадо в Денвере (1997) Загрузить PDF
6. ^Мёрти (1983, 14.2 Вычислительная сложность в наихудшем случае, стр. 434–437)
7. ^ Terlaky Zhang (1993)
8. ^Роберт Дж. Блэнд (май 1977 г.). «Новые конечные правила поворота для симплекс-метода». Математика исследования операций. 2 (2): 103–107. doi : 10.1287 / moor.2.2.103. JSTOR 3689647. MR 0459599. CS1 maint: ref = harv (ссылка )
9. ^Мёрти (1983, Глава 10.5, стр. 331–333; проблема 14.8, стр. 439) описывает правило Бланда.
10. ^Мёрти (1983, проблема 14.3, стр. 438; проблема 14.8, п. 439) описывает наихудшую сложность правила Бланда.
11. ^Roos (1990)
12. ^Fukuda Terlaky (1997)
13. ^Megiddo Shub (1989)
14. ^В более общем плане для симплексного алгоритма ожидаемое количество шагов пропорционально D для задач линейного программирования. которые случайным образом взяты из евклидовой единичной сферы, как доказано Боргвардтом и Смейлом.

    Боргвардтом (1987) : Боргвардт, Карл- Хайнц (1987). Симплексный метод: вероятностный анализ. Алгоритмы и комбинаторика (учебные и исследовательские тексты). 1 . Берлин: Springer-Verlag. С. xii + 268. ISBN 978-3-540-17096-9. MR 0868467. CS1 maint: ref = harv (ссылка )

15. ^Фукуда и Намики (1994, стр. 367)
16. ^Фукуда и Терлаки (1997, стр. 385)

• Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Как хорошо они методы внутренней точки? Кубы Кли-Минти ужесточают границы итерационной сложности ". Математическое программирование. 113 (1): 1–14. CiteSeerX 10.1.1.214.111. doi : 10.1007 / s10107-006-0044-x. MR 2367063. CS1 maint: ref = harv (ссылка )
• ; Намики, Макото (март 1994). «Об экстремальном поведении метода наименьшего индекса Мурти». Математическое программирование. 64 (1): 365–370. doi : 10.1007 / BF01582581. MR 1286455. CS1 maint: ref = harv (link )
• ; (1997). Thomas M. Liebling; Dominique de Werra (eds.). «Перекрестные методы: свежий взгляд на алгоритмы поворота ". Математическое программирование, серия B. 79 (Материалы 16-го Международного симпозиума по математическому программированию amming в Лозанне, 1997 г.): 369–395. CiteSeerX 10.1.1.36.9373. doi : 10.1007 / BF02614325. MR 1464775. Препринт Postscript. CS1 maint: ref = harv (ссылка )
• Gartner, B.; Ziegler, GM (1994). Рандомизированные симплексные алгоритмы на Klee- Minty cubes. Foundations of Computer Science, Annual IEEE Symposium on. IEEE. Pp. 502–510. CiteSeerX 10.1.1.24.1405. doi : 10.1109 / SFCS.1994.365741. ISBN 978-0-8186-6580-6. CS1 maint: ref = harv (ссылка )
• Klee, Victor ; (1972). «Насколько хорош симплексный алгоритм?». In Shisha, Oved (ed.). Inequalities III (Труды третьего симпозиума по неравенствам, проведенного в Калифорнийском университете в Лос-Анджелесе, Калифорния, 1–9 сентября 1969 г., посвященная памяти Теодора С. Моцкина). Нью-Йорк-Лондон: Academic Press. Стр. 159–175. MR 0332165. CS1 maint: ref = harv (ссылка )
• Мегиддо, Нимрод ; Майкл Шуб (февраль 1989 г.). «Граничное поведение алгоритмов внутренней точки в линейном программировании». Математика исследования операций. 14 (1): 97–146. CiteSeerX 10.1.1.80.184. doi : 10.1287 / moor.14.1.97. JSTOR 3689840. MR 0984561. CS1 maint: ref = harv (link )
• (1983). Линейное программирование. Нью-Йорк: John Wiley Sons. pp. xix + 482. ISBN 978-0-471-09725-9. MR 0720547. CS1 maint: ref = harv (link )
• Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование. Серия A. 46 (1): 79–84. doi : 10.1007 / BF01585729. MR 1045573. CS1 maint: ref = harv (ссылка )
• Terlaky, Tamás; Zhang, Shu Zhong (1993). Pivot правила линейного программирования: Обзор последних теоретических разработок ». Annals of Operations Research. 46–47 (Вырождение в задачах оптимизации, номер 1): 203–233. CiteSeerX 10.1.1.36.7658. doi : 10.1007 / BF02096264. ISSN 0254-5330. MR 1260019. CS1 maint: ref = harv (ссылка )

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

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

• Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренней точки? Кубы Кли-Минти ужесточают границы сложности итераций». Математическое программирование. 113 (1): 1–14. CiteSeerX 10.1.1.214.111. doi : 10.1007 / s10107-006-0044-x. MR 2367063. (требуется подписка). pdf-версия на домашней странице профессора Дезы. CS1 maint: ref = harv (ссылка )
• Gartner, B.; Ziegler, GM (1994). Рандомизированный симплекс алгоритмы на кубах Кли-Минти. Основы информатики, Ежегодный симпозиум IEEE по IEEE. стр. 502–510. CiteSeerX 10.1.1.24.1405. doi : 10.1109 / SFCS.1994.365741. ISBN 978-0-8186-6580-6. IEEE неправильно записывает имя Gärnter как Gartner (sic.). CS1 maint: ref = harv (ссылка )

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

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