Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 87
Текст из файла (страница 87)
Поэтому сведение какой-либо задачи к поиску ппп ув(х) на компакте справедливо считают почти исчерпывающим ее решением, Многие сложные задачи естествознания и техники стремятся оформить именно как варнациоиные задачи. Однако внешняя простота решения обманчива. Дело в том, что задача проста, если она решается «в принципе»: на уровне доказательства сходнмости. Но пока не обсуждался важнейший фактор — эффективность процесса поиска минимума, количество вычислений функции ув, которое по- 413 з 2М ПОИСК МИНИМУМА надобится для определения пип г»(х) с какой-то (часто не очень высокой) степенью точности.
Продолжающееся до сих пор конструирование алгоритмов поиска минимума имеет основной целью повышение их эффективности и надежности. Такая работа должна опираться на достаточно четкую теоретическую концепцию, обьясняюшую причины возможной крайне низкой скорости убывания /О(хз). конечно, одной из причин этого может быть существенная фактическая негладкость гв, даже Если формально она имеет сколько угодно непрерывных производных. С точки зрения вычислителя гладкость — это не число существующих производных, а константы, ограничивающие их значения.
Если эти константы просто «конечны», то нет особой разницы между классами гладких и негладких функций. Эту причину (существенную негладкость /'О) оставим пока в стороне. Ведь отношение вычислителя к тем или иным методам определяется не столько их способностью решать задачу данного типа в ее общей формулировке, сколько эффективностью метода в классе тех задач, которые нуждаются в фактическом решении.
Итак, в каком случае методы спуска оказываются эффективными, а в каком нет? Этот вопрос сейчас изучен достаточно полно. Основной моделью, на которой получаются точные результаты, является класс квадратичных функций /з(х) = (а, х) + 0.5(Ах, х) с положительно-определенной самосопряженной матрнцей А. В окрестности точки минимума (слово «локальный» будем для краткости опускать) гладкая функция / хорошо аппроксимируется именно квадратичной функцией.
Матрица А в данном случае аналогична матрице дзГП/дх1дхз, именуемой гессианом. Существенным фактором, определяющим эффективность метода спуска по градиенту, является обусловленность матрицы А, т.е. отношение 1з = 1/1., где 1. н 1 — максимальное и минимальное собственные числа А. Расстояние 11х1 — х'11 убывает, как д1, где о= (1.
— 1)/(1. +1). При малых значениях 11 имеем д ж 1 — 2 у~. Чем меньше ть тем медленнее осуществляется поиск минимума. Число Ч имеет простую геометрическую интерпретацию: линии уровня квадратичной функции (при А > О) суть «эллипсоиды», отношение экстремальных полуосей которых как раз и есть у~. Таким образом, «трудная» функция /О(х) — это функция, график которой похож на «овраг» с крутыми «склонами» и очень длинным пологим «дном», вдоль которого нужно очень долго идти до точки минимума. Первые шаги процессов поиска приводят к быстрому спуску со «склона» на дно оврага, после чего начинается длительное «зигзагообразное» движение вдоль «дна» с очень медленным темпом убывания / за шаг.
Прн и =! (линии уровня — сферы) метод спуска по 414 ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ 1ч. и градиенту приводит к минимуму за один шаг. Скорость сходнмости (число д) покоординатного спуска в этом случае легко оценить. Предоставим это поучительное упражнение читателю (здесь интересна зависимость о от размерности пространства). Несколько сложнее оценивается математическое ожидание убывания уо (при з1 = 1) за один шаг спуска в случайном направлении. Здесь существенна размерность, причем сказывается следующее неприятное обстоятельство: почти вся площадь сферы в Ях сосредоточена в узком поясе около экватора (это свойство сфер проявляется тем резче, чем больше М). Поэтому «почти любое» случайное направление «почти ортогональное направлению градиента, т.е.
направлению в точку минимума такой просгой функции, как " х~. (Предоставим читателю эти вычисления. Они не составят труда для того, кто знает формулу площади многомерной сферы.) Эффективность процесса поиска минимума можно существенно повысить линейным преобразованием пространства, т.е. используя замену х = Ву, Легко понять, какой должна быть матрица В; квадратичная форма после замены переменных перейдет в (АВу, Ву) = (В'АВу, у). Чтобы в переменных у получить просто сумму квадратов, следует найти В из уравнения В'АВ = Е, например.
В качестве В можно взять А из. Это, конечно, рецепт чисто теоретический. Ои только указывает направление, в котором следует искать В: ведь можно брать матрицы В, близкие к идеальной, но более доступные иа практике. Приведенные выше соображения можно трактовать несколько иначе. В линеаризованной задаче ограничение Ьх можно сформулировать в какой-то другой метрике, например (В Ьх, Ьх) и е~ с положительной самосопряжеиной матрицей В. В этом случае методом Лагранжа найдем Ьх ж В 'У~(хэ). Квадратичная модель подсказывает идеальный выбор В: это должна быть матрица, близкая к гессиаиу А. Практическая реализация такой подсказки возможна двумя способами. Самый очевидный — использовать метод, основанный на квадратичной аппроксимации: Уо(х+ Ьх) Уо(х) + Уо Ьх+ О 5(УО Ьх Ьх) В очередной точке хг следует вычислить Д(хг) и гессиан у~„.(хт), решить задачу минимизации квадратичной функции.
Например, если размерность пространства Ф нЕ Очень велика, можно решить систему линейных уравнений уо(х~) +уо„(х') Ьх=О. Такой алгоритм иногда называют методом Ньютона, так как его можно трактовать как решение системы нелинейных уравнений У~(х) = О. Применение вышеприведенной схемы вычислений сталкивается с двумя препятствиями. В начальной точке хо гессиан у~„может ие 415 й зб1 поиск мииимтмл быть положительно-определенным.
Тогда решение задачи минимизации квадратичной формы (если мы ее действительно минимизируем) уводит нас в бесконечность. Если же решается система линейных уравнений (необходимое условие экстремума квадратичной формы), то мы уже не отличаем минимума от максимума и от другого типа стационарных точек. Поэтому такая техника применяется после некоторого числа шагов спуска по градиенту, которые проходят достаточно эффективно и выводят точку х' в область положительности гессиана.
Более серьезным препятствием является необходимость вычисления вторых производных. В пространствах не очень малой размерности это очень дорогая операция. В семидесятых годах был найден удачный компромисс, приведший к созданию так называемых квазиньютоновских процедур. Оии основаны на следующем соображении. В методе спуска по градиенту, располагая значениями градиента в разных точках у„(х.), мы получаем некоторую ограниченную на каждом шаге информацию и о у„„. В самом деле, если смещение 11х'+' — х1й ие очень велико, У,(х'+1) — /„(хэ) г„„(ху~' — хэ), т.е. если пренебречь величинами О(11х1+1 — х111з), мы знаем величины Н линейных комбинаций из элементов Ж-ьН матрицы ~„„. Накапливая такую информацию на нескольких подряд идущих шагах, можно с какой-то точностью восстановить и гессиан.
Практическая реализация вышеизложенных соображений приводит к процессу следующего типа. Кроме точки х1, имеем еще и положительно-определенную самосопряженную матрицу Н'. Функцию /(х~ + Ьх) аппрокснмируем разложением У(х1+ Ьх) ж Лхз) + /„(х1) Ъх+ 0.5(Нзбх, Ьх). Минимизируя правую часть, определяем Ьх, т.е. Ьх = — (Н'),Г„. После нахождения точки ххь1 = хз + Ьх определяем У„(х'+') и пересчитываем матрицу Н, вычисляя Н1~' таким образом, чтобы выполнялись Н вышеупоыянутых соотношений между М(У + 1)/2 элементами гессиана.
Элементы Н этими соотношениями, конечно, однозначно ие определяются. Поэтому нужно привлечь какие-то дополнительные эвристические соображения, например минимизацию отличия Нэь' от Н1 или что-либо в этом роде. Не будем доводить дело до конкретных расчетных формул (все это описано в обширной литературе по математическому программированию); ограничимся лишь изложением основных идей. В настоящее время квазиньютоновские ме- 416 пгизлижвнньш матовы вычислительной»изики (ч. и тоды составляют основу наиболее эффективных алгоритмов безусловной минимизации. Правда, нх высокая эффективность проявилась пока в задачах сравнительно невысокой размерности. Поиск глобального минимума. Это характерный пример проблемы, которая с одной точки зрения тривиальна, с другой — в сущности неразрешима.
В самом деле, вот ее тривиальное решение. Введем в Я" куб ~х„~ а Х и сетку с шагом л, покрывающую куб. Вычислим Уз(х) в узлах сетки (это потребует конечного числа операций) и найдем точку сетки, в которой достигается минимальноЕ значение Уз. Затем удвоим размер куба (Хн»2Х), уменьшим шаг Ь вдвое и повторим вышеописанную операцию. Нетрудно доказать, что для любой непрерывной функции /» мож но получить последовательность точек, сходящихся к точке глобального (абсолютного) минимума.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
