Норенков И.П. - Автоматизированное производство (1054022), страница 38
Текст из файла (страница 38)
4.7, где дополнительный шаг выполняют в направлении вектора X3- X1, что и приводит в точку X4.Поиск экстремума /$&#-#/ -$E#"/'"7$/#8# /*#8#8")**'%)основан на построении многогранника с (n + 1) вершинами накаждом шаге поиска, где n — размерность пространства управляемых параметров. В начале поиска эти вершины выбирают произвольно, на последующих шагах выбор подчинен правилам метода.Эти правила поясняются рис. 4.8 на примере двумерной за%+,. 4.7. Иллюстрация методаконфигурацийдачи оптимизации.
Выбраны вершины исходного треугольника:X1, X2, X3. Новая вершина X4 находится на луче, проведенном из худшей вершины X1 (из вершины снаибольшим значением целевой функции) через центр тяжести SM многогранника, причем рекомендуется X4 выбирать на расстоянии d от SM, равном |SM-X1|.
Новая вершина X4 заменяет худшую вер&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1025@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mшину X1. Если оказывается, что X4 имеет лучшеезначение целевой функции среди вершин многогранника, то расстояние d увеличивают. На рисунке именно эта ситуация имеет место и увеличение d дает точку X5. В новом многограннике свершинами X2, X3, X5 худшей является вершинаX2, аналогично получают вершину X6, затем вершину X7 и т.д. Если новая вершина окажется худшей, то в многограннике нужно сохранить лучшую вершину, а длины всех ребер уменьшить,например вдвое (стягивание многогранника клучшей вершине).
Поиск прекращается при выполнении условия уменьшения размеров много%+,. 4.8. Иллюстрация метода деформируемогогранника до некоторого предела.многогранника:471);*.$ /$&#-. поиска характеризуются тем, что направления поиска g выбирают случайным образом.Особенностью /$&#-) *)'+%#"$;>$8# +07+%) является выполнение шагов поиска в градиентномнаправленииXk+1 = Xk + h grad F(X) / |grad F(X)|,шаг h выбирается оптимальным с помощью одномерной оптимизации.При использовании метода наискорейшего спуска, как и большинства других методов, эффективность поиска существенно снижается в овражных ситуациях. Траектория поиска приобретает зигзагообразный вид с медленным продвижением вдоль дна оврага в сторону экстремума.
Чтобы повысить эффективность градиентных методов, используют несколько приемов.Один из приемов, использованный в /$&#-$ +#0"9@$**., 8")-'$*&#( (называемом также методом Флетчера-Ривса), основан на понятии сопряженности векторов. Векторы C и ( называют Q-сопряженными, если ATQB = 0, где Q — положительно определенная квадратная матрица того же порядка, что и размер N векторов C и ( (частный случай сопряженности — ортогональность векторов,когда Q является единичной матрицей порядка N), AT -вектор-строка, B — вектор-столбец.Особенность сопряженных направлений для Q = K, где K — матрица Гессе, при в задачах с квадратичной целевой функцией F(X) заключается в следующем: одномерная минимизация F(X) последовательно по N сопряженным направлениям позволяет найти экстремальную точку не более, чем заN шагов.+ - 0 B .F 6 9 0 .
. L)&"'=$; V$++$ называют матрицу вторых частных производных целевой функции по управляемым параметрам.Основанием для использования поиска по K-сопряженным направлениям является то, что дляфункций F(X) общего вида может быть применена квадратичная аппроксимация, что на практике выливается в выполнение поиска более, чем за N шагов.+ - 0 B .
- . Поиск экстремума выполняют в соответствии с формулойXi = Xi-1 + hSi.(4.8)Направление Si+1 поиска на очередном шаге связано с направлением поиска Si на предыдущем шаге соотношениемSi+1 = - gradF(Xi) + wiSi,(4.9)где wi — коэффициент. Кроме того, учитывают условие сопряженностиSi+1 ТKSi = 0(4.10)и линейную аппроксимацию gradF(X) в окрестностях точки Nigrad F(Xi+1) = grad F(Xi) + K(Xi+1 - Xi).(4.11)Поскольку шаг h рассчитывается исходя из условия одномерной оптимизации, то, во-первых, справедливо соотношениеSi Тgrad F(Xi) = 0,&.+.)$(*),$" . !"#$%!#&'&($"!))$*(4.12)+($*,#&($"!)&*1035@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mво-вторых, имеемXi = Xi-1 + hwi-1 Si-1 - h grad F(Xi-1),откуда получаем∂F/∂h = (∂F(X)/∂X)(∂X/∂h) = grad F(Xi) grad F(Xi-1) = 0.(4.13)Алгоритм поиска сводится к применению формулы (4.9), пока не будет выполнено условие окончания вычислений|grad F(Xk)| < ε.Чтобы определить коэффициент wi решают систему уравнений (4.8)-(4.13) путем подстановки в (4.10) величин Si+1из (4.9) и Si из (4.8)Si+1TKSi = (wi Si - grad F(Xi))T K(Xi — Xi-1) / h == (wi Si - grad F(Xi))T KK -1 (grad F(Xi) - grad F(Xi-1)) / h = 0;или(wi Si - grad F(Xi))T (grad F(Xi) - grad F(Xi-1)) = 0,откудаwi SiT (grad F(Xi) - grad F(Xi-1)) - grad F(Xi)T grad F(Xi) + grad F(Xi)T grad F(Xi-1) = 0и с учетом (4.12) и (4.13)wi SiT grad F(Xi-1) + grad F(Xi)T grad F(Xi) = 0.Следовательно,wi = grad F(Xi)T grad F(Xi) / SiT grad F(Xi-1)(4.14)На первом шаге поиска выбирают S1 = — grad F(X0) и находят точку N1.
На втором шаге по формуле (4.14) рассчитывают w1, по формулам (4.9) и (4.8) определяют S2 и N2 и т.д.L$&#- 0$"$/$**#; /$&"'%' (иначе метод Девидона-Флетчера-Пауэлла) можно рассматриватькак результат усовершенствования метода второго порядка — метода Ньютона.L$&#- G5<&#*) основан на использовании необходимых условий безусловного экстремума целевой функции F(X)grad F(X) = 0.(4.15)Выражение (4.15) представляет собой систему алгебраических уравнений, для решения которойможно применить известный численный метод, называемый методом Ньютона. Корень системы(4.15) есть стационарная точка, т.е. возможное решение экстремальной задачи.
Метод Ньютона является итерационным, он основан на линеаризации (4.15) в окрестности текущей точки поиска Nkgrad F(X) = grad F(Xk) + K(X-X k) = 0.(4.16)Выражение (4.16) — это система линейных алгебраических уравнений. Ее корень есть очередное приближение Nk+1 к решению Xk+1 = Xk - K-1(Xk) grad F(Xk).Если процесс сходится, то решение достигается за малое число итераций, окончанием которыхслужит выполнение условия|Xk+1 - Xk| < ε.Главный недостаток метода — высокая трудоемкость вычисления и обращения матрицы K, к тому же ее вычисление численным дифференцированием сопровождается заметными погрешностями,что снижает скорость сходимости.В методе переменной метрики вместо трудно вычисляемой обратной матрицы Гессе используют некоторую более легко вычисляемую матрицу N, т.е.Xk+1 = Xk + N grad F(Xk).Введем обозначения:dgk= grad F(Xk) - grad F(Xk-1);dXk= Xk - Xk-1;E — единичная матрица.
Начальное значение матрицы N0 = E. Матрицу N корректируют на каждом шаге, т.е.&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1045@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&MNk+1= Nk + Ak TBk,гдеAk = dXk dXk T / (dXTdgk),Bk= Nk dgk dgkT NkT / (dgkTNk dgk).ПоэтомуkkNk+1 = E +∑ Ai — ∑ Bi.i=0i=0Можно показать, что Ai стремится к K-1, (i — к E при k→ n, где n — размерность пространства управляемых параметров.
Спустя n шагов, нужно снова начинать с Nn+1 = E.#.4B645+/1. <,D49+> T7,-8./</:. В задачах безусловной оптимизации необходимые условияпредставляют собой равенство нулю градиента целевой функцииgrad F(X) = 0.В общей задаче математического программирования (4.1) необходимые условия экстремума, называемые условиями Куна-Таккера, формулируются следующим образом:Для того чтобы точка Q была экстремальной точкой выпуклой задачи математического программирования (ЗМП), необходимо наличие неотрицательных коэффициентов ui, таких, чтоui ϕi(Q) = 0, i = 1,2,...m;(4.17)и при этом соблюдались ограничения задачи, а также выполнялось условиеmgrad F(Q) + ∑ ui grad ϕi (Q) +i=WL∑ aj ψj (Q) = 0,j=W(4.18)где m — число ограничений типа неравенств, L — то же равенств, коэффициенты aj > 0.За приведенной абстрактной формулировкой условий скрывается достаточно просто понимаемый геометрический смысл.
Действительно, рассмотрим сначала случай с ограничениями только типа неравенств. Если максимум находится внутри допустимой области R, то, выбирая все ui = 0, добиваемся выполнения (4.17); если же точка максимума Q лежит на границе области R, то, как видно излевой части рис. 4.9, эту точку всегда соответствующим подбором неотрицательных ui можно поместить внутрь оболочки, натянутой на градиенты целевой функции F(X) и функций-ограничений ϕi(X).Наоборот, если точка не является экстремальной, то (4.17) нельзя выполнить при любом выборе положительных коэффициентов ui (см.
правуючасть рис. 4.9, где рассматриваемаяточка N лежит вне выпуклой оболочки,натянутой на градиенты). Учет ограничений типа равенств очевиден, если добавляется последняя из указанных в%+,. 4.9. К пояснению условий Куна-Таккера(4.18) сумма.E.-451 34+,7: <,D49016 T7,-8./</49. Широко известен метод множителей Лагранжа, ориентированный на поиск экстремума при наличии ограничений типа равенств ψ(X) = 0, т.е. на решение задачиextr F(X),(4.19)X∈Rгде R = { X | ψ(X) = 0 }.Cуть метода заключается в преобразовании задачи условной оптимизации (4.19) в задачу безусловной оптимизации с помощью образования новой целевой функцииLФ(N,V) = F(X) + ∑ λi ψi (X),i=W&.+.)$(*),$" . !"#$%!#&'&($"!))$*+($*,#&($"!)&*1055@!"! 4%!#*%!#&F*:,$*$I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&Mгде Λ = (λ1, λ2, λ3 ...λh) — вектор множителей Лагранжа, L — число ограничений.Необходимые условия экстремума функции Ф(N):L∂Ф(N,Λ)/∂N = ∂F(X)/∂N + ∑ λi ∂ψi (X)/∂X = 0;i=W(4.20)∂Ф(N,Λ)/∂Λ = ψ (X) = 0.Система (4.20) содержит n+L алгебраических уравнений, где n — размерность пространства управляемых параметров, ее решение дает искомые координаты экстремальной точки и значения множителей Лагранжа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
