Радиоэлектронные системы Основы построения и теория. Справочник . Под ред. Я.Д. Ширмана (2007) (1151789), страница 102
Текст из файла (страница 102)
Вторая производная по вектору Й~г(а)/Йа =)~д г/да<'>да<г~~ (14.8) Й~г(а)<'Йа =д~г!да„>да<,>~~ называется матрилей Якоби — Гессе или гессианам (см. разд. 26.7). Регулнризованный метод Ньютона. К гессиану Й г(а) ! Йа добавляется диагональная матрица е1, где е — малое положительное число.
Этим предотвращается появление чрезмерно больших приращений ал„-ак, возникающих в окрестности минимума по мере приближения определителя гессиана (якобиана) к нулю. Достоинствам регуляризаваннага .метода Ньютона является быстрая сходимость приближений, недостатком — чрезмерно большой объем вычислений. Градиентный метод. Является упрощением метода Ньютона. С этой целью: ° вторая производная функции «(а) скалярного аргумента заменяется некоторой скалярной постоянной у-' > О; ° матрица вторых производных (14.8) функции «(а) векторного аргумента (гессиан) приближенно заменяется произведением у '1 скалярной постоянной у » О на единичную матрицу!.
Тогда в общем случае векторного аргумента принимается, что аь,= аг — уЙ«(аг)/Йа. (14.9) Смысл выражения (14.9) легко истолковать. Поскольку градиент Й«(а )<Йа = 8«ай г(а ) ориентирован в сторону наибольшего возрастания функции г(а ), то антиграднент (-Й(а)>Йа) ориентирован в сторону наибольшего ее убывания. Добавление к а< произведения у Й«(ал))Йа, достаточно малого по модулю, уменьшает значение «( а ), приближает его к минимуму. На рис. !4.3 итерационный лракесс, иначе снуск к минимуму функции г( а ), пояснен с помощью линий А уровня.
Видно, что с уменьшением коэффициента у итерационная процедура затягивается. Чрезмерное же завыше- ние коэффициенга у привоРис. 14.3 дит к проскакиваниям последовательных решений мимо минимума функции А г(а) (рис. 14.4). Таким образом, достоинством градиентного метода является простота вычисления последовательных Рис. 14.4 приближений, определенным недостатком — медленная сходимость, особенно при неудачном выборе коэффициента у. Возможны застревания в «оврагах». Внимание поэтому уделяют вариантам: ° подбора фиксированных значений коэффициента у и их изменений в динамике расчета; ° использованию промежуточнь>х расчетных результатов в ходе последующей оптимизации. Остановимся на некоторых из них. Метод «наискорейшего спуска». Является разновидностью градиентного метода, отличающейся опти- 218 мизацией подбора коэффициента у.
Этот коэффициент подбирается из условия минимизации функции «(а ) по значению у и обращения в нуль производной с/г(а)/</у. Расчет при этом усложняется, хотя и оправдывается приближением итерационной процедуры к ньютоновской. Приближение, однако, оказывается неполньп«. «Спуск» оптимизируется вдоль градиента минимизируемой функции с/«(а)/с/а, тогда как в общем случае неднагональности гессиана ньютоновский спуск осуществляется и вдоль, и поперек этого градиента. Метод сопряженных градиентов.
Частично восполняет указанный выше недостаток метода «наискорейшего спуска». Последний в чистом виде используется только на первом (/< = 1) шаге. Далее в процедуру (! 4.9) (/с = 2, 3, ...) с некоторым коэффициентом з) вводится градиент предыдущего шага а<«с = а « — у йг(а г)(/с/а — т! с/г (а ь<)/с/а. (14.10) <<Спуск» в направлении линейной комбинации градиентов, текущего и предыдущего, имеет определенное достоинство.
Иаправявния этих градиентов сопряжены (ортогональны) при наискорейшем спуске на предыдущем шаге. Если бы текущий градиент содержал составляющую, коллинеарную предыдущему, то предыдущий спуск не являлся бы наискорейшим. Метод сопряженных градиентов рассчитан на снижение эффекта «застревания» в «оврагах», далеких от глобального минимума функции «(а) при малых размерностях вектора а. К сожалению, при размерности вектора а, большей двух, ортогональное вектору с/«(а«)/с/а направление с/«(аг <)/«сане совпадает с ортогональным этому вектору направлением при ньютоновской процедуре.
Градиентная же процедура значительно усложняется. Метод парных градиентов. Упрощая оптимизацию, можно возвратиться на первом шаге (/с = 1) к простой градиентной процедуре, но на шагах /! = 2, 3,... использовать алгоритм (14.10) при фиксированных коэффициентах у и ц. В этом случае экспериментально наблюдается некоторый выигрыш от парности градиентов без значительных усложнений вычислительных процедур. Использование описанного метода при нейросетевом обучении обсуждается в разд.
24.!3. 14.4. Локальные экстремумы скалярных функций при ограничениях в виде равенств 14.4.1. Локальный экстремум при наличии одного ограничения На рис. 14.5 в плоскости двух скалярных переменных а<, аь образующих векторную переменную а представлены: ° область (кривая) заданного ограничения я(а) = я(а,,аз) = 0 (заштрихована), это значит, что на экстремум исследуются только точки А, В и другие, принадлежащие данной области (здесь принадлежащие заданной кривой); ° линии уровня г(а) = с< и г(а) = сз скалярной функции двух переменных г(а) = г(а<,аэ), подлежащей минимизации, которые проходят через точки А и В; ° векторы-градиенты с/я/с/а ограничивающих функций я(а) вточкахА иВ; ° векторы-антиградиенты (с/г/с/а ) минимизируемых функций «(а ) в точках А и В; Для точки А направление антиградиента (-вг/с/а) минимизируемой функции не совпадает направлением градиента с/я/оса ограничивающей функции, идущей по нормали к кривой я(а) = О.
В отсутствие ограничения любое малое перемещение от точки А вдоль или в сторону вектора-антиградиента приводило бы к перехолу на линии меньшего уровня г. При наличии ограничения минимизация осуществляется в процессе перемещения от точки к точке только по касательной к кривой я(а) = 0 (не показана). а! Рне. 14.5 /«/инин<<зачин прекращается в точке В, когда спадание функции с(а) сменяется нарастанием, а вектор с/«/оса становится коллннеарным вектору </д/с/а.
Условие коллинеарности имеет вид -с/г/с/а = Л вся/с/а, (14.11) где Л вЂ” числовой множитель, называемый мйожитвяв.и Лагранжа. Вводя функцию Лагранжа Ц а;Л) = г(а ) + Л я(а ), (14.12) необходимые условия минимума функции «(а) при наличии ограничения я(а ) = 0 представляют в виде дЬ / да = О, д/. / дЛ = 0. (14.13) Первое из условий (!4.13) сводится к условию коллинеарности (14.11). Второе условие сводится к заданному ограничению я(а ) = О. Его можно опускать, если это ограничение учитывается самостоятельно. В целом же, задача на условный экстремум функции г(а) свелась к задаче на безусловный экстремум функции Ца;Л).
14 4.2. Локальный экстремум при наличии нескольких ограничений Пусть вектор а содержит не менее т е 1 составляющих, так что может быть задано т ограничений я,(а ) = = 0 (/ = 1, 2, ..., т). Задача на условный экстремум функции г(а)сводится и в этом случае к задаче на безусловный экстремум функции Лагранжа: кс Ца, Л„Л,,...„Л ) =г(а) е „'Г Л,я,(а). (14.!4) пп 219 Необходимые условия экстремума будут д«'.! да = О, дТ!д)., = О (! = 1, 2, ..., и«), (14.15) После введения вектора ограничений й(а) = ()8,(а)~ и вектора множителей Лагранжа ) =]]2.,~ функция Лагранжа принимает внд Ца,)ь)=г(а)«).'й(а).
(14.16) Условия (14.15) безусловного экстремума функции Ца, Х)) сводятся прн этом к равенству нулю ее частньзх граднептов по векторным переменным а и )ь д«. ! да = О, дЕ! д). = О. (14.17) Результаты (14.16), (14.17) используются в разд. 14.5, ! 7.6, 23.6. 14.4.3. Численные методы нахождения условных экстремумов Являются развитием численных методов нахождення безусловных экстремумов (разд. 143.4). Совокупность составляющих п — мерного вектора а и т — мерного вектора Л можно рассматривать тогда как (п -«т) — мерный вектор А = (~з Л)! Пусть известно некоторое «-е значение А, такое что значение функции Лагранжа 1(А«) =Ца«,1«) =г(а«)+) «18(а«) близко к экстремуму. Рекуррентную процедуру уточнення А «можно строить тогда на основе метода Ньютона, граднентного метода и т.д.
Например, согласно методу Ньютона А«! = А« -(а г(А«)/«УА ] (йг(А«)! ЫА], "2 2 а согласно градиентному методу А «, = А « - у ««г(А «) /««А, где смысл постоянной у такой же, как и в соотношении (14.9). функций г(а ) и ограничений я,(а ) (~ = 1, 2, ..., т), как функций многих переменных а =]]а ]] О =1,2,, п) про- граммнрованне называют линейным програчмированивм (разд. 14.6). Частный, и практически особенно сложный, случай нелинейного программирования соответствует оптнмнзацнн функционалов (функцнй от функций) г[а,п(а)].
Его относят к динамическол«у програмлшрованию, если задачу может быть сведена к проводимым во взаимосвязи пошаговым оптимизациям. В более общем случае задача относится к вариационному исчислению. Динамнческое программирование нспользуют прн синтезе систем управления (аналогичное см. в разд. 23.6). В том случае, когда хотя бы один нз аргументов а, случаен, программирование называют стахастичвскич програччированиеи и для оптимизации используют статистические методы.
Статистические методы оптнмнзацнн рассматриваются в разд. !5 и последующих разделах Справочника. Если скалярные аргументы а, ограничиваются це- лымн числами, программирование называют целочисленныч програачированиеч. Один нз методов целочисленного программирования (генетнческнй, и прнтом стохастнческнй метод) описан в разд. 25.7.2. 14.$.2. Трафическое пояснение оптимизации при ограничениях в виде неравенств Пояснение упрощается прн размерности вектора а, равной двум, т. е.
а=]] а~ аз]]'. Примеры (рнс. 14.6,а,б) соответствуют отысканию минимумов нелинейной функции «(а) = а, «аз. (14.! 8) аз 14.$. Локальные экстремумы прн ограничениях в виде неравенств Наряду с ограннченнямн в виде равенств я( а ) = О часто учитывают ограничения в виде неравенств я(а ) «О нлн я,( а )» О. 14.б.1. Терминология Для привлечения вычислительных средств к оптнмнзацнн с ограничениями требуется план (ргойгаш) решения. Теорию подобного планирования называют .чате.чатическич програччированиеле Смысл слова кпрограммнрованне» отлнчается здесь от распространенного, соответствующего переводу алгоритмов на язык ЭВМ. Различают несколько видов математического программнровання. Прн нелинейности какой-либо нз функций, хотя бы г(а ) нлн я,( а ) (! = 1, 2, ..., т) программирование называют нелинейныл«программированием (простейшне примеры см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
