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

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

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

История

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

Затем несколько групп независимо друг от друга разработали вариант алгоритма Кармаркара. Э.Р. Барнс из IBM , команда под руководством Р. Дж. Вандербея из AT&T , и ряд других заменили проективные преобразования , которые Кармаркар использовал , аффинными . Через несколько лет стало понятно, что «новые» алгоритмы аффинного масштабирования на самом деле были переосмыслением результатов Дикина десятилетней давности. Из первооткрывателей только Барнс и Вандербей и др. удалось провести анализ свойств сходимости аффинного масштабирования. Кармаркар, который также применил аффинное масштабирование в этот период времени, ошибочно полагал, что оно сходится так же быстро, как и его собственный алгоритм.

Алгоритм

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

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

минимизировать c ⋅ x

при условии Ax знак равно б , Икс ≥ 0 .

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

Формально итерационный метод, лежащий в основе аффинного масштабирования, принимает в качестве входных данных A , b , c начальное предположение x ⁰ > 0, что строго допустимо (т. е. Ax ⁰ = b ), допуск ε и размер шага β . Затем он продолжается путем итерации

• Пусть D _k — диагональная матрица с x ^к на его диагонали.
• Вычислите вектор двойственных переменных:

  $w^{k}=(AD_{k}^{2}A^{\operatorname {T} })^{-1}AD_{k}^{2}c.$

• Вычислите вектор приведенных затрат , который измеряет гибкость ограничений неравенства в двойственном:

  $r^{k}=c-A^{\operatorname {T} }w^{k}.$

• Если $r^{k}>0$ и $\mathbf {1} ^{\operatorname {T} }D_{k}r^{k}<\varepsilon$, текущее решение x ^к является ε -оптимальным.
• Если $-D_{k}r^{k}\geq 0$, проблема безгранична.
• Обновлять $x^{k+1}=x^{k}-\beta {\frac {D_{k}^{2}r^{k}}{\|D_{k}r^{k}\|}}$

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

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

$v=b-Ax^{0}$.

Если v = 0 , x ⁰ осуществимо. Если это не так, этап I решает вспомогательную задачу.

минимизировать тебя

при условии, что Ax + uv знак равно б , Икс ≥ 0 , ты ≥ 0 .

Эта задача имеет правильную форму для решения описанным выше итерационным алгоритмом: и

${\begin{pmatrix}x^{0}\\1\end{pmatrix}}$

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

${\begin{pmatrix}x^{*}\\u^{*}\end{pmatrix}}$.

Если ты ^* = 0 , тогда х ^* ≥0 допустимо в исходной задаче (хотя и не обязательно строго внутренней), а если u ^* > 0 исходная задача неразрешима.

Анализ

Хотя аффинное масштабирование легко сформулировать, его было трудно анализировать. Его сходимость зависит от размера шага β . Для размеров шага β ≤ 2/3 . было доказано , что вариант аффинного масштабирования Вандербея сходится, в то время как для β > 0,995 известен пример задачи, которая сходится к субоптимальному значению Было показано, что другие варианты алгоритма демонстрируют хаотическое поведение даже при небольших задачах, когда β > 2 / 3 .

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

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

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

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