Метод активного набора

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

Задача оптимизации определяется с использованием целевой функции для минимизации или максимизации и набора ограничений.

g_{1}(x)\geq 0,\dots ,g_{k}(x)\geq 0

которые определяют допустимую область , то есть набор всех x для поиска оптимального решения. Учитывая точку $x$ в допустимой области ограничение

g_{i}(x)\geq 0

называется активным в $x_{0}$ если $g_{i}(x_{0})=0$ и неактивен в $x$ если $g_{i}(x_{0})>0.$ Ограничения равенства всегда активны. Активный набор в $x_{0}$ состоит из этих ограничений $g_{i}(x_{0})$ которые активны в текущий момент ( Nocedal & Wright 2006 , стр. 308).

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

Методы активного множества

В целом алгоритм активного набора имеет следующую структуру:

Найдите подходящую отправную точку

повторять до тех пор, пока не станет «достаточно оптимально»

решить проблему равенства, определенную активным набором (приблизительно)

вычислить множители Лагранжа активного набора

удалить подмножество ограничений с отрицательными множителями Лагранжа

поиск невыполнимых ограничений

конец повтора

К методам, которые можно охарактеризовать как методы активного набора, относятся: ^[1]

Производительность

Рассмотрим задачу выпукло-квадратичного программирования с линейными ограничениями. При разумных предположениях (задача разрешима, система ограничений регулярна в каждой точке, квадратичная цель сильно выпукла) метод активного множества завершается после конечного числа шагов и дает глобальное решение задачи. Теоретически метод активного набора может выполнять число итераций, экспоненциальное по m , как и симплексный метод . Однако его практическое поведение обычно намного лучше. ^[2]^{: Раздел 9.1}

Ссылки

^ Носедал и Райт 2006 , стр. 467–480.
^ Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

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

Мурти, КГ (1988). Линейная дополнительность, линейное и нелинейное программирование . Серия Сигма в прикладной математике. Том. 3. Берлин: Хелдерманн Верлаг. стр. xlviii+629 стр. ISBN 3-88538-403-5 . МР 0949214 . Архивировано из оригинала 1 апреля 2010 г. Проверено 3 апреля 2010 г.
Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag . ISBN 978-0-387-30303-1 .

[1] Носедал и Райт 2006 , стр. 467–480.

[:0-2] Немировский и Бен-Тал (2023). «Оптимизация III: Выпуклая оптимизация» (PDF) .

[1]

[2]