Автоматизированное проектирование. Норенков И.П. - 103 стр.

 5@!"! 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) в окрестностях точки Ni
          grad F(Xi+1) = grad F(Xi) + K(Xi+1 - Xi).                                                            (4.11)
      Поскольку шаг h рассчитывается исходя из условия одномерной оптимизации, то, во-первых, справедливо соотношение
          Si Тgrad F(Xi) = 0,                                                                                  (4.12)

 &.+.)$(*),$" . !"#$%!#&'&($"!))$*                   +($*,#&($"!)&*                                                103