Норенков И.П. - Основы автоматизированного проектирования (1060628), страница 38
Текст из файла (страница 38)
1 3) путемподстановки в (4. 10) величин Si+| из (4.9) и S из (4.8)илиS|+irS = (WjS, - grad F(X ))т Г(Х - X . ,)/А == (w,S - gradF(X))TIT-' (gradF(X) - grad F(X _,))//; = О,(w, S - grad F(X ))T (grad F(\) - grad F(X _ ,)) = 0,откудаw, S/ (grad F(X) - grad F(X _ ,)) - grad F(X )T grad F(X ) + grad F(X )T grad F(X,_ ,) = 0и с учетом (4. 1 2) и (4. 1 3)w S^grad F(X ,) + grad F(X )T grad F(X ) = 0.Следовательно,w = grad F(X)T grad F(X) / (S] grad F(X _ ,)).(4.14)На первом шаге поиска выбирают S, = - grad F (X0) и находят точку X, . На втором шаге по формуле (4. 14) рассчитывают w p по формулам (4.9) и (4.8) определяют 82и Х2 и т.
д.Метод переменной метрики (иначе метод Девидона - Флетчера - Пауэлла) можно рассматривать как результат усовершенствования метода второгопорядка - метода Ньютона.Метод Ньютона основан на использовании необходимых условий безусловного экстремума целевой функции F(X)gradF(X) = 0.(4.15)Выражение (4.15) представляет собой систему алгебраических уравнений,для решения которой можно применить известный численный метод, называемый методом Ньютона.
Корень системы (4.15) есть стационарная точка, т. е.возможное решение экстремальной задачи. Метод Ньютона является итерационным, он основан на линеаризации (4. 1 5) в окрестности текущей точки поиска \k:grad F(X) = grad F(X 4 ) + Г(Х - X t ) = 0.(4.16)Выражение (4.16) - это система линейных алгебраических уравнений. Еекорень есть очередное приближение Хж к решениюЕсли процесс сходится, то решение достигается за малое число итераций,окончанием которых служит выполнение условияГлавный недостаток метода - высокая трудоемкость вычисления и обращения матрицы Г, к тому же ее вычисление численным дифференцированиемсопровождается заметными погрешностями, что снижает скорость сходимости.1644.2. Обзор методов оптимизацииВ методе переменной метрики вместо трудно вычисляемой обратной матрицы Гессе используют некоторую более легко вычисляемую матрицу N, т.
е.'X w = X t + N grad /KXt).Введем обозначения:dg4= grad *10д- gradЕ - единичная матрица. Начальное значение матрицы N0= Е. Матрицу N корректируют на каждом шаге, т. е.гдеПоэтомуLA-IB,.i-O/=01Можно показать, что А, стремится к Г" , В(- к Е при k—>n, где п - размерность пространства управляемых параметров. Спустя п шагов нужно снованачинать с NИ _,+_ 1, = Е.Необходимые условия экстремумаВ задачах безусловной оптимизации необходимые условия представляютсобой равенство нулю градиента целевой функцииgrad F(X) = 0.В общей задаче математического программирования (4.1) необходимыеусловия экстремума, называемые условиями Куна - Таккера, формулируются следующим образом.Для того чтобы точка Э была экстремальной точкой выпуклой задачи математического программирования (ЗМП), необходимо наличие неотрицательных коэффициентов м(, таких, чтоиф,(Э) = 0, / = 1, 2, ..., т,(4.17)и соблюдение при этом ограничений задачи, а также выполнение условияgrad F(3) + Z и grad Ф,(Э) + Z а ш (Э) = 0,/=!(4.18)у=1где т - число ограничений типа неравенств; L- то же типа равенств; а > 0 коэффициенты.1654.
Математическое обеспечение синтеза проектных решенийРис. 4.9. К пояснению условий Куна - ТаккераЗа приведенной абстрактной формулировкой условий скрывается достаточно просто понимаемый геометрический смысл. Действительно, рассмотримсначала случай с ограничениями только типа неравенств. Если максимум находится внутри допустимой области R, то, выбирая все и = 0, добиваемся выполнения (4.17); если же точка максимума Э лежит на границе области R, то,как видно из левой части рис. 4.9, эту точку всегда соответствующим подбором неотрицательных ut можно поместить внутрь оболочки, натя!гутой на градиенты целевой функции ДХ) и функций-ограничений ф,(Х).
Наоборот, еслиточка не является экстремальной, то (4.17) нельзя выполнить при любом выборе положительных коэффициентов и (см. правую часть рис. 4.9, где рассматриваемая точка X лежит вне выпуклой оболочки, натянутой на градиенты). Учет ограничений типа равенств очевиден, если добавляется последняяиз указанных в (4.
18) сумма.Методы поиска условных экстремумовШироко известен метод множителей Лагранжа, ориентированный на поиск экстремума при наличии ограничений типа равенств vj/(X) = 0, т. е. на решение задачиextr FX),(4.19)XeRг д е К = { Х | ч / ( Х ) = 0}.Суть метода заключается в преобразовании задачи условной оптимизации(4.19) в задачу безусловной оптимизации с помощью образования новой целевой функциигде L = (А,,, Х-2, "ky ..., A,L) - вектор множителей Лагранжа; L - число ограничений.Необходимые условия экстремума функции Ф(Х):5Ф(Х,Ь)/5Х = дР(Х)1дХ+ I X, дч,(Х)/дХ5Ф(Х, D/SL = \|/ (X) = 0.166= 0;(4.20)4 2 Обзор методов оптимизацииСистема (4.20) содержит п + L алгебраических уравнений, где п - размерность пространства управляемых параметров, ее решение дает искомые координаты экстремальной точки и значения множителей Лагранжа.
Однако причисленном решении (4.20), что имеет место при использовании алгоритмических моделей, возникают те же трудности, что и в методе Ньютона. Поэтому вСАПР основными методами решения ЗМП являются методы штрафных функций и проекции градиента.Важная идея методов штрафных функций - преобразование задачи условной оптимизации в задачу безусловной оптимизации путем формированияновой целевой функции Ф(Х), за счет введения в исходную целевую функциюF(X) специальным образом выбранной функции штрафа 5(Х):где г - множитель, значение которого можно изменять в процессе оптимизации.Среди методов штрафных функций различают методы внутренней и внешней точки. Согласно методам внутренней точки (иначе называемым методами барьерных функции), исходную для поиска точку можно выбирать тольковнутри допустимой области, а для методов внешней точки - как внутри, так ивне допустимой области (важно лишь, чтобы в ней функции целевая и ограничений были определены).
Ситуация появления барьера у целевой функции Ф(х)и соотношение между условным в точке х2 и безусловным в точке я, минимумами F(x) в простейшем одномерном случае иллюстрируется рис. 4.10.Примеры штрафных функций:1) для метода внутренней точки при ограничениях ф((Х) > Огде т - число ограничений типа неравенств;2) для метода внешней точки при таких же ограничениях= Z(mm{0,<p/X)})2,1=1здесь штраф сводится к включению в Ф(Х)суммы квадратов активных (т. е. нарушенных) ограничений;3) в случае ограничений типа равенствS(X)=Z(vi/,(X))2.1=1Чем больше коэффициент г, тем точнеерешение задачи, однако при больших г может ухудшаться ее обусловленность.
Поэтому в начале поиска обычно выбирают умеренные значения г, увеличивая их в окрестностях экстремума.ДопустимаяобластьРис. 4.10. Ситуация появлениябарьера в простейшемодномерном случае1674. Математическое обеспечение синтеза проектных решенийОсновной вариант метода проекции градиента ориентирован на задачиматематического программирования с ограничениями типа равенств.Поиск при выполнении ограничений осуществляется в подпространстве(п - т) измерений, где п - число управляемых параметров, т - число ограничений, при этом движение осуществляется в направлении проекции градиентацелевой функции F(X) на гиперплоскость, касательную к гиперповерхности ограничений (точнее к гиперповерхности пересечения гиперповерхностей ограничений).Поиск минимума начинают со спуска из исходной точки на гиперповерхность ограничений.
Далее выполняют шаг в указанном выше направлении (шагвдоль гиперповерхности ограничений). Поскольку этот шаг может привести кзаметному нарушению ограничений, вновь повторяют спуск на гиперповерхность ограничений и т. д. Другими словами, поиск заключается в выполнениипар шагов, каждая пара включает спуск на гиперповерхность ограничений идвижение вдоль гиперповерхности ограничений.Идею метода легко пояснить для случая поиска в 2В-пространстве при одном ограничении у(Х) = 0.
На рис. 4.11 это ограничение представлено жирнойлинией, а целевая функция - совокупностью более тонких линий равного уровня. Спуск обычно осуществляют по нормали к гиперповерхности ограничений(в данном случае к линии ограничения). Условие окончания поиска основано насопоставлении значений целевой функции в двух последовательных точках,получаемых после спуска на гиперповерхность ограничений.Рассмотрим вопрос, касающийся получения аналитических выражений длянаправлений спуска и движения вдоль гиперповерхности ограничений.Рис. 4.11. Траектория поиска в соответствии с методом проекции градиента:Э - условный экстремум; 0,1,2,..., 7 - точки на траектории поиска1684.2. Обзор методов оптимизацииСпуск. Необходимо из текущей точки поиска В попасть в точку А, являющуюся ближайшей к В точкой на гиперповерхности ограничений, т.
е. решитьзадачуmin |В - А|при условии х|/(Х) = 0, которое после линеаризации в окрестностях точки В имеет вид\|/(В) + (grad у(В))т(А - В) = 0.Используя метод множителей Лагранжа, обозначая А-В = U и учитывая,что минимизация расстояния равнозначна минимизации скалярного произведения U на U, запишемФ(А) = U T U + Л(\|/(В) + (grad X|/(B))TU);ЗФ/ЭА = 2U + ?i(grad \|/(B)) = 0;TеФ/аХ = \[/(В) + (grad y(B)) U = 0.Тогда из (4.2 1) получаем выражение(4.21)(4.22)U = -0,5A.(grad\|/(B)).Подставляя его в (4.22), имеем\у(В) - 0,5X(grad v|/(B))T grad \j/(B) = 0,откудаA. = (2(grad v|/(B))Tgrad ч/(В)»(В).Окончательно, подставляя X, в (4.21), находимU = - grad vKB)(grad vj/(B))Tgrad \КВ)Г' V(B).Движение вдоль гиперповерхности ограничений.
Шаг в гиперплоскости D, касательной к гиперповерхности ограничений, следует сделать в направлении вектора S, на котором целевая функция уменьшается в наибольшеймере при заданном шаге h. Уменьшение целевой функции при переходе из точки А в новую точку С подсчитывают, используя формулу линеаризации F(X) вокрестностях точки А:F(C) - F(A) =Tздесь grad F(A) S - приращение /XX), которое нужно минимизировать, варьируя направления S:Tmin F(C) = min ((grad F(A)) S),(4.23)где вариация S осуществляется в пределах гиперплоскости D; gradv|/(A) иS - ортогональные векторы. Следовательно, минимизацию (4.23) необходимовыполнять при ограничениях(grad ij/(A))TS = 0,S T S=1.1694.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
