Метод внутренней точки - Interior-point method
Методы внутренней точки (также называемые барьерными методами или IPM ) представляют собой определенный класс алгоритмов , решающих линейные и нелинейные задачи выпуклой оптимизации .
Метод внутренней точки был открыт советским математиком И.И. Дикиным в 1967 году и заново изобретен в США в середине 1980-х годов. В 1984 году Нарендра Кармаркар разработал метод линейного программирования, названный алгоритмом Кармаркара , который работает за доказуемо полиномиальное время и также очень эффективен на практике. Это позволило решить задачи линейного программирования, которые выходили за рамки возможностей симплекс-метода . В отличие от симплексного метода, он достигает наилучшего решения, пересекая внутреннюю часть допустимой области . Метод может быть обобщен на выпуклое программирование на основе самосогласованной барьерной функции, используемой для кодирования выпуклого множества .
Любая задача выпуклой оптимизации может быть преобразована в минимизацию (или максимизацию) линейной функции над выпуклым множеством путем преобразования в форму надграфика . Идея кодирования допустимого множества с помощью барьера и проектирования барьерных методов была изучена Энтони В. Юрий Нестеров , а Аркадий Немировский придумал специальный класс таких барьеров, которые можно использовать для кодирования любого выпуклого множества. Они гарантируют, что количество итераций алгоритма ограничено полиномом по размерности и точности решения.
Прорыв Кармаркара возродил изучение методов внутренней точки и проблем с барьерами, показав, что можно создать алгоритм для линейного программирования, характеризующийся полиномиальной сложностью и, более того, который конкурирует с симплекс-методом. Уже Хачиян «S эллипсоид метод был полиномиальный алгоритм времени; однако это было слишком медленно, чтобы представлять практический интерес.
Класс методов прямого двойственного следования по внутренним точкам считается наиболее успешным. Алгоритм предиктора-корректора Mehrotra обеспечивает основу для большинства реализаций этого класса методов.
Первично-дуальный метод внутренней точки для нелинейной оптимизации
Идею первично-двойственного метода легко продемонстрировать для нелинейной оптимизации с ограничениями . Для простоты рассмотрим вариант задачи нелинейной оптимизации с полным неравенством:
- минимизировать в зависимости от того, где
Затем эта задача оптимизации с ограничениями по неравенству решается путем преобразования ее в неограниченную целевую функцию, минимум которой мы надеемся найти эффективно. В частности, логарифмическая барьерная функция, связанная с (1), равна
Вот небольшой положительный скаляр, иногда называемый «параметром барьера». При сходе к нулю минимум должен сходиться к решению (1).
Градиент барьерной функции равен
где - градиент исходной функции , а - градиент .
В дополнение к исходной («первичной») переменной мы вводим двойную переменную, вдохновленную множителем Лагранжа.
(4) иногда называют условием «возмущенной дополнительности» из-за его сходства с «дополнительным провисанием» в условиях KKT .
Мы пытаемся найти те, для которых градиент барьерной функции равен нулю.
Применяя (4) к (3), получаем уравнение для градиента:
где матрица - якобиан ограничений .
Интуиция, лежащая в основе (5), заключается в том, что градиент должен лежать в подпространстве, охватываемом градиентами ограничений. «Возмущенная дополнительность» с малым (4) может пониматься как условие, при котором решение либо должно лежать вблизи границы , либо проекция градиента на нормаль компонента ограничения должна быть почти нулевой.
Применяя метод Ньютона к (4) и (5), мы получаем уравнение для обновления :
где есть матрица Гесса из , является диагональной матрицей из , и является диагональной матрицей с .
В силу (1), (4) условие
должны соблюдаться на каждом этапе. Это можно сделать, выбрав подходящие :
Смотрите также
- Аффинное масштабирование
- Дополненный лагранжев метод
- Штрафной метод
- Условия Каруша – Куна – Таккера.
использованная литература
Библиография
- Дикин, II (1967). «Итерационное решение задач линейного и квадратичного программирования» . Докл. Акад. АН СССР . 174 (1): 747–748.
- Боннанс, Ж. Фредерик; Гилберт, Дж. Чарльз; Лемарешаль, Клод ; Сагастизабал, Клаудиа А. (2006). Численная оптимизация: теоретические и практические аспекты . Universitext (Второе исправленное издание перевода французского издания 1997 г.). Берлин: Springer-Verlag. С. xiv + 490. DOI : 10.1007 / 978-3-540-35447-5 . ISBN 978-3-540-35445-1. Руководство по ремонту 2265882 .
- Кармаркар, Н. (1984). «Новый алгоритм полиномиального времени для линейного программирования» (PDF) . Материалы шестнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '84 . п. 302. DOI : 10,1145 / 800057,808695 . ISBN 0-89791-133-4. Архивировано из оригинального (PDF) 28 декабря 2013 года.
- Мехротра, Санджай (1992). «О реализации метода первично-дуальной внутренней точки». SIAM Journal по оптимизации . 2 (4): 575–601. DOI : 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) . Издательство Кембриджского университета.