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

Пример поиска решения. Синие линии показывают ограничения, красные точки показывают повторяющиеся решения.

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

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

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

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

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

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

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

минимизировать в зависимости от того, где

Затем эта задача оптимизации с ограничениями по неравенству решается путем преобразования ее в неограниченную целевую функцию, минимум которой мы надеемся найти эффективно. В частности, логарифмическая барьерная функция, связанная с (1), равна

Вот небольшой положительный скаляр, иногда называемый «параметром барьера». При сходе к нулю минимум должен сходиться к решению (1).

Градиент барьерной функции равен

где - градиент исходной функции , а - градиент .

В дополнение к исходной («первичной») переменной мы вводим двойную переменную, вдохновленную множителем Лагранжа.

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

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

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

где матрица - якобиан ограничений .

Интуиция, лежащая в основе (5), заключается в том, что градиент должен лежать в подпространстве, охватываемом градиентами ограничений. «Возмущенная дополнительность» с малым (4) может пониматься как условие, при котором решение либо должно лежать вблизи границы , либо проекция градиента на нормаль компонента ограничения должна быть почти нулевой.

Применяя метод Ньютона к (4) и (5), мы получаем уравнение для обновления :

где есть матрица Гесса из , является диагональной матрицей из , и является диагональной матрицей с .

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

должны соблюдаться на каждом этапе. Это можно сделать, выбрав подходящие :

Траектория итераций x с использованием метода внутренней точки.

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

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

Библиография