Широко известен метод множителей Лагранжа, ориентированный на поиск экстремума при наличии ограничений типа равенств , т.е. на решение задачи

(1)

где .

Суть метода заключается в преобразовании задачи условной оптимизации (1) в задачу безусловной оптимизации с помощью образования новой целевой функции

где — вектор множителей Лагранжа, — число ограничений.

Необходимые условия экстремума функции :

(2)

Система (2) содержит алгебраических уравнений, где — размерность пространства управляемых параметров, ее решение дает искомые координаты экстремальной точки и значения множителей Лагранжа. Однако при численном решении (2), что имеет место при использовании алгоритмических моделей, возникают те же трудности, что и в методе Ньютона. Поэтому в САПР основными методами решения задач математического программирования (ЗМП) являются методы штрафных функций и проекции градиента.

Основная идея методов штрафных функций — преобразование задачи условной оптимизации в задачу безусловной оптимизации путем формирования новой целевой функции введением в исходную целевую функцию специальным образом выбранной функции штрафа :

где — множитель, значения которого можно изменять в процессе оптимизации.

Среди методов штрафных функций различают методы внутренней и внешней точки. Согласно методам внутренней точки (иначе называемым методами барьерных функций), исходную для поиска точку можно выбирать только внутри допустимой области, а для методов внешней точки как внутри, так и вне допустимой области (важно лишь, чтобы в ней функции целевая и ограничений были бы определены). Ситуация появления барьера у целевой функции и соотношение между условным в точке и безусловным в точке минимумами в простейшем одномерном случае иллюстрируется рис. 1.

Примеры штрафных функций:

Чем больше коэффициент , тем точнее решение задачи, однако при больших может ухудшаться ее обусловленность. Поэтому в начале поиска обычно выбирают умеренные значения , увеличивая их в окрестностях экстремума.

Основной вариант метода проекции градиента ориентирован на задачи математического программирования c ограничениями типа равенств.

Поиск при выполнении ограничений осуществляется в подпространстве измерений, где — число управляемых параметров, — число ограничений, при этом движение осуществляется в направлении проекции градиента целевой функции на гиперплоскость, касательную к гиперповерхности ограничений (точнее к гиперповерхности пересечения гиперповерхностей ограничений).

Поиск минимума начинают со спуска из исходной точки на гиперповерхность ограничений. Далее выполняют шаг в указанном выше направлении (шаг вдоль гиперповерхности ограничений). Поскольку этот шаг может привести к заметному нарушению ограничений, вновь повторяют спуск на гиперповерхность ограничений и т.д. Другими словами, поиск заключается в выполнении пар шагов, каждая пара включает спуск на гиперповерхность ограничений и движение вдоль гиперповерхности ограничений.

Идею метода легко пояснить для случая поиска в двумерном пространстве при одном ограничении . На рис. 2 это ограничение представлено жирной линией, а целевая функция — совокупностью более тонких линий равного уровня. Спуск обычно осуществляют по нормали к гиперповерхности ограничений (в данном случае к линии ограничения). Условие окончания поиска основано на сопоставлении значений целевой функции в двух последовательных точках, получаемых после спуска на гиперповерхность ограничений.

Рассмотрим вопрос, касающийся получения аналитических выражений для направлений спуска и движения вдоль гиперповерхности ограничений.

1. Спуск.

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

при условии , которое после линеаризации в окрестностях точки имеет вид

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

(3)

(4)

Тогда из (3) получаем выражение

подставляя его в (4), имеем

откуда

и окончательно, подставляя в (3), находим

2. Движение вдоль гиперповерхности ограничений.

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

где — приращение , которое нужно минимизировать, варьируя направления

(5)

где вариация осуществляется в пределах гиперплоскости ; и — ортогональные векторы. Следовательно, минимизацию (5) необходимо выполнять при ограничениях

Последнее ограничение говорит о том, что при поиске направления движения, вектор должен лишь указывать это направление, т.е. его длина несущественна (пусть — единичный вектор).

Для решения (5) используем метод множителей Лагранжа

где и — множители Лагранжа;

(6)

(7)

(8)

Из (6) следует, что

подставляя в (7), получаем

откуда


или

(9)

Таким образом, матрица

представляет собой проектирующую матрицу, а вектор , рассчитанный по (9), — проекцию градиента на гиперповерхность ограничений.

Частным случаем применения метода проекции градиента являются задачи оптимизации с максиминным критерием. Действительно, для поиска экстремума функции минимума

где — нормированная величина -го выходного параметра , удобно применять метод проекции градиента. В качестве ограничений задачи в исходной постановке фигурируют только прямые ограничения

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

(10)

то поиск продолжается в направлении проекции градиента функции на гиперповерхность гребня (10).