Алгоритм поиска шаблона использует алгоритм Увеличенного лагранжевого поиска шаблона (ALPS), чтобы решить нелинейные ограничительные проблемы. Задача оптимизации, решенная алгоритмом ALPS,
таким образом, что
где c (x) представляет нелинейные ограничения неравенства, ceq (x) представляет ограничения равенства, m является количеством нелинейных ограничений неравенства, и mt является общим количеством нелинейных ограничений.
Алгоритм ALPS пытается решить нелинейную задачу оптимизации с нелинейными ограничениями, линейными ограничениями и границами. В этом подходе границы и линейные ограничения обработаны отдельно от нелинейных ограничений. Подпроблема формулируется путем объединения целевой функции и нелинейной ограничительной функции использование функции Лагранжа и параметров штрафа. Последовательность таких задач оптимизации приблизительно минимизирована с помощью алгоритма поиска шаблона, таким образом, что линейные ограничения и границы удовлетворены.
Каждое подпроблемное решение представляет одну итерацию. Количество функциональных оценок на итерацию поэтому намного выше при использовании нелинейных ограничений, чем в противном случае.
Подпроблемная формулировка задана как
где
Компоненты λi векторного λ является неотрицательным и является известным как оценки множителя Лагранжа
Элементы si векторного s являются неотрицательными сдвигами
ρ является положительным параметром штрафа.
Алгоритм начинается при помощи начального значения для параметра штрафа (InitialPenalty).
Поиск шаблона минимизирует последовательность подпроблем, каждая из которых является приближением исходной проблемы. Каждая подпроблема имеет фиксированное значение λ, s и ρ. Когда подпроблема минимизирована к требуемой точности и удовлетворяет условия выполнимости, лагранжевые оценки обновляются. В противном случае параметр штрафа увеличен фактором штрафа (PenaltyFactor). Это приводит к новой подпроблемной формулировке и проблеме минимизации. Эти шаги повторяются, пока критерию остановки не соответствуют.
Каждое подпроблемное решение представляет одну итерацию. Количество функциональных оценок на итерацию поэтому намного выше при использовании нелинейных ограничений, чем в противном случае.
Для полного описания алгоритма смотрите следующие ссылки:
[1] Колда, Тамара Г., Роберт Майкл Льюис и Вирджиния Торкзон. “Генерация установила увеличенный лагранжевый алгоритм прямого поиска для оптимизации с комбинацией общих и линейных ограничений”. Технический отчет SAND2006-5315, Национальные лаборатории Сандиа, август 2006.
[2] Коннектикут, A. R. Н. Ай. М. Гулд и Ph Л. Тойнт. “Глобально Конвергентный Увеличенный лагранжевый Алгоритм для Оптимизации с Общими ограничениями и Простыми Границами”, SIAM Journal согласно Числовому Анализу, Объем 28, Номер 2, страницы 545-572, 1991.
[3] Коннектикут, A. R. Н. Ай. М. Гулд и Ph Л. Тойнт. “Глобально Конвергентный Увеличенный лагранжевый Алгоритм Барьера для Оптимизации с Общими Ограничениями неравенства и Простыми Границами”, Математика Вычисления, Объем 66, Номер 217, страницы 261-288, 1997.