Куб Кли-Мятный или Кли-Минти многогранник (названная в честь Виктора Клея и Джордж Дж Минти ) представляет собой блок гиперкуб переменной размерности , углы были возмущены. Кли и Минти показали , что Джордж Данциг «s симплексный алгоритм имеет низкую производительность в худшем случае , когда инициализируется в одном углу их„раздавленного куб“. В трехмерной версии симплекс-алгоритм и алгоритм крест-накрест в худшем случае посещают все 8 углов.
В частности, многие алгоритмы оптимизации для линейной оптимизации демонстрируют низкую производительность при применении к кубу Кли-Минти. В 1973 году Кли и Минти показали, что симплексный алгоритм Данцига не является алгоритмом с полиномиальным временем при применении к их кубу. [1] Позже, модификации куба Кли-Minty показали плохое поведение как для других основы - обмен алгоритмов поворота , а также для алгоритмов внутренних точек. [2]
Описание куба
Куб Кли-Минти изначально был задан параметризованной системой линейных неравенств с размерностью в качестве параметра. Когда размерность равна двум, «куб» представляет собой сплющенный квадрат. Когда измерение равно трем, «куб» представляет собой сжатый куб. Помимо алгебраических описаний появились иллюстрации «куба». [3] [4]
Многогранник Кли – Минти дается формулой [5]
Это имеет D переменные, D , отличные от ограничений D ограничений неотрицательности и 2 D вершины, так же , как D - мерный гиперкуб делает. Если максимальная целевая функция равна
и если начальной вершиной для симплекс-алгоритма является начало координат, то алгоритм, сформулированный Данцигом, посещает все 2 D вершины, наконец достигая оптимальной вершины
Вычислительная сложность
Куб Кли-Минти использовался для анализа производительности многих алгоритмов как в худшем случае, так и в среднем. Временная сложность из алгоритма подсчитывает количество арифметических операций , достаточных для алгоритма , чтобы решить эту проблему. Например, для исключения Гаусса требуется порядка D 3 операций, поэтому говорят, что он имеет полиномиальную временную сложность, потому что его сложность ограничена кубическим полиномом . Есть примеры алгоритмов, не имеющих полиномиальной сложности. Например, обобщение метода исключения Гаусса, называемое алгоритмом Бухбергера, имеет для своей сложности экспоненциальную функцию данных задачи ( степень многочленов и количество переменных многомерных многочленов ). Поскольку экспоненциальные функции в конечном итоге растут намного быстрее, чем полиномиальные, экспоненциальная сложность означает, что алгоритм имеет низкую производительность при решении больших задач.
Худший случай
В математической оптимизации, куб Кли-Минти пример , который показывает , что в худшем случае вычислительная сложность многих алгоритмов в линейной оптимизации . Это деформируется куб ровно 2 D углов в размерности D . Кли и Минти показали , что Данциг в симплексном алгоритме посещение всех углов (возмущенная) кубы в размерности D в худшем случае . [1] [6] [7]
Модификации конструкции Кли-Минти показали аналогичную экспоненциальную временную сложность для других правил поворота симплексного типа, которые поддерживают прямую выполнимость, таких как правило Бланда . [8] [9] [10] Другая модификация показала, что перекрестный алгоритм , который не поддерживает первичную выполнимость, также посещает все углы модифицированного куба Кли-Минти. [7] [11] [12] Как и симплекс-алгоритм, перекрестный алгоритм посещает все 8 углов трехмерного куба в худшем случае.
Алгоритмы следования по пути
Дальнейшие модификации куба Кли-Minty показали низкую эффективность центрального пути алгоритмов -following для линейной оптимизации, в том , что центральный пути приходит сколь угодно близко к каждому из углов кубы. Эта производительность «перехвата вершин» удивительна, потому что такие алгоритмы следования по пути имеют полиномиальную временную сложность для линейной оптимизации. [3] [13]
Средний случай
Куб Клее – Минти также вдохновил на исследования средней сложности . Когда подходящие повороты выполняются случайным образом (а не по правилу наискорейшего спуска), симплексный алгоритм Данцига требует в среднем квадратично большого числа шагов ( порядка O ( D 2 ). [4] Стандартные варианты симплексного алгоритма в среднем занимают D шагов для куба. [14] Когда он инициализируется в случайном углу куба, алгоритм перекрестного пересечения посещает только D дополнительных углов, однако, согласно статье 1994 года Фукуда и Намики. [15] [16] Оба симплексный алгоритм и алгоритм крест-накрест в среднем посещают ровно 3 дополнительных угла трехмерного куба.
Смотрите также
- Проективный алгоритм Кармаркара
- Эллипсоидальный алгоритм Хачияна
Заметки
- ^ a b Клее и Минти (1972)
- ^ Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренней точки? Кубы Кли-Минти ужесточают границы сложности итераций». Математическое программирование . 113 (1): 1–14. CiteSeerX 10.1.1.214.111 . DOI : 10.1007 / s10107-006-0044-х . Руководство по ремонту 2367063 . (требуется подписка) . pdf-версию на домашней странице профессора Дезы .
- ^ a b Deza, Nematollahi & Terlaky (2008) ошибка harvtxt: несколько целей (3 ×): CITEREFDezaNematollahiTerlaky2008 ( справка )
- ^ a b Gartner & Ziegler (1994) ошибка harvtxt: несколько целей (2 ×): CITEREFGartnerZiegler1994 ( справка )
- ^ Гринберг, Харви Дж., Многогранник Кли-Минти демонстрирует экспоненциальную временную сложность симплекс-метода Университет Колорадо в Денвере (1997) Скачать PDF
- ^ Мурти (1983 , 14,2 Пессимистический вычислительная сложность, стр. 434-437)
- ^ a b Терлаки и Чжан (1993)
- ^ Блэнд, Роберт Г. (май 1977 г.). «Новые правила конечного поворота для симплекс-метода». Математика исследования операций . 2 (2): 103–107. DOI : 10.1287 / moor.2.2.103 . JSTOR 3689647 . Руководство по ремонту 0459599 .
- ^ Мёрти (1983 , глава 10.5, стр. 331–333; проблема 14.8, стр. 439) описывает правило Блэнда .
- ^ Мёрти (1983 , проблема 14.3, стр. 438; проблема 14.8, стр. 439) описывает сложность наихудшего случая правила Бланда.
- ^ Роос (1990)
- ^ Фукуда & Terlaky (1997)
- ↑ Мегиддо и Шуб (1989)
- ^ В более общем смысле для симплексного алгоритма ожидаемое количество шагов пропорционально D для задач линейного программирования, которые случайным образом извлекаются из евклидовой единичной сферы , как было доказано Боргвардтом и Смейлом .
Боргвардт (1987) : Боргвардт, Карл-Хайнц (1987). Симплексный метод: вероятностный анализ . Алгоритмы и комбинаторика (учебные и исследовательские тексты). 1 . Берлин: Springer-Verlag. С. xii + 268. ISBN 978-3-540-17096-9. Руководство по ремонту 0868467 .
- ↑ Фукуда и Намики (1994 , с. 367)
- ^ Фукуда & Terlaky (1997 , стр. 385)
Рекомендации
- Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренней точки? Кубы Кли-Минти ужесточают границы сложности итераций». Математическое программирование . 113 (1): 1–14. CiteSeerX 10.1.1.214.111 . DOI : 10.1007 / s10107-006-0044-х . Руководство по ремонту 2367063 .
- Фукуда, Комей ; Намики, Макото (март 1994). «Об экстремальном поведении метода наименьшего индекса Мурти». Математическое программирование . 64 (1): 365–370. DOI : 10.1007 / BF01582581 . Руководство по ремонту 1286455 .
- Фукуда, Комей ; Терлаки, Тамаш (1997). Томас М. Либлинг; Доминик де Верра (ред.). «Перекрестные методы: свежий взгляд на алгоритмы разворота». Математическое программирование, серия B . 79 (Материалы 16-го Международного симпозиума по математическому программированию, состоявшегося в Лозанне, 1997 г.): 369–395. CiteSeerX 10.1.1.36.9373 . DOI : 10.1007 / BF02614325 . Руководство по ремонту 1464775 . Постскриптум препринт .
- Gartner, B .; Зиглер, GM (1994). Рандомизированные симплексные алгоритмы на кубах Кли-Минти . Основы компьютерных наук, Ежегодный симпозиум IEEE по . IEEE. С. 502–510. CiteSeerX 10.1.1.24.1405 . DOI : 10.1109 / SFCS.1994.365741 . ISBN 978-0-8186-6580-6.
- Клее, Виктор ; Минти, Джордж Дж. (1972). «Насколько хорош симплексный алгоритм?». В кальяне, Овед (ред.). Неравенства III (Труды Третьего симпозиума по неравенству, проходившего в Калифорнийском университете, Лос-Анджелес, Калифорния, 1–9 сентября 1969 г., посвященного памяти Теодора С. Моцкина) . Нью-Йорк-Лондон: Academic Press. С. 159–175. Руководство по ремонту 0332165 .
- Мегиддо, Нимрод ; Шуб, Михаил (февраль 1989 г.). «Граничное поведение алгоритмов внутренней точки в линейном программировании». Математика исследования операций . 14 (1): 97–146. CiteSeerX 10.1.1.80.184 . DOI : 10.1287 / moor.14.1.97 . JSTOR 3689840 . Руководство по ремонту 0984561 .
- Мурти, Катта Г. (1983). Линейное программирование . Нью-Йорк: Джон Вили и сыновья. С. xix + 482. ISBN 978-0-471-09725-9. Руководство по ремонту 0720547 .
- Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование . Series A. 46 (1): 79–84. DOI : 10.1007 / BF01585729 . Руководство по ремонту 1045573 .
- Терлаки, Тамаш; Чжан, Шу Чжун (1993). «Правила поворота для линейного программирования: обзор последних теоретических разработок». Анналы исследований операций . 46–47 (Вырождение в задачах оптимизации, номер 1): 203–233. CiteSeerX 10.1.1.36.7658 . DOI : 10.1007 / BF02096264 . ISSN 0254-5330 . Руководство по ремонту 1260019 .
Внешние ссылки
Алгебраическое описание с иллюстрацией
Первые две ссылки имеют как алгебраическую конструкцию, так и изображение трехмерного куба Кли – Минти:
- Деза, Антуан; Нематоллахи, Эйсса; Терлаки, Тамаш (май 2008 г.). «Насколько хороши методы внутренней точки? Кубы Кли-Минти ужесточают границы сложности итераций». Математическое программирование . 113 (1): 1–14. CiteSeerX 10.1.1.214.111 . DOI : 10.1007 / s10107-006-0044-х . Руководство по ремонту 2367063 . (требуется подписка) . pdf-версию на домашней странице профессора Дезы .
- Gartner, B .; Зиглер, 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» (так в оригинале).
Картинки без линейной системы
- Статьи Э. Нематоллахи, в которых обсуждается куб Клее-Минти с иллюстрациями.
- Изображение куба Кли-Минти, показывающее путь симплекс-алгоритма (автоматический перевод немецкого языка ), сделанный Гюнтером Циглером . Картинка во второй половине страницы.