Алгоритм поиска шаблона использует алгоритм Augmented Lagrangian Pattern Search (ALPS), чтобы решить нелинейные проблемы ограничений. Задача оптимизации, решенная алгоритмом ALPS,
таким, что
где c (x) представляет нелинейные ограничения неравенства, ceq (x) представляет ограничения равенства, m является количеством нелинейных ограничений неравенства, и mt является общим количеством нелинейных ограничений.
Алгоритм ALPS пытается решить нелинейную задачу оптимизации с нелинейными ограничениями, линейными ограничениями и границами. В этом подходе ограничения и линейные ограничения обрабатываются отдельно от нелинейных ограничений. Подпрограмма сформулирована путем объединения целевой функции и нелинейной ограничительной функции с помощью Лагранжиана и параметров штрафа. Последовательность таких задач оптимизации приблизительно минимизируется с помощью алгоритма поиска шаблона, таким образом, что линейные ограничения и ограничения выполняются.
Каждое решение подпроблема представляет одну итерацию. Поэтому количество вычислений функции на итерацию намного выше при использовании нелинейных ограничений, чем в противном случае.
Формулировка подформулировка задачи определяется как
где
Компоненты λi векторных λ неотрицательны и известны как оценки множителя Лагранжа
Элементы si векторных s являются неотрицательными сдвигами
ρ является положительным параметром штрафа.
Алгоритм начинается с использования начального значения для параметра штрафа (InitialPenalty).
Поиск шаблона минимизирует последовательность подпрограмм, каждая из которых является приближением исходной задачи. Каждая подпрограмма имеет фиксированное значение λ, s и ρ. Когда подпрограмма минимизируется до необходимой точности и удовлетворяет условиям выполнимости, оценки Лагранжа обновляются. В противном случае параметр штрафа увеличивается на коэффициент штрафа (PenaltyFactor). Это приводит к новой формулировке подформулировки задачи и проблеме минимизации. Эти шаги повторяются до тех пор, пока не будут достигнуты критерии остановки.
Каждое решение подпроблема представляет одну итерацию. Поэтому количество вычислений функции на итерацию намного выше при использовании нелинейных ограничений, чем в противном случае.
Полное описание алгоритма смотрите в следующих ссылках:
[1] Колда, Тамара Г., Роберт Майкл Льюис и Вирджиния Торчзон. «Генерирующий набор прямого поиска увеличил алгоритм Лагранжа для оптимизации с комбинацией общих и линейных ограничений». Technical Report SAND2006-5315, Sandia National Laboratories, август 2006 года.
[2] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. Глобально сходимый дополненный алгоритм Лагранжа для оптимизации с общими ограничениями и простыми границами, SIAM Journal по численному анализу, том 28, номер 2, страницы 545-572, 1991.
[3] Conn, A. R., N. I. M. Gould, and Ph. L. Toint. «Глобально сходимый дополненный лагрангийский барьерный алгоритм для оптимизации с общими ограничениями неравенства и простыми границами», Математика расчетов, том 66, число 217, страницы 261-288, 1997.