Классификация методов математического программирования. В САПР основными методами оптимизации являются поисковые методы. Поисковые методы основаны на пошаговом изменении управляемых параметров
X k +1 = X k + D X k, (4.5)
где в большинстве методов приращение D X k вектора управляемых параметров вычисляется по формуле
D X k = h g (X k). (4.6)
Здесь X k — значение вектора управляемых параметров на k -м шаге, h — шаг, а g (X k) — направление поиска. Следовательно,. если выполняются условия сходимости, то реализуется пошаговое (итерационное) приближение к экстремуму.
Методы оптимизации классифицируют по ряду признаков.
В зависимости от числа управляемых параметров различают методы одномерной и многомерной оптимизации, в первых из них управляемый параметр единственный, во вторых размер вектора X не менее двух. Реальные задачи в САПР многомерны, методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.
Различают методы условной и безусловной оптимизации по наличию или отсутствию ограничений. Для реальных задач характерно наличие ограничений, однако методы безусловной оптимизации также представляют интерес, поскольку задачи условной оптимизации с помощью специальных методов могут быть сведены к задачам без ограничений.
В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные. Если метод ориентирован на определение какого-либо локального экстремума, то такой метод относится к локальным методам. Если же результатом является глобальный экстремум, то метод называют методом глобального поиска. Удовлетворительные по вычислительной эффективности методы глобального поиска для общего случая отсутствуют и потому на практике в САПР используют методы поиска локальных экстремумов.
Наконец, в зависимости от того, используются при поиске производные целевой функции по управляемым параметрам или нет, различают методы нескольких порядков. Если производные не используются, то имеет место метод нулевого порядка, если используются первые или вторые производные, то соответственно метод первого или второго порядка. Методы первого порядка называют также градиентными, поскольку вектор первых производных F (X) по N есть градиент целевой функции
grad (F (X)) = (¶ F /¶ x 1, ¶ F /¶ x 2,...¶ F /¶ xn).
Конкретные методы определяются следующими факторами:
1) способом вычисления направления поиска g (X k) в формуле (4.6);
2) способом выбора шага h;
3) способом определения окончания поиска.
Определяющим фактором является первый из перечисленных в этом списке, он подробно описан ниже.
Шаг может быть или постоянным, или выбираться исходя из одномерной оптимизации — поиска минимума целевой функции в выбранном направлении g (X k). В последнем случае шаг будем называть оптимальным.
Окончание поиска обычно осуществляют по правилу: если на протяжении r подряд идущих шагов траектория поиска остается в малой -окрестности текущей точки поиска X k, то поиск следует прекратить, следовательно, условие окончания поиска имеет вид
|Xk - Xk-r| < ε.
Необходимые условия экстремума. В задачах безусловной оптимизации необходимые условия представляют собой равенство нулю градиента целевой функции
grad F (X) = 0.
В общей задаче математического программирования (4.1) необходимые условия экстремума, называемые условиями Куна-Таккера, формулируются следующим образом:
Для того чтобы точка Q была экстремальной точкой выпуклой задачи математического программирования (ЗМП), необходимо наличие неотрицательных коэффициентов ui, таких, что
ui φi(Э) = 0, i = 1,2,...m; (4.17)
и при этом соблюдались ограничения задачи, а также выполнялось условие
(4.18)
где m — число ограничений типа неравенств, L — то же равенств, коэффициенты aj > 0.
За приведенной абстрактной формулировкой условий скрывается достаточно просто понимаемый геометрический смысл. Действительно, рассмотрим сначала случай с ограничениями только типа неравенств. Если максимум находится внутри допустимой области R, то, выбирая все ui = 0, добиваемся выполнения (4.17); если же точка максимума Q лежит на границе области R, то, как видно из левой части рис. 4.9, эту точку всегда соответствующим подбором неотрицательных ui можно поместить внутрь оболочки, натянутой на градиенты целевой функции F (X) и функций-ограничений φ i (X).
Рис. 4.9. К пояснению условий Куна-Таккера
Наоборот, если точка не является экстремальной, то (4.17) нельзя выполнить при любом выборе положительных коэффициентов ui (см. правую часть рис. 4.9, где рассматриваемая точка N лежит вне выпуклой оболочки, натянутой на градиенты). Учет ограничений типа равенств очевиден, если добавляется последняя из указанных в (4.18) сумма.
Методы поиска условных экстремумов. Широко известен метод множителей Лагранжа, ориентированный на поиск экстремума при наличии ограничений типа равенств ψ(X) = 0, т.е. на решение задачи
extr F (X), (4.19)
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).