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

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

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

называется активный в если , и неактивный в если Ограничения равенства всегда активны. В активный набор в состоит из этих ограничений которые активны в текущей точке (Нокедал и Райт 2006, п. 308).

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

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

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

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

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

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

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

  • Мурти, К. Г. (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 (связь)