Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 55
Текст из файла (страница 55)
Итерационный процесс здесь уже не оканчивается после конечного числа шагов, а направления р< "> не являются, вообще говоря, сопряженными относительно некоторой матрицы. Решение задач одномерной минимизации (10.40) приходится осуществлять численно. Отметим также то, что часто в методе сопряженных градиентов при в = ш, 2ти, Зш, ... коэффициент Д, ~ не вычисляют по формулам (10.36), (10.37), а полагают равным нулю. При этом очередной шаг производят фактически методом наискорейшего спуска.
Такое "обновление" метода позволяет уменьшить влияние вычислительной погрешности. Для сильно выпуклой гладкой функции ~при некоторых дополнительных условиях метод сопряженных градиентов обладает высокой сверхлинейной скоростью сходимости. В то же время его трудоемкость невысока и сравнима с трудоемкостью метода наискорейшего спуска. Как показывает вычислительная практика, он незначительно уступает по эффективности квазиньютоновским методам, но предъявляет значительно меньшие требования к используемой памяти ЭВМ. В случае, когда решается задача минимизации функции с очень большим числом переменных, метод сопряженных градиентов, по-видимому, является единственным подходящим универсальным методом. т 10.6. Методы минимизации без вычисления производных 1. Методы прямого поиска.
Метод деформнруемого многогранника. Существует большой класс методов минимизации, каждый из которых основан на сравнении значений целевой функции в последовательно вычисляемых пробных точках. Это так называемые всходи аряло~о «оиска. Обычно они применяются тогда, когда в любой окрестности точки локального минимума целевая функция не является гладкой, а множество точек, в которых она недифференцируема, имеет слишком сложную структуру. К сожалению, методы прямого поиска в большин-' стве случаев очень неэффективны. Обращаться к ним, по-видимому,'' 2Я7 имвет смысл только тогда, когда есть уверенность, что никакие другие подходы к решению задачи минимизации невозможны. Рассмотрим кратко один из наиболее известных методов прямого поиска — летпод деформируемо1о ммо1о1ранника, Сначала необходимо задать т + 1 точку х<®, х'О>, ..., х~о> так, чтобы векторы х~~~~ — х<м Ыо> — Ыо>, ..., х<011 — х'О> были линейно независимы.
Тогда эти точ ки можно интерпретировать как вершины тв-мерного многогранника. Обычно начальный многогранник выбирают правильным. Опишем очередную (и + 1)-ю итерацию простейшего варианта метода. Будем предполагать, что точки х,'"1, х<"', ..., х~',", являются вершинами многогранника, полученного на предыдущей итерации, и занумерованы так, что ~(х< ">) = ш1п у(х~"') ~(Ыю) = 1< ~ ~яг+1 гпах ~(х~."~). Отбрасывают точку х~~",> как самую неудачную. 1~ г(я+1 Затем вычисляют "центр тяжести" оставшихся точек по формуле ] И х<"' = — Е х("' и строят пробную точку х'"' = а'"> + (х'"~ т ;=1 пр — х~~,"',), отразив симметрично вершину х~~',", относительно точки х'"'. Геометрическая иллюстрация этой операции в случае т = 2 приведена на рис.'10.9„а.
Заметим, что в плоском случае роль многогранника играет треугольник. к, ( к'" У ,/и/ д) Р . ~Од Далее возможны три случая. С л у ч а й 1: ~(х,'"') < ~(х~~"') < ~(х~~ "1), т. е. пробная точка не привела к уменьшению значения целевой функции, но и не стала "худшей" в наборе х<"', х<"), ..., х~~"', х~~ "~. В этом случае точку признают удовлетворительной и х~ "~ заменяют на х'"'. и+1 пр 288 С л у ч а й 2: /(я~~ ">) < /(я["'), т. е. выбор пробной точки привел к уменьшению значения целевой функции. Тогда направление отражения считают удачным и делают попытку "растянуть" многогранник в этом направлении с коэффициентом растяжения ф > 1 (обычно 2 1 д < ь 3). Находят точку я~ "1 = н< "> + ф (з'"> — я~,"~,).
Если /(а< "~) < < ~(я~~ ">), то растяжение прошло удачно и точку я~~",[ заменяют на я~ "~. В противном случае растяжение было неудачным и производят Р замену Ы"' на а< ">. На рис. 10.9 б показано "растяжение" с коэффи— а+1 пр ) циентом р = 2. С л у ч а й 3: /(х~~ "~)>~(я< ™). В этом случае считают, что многогранник следует сжать.
Если /(яф~ ) > /(в~~",11), то вершину *~ ',", заменяют точкой я~ "> = в~ "> — Ян<"' — я~~п>,). Если же /(я<"') 4 1(я~~",[), '1 то я~~",[ заменяют на х~~ "> = з<"'+ ~(н' ю — я~~",[). Здесь 0 < у < 1, 7— 2 коэффициент сжатия (обычно у = 1/2). На рис. 10.9, в показано "сжатие" с коэффициентом т = 1/2. Помимо операций отражения, сжатия и растяжения периодически (после выполнения определенного числа итераций) производят операцию замены текущего многогранника правильным многогранником— так называемое восстановление. Прн восстановлении сохраняются лишь две лучшие точки последнего многогранника.
расстояние между этими точками принимают за длину ребра вновь генерируемого правильного многогранника. Эта операция позволяет ликвидировать излишние деформации, возникающие в ходе итераций. Известно большое число различных модификаций этого метода. Подробно они описаны в книгах [24~, [91]. Там же указаны различные критерии окончания. 2.
Методы минимизации гладких функций, испояьзукнцие конечноразностные аппроксимации производных. Довольно часто в приложениях возникает необходимость в мчнимизации функций, обладающих достаточным числом производных, которые тем не менее недоступны для прямого вычисления. Например, такая ситуация имеет место тогда, когда значение функции является результатом решения сложной математической задачи. В этом случае приходится применять алгоритмы, использующие лишь вычисляемые в различных точках значения функции ~ Здесь обращение к методам прямого поиска (типа метода деформируемого многогранника), специально разработанным для минимизации негладких функций, вряд ли целесообразно, 1Π— гз 289 так как эти методы не позволяют извлекать никакой выгоды из возможной гладкости функции.
Часто существенно лучший результат можно получить, заменив в одном из алгоритмов спуска используемые в нем производные их аппроксимациями в соответствии с формулами численного дифференцирования (см. гл. 12). Например, для производной ~' простейшая аппроксимация такова: 2 У;(з1, хъ ..., ха) ~ 'У' 1 'з — (~(х1, ..., х1 Ь х1 + И~, х~ ~, ..., юа) — /(аи зт, ..., з~)).
Подобная модификация алгоритмов не является тривиальной и требует достаточной осторожности в реализации. Это связано с высокой чувствительностью формул численного дифференцирования к ошибкам в вычислении функции (см. ~ 12.3). Более подробное обсуждение методов минимизации, использующих конечно-разностное аппроксимации производных, можно найти в ~24] и 132~.
В заключение все же отметим, что конечно-разностные аппроксимации производных используются в алгоритмах минимизации тогда, когда аналитическое вычисление производных невозможно. Если же производные можно вычислить аналитически, то усилия, потраченные на такое вычисление, как правило, окупаются.
З 10.7. Допсиппвтельные замечания 1. Задача о наименыпих квадратах. Среди задач безусловной минимизации особое место занимает задача минимизации функций вида К Ф (в) = Е ~(я)т у=1 (10А1) У~(я) = 0 (у = 1, 2, ..., Л~) (10.42) (см. гл. 7). Действительно, если решение я системы (1О.42) существует, то оно совпадает с точкой глобального минимума функции Ф, причем Ф (я) = О.
290 где Я(я), ..., Ят) — некоторые функции т переменных. Необходимость в минимизации таких функций возникает, например, при использовании метода наименьших квадратов для решения задачи аппроксимации функции (см. гл. 11) либо для решения проблемы идентификации математической модели по данным зксперимента. К поиску точки минимума функции вида (10.41) сводится и задача решения системы нелинейных уравне- ний - Для минимизации функции (10.41) в принципе можно применить любой из универсальных методов минимизации.
Однако, как правило, этого не делают, а используют алгоритмы, специально разработанные для решения задачи о наименьших квадратах. Достаточно подробное их обсуждение можно найти, например, в [32]. 2. Естественно, что в данной книге содержится лишь краткое введение в методы решения задач безусловной минимизации, Более подробное изложение можно найти, например, в [6], [18], [24], [32], [64], [66], [76], [9Ц и др.
3. Задачи условной минимизации. Множество , .Х, на котором минимизируется функция у часто задается с помощью системы неравенств вида у,(т~, л2, ..., хм) 1 О, 1= 1, 2, ..., к Если целевая функция у и задающие множество Х функции у; линейны, то задачу минимизации называют задачей линейного вроьра иаироеиния. Если же хотя бы одна из этих функций нелинейна, то говорят о задаче нелинейно~о вро1ра имировзнил. Обсуждение методов решения задач условной минимизации при всей их важности выходит за рамки данной книги. Укажем, например, на книги [18], [24], [76], [9Ц, содержащие достаточно подробное и доступное введение в соответствующие методы. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
