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

 5@!"! 4                           %!#*%!#&F*:,$*   $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

                             4.2. $B?48 /.-4549 43-+/+?:=++
     'D:,,+H+7:=+> /.-4549 /:-./:-+A.,74@4 384@8://+849:0+>. В САПР основными метода-
ми оптимизации являются поисковые методы. Поисковые методы основаны на пошаговом изменении
управляемых параметров
        Xk+1 = Xk + ∆Xk,                                                         (4.5)
где в большинстве методов приращение ∆Xk вектора управляемых параметров вычисляется по формуле
         ∆Xk = hg(Xk).                                                                 (4.6)
Здесь Xk — значение вектора управляемых параметров на k-м шаге, h — шаг, а g(Xk) — направление
поиска. Следовательно,. если выполняются условия сходимости, то реализуется пошаговое (итераци-
онное) приближение к экстремуму.
     Методы оптимизации классифицируют по ряду признаков.
     В зависимости от числа управляемых параметров различают методы #-*#/$"*#; и /*#8#/$"*#;
оптимизации, в первых из них управляемый параметр единственный, во вторых размер вектора X не
менее двух. Реальные задачи в САПР многомерны, методы одномерной оптимизации играют вспомо-
гательную роль на отдельных этапах многомерного поиска.
     Различают методы 7+4#(*#; и 2$67+4#(*#; оптимизации по наличию или отсутствию ограниче-
ний. Для реальных задач характерно наличие ограничений, однако методы безусловной оптимизации
также представляют интерес, поскольку задачи условной оптимизации с помощью специальных ме-
тодов могут быть сведены к задачам без ограничений.
     В зависимости от числа экстремумов различают задачи одно- и многоэкстремальные. Если ме-
тод ориентирован на определение какого-либо локального экстремума, то такой метод относится к 4#-
%)45*./ /$&#-)/. Если же результатом является глобальный экстремум, то метод называют /$&#-#/
84#2)45*#8# 0#'+%). Удовлетворительные по вычислительной эффективности методы глобального по-
иска для общего случая отсутствуют и потому на практике в САПР используют методы поиска локаль-
ных экстремумов.
     Наконец, в зависимости от того, используются при поиске производные целевой функции по уп-
равляемым параметрам или нет, различают методы нескольких порядков. Если производные не ис-
пользуются, то имеет место метод *74$(#8# 0#"9-%), если используются первые или вторые производ-
ные, то соответственно метод 0$"(#8# или (&#"#8# 0#"9-%). Методы первого порядка называют так-
же градиентными, поскольку вектор первых производных F(X) по N есть градиент целевой функции
         grad (F(X)) = (∂F/∂x1, ∂F/∂x2,...∂F/∂xn).
      Конкретные методы определяются следующими факторами:
      1) способом вычисления направления поиска g(Xk) в формуле (4.6);
      2) способом выбора шага h;
      3) способом определения окончания поиска.
      Определяющим фактором является первый из перечисленных в этом списке, он подробно опи-
сан ниже.
      Шаг может быть или постоянным, или выбираться исходя из одномерной оптимизации — поис-
ка минимума целевой функции в выбранном направлении g(Xk). В последнем случае шаг будем назы-
вать оптимальным.
      Окончание поиска обычно осуществляют по правилу: если на протяжении r подряд идущих ша-
гов траектория поиска остается в малой ε-окрестности текущей точки поиска Xk, то поиск следует
прекратить, следовательно, условие окончания поиска имеет вид
          |Xk - Xk-r| < ε.
     E.-451 4504/.8042 43-+/+?:=++. К методам одномерной оптимизации относятся методы ди-
хотомического деления, золотого сечения, чисел Фибоначчи, полиномиальной аппроксимации и ряд
их модификаций.
     Пусть задан отрезок [A,B], на котором имеется один минимум (в общем случае нечетное число

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