XÎR

где R = { X | ψ(X) = 0 }.

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

где L= (λ1, λ 2, λ 3... λ h) — вектор множителей Лагранжа, L — число ограничений.

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

(4.20)

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

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

Ф(N) = F(X) + rS(X),

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

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

Рис. 4.10. Пояснение метода штрафных функций

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

1) для метода внутренней точки при ограничениях φ i (X)> 0

где m — число ограничений типа неравенств;

2) для метода внешней точки при таких же ограничениях

здесь штраф сводится к включению в Ф(N) суммы квадратов активных (т.е. нарушенных) ограничений;

3) в случае ограничений типа равенств ψ i (X) = 0

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

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

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

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

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

Рис.)). Траектория поиска в соответствии с методом проекции градиента: Э - условный экстремум; 0, 1, 2, 3 - точки на траектории поиска

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

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

min |B-A|

при условии ψ(X)=0, которое после линеаризации в окрестностях точки ( имеет вид

ψ(B) + (grad ψ(B))T(A-B) = 0.

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

Ф(А)=UTU+λ(ψ(B)+(gradψ(B))TU);

¶Ф/¶A=2U+λ(gradψ(B))=0; (4.21)

¶Ф/¶λ=ψ(B)+(gradψ(B))TU=0 (4.22)

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

U = - 0,5λ(grad ψ(B)),

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

ψ(B) - 0,5λ(grad ψ(B))T grad ψ(B)= 0;

откуда

λ= (0,5(grad ψ(B))T grad ψ(B))-1ψ(B).

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

U = - grad ψ(B)(grad ψ(B))T grad ψ(B))-1 ψ(B).

Движение вдоль гиперповерхности ограничений. Шаг в гиперплоскости D, касательной к гиперповерхности ограничений, следует сделать в направлении вектора S, на котором целевая функция уменьшается в наибольшей мере при заданном шаге h. Уменьшение целевой функции при переходе из точки А в новую точку С подсчитывают, используя формулу линеаризации F (X) в окрестностях точки А:

F(C) - F(A) = h(grad F(A))TS,

где grad F (A)T S — приращение F (X), которое нужно минимизировать, варьируя направления S

min F(C) = min ((grad F(A))TS), (4.23)

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

(grad ψ(A))T S = 0,

S T S = 1.

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

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

Ф(S,λ,q) = (grad F(A))TS + λ(grad ψ(A))TS + q(STS-1),

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

¶Ф/¶S = grad F(A) + λgrad ψ(A) + qS = 0; (4.24)

¶Ф/¶λ= (grad ψ (A))TS = 0; (4.25)

¶Ф/¶q = STS-1 = 0. (4.26)

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

S = -(grad F(A) + λgrad ψ(A))/q;

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

(grad ψ(A))T grad F(A) + λ(grad ψ(A))T grad ψ(A) = 0,

откуда

λ= - [(grad ψ(A))T grad ψ(A)]-1 (grad ψ(A))T grad F(A),

S == - {gradF(A)-grad ψ(A)[(grad ψ(A))Tgrad ψ(A)]-1(grad ψ(A))TgradF(A)}/q =

= - {E - grad ψ(A)[(grad ψ(A))T grad ψ(A)]-1 (grad ψ(A))T}grad F(A)/q. (4.27)

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

Р = E - grad ψ(A)[(grad ψ(A))T grad ψ(A)]-1 grad ψ(A))T

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

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

max min Zj (X),

X j

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

x max i > xi > x min i.

Здесь x max i и x min i — граничные значения допустимого диапазона варьирования параметра ,i. В процессе поиска, если минимальной является функция Zq (X) и траектория поиска пересекает гребень

Zq(X) - Zk(X) = 0, (4.28)

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

Дата добавления: 2015-07-07