Метод внутренней точки - Interior-point method

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

Пример решения

Джон фон Нейман^[1] предложил метод внутренней точки линейного программирования, который не был ни методом полиномиального времени, ни эффективным методом на практике. На самом деле он оказался медленнее, чем обычно используемый симплексный метод.

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

Любую задачу выпуклой оптимизации можно преобразовать в минимизацию (или максимизацию) линейная функция над выпуклым множеством преобразованием к эпиграф форма.^[2] Идея кодирования возможный набор Использование барьера и методы проектирования барьера были изучены Энтони В. Юрий Нестеров и Аркадий Немировский придумал особый класс таких барьеров, которые можно использовать для кодирования любого выпуклого множества. Они гарантируют, что количество итерации алгоритма ограничена полиномом по размерности и точности решения.^[3]

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

Класс методов прямого двойственного следования по внутренним точкам считается наиболее успешным.Алгоритм предсказателя-корректора Mehrotra обеспечивает основу для большинства реализаций этого класса методов.^[4]

Первично-дуальный метод внутренней точки для нелинейной оптимизации

Идею первично-двойственного метода легко продемонстрировать на примере ограниченного нелинейная оптимизация.Для простоты рассмотрим вариант задачи нелинейной оптимизации с полным неравенством:

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

{ displaystyle f (x)}

при условии

{ displaystyle c_ {i} (x) geq 0 ~ { text {for}} ~ i = 1, ldots, m, ~ x in mathbb {R} ^ {n},}

где

{ displaystyle f: mathbb {R} ^ {n} to mathbb {R}, c_ {i}: mathbb {R} ^ {n} rightarrow mathbb {R} quad (1).}

Логарифмический барьерная функция связанный с (1)

{ Displaystyle В (х, му) = е (х) - му сумма _ {я = 1} ^ {м} журнал (c_ {я} (х)). quad (2)}

Вот ${ displaystyle mu}$ - небольшой положительный скаляр, иногда называемый «параметром барьера». Так как ${ displaystyle mu}$ сходится к нулю минимум ${ Displaystyle В (х, му)}$ должен сходиться к решению (1).

Барьерная функция градиент является

{ displaystyle g_ {b} = g- mu sum _ {i = 1} ^ {m} { frac {1} {c_ {i} (x)}} nabla c_ {i} (x), quad (3)}

где ${ displaystyle g}$ градиент исходной функции ${ displaystyle f (x)}$ , и ${ displaystyle nabla c_ {i}}$ это градиент ${ displaystyle c_ {i}}$ .

В дополнение к исходной ("первичной") переменной ${ displaystyle x}$ мы вводим Множитель Лагранжа вдохновленный двойной переменная ${ displaystyle lambda in mathbb {R} ^ {m}}$

{ displaystyle c_ {i} (x) lambda _ {i} = mu, forall i = 1, ldots, m. quad (4)}

(4) иногда называют условием "возмущенной дополнительности" из-за его сходства с "дополнительным провисанием" в Условия ККТ.

Мы пытаемся найти тех ${ Displaystyle (х _ { му}, лямбда _ { му})}$ для которых градиент барьерной функции равен нулю.

Применяя (4) к (3), мы получаем уравнение для градиента:

{ displaystyle g-A ^ {T} lambda = 0, quad (5)}

где матрица ${ displaystyle A}$ это Якобиан ограничений ${ Displaystyle с (х)}$ .

Интуиция за (5) заключается в том, что градиент ${ displaystyle f (x)}$ должен находиться в подпространстве, ограниченном градиентами ограничений. «Возмущенная дополнительность» с малым ${ displaystyle mu}$ (4) можно понимать как условие, что решение либо должно лежать вблизи границы ${ Displaystyle c_ {я} (х) = 0}$ , или что проекция градиента ${ displaystyle g}$ на компоненте ограничения ${ Displaystyle c_ {я} (х)}$ в норме должно быть почти ноль.

Применение Метод Ньютона к (4) и (5), получаем уравнение для ${ Displaystyle (х, лямбда)}$ Обновить ${ displaystyle (p_ {x}, p _ { lambda})}$ :

{ displaystyle { begin {pmatrix} W & -A ^ {T} Lambda A&C end {pmatrix}} { begin {pmatrix} p_ {x} p _ { lambda} end {pmatrix}} = { begin {pmatrix} -g + A ^ {T} lambda mu 1-C lambda end {pmatrix}},}

где ${ displaystyle W}$ это Матрица Гессе из ${ Displaystyle В (х, му)}$ , ${ displaystyle Lambda}$ это диагональная матрица из ${ displaystyle lambda}$ , и ${ displaystyle C}$ диагональная матрица с ${ displaystyle C_ {ii} = c_ {i} (x)}$ .

В силу (1), (4) условие

{ displaystyle lambda geq 0}

должны выполняться на каждом этапе. Это можно сделать, выбрав подходящий ${ displaystyle alpha}$ :

{ displaystyle (x, lambda) to (x + alpha p_ {x}, lambda + alpha p _ { lambda}).}

Воспроизвести медиа

Траектория итераций Икс методом внутренней точки.

Смотрите также

использованная литература

^ Данциг, Джордж Б .; Тапа, Мукунд Н. (2003). Линейное программирование 2: теория и расширения. Springer-Verlag.
^ Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация. Кембридж: Издательство Кембриджского университета. п. 143. ISBN 978-0-521-83378-3. Г-Н 2061575.
^ Райт, Маргарет Х. (2004). «Революция внутренней точки в оптимизации: история, последние события и долгосрочные последствия». Бюллетень Американского математического общества. 42: 39–57. Дои:10.1090 / S0273-0979-04-01040-7. Г-Н 2115066.
^ Potra, Florian A .; Стивен Дж. Райт (2000). «Методы внутренней точки». Журнал вычислительной и прикладной математики. 124 (1–2): 281–302. Дои:10.1016 / S0377-0427 (00) 00433-7.

Список используемой литературы

Дикин, И. (1967). «Итерационное решение задач линейного и квадратичного программирования». Докл. Акад. АН СССР. 174 (1): 747–748.
Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты. Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. С. xiv + 490. Дои:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. Г-Н 2265882.
Кармаркар, Н. (1984). «Новый полиномиальный алгоритм линейного программирования» (PDF). Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84. п. 302. Дои:10.1145/800057.808695. ISBN 0-89791-133-4. Архивировано из оригинал (PDF) 28 декабря 2013 г.
Мехротра, Санджай (1992). «О реализации метода первично-дуальной внутренней точки». SIAM Journal по оптимизации. 2 (4): 575–601. Дои:10.1137/0802028.
Нокедаль, Хорхе; Стивен Райт (1999). Численная оптимизация. Нью-Йорк, штат Нью-Йорк: Спрингер. ISBN 978-0-387-98793-4.
Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). «Раздел 10.11. Линейное программирование: методы внутренней точки». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.
Райт, Стивен (1997). Первоначально-двойственные методы внутренней точки. Филадельфия, Пенсильвания: SIAM. ISBN 978-0-89871-382-4.
Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация (PDF). Издательство Кембриджского университета.

[1] Данциг, Джордж Б .; Тапа, Мукунд Н. (2003). Линейное программирование 2: теория и расширения. Springer-Verlag.

[2] Бойд, Стивен; Ванденберге, Ливен (2004). Выпуклая оптимизация. Кембридж: Издательство Кембриджского университета. п. 143. ISBN 978-0-521-83378-3. Г-Н 2061575.

[3] Райт, Маргарет Х. (2004). «Революция внутренней точки в оптимизации: история, последние события и долгосрочные последствия». Бюллетень Американского математического общества. 42: 39–57. Дои:10.1090 / S0273-0979-04-01040-7. Г-Н 2115066.

[4] Potra, Florian A .; Стивен Дж. Райт (2000). «Методы внутренней точки». Журнал вычислительной и прикладной математики. 124 (1–2): 281–302. Дои:10.1016 / S0377-0427 (00) 00433-7.

[1]

[2]

[3]

[4]