Аффинное масштабирование - Affine scaling

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

В математическая оптимизация, аффинное масштабирование является алгоритм для решения линейное программирование проблемы. В частности, это метод внутренней точки, обнаруженный Советский математик И. И. Дикин в 1967 г. и заново открыл в НАС. в середине 1980-х гг.

История

Аффинное масштабирование имеет историю множественное открытие. Впервые он был опубликован И. И. Дикиным в Институте энергетических систем РАН (в то время Сибирский энергетический институт АН СССР) в 1967 г. Доклады Академии Наук СССР, за которым последовало доказательство его сходимости в 1974 г.^[1] Работа Дикина оставалась практически незамеченной до открытия в 1984 г. Алгоритм Кармаркара, первый практический полиномиальное время алгоритм линейного программирования. Важность и сложность метода Кармаркара побудили математиков искать более простой вариант.

Затем несколько групп независимо друг от друга разработали вариант алгоритма Кармаркара. Э. Р. Барнс в IBM,^[2] команда во главе с Р. Дж. Вандербей в AT&T,^[3] и несколько других заменили проективные преобразования который Кармаркар использован аффинный ед. Спустя несколько лет стало понятно, что «новые» алгоритмы аффинного масштабирования на самом деле являются переосмыслением результатов Дикина, полученных несколько десятилетий назад.^[1]^[4] Из открывателей только Барнс и Вандербей и другие. удалось провести анализ свойств сходимости аффинного масштабирования. Кармаркар, который также использовал аффинное масштабирование в этот период времени, ошибочно полагал, что оно сходится так же быстро, как и его собственный алгоритм.^[5]^:346

Алгоритм

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

Обе фазы решают линейные программы в форме равенства, а именно.

свести к минимуму

c \cdot Икс

при условии

Топор = б

,

Икс \geq 0

.

Эти проблемы решаются с помощью итерационный метод, который концептуально продолжается путем построения траектории точек строго внутри допустимой области задачи, вычисляя прогнозируемый градиентный спуск шаги в масштабированной версии проблемы, а затем масштабирование шага обратно к исходной проблеме. Масштабирование гарантирует, что алгоритм может продолжать делать большие шаги, даже если рассматриваемая точка близка к границе допустимой области.^[5]^:337

Формально итерационный метод, лежащий в основе аффинного масштабирования, принимает в качестве входных данных $А$ , $б$ , $c$ , первоначальное предположение $Икс 0 > 0$ что строго выполнимо (т. е. $Топор 0 = б$ ), допуск $ε$ и шаг $β$ . Затем он повторяет^[1]^:111

Позволять $D k$ быть диагональная матрица с $Икс k$ по его диагонали.
Вычислить вектор двойной переменные:
${ displaystyle w ^ {k} = (AD_ {k} ^ {2} A ^ { operatorname {T}}) ^ {- 1} AD_ {k} ^ {2} c.}$
Вычислить вектор снижение затрат, которые измеряют расслабленность ограничений-неравенств в дуале:
${ displaystyle r ^ {k} = c-A ^ { operatorname {T}} w ^ {k}.}$
Если ${ displaystyle r ^ {k}> 0}$ и ${ displaystyle mathbf {1} ^ { operatorname {T}} D_ {k} r ^ {k} < varepsilon}$ , текущее решение $Икс k$ является $ε$ -оптимально.
Если ${ displaystyle -D_ {k} r ^ {k} geq 0}$ , проблема неограниченна.
Обновлять ${ displaystyle x ^ {k + 1} = x ^ {k} - beta { frac {D_ {k} ^ {2} r ^ {k}} { | D_ {k} r ^ {k} |}}}$

Инициализация

Фаза I, инициализация, решает вспомогательную задачу с дополнительной переменной $ты$ и использует результат, чтобы получить начальную точку для исходной проблемы. Позволять $Икс 0$ - произвольная строго положительная точка; это не обязательно должно быть выполнимым для исходной проблемы. Невозможность $Икс 0$ измеряется вектором

{ displaystyle v = b-Ax ^ {0}}

.

Если $v = 0$ , $Икс 0$ возможно. Если это не так, этап I решает вспомогательную проблему.

свести к минимуму

ты

при условии

Топор + УФ = б

,

Икс \geq 0

,

ты \geq 0

.

Эта задача имеет правильный вид для решения с помощью описанного выше итерационного алгоритма,^[а] и

{ displaystyle { begin {pmatrix} x ^ {0} 1 end {pmatrix}}}

это возможная начальная точка. Решение вспомогательной задачи дает

{ displaystyle { begin {pmatrix} x ^ {*} u ^ {*} end {pmatrix}}}

.

Если $ты * = 0$ , тогда $Икс * = 0$ выполнима в исходной задаче (хотя и не обязательно строго внутренней), а если $ты * > 0$ , исходная проблема невозможна.^[5]^:343

Анализ

Хотя аффинное масштабирование легко сформулировать, было трудно проанализировать. Его сходимость зависит от размера шага, $β$ . Для размеров шага $β \leq 2 / 3$ , Вариант аффинного масштабирования Вандербея сходится, а для $β > 0.995$ известен пример проблемы, которая сходится к неоптимальному значению.^[5]^:342 Было показано, что другие варианты алгоритма демонстрируют хаотичный поведение даже при небольших проблемах, когда $β > 2 / 3$ .^[6]^[7]

Примечания

^ Структура вспомогательной задачи позволяет упростить формулы.^[5]^:344

дальнейшее чтение

Адлер, Илан; Монтейро, Ренато Д. К. (1991). «Предельное поведение аффинных масштабируемых непрерывных траекторий для задач линейного программирования» (PDF). Математическое программирование. 50 (1–3): 29–51. Дои:10.1007 / bf01594923.
Сайгал, Ромеш (1996). "Простое доказательство первичного метода аффинного масштабирования" (PDF). Анналы исследований операций. 62: 303–324. Дои:10.1007 / bf02206821.
Ценг, Пол; Ло, Чжи-Цюань (1992). «О сходимости алгоритма аффинного масштабирования» (PDF). Математическое программирование. 56 (1–3): 301–319. CiteSeerX 10.1.1.94.7852. Дои:10.1007 / bf01580904. HDL:1721.1/3161.

внешняя ссылка

«15.093 Методы оптимизации, Лекция 21: Алгоритм аффинного масштабирования» (PDF). MIT OpenCourseWare. 2009.
Митчелл, Джон (ноябрь 2010 г.). "Методы внутренней точки". Политехнический институт Ренсселера.
«Лекция 6: Метод внутренней точки» (PDF). NCTU OpenCourseWare. Архивировано из оригинал (PDF) на 2016-10-11. Получено 2016-02-06.

[6] Структура вспомогательной задачи позволяет упростить формулы.^[5]^:344

[vanderbei90-1] а ^б ^c Vanderbei, R.J .; Лагариас, Дж. К. (1990). «Результат сходимости И. И. Дикина для алгоритма аффинного масштабирования». Математические разработки, вытекающие из линейного программирования (Brunswick, ME, 1988). Современная математика. 114. Провиденс, Род-Айленд: Американское математическое общество. С. 109–119. Дои:10,1090 / conm / 114/1097868. МИСТЕР 1097868.

[2] Барнс, Эрл Р. (1986). «Вариант алгоритма Кармаркара для решения задач линейного программирования». Математическое программирование. 36 (2): 174–182. Дои:10.1007 / BF02592024.

[3] Вандербей, Роберт Дж .; Meketon, Marc S .; Фридман, Барри А. (1986). «Модификация алгоритма линейного программирования Кармаркара» (PDF). Алгоритмика. 1 (1–4): 395–407. Дои:10.1007 / BF01840454.

[4] Байер, Д. А .; Лагариас, Дж. К. (1989). «Нелинейная геометрия линейного программирования I: аффинные и проективные масштабные траектории» (PDF). Труды Американского математического общества. 314 (2): 499. Дои:10.1090 / S0002-9947-1989-1005525-6.

[lpfe-5] а ^б ^c ^d ^е Вандербей, Роберт Дж. (2001). Линейное программирование: основы и расширения. Springer Verlag. С. 333–347.

[7] Bruin, H .; Fokkink, R.J .; Gu, G .; Роос, К. (2014). «О хаотическом поведении алгоритма прямого и двойственного аффинного масштабирования для линейной оптимизации» (PDF). Хаос. 24 (4): 043132. arXiv:1409.6108. Bibcode:2014 Хаос..24d3132B. Дои:10.1063/1.4902900. PMID 25554052.

[8] Кастильо, Илеана; Барнс, Эрл Р. (2006). «Хаотическое поведение алгоритма аффинного масштабирования для линейного программирования». СИАМ Дж. Оптим. 11 (3): 781–795. Дои:10.1137 / S1052623496314070.

[1]

[2]

[3]

[4]

[5]

[а]

[6]

[7]