Алгоритм крест-накрест

Эта статья об алгоритме математической оптимизации. Чтобы узнать о других значениях, см. «Перекресток» .

алгоритм крест-накрест посещает все 8 углов куба Кли-Минти В худшем случае . В среднем он посещает 3 дополнительных угла. Куб Кли-Минти представляет собой возмущение показанного здесь куба.

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

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

История

Алгоритм крест-накрест был независимо опубликован Тамашем Терлаки. and by Zhe-Min Wang; связанные алгоритмы появились в неопубликованных отчетах других авторов.

Сравнение с симплексным алгоритмом линейной оптимизации

См. также: Линейное программирование , Симплексный алгоритм и правило Бланда.

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

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

Алгоритм крест-накрест проще, чем симплекс-алгоритм, поскольку алгоритм крест-накрест имеет только одну фазу. Его правила поворота аналогичны правилу поворота наименьшего индекса Бланда . Правило Блэнда использует только знаки коэффициентов, а не их (действительный) порядок при принятии решения о подходящих разворотах. Правило Блэнда выбирает входные переменные путем сравнения значений приведенных затрат, используя упорядочивание действительных чисел подходящих опорных точек. В отличие от правила Бланда, алгоритм крест-накрест является «чисто комбинаторным», выбирая входную и выходную переменную, учитывая только знаки коэффициентов, а не порядок их действительных чисел. Алгоритм крест-накрест был применен для получения конструктивных доказательств основных результатов линейной алгебры , таких как лемма Фаркаша .

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

Описание

Алгоритм перекрещивания работает со стандартной сводной таблицей (или с вычисляемыми на лету частями таблицы, если она реализована как пересмотренный симплекс-метод). На общем этапе, если таблица является простой или двойственной недопустимой, она выбирает одну из недопустимых строк/столбцов в качестве основной строки/столбца, используя правило выбора индекса. Важным свойством является то, что выбор осуществляется по объединению недопустимых индексов и стандартная версия алгоритма не различает индексы столбцов и строк (т. е. индексы столбцов, основные в строках). Если выбрана строка, то алгоритм использует правило выбора индекса для определения положения опорного элемента двойного типа, а если выбран столбец, то он использует правило выбора индекса для поиска положения строки и выполняет поворот основного типа.

Вычислительная сложность: худшие

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

Некоторые алгоритмы линейного программирования , Хачияна — эллипсоидный алгоритм проективный и Кармаркара алгоритм алгоритмы центрального пути — имеют полиномиальную временную сложность (в худшем случае и, следовательно, в среднем ). Эллипсоидальный и проективный алгоритмы были опубликованы до алгоритма крест-накрест.

Однако, как и симплекс-алгоритм Данцига, алгоритм крест-накрест не является алгоритмом линейного программирования с полиномиальным временем. Алгоритм перекрещивания Терлаки посещает все 2 ^Д углы (возмущенного) куба в размерности D согласно статье Рооса; Статья Рооса модифицирует конструкцию Клее -Минти куба , на которой симплексный алгоритм принимает 2 ^Д шаги. Как и симплексный алгоритм, алгоритм крест-накрест в худшем случае посещает все 8 углов трехмерного куба.

когда он инициализируется в случайном углу куба, алгоритм крест-накрест посещает только D дополнительных углов. Однако, согласно статье Фукуды и Намики 1994 года, Тривиально, симплексный алгоритм требует в среднем D шагов для куба. Как и симплексный алгоритм, алгоритм крест-накрест в среднем посещает ровно 3 дополнительных угла трехмерного куба.

Варианты

Алгоритм крест-накрест был расширен для решения более общих задач, чем задачи линейного программирования.

задачи оптимизации с

Существуют варианты алгоритма крест-накрест для линейного программирования, для квадратичного программирования и для задачи линейной дополнительности с «достаточными матрицами»; и наоборот, для задач линейной дополнительности алгоритм крест-накрест завершается конечно, только если матрица является достаточной матрицей. Достаточной матрицей является обобщение как положительно определенной матрицы, так и P-матрицы , главные миноры которой положительны. Алгоритм крест-накрест был адаптирован и для дробно-линейного программирования .

Перечисление вершин

Алгоритм перекрещивания использовался в алгоритме перечисления всех вершин многогранника , который был опубликован Дэвидом Ависом и Комеи Фукуда в 1992 году. Эвис и Фукуда представили алгоритм, который находит v вершины многогранника, заданного невырожденной системой n линейных неравенств в D измерениях (или, вдвойне, v граней выпуклой оболочки из n точек в D измерениях, где каждая грань содержит ровно D заданных точек) во времени O ( nDv ) и O( nD ) пространстве .

Ориентированные матроиды

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

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

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

Резюме

Алгоритм крест-накрест — это упрощенно сформулированный алгоритм линейного программирования. Это был второй полностью комбинаторный алгоритм линейного программирования. Частично комбинаторный симплексный алгоритм циклов Бленда на некоторых (нереализуемых) ориентированных матроидах. Первый полностью комбинаторный алгоритм был опубликован Тоддом, и он также похож на симплексный алгоритм в том смысле, что сохраняет осуществимость после создания первого допустимого базиса; однако правило Тодда сложное. Алгоритм крест-накрест не является симплексным алгоритмом, поскольку ему не требуется поддерживать осуществимость. Однако алгоритм крест-накрест не имеет полиномиальной временной сложности.

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

См. также

• Джек Эдмондс (пионер комбинаторной оптимизации и теоретик ориентированного матроида; научный руководитель Комэя Фукуды)

Ссылки

• Авис, Дэвид ; Фукуда, Комэй (декабрь 1992 г.). «Алгоритм поворота для выпуклых оболочек и перечисления вершин компоновок и многогранников» . Дискретная и вычислительная геометрия . 8 (Симпозиум ACM по вычислительной геометрии (Норт-Конвей, Нью-Хэмпшир, 1991), номер 1): 295–313. дои : 10.1007/BF02293050 . МР   1174359 .
• Чизмадия, Жолт; Иллес, Тибор (2006). «Новые алгоритмы типа крест-накрест для задач линейной дополнительности с достаточными матрицами» (PDF) . Методы оптимизации и программное обеспечение . 21 (2): 247–266. дои : 10.1080/10556780500095009 . МР   2195759 . S2CID   24418835 . Архивировано из оригинала (pdf) 23 сентября 2015 года . Проверено 30 августа 2011 г.
• Фукуда, Комей ; Намики, Макото (март 1994 г.). «Об экстремальном поведении метода наименьшего индекса Мерти». Математическое программирование . 64 (1): 365–370. дои : 10.1007/BF01582581 . МР   1286455 . S2CID   21476636 .
• Фукуда, Комей ; Терлаки, Тамаш (1997). Либлинг, Томас М.; де Верра, Доминик (ред.). «Перекрестные методы: свежий взгляд на алгоритмы поворота». Математическое программирование, серия Б. 79 (Документы 16-го Международного симпозиума по математическому программированию, проходившего в Лозанне, 1997 г., номера 1–3): 369–395. CiteSeerX   10.1.1.36.9373 . дои : 10.1007/BF02614325 . МР   1464775 . S2CID   2794181 . Препринт постскриптума .
• ден Хертог, Д.; Роос, К.; Терлаки, Т. (1 июля 1993 г.). «Проблема линейной дополнительности, достаточные матрицы и метод крест-накрест» (PDF) . Линейная алгебра и ее приложения . 187 : 1–14. дои : 10.1016/0024-3795(93)90124-7 . МР   1221693 .
• Иллес, Тибор; Сирмаи, Акос; Терлаки, Тамаш (1999). «Метод конечных перекрещиваний гиперболического программирования» . Европейский журнал операционных исследований . 114 (1): 198–214. дои : 10.1016/S0377-2217(98)00049-6 . Збл   0953.90055 . Препринт постскриптума .
• Клафски, Эмиль; Терлаки, Тамаш (июнь 1991 г.). «Роль поворота в доказательстве некоторых фундаментальных теорем линейной алгебры» . Линейная алгебра и ее приложения . 151 : 97–118. дои : 10.1016/0024-3795(91)90356-2 . МР   1102142 .
• Роос, К. (1990). «Экспоненциальный пример правила поворота Терлаки для симплексного метода крест-накрест». Математическое программирование . Серия А. 46 (1): 79–84. дои : 10.1007/BF01585729 . МР   1045573 . S2CID   33463483 .
• Терлаки, Т. (1985). «Конвергентный метод крест-накрест». Оптимизация: журнал математического программирования и исследования операций . 16 (5): 683–690. дои : 10.1080/02331938508843067 . ISSN   0233-1934 . МР   0798939 .
• Терлаки, Тамаш (1987). «Конечный метод крест-накрест для ориентированных матроидов» . Журнал комбинаторной теории . Серия Б. 42 (3): 319–327. дои : 10.1016/0095-8956(87)90049-9 . ISSN   0095-8956 . МР   0888684 .
• Терлаки, Тамаш ; Чжан, Шу Чжун (1993) [1991]. «Опорные правила линейного программирования: обзор последних теоретических разработок». Анналы исследования операций . 46–47 (Вырождение в задачах оптимизации, номер 1): 203–233. CiteSeerX   10.1.1.36.7658 . дои : 10.1007/BF02096264 . ISSN   0254-5330 . МР   1260019 . S2CID   6058077 .
• Ван, Чжэ Минь (1987). «Конечный алгоритм без конформного исключения над ориентированным матроидным программированием». Китайские анналы математики (Шюсюэ Нянькан Б Цзи) . Серия Б. 8 (1): 120–125. ISSN   0252-9599 . МР   0886756 .

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

• Комей Фукуда (ETH Zentrum, Цюрих) с публикациями
• Тамаш Терлаки (Университет Лихай) с публикациями. Архивировано 28 сентября 2011 г. в Wayback Machine.