Федоренко Р.П. Введение в вычислительную физику (1185915), страница 87
Текст из файла (страница 87)
Поэтому нужно привлечь какие-то дополнительные эвристические соображения, например минимизацию отличия Нэь' от Н1 или что-либо в этом роде. Не будем доводить дело до конкретных расчетных формул (все это описано в обширной литературе по математическому программированию); ограничимся лишь изложением основных идей. В настоящее время квазиньютоновские ме- 416 пгизлижвнньш матовы вычислительной»изики (ч.
и тоды составляют основу наиболее эффективных алгоритмов безусловной минимизации. Правда, нх высокая эффективность проявилась пока в задачах сравнительно невысокой размерности. Поиск глобального минимума. Это характерный пример проблемы, которая с одной точки зрения тривиальна, с другой — в сущности неразрешима. В самом деле, вот ее тривиальное решение. Введем в Я" куб ~х„~ а Х и сетку с шагом л, покрывающую куб.
Вычислим Уз(х) в узлах сетки (это потребует конечного числа операций) и найдем точку сетки, в которой достигается минимальноЕ значение Уз. Затем удвоим размер куба (Хн»2Х), уменьшим шаг Ь вдвое и повторим вышеописанную операцию. Нетрудно доказать, что для любой непрерывной функции /» мож но получить последовательность точек, сходящихся к точке глобального (абсолютного) минимума. Описанная выше операция носит название сканирования.
Единственное возражение против ее использования — число (Х/Ь)~ вычислений у» на каждом этапе. Сканирование используется в пространствах невысокой размерности (М = 1, 2, 3) на достаточно грубых сетках, но серьезного практического значения эта универсальная процедура поиска не имеет. Более реалистичной и достаточно часто используемой является процедура случайного поиска. При поиске ппп У»(х) в кубе !ха ж Х (величина Х задает априорную информацию о расположении минимума) значение Г~ вычисляется в последовательности точЕк х~, генерируемых датчиком случайных чисел, равномерно распределенных в кубе. Из этих точек выбирается точка с минимальным значением У».
Доказательство того, что найденная точка находится на расстоянии а, от точки минимума с вероятностью 1 — ез, где еп ез могут быль сделаны сколь угодно малыми за счет' соответственно большого числа «испытаний», является упражнением. по теории вероятностей студенческого уровня и особого интереса ие представляет. Ответ почти очевиден. Действительно трудной и интересной алгоритмической задачей является конструирование программных датчиков так называемых «псевдослучайных» чисел с равномерным распределением. Хороший датчик генерирует такую последовательность точек, что каждый ее отрезок достаточно хорошо имитирует равномерное распрЕ- деление: точки отрезка не должны «сбиваться в кучу», с одной стороны, и не должны оставлять «пустот» в кубе — с другой.
Имея такие генераторы точек, можно (при приемлемом числе вычислений У») «прощупать» ее значение в кубе и найти не слишком уж грубую оценку пнп у»(х). Число необходимых испытаний (вычислений У») существенным образом зависит от размерности куба, 417 526\ ПОИСК МИНИМУМА требуемой точности и гладкости ув(х). Ограничимся этими общими и почти очевидными сведениями. Случайный поиск давно оформился в самостоятельную дисциплину, и по этому вопросу есть богатая специальная литература.
Метод исчерпываиия. Пусть известно, что ув удовлетворяет условию Липшипд с константой С. Генерируется последовательность точек куба, выбирается точка с минимальным значением у«. Обозначим через У' минимальное значение функции после у-го испытания, Вычислим значение в очередной точке хз»'. Если ув(хз+1) > /", то около точки х1~1 можно «вырезать» сферу радиусом (У~(хз+') — У')/с, в которой значение У~ заведомо не меньше ! уз и в которой в дальнейшем вычислять значения /В не имеет / смысла. Таким образом, после каждого испытания накапливается информация о тех частях куба, в которых минимум заведомо не находится. Реализация столь простого аюбражения связана с большими алгоритмическими сложностями, касающимися в сущности двух проблем: хранения накапливающейся информации (и, возможно, ее коррекции; если после очередного испытания значение 7' изменилось, исключаемые из просмотра части куба могут быть, соответственно, расширены) и ее использования (не так-то просто генерировать разумным образом распределенные точки в оставшемся «дырявом» множестве).
Так что и эта конструкция имеет достаточно ограниченные возможности практической реализации. Одним из наиболее часто применяемых способов хоть какой-то борьбы с «опасностью локального минимума» является поиск локального минимума при разных выборах стартовых точек хо; а для выбора хе используются соображения, например, случайного поиска. Итак, простейшая задача (1) послужила поводом познакомить читателя с основными понятиями этой темы.
Перейдем к более сложным задачам. Поиск условного минимума. Начнем постепенное усложнение постановки задачи. Рассмотрим задачу (1) при условии (2а). В этом случае применимы предыдущие алгоритмы спуска по различным направлениям с небольшим алгоритмически несложным дополнением — «проецированием» точек на прямоугольник в ФУ: и = [Х, Х+1, Пусть в точке хз найдено направление е (например, е«« — у~(ху)) и образуется «линия» (в общем случае ломаная) х(г) = Р(х' + зе), где Рз — операция проецирования точки 14 — 1ЗЗЗ ЕРИБЛИЖЕИИЫЕ МЕТОДЫ ВЫЧИГЛИТЕЛЬИОЙ ФИЗИКИ [ч, и 418 е на н.
проецирование е сводится к нахождению в х точки, ближайшей к е. Решение этой задачи элементарно и состоит в покомпонеитной БСРЕЗКЕБЕ (Ре)„= (Х„, з„( Х„; з„, Х„Н е„ж Х+; Х+, г„> Х+), параметр л находится решением задачи ппп УО(Р(х1+ ее)). надо, правда, иметь в виду, что в некоторых случаях прн гладкой функции уз функция Ув(Р(х+ ее)) может иметь разрывы производных.
Вместо условий Х 6 х н ХТ можно ввести общее условие х 1= Х, где Я' — некоторое замкнутое множество. Но, конечно, с усложнением геометрии' лг' операция проецирования на е' усложняется. Метод множителей Лагранжа. Следующий класс задач был исследован очень давно. это — задачи поиска ппп /В(х) прн условиях /1(х) =.О (1 = 1, 2, ..., 1).
Подчеркнем, что в рассматриваемой задаче отсутствуют условия-неравенства. Анализ (проведенный еще Лагранжем) достаточно прост и поучителен. Пусть точка х допустима, т,е. Г1(х) =О (1= 1, 2, ..., 1). Выясним; может лн точка к быть точкой минимума и, если нег, как ее улучшить, т.е. найти допустимую точку с меньшим значением РВ? Исследование проводится методами анализа бесконечно малых. Рассмотрим последствия малого возмущения точки х.
Пусть Ьх— малое возмущение. Тогда все функции изменятся на Ы1ж /' Ьх. Итак, следует рассмотреть разрешимость задачи: у~(х) Ьх ВВ О, у1(х) Ьх = О, ! = 1, 2, ..., А Если для всех Ьх из У1(х) Ьх= О (1=1,2, ..., 2) следует Уе(х) Ьх =О, задача неразрешима и рассматриваемая точка удовлетворяет необходимым условиям экстремума. Известная теорема линейной алгебры утверждает, что в этом случае вектор у~(х) есть линейная комбинация векторов Р'„1(х) (1 = 1, 2, ..., 1), т.е. сущест- 1 вуют множители Лагранжа Л„такие, что У~(х) = ~ Х, У„'(х). Если 1 1 такого представления не существует, то задача для Ьх разрешима и существует вариация Ьх, такая, что условия /1(х+Ьх) =О вы" полняются (в первом порядке) н уВ(х + Ьх) (нли ~В(х — Ьх)) меньше /О(х).
з 26! ПОИСК МИНИМУМА Вышеприведенное рассуждение необходимо дополнить не очень сложным процессом коррекции на величины 0()~Ьхй ), с тем чтобы доказать существование таких малых Ьх = Ьх + 0(11 Ьх112), что с учетом нелинейности УО(х + Ьх) < 7О(х) и /'(х + Ьх) = Г'1(х + Ьх). С этим результатом связаны два возможных алгоритма решения задачи. Первый следует классическому рецепту Лагранжа. Образуется функция Лагранжа и ищется точка ее безусловного минимума Х(Х) =аГКППП х'(Х, Л) .х-"(Х, Х) = — (Л,ДХ)), 1ХО! = К (4) Множители Х здесь пока не определены. Разумеется, при произвольных множителях Х условия будут нарушены и для их определения ставится естественная задача д.У/дХ,.
= у1(х(Х)) = О, 1' = 1, 2, ..., 1. Это — система 1 нелинейных уравнений с / неизвестными. Ее следует решать подходящим методом, например методом Ньютона. Здесь есть, конечно, осложнения. Зависимость (4) для х(Х) реализуется решением задачи поиска безусловного минимума, а ее придется решать много раз при разных значениях Х. Положение несколько облегчается тем, что при вычислении х(Х) предыдущие значения х могут служить хорошим начальным приближением. Сложным является и вычисление производных д/1(х(Х))/дА, т,е. дифференцирование функций х(А), определенных не совсем обычным образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
