Федоренко Р.П. Введение в вычислительную физику (1185915), страница 86
Текст из файла (страница 86)
Он отличается от описанных выше тем, что в качестве направления движения выбирается «случайное» направление, т,е. единичный вектор е, генерируемый каким-либо датчиком случайных векторов, равномерно распределенных на единичной сфере в Р (такие датчики входят в состав математического обеспечения современных ЭВМ).
«Почти любое» направление е является направлением «спуска», если, конечно, рассматривать как положительные, так н отрицательные значения ю. Стационарными точками процесса построения минимизирующей последовательности являются только точки локального минимума уо. Эффективность методов спуска. «Овраги».
Задача поиска минимума гладкой функции с общематематической точки зрения является одной из простейших. Основная идея решения (построение минимизирующей последовательности) очевидна, да н конструктивная ее реализация не очень сложна. Проблема существования решения н сходимостн процесса решается тоже ие очень сложными средствамн. Ответ дают такие простые факторы, как непрерывность н принадлежность всех точек хт некоторому компакту. Поэтому сведение какой-либо задачи к поиску ппп ув(х) на компакте справедливо считают почти исчерпывающим ее решением, Многие сложные задачи естествознания и техники стремятся оформить именно как варнациоиные задачи. Однако внешняя простота решения обманчива.
Дело в том, что задача проста, если она решается «в принципе»: на уровне доказательства сходнмости. Но пока не обсуждался важнейший фактор — эффективность процесса поиска минимума, количество вычислений функции ув, которое по- 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 элементами гессиана. Элементы Н этими соотношениями, конечно, однозначно ие определяются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
