Алгоритм поиска шаблона использует алгоритм Augmented Lagrangian Pattern Search (ALPS) для решения проблем нелинейных ограничений. Задача оптимизации, решаемая алгоритмом ALPS,
)
такой, что
mtA⋅x≤bAeq⋅x=beqlb≤x≤ub,
где c (x) - нелинейные ограничения неравенства, ceq (x) - ограничения равенства, m - число нелинейных ограничений неравенства, mt - общее число нелинейных ограничений.
Алгоритм ALPS пытается решить проблему нелинейной оптимизации с нелинейными ограничениями, линейными ограничениями и границами. В этом подходе границы и линейные ограничения обрабатываются отдельно от нелинейных ограничений. Подпроблема формулируется путем объединения целевой функции и нелинейной функции ограничения с использованием лагранжевых и штрафных параметров. Последовательность таких задач оптимизации приблизительно минимизируется с использованием алгоритма поиска шаблона, так что выполняются линейные ограничения и границы.
Каждое решение подпроблемы представляет одну итерацию. Поэтому при использовании нелинейных ограничений количество оценок функций на одну итерацию намного больше, чем в противном случае.
Формулировка подпроблемы определяется как
+ρ2∑i=m+1mtceqi (x) 2,
где
Компоненты λ i вектора λ неотрицательны и известны как оценки множителя Лагранжа
Элементы si вектора s являются неотрицательными сдвигами
start- положительный штрафной параметр.
Алгоритм начинается с использования начального значения штрафного параметра (InitialPenalty).
Поиск шаблона минимизирует последовательность подпроблем, каждая из которых является аппроксимацией исходной задачи. Каждая подпроблема имеет фиксированное значение λ, s и start. Когда подпроблема минимизируется до требуемой точности и удовлетворяет условиям осуществимости, оценки Лагранжа обновляются. В противном случае штрафной параметр увеличивается на штрафной коэффициент (PenaltyFactor). Это приводит к возникновению новой проблемы формулирования и минимизации подпроблем. Эти шаги повторяются до тех пор, пока не будут выполнены критерии остановки.
Каждое решение подпроблемы представляет одну итерацию. Поэтому при использовании нелинейных ограничений количество оценок функций на одну итерацию намного больше, чем в противном случае.
Полное описание алгоритма см. в следующих ссылках:
[1] Кольда, Тамара Г., Роберт Майкл Льюис и Вирджиния Торкзон. «Генерирующий набор прямого поиска увеличил алгоритм Лагранжа для оптимизации с комбинацией общих и линейных ограничений». Технический отчет SAND2006-5315, национальные лаборатории Сандии, август 2006 года.
[2] Конн, А. Р., Н. И. М. Гулд и Ф. Л. Тоунт. «Глобально конвергентный дополненный лагранжевый алгоритм оптимизации с общими ограничениями и простыми границами», SIAM Journal on Numerical Analysis, Volume 28, Number 2, pages 545-572, 1991.
[3] Конн, А. Р., Н. И. М. Гулд и Ф. Л. Тоунт. «Глобально конвергентный дополненный лагранжевый барьерный алгоритм для оптимизации с общими ограничениями неравенства и простыми границами», Математика вычислений, том 66, число 217, стр. 261-288, 1997.