В математической оптимизации алгоритм «крест-накрест» — это любой из семейства алгоритмов линейного программирования . Варианты алгоритма «крест-накрест» также решают более общие задачи с линейными ограничениями неравенства и нелинейными целевыми функциями ; существуют алгоритмы «крест-накрест» для задач линейно-дробного программирования , [1] [2] задач квадратичного программирования и задач линейной комплементарности . [3]
Как и симплексный алгоритм Джорджа Б. Данцига , алгоритм крест-накрест не является алгоритмом полиномиального времени для линейного программирования. Оба алгоритма посещают все 2 D- углы (возмущенного) куба размерности D , куба Кли–Минти (в честь Виктора Клее и Джорджа Дж. Минти ), в худшем случае . [4] [5] Однако, когда он запускается со случайного угла, алгоритм крест-накрест в среднем посещает только D дополнительных углов. [6] [7] [8] Таким образом, для трехмерного куба алгоритм посещает все 8 углов в худшем случае и ровно 3 дополнительных угла в среднем.
Алгоритм «крест-накрест» был опубликован независимо Тамашем Терлаки [9] и Чжэ-Мином Вангом [10] ; связанные алгоритмы появились в неопубликованных отчетах других авторов [3] .
В линейном программировании алгоритм крест-накрест вращается между последовательностью базисов, но отличается от симплексного алгоритма . Симплексный алгоритм сначала находит (первичный) допустимый базис, решая « задачу фазы один »; на «фазе два» симплексный алгоритм вращается между последовательностью базисных допустимых решений так, что целевая функция не уменьшается с каждым поворотом, завершаясь оптимальным решением (также в конечном итоге находя «двойное допустимое» решение). [3] [11]
Алгоритм крест-накрест проще, чем симплексный алгоритм, потому что алгоритм крест-накрест имеет только одну фазу. Его правила поворота аналогичны правилу поворота с наименьшим индексом Бланда . [12] Правило Бланда использует только знаки коэффициентов, а не их (действительный) порядок при принятии решения о приемлемых поворотах. Правило Бланда выбирает входящие переменные, сравнивая значения приведенных затрат, используя действительный порядок допустимых поворотов. [12] [13] В отличие от правила Бланда, алгоритм крест-накрест является «чисто комбинаторным», выбирая входящую переменную и выходящую переменную, учитывая только знаки коэффициентов, а не их действительный порядок. [3] [11] Алгоритм крест-накрест применялся для предоставления конструктивных доказательств основных результатов в линейной алгебре , таких как лемма Фаркаша . [14]
В то время как большинство симплексных вариантов являются монотонными по цели (строго в невырожденном случае), большинство вариантов алгоритма «крест-накрест» не имеют монотонной оценочной функции, что может быть недостатком на практике.
Алгоритм крест-накрест работает на стандартной сводной таблице (или на вычисляемых на лету частях таблицы, если реализовано как пересмотренный симплексный метод). На общем этапе, если таблица является первичной или двойной недопустимой, она выбирает одну из недопустимых строк/столбцов в качестве сводной строки/столбца с использованием правила выбора индекса. Важным свойством является то, что выбор делается на основе объединения недопустимых индексов, а стандартная версия алгоритма не различает индексы столбцов и строк (то есть индексы столбцов являются базовыми в строках). Если выбрана строка, то алгоритм использует правило выбора индекса для определения позиции для сводной таблицы двойного типа, в то время как если выбран столбец, то он использует правило выбора индекса для поиска позиции строки и выполняет сводную таблицу первичного типа.
Временная сложность алгоритма подсчитывает количество арифметических операций, достаточных для того, чтобы алгоритм решил задачу. Например, исключение Гаусса требует порядка D 3 операций , и поэтому говорят, что оно имеет полиномиальную временную сложность, потому что его сложность ограничена кубическим полиномом . Существуют примеры алгоритмов , которые не имеют полиномиальной временной сложности. Например, обобщение исключения Гаусса, называемое алгоритмом Бухбергера, имеет для своей сложности экспоненциальную функцию от данных задачи ( степень полиномов и количество переменных многомерных полиномов ). Поскольку экспоненциальные функции в конечном итоге растут намного быстрее, чем полиномиальные функции, экспоненциальная сложность подразумевает, что алгоритм имеет низкую производительность на больших задачах.
Несколько алгоритмов линейного программирования — эллипсоидальный алгоритм Хачияна , проективный алгоритм Кармаркара и алгоритмы центрального пути — имеют полиномиальную временную сложность (в худшем случае и, следовательно, в среднем ). Эллипсоидальные и проективные алгоритмы были опубликованы до алгоритма крест-накрест.
Однако, как и симплексный алгоритм Данцига, алгоритм «крест-накрест» не является алгоритмом полиномиального времени для линейного программирования. Алгоритм «крест-накрест» Терлаки посещает все 2 -мерные углы (возмущенного) куба размерности D , согласно статье Руса; статья Руса модифицирует конструкцию Кли -Минти куба , на которой симплексный алгоритм делает 2 -мерные шаги. [3] [4] [5] Как и симплексный алгоритм, алгоритм «крест-накрест» посещает все 8 углов трехмерного куба в худшем случае.
Однако, согласно статье Фукуды и Намики 1994 года, при инициализации в случайном углу куба алгоритм «крест-накрест» посещает только D дополнительных углов. [6] [7] Тривиально, симплексный алгоритм в среднем занимает D шагов для куба. [8] [15] Как и симплексный алгоритм, алгоритм «крест-накрест» посещает в среднем ровно 3 дополнительных угла трехмерного куба.
Алгоритм «крест-накрест» был расширен для решения более общих задач, чем задачи линейного программирования.
Существуют варианты алгоритма «крест-накрест» для линейного программирования, для квадратичного программирования и для задачи линейной дополнительности с «достаточными матрицами»; [3] [6] [16] [17] [18] [19] наоборот, для задач линейной дополнительности алгоритм «крест-накрест» завершается конечно, только если матрица является достаточной матрицей. [18] [19] Достаточная матрица является обобщением как положительно-определенной матрицы , так и P-матрицы , главные миноры которой положительны. [18] [19] [20] Алгоритм «крест-накрест» был также адаптирован для дробно-линейного программирования . [1] [2]
Алгоритм крест-накрест использовался в алгоритме перечисления всех вершин многогранника , опубликованном Дэвидом Ависом и Комеем Фукудой в 1992 году. [21] Авис и Фукуда представили алгоритм, который находит v вершин многогранника, заданного невырожденной системой n линейных неравенств в D измерениях (или, двойственно, v граней выпуклой оболочки из n точек в D измерениях, где каждая грань содержит ровно D заданных точек) за время O ( nDv ) и O( nD ) пространства . [22]
Алгоритм крест-накрест часто изучается с использованием теории ориентированных матроидов (OM), которая является комбинаторной абстракцией теории линейной оптимизации. [17] [23] Действительно, правило поворота Бланда было основано на его предыдущих работах по теории ориентированных матроидов. Однако правило Бланда демонстрирует цикличность в некоторых задачах линейного программирования ориентированных матроидов. [17] Первый чисто комбинаторный алгоритм для линейного программирования был разработан Майклом Дж. Тоддом. [17] [24] Алгоритм Тодда был разработан не только для линейного программирования в условиях ориентированных матроидов, но также для задач квадратичного программирования и задач линейной дополнительности . [17] [24] К сожалению, алгоритм Тодда сложен даже для формулировки, и его доказательства конечной сходимости довольно сложны. [17]
Алгоритм крест-накрест и его доказательство конечного завершения можно просто сформулировать и легко расширить настройку ориентированных матроидов. Алгоритм может быть еще более упрощен для линейных задач осуществимости , то есть для линейных систем с неотрицательными переменными ; эти задачи можно сформулировать для ориентированных матроидов. [14] Алгоритм крест-накрест был адаптирован для задач, которые сложнее линейного программирования: существуют также варианты ориентированных матроидов для задачи квадратичного программирования и для задачи линейной дополнительности. [3] [16] [17]
Алгоритм «крест-накрест» — это просто сформулированный алгоритм для линейного программирования. Это был второй полностью комбинаторный алгоритм для линейного программирования. Частично комбинаторный симплексный алгоритм циклов Бланда на некоторых (нереализуемых) ориентированных матроидах. Первый полностью комбинаторный алгоритм был опубликован Тоддом, и он также похож на симплексный алгоритм в том, что сохраняет осуществимость после генерации первого допустимого базиса; однако правило Тодда сложное. Алгоритм «крест-накрест» не является симплексоподобным алгоритмом, поскольку ему не нужно поддерживать осуществимость. Однако алгоритм «крест-накрест» не имеет полиномиальной временной сложности.
Исследователи расширили алгоритм крест-накрест для многих задач оптимизации, включая линейно-дробное программирование. Алгоритм крест-накрест может решать задачи квадратичного программирования и задачи линейной комплементарности, даже в условиях ориентированных матроидов. Даже будучи обобщенным, алгоритм крест-накрест остается просто сформулированным.
Rockafellar, RT (1969). "Элементарные векторы подпространства R N {\displaystyle R^{N}} (1967)" (PDF) . В RC Bose и TA Dowling (ред.). Комбинаторная математика и ее приложения . Серия монографий Университета Северной Каролины по теории вероятностей и статистике. Чапел-Хилл, Северная Каролина: Издательство Университета Северной Каролины. стр. 104–127. MR 0278972. Перепечатка в формате PDF.
На Рокафеллара оказали влияние более ранние исследования Альберта В. Такера и Джорджа Дж. Минти . Такер и Минти изучали знаковые закономерности матриц, возникающих в результате поворотных операций симплексного алгоритма Данцига.