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

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

Таким образом, задача условной минимизации f (x) заменяется последовательностью задач безусловной минимизации
при k =1,2,.... При этом, исходя из заданной начальной точки x0, находится последовательность точек
сходящаяся при определенных условиях к решению
исходной задачи. В зависимости от вида Ф(х, а) различают методы внешних штрафных функций и методы внутренних штрафных функций или барьерных функций.
На рис.- внутренние щтрафные функции.

Рис. 10. Метод штрафных функций
Основной вариант метода проекции градиента ориентирован на задачи математического программирования c ограничениями типа равенств.
Поиск при выполнении ограничений осуществляется в подпространстве
измерений, где
— число управляемых параметров,
— число ограничений, при этом движение осуществляется в направлении проекции градиента целевой функции
на гиперплоскость, касательную к гиперповерхности ограничений (точнее к гиперповерхности пересечения гиперповерхностей ограничений).
Поиск минимума начинают со спуска из исходной точки на гиперповерхность ограничений. Далее выполняют шаг в указанном выше направлении (шаг вдоль гиперповерхности ограничений). Поскольку этот шаг может привести к заметному нарушению ограничений, вновь повторяют спуск на гиперповерхность ограничений и т.д. Другими словами, поиск заключается в выполнении пар шагов, каждая пара включает спуск на гиперповерхность ограничений и движение вдоль гиперповерхности ограничений.
Идею метода легко пояснить для случая поиска в двумерном пространстве при одном ограничении
. На рис. 11 это ограничение представлено жирной линией, а целевая функция — совокупностью более тонких линий равного уровня. Спуск обычно осуществляют по нормали к гиперповерхности ограничений (в данном случае к линии ограничения). Условие окончания поиска основано на сопоставлении значений целевой функции в двух последовательных точках, получаемых после спуска на гиперповерхность ограничений.
Рис. 11. Траектория поиска в соответствии с методом проекции градиента
Воспользуйтесь поиском по сайту: