Активно-наборный метод

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

${\ Displaystyle г_ {1} (х) \ geq 0, \ точки, g_ {к} (х) \ geq 0}$

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

${\ Displaystyle g_ {я} (х) \ geq 0}$

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

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

Методы активного набора [ править ]

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

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

повторять до "достаточно оптимального"

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

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

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

поиск недопустимых ограничений

конец повтор

Методы, которые можно описать как методы активного набора, включают: ^[1]

• Последовательное линейное программирование (SLP)
• Последовательное квадратичное программирование (SQP)
• Последовательное линейно-квадратичное программирование (SLQP)
• Метод пониженного градиента (RG)
• Обобщенный метод редуцированного градиента (GRG)

Ссылки [ править ]

Библиография [ править ]

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