Алгоритм поиска шаблона использует алгоритм Увеличенного лагранжевого поиска шаблона (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.