Актив-сет метод - Active-set method

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

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

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

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

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

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

Активно-сетевые методы

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

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

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

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

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

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

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

конец повторения

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

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

Рекомендации

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

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