Математическая энциклопедия - овражных функций методы минимизации

численные методы отыскания минимумов функций многих переменных. Пусть задана ограниченная снизу дважды непрерывно дифференцируемая по своим аргументам функция

для к-рой известно, что при нек-ром векторе (знак транспонирования) она принимает наименьшее значение. Требуется построить последовательность векторов такую, что

Существует много методов, позволяющих получить указанную последовательность векторов. Однако общим недостатком большинства алгоритмов является резкое ухудшение их свойств в случаях, когда поверхности уровня минимизируемой функции имеют структуру, сильно отличающуюся от сферической. В этом случае нек-рую область , в к-рой норма вектора-градиента существенно меньше, чем в остальной части пространства, наз. дном оврага, а саму функцию овражной функцией. Если размерность пространства аргументов минимизируемой функции больше двух, то структура поверхностей уровня овражных функций может оказаться весьма сложной. Появляются (т-к)-мерные овраги, где число кизменяется от 1 до т-1. В трехмерном пространстве, напр., возможны одномерные и двумерные овраги.

Функции овражного типа локально характеризуются плохой обусловленностью матриц двух производных (матриц Гессе)

что приводит к сильному изменению функции вдоль направлений, совпадающих с собственными векторами матрицы Гессе для больших собственных чисел, и к слабому изменению вдоль других направлений, отвечающих малым собственным значениям матрицы Гессе. Большинство известных методов оптимизации позволяет достаточно быстро попадать на дно оврага, приводя иногда к существенному уменьшению значения функции J(х)по сравнению с его значением в начальной точке (спуск на дно оврага). Однако далее процесс резко замедляется и практически останавливается в нек-рой точке из Q, к-рая может быть расположена очень далеко от истинной точки минимума.

Дважды непрерывно дифференцируемая по своим аргументам функция J(х)наз. овражной функцией (см. [1]), если существует нек-рая область , где собственные значения матрицы Гессе , упорядоченные в любой точке по убыванию модулей, удовлетворяют неравенствам

Степень овражности характеризуется числом

Если собственные значения в области Gудовлетворяют неравенствам

то число r наз. размерностью оврага функции при (см. [1]).

Системы дифференциальных уравнений, описывающие траекторию спуска овражной функции ,

являются жесткими дифференциальными системами. В частности, когда функция J(х)сильно выпуклая и матрица Гессе положительно определена (все ее собственные значения строго больше нуля), неравенства (1) совпадают с известным требованием плохой обусловленности матрицы Гессе

В этом случае спектральное число обусловленности совпадает со степенью овражности.

Метод покоординатного спуска (см. [2])

несмотря на простоту и универсальность, в овражной ситуации эффективен лишь в редких случаях ориентации оврагов вдоль координатных осей.

Предложена (см. [2]) модернизация метода (4), состоящая в использовании процедуры вращения осей координат так, чтобы одна из осей была направлена вдоль после чего начинается поиск на (k+1)-м шаге. Такой подход приводит к тому, что одна из осей имеет тенденцию выстраиваться вдоль образующей дна оврага, позволяя в ряде случаев весьма успешно проводить минимизацию функций с одномерными оврагами. В случае многомерных оврагов метод непригоден.

Схема метода наискорейшего спуска задается разностным уравнением

где выбирается из условия

Для сильно выпуклой овражной функции, в частности квадратичной

последовательность построенная алгоритмом (5), сходится к точке минимума функции по закону геометрия, прогрессии (см. [3])

где С=const,

Так как для овражной функции и сходимость практически отсутствует.

Аналогичная картина наблюдается и для простой градиентной схемы (см. [4])

Ускорение ее сходимости основано на использовании результатов предыдущих итераций для уточнения дна оврага. Может быть использован (см. [4] [5]) градиентный метод (7) с вычислением на каждой итерации отношения Когда оно устанавливается около нек-рого постоянного значения , делается большой ускоряющий шаг согласно выражению

Далее из точки xk+1 продолжается спуск градиентным методом до следующего ускоряющего шага.

Различные версии метода параллельных касательных (см. [4] [6]) основаны на выполнении ускоряющего шага вдоль направления задаваемого точками в градиентном методе. В методе "тяжелого шарика" (см. [4]) очередное приближение имеет вид

Вметоде оврагов (см. [7]) предлагается провести локальные спуски градиентным методом (7) из двух случайно выбранных исходных точек, а затем выполнить ускоряющий шаг по направлению, задаваемому двумя полученными на дне оврага точками.

Все эти методы немногим сложнее градиентного метода (7) и построены на его основе. Ускорение сходимости получается для одномерных оврагов. В более общих случаях многомерных оврагов, где сходимость этих схем резко замедляется, приходится обращаться к более мощным методам квадратичной аппроксимации, в основе к-рых лежит метод Ньютона

Точка минимума функции (6) удовлетворяет системе линейных уравнений

и при условии абсолютной точности всех вычислений для квадратичной функции метод Ньютона независимо от степени овражности (2) и размерности оврагов приводит к минимуму за один шаг. На самом деле, при больших числах обусловленности k(D)при ограниченной разрядности вычислений задача получения решения (9) может быть некорректной, и небольшие деформации элементов матрицы Dи вектора могут приводить к большим вариациям

При умеренных степенях овражности в выпуклой ситуации метод Ньютона часто оказывается более предпочтительным по скорости сходимости, чем другие, напр, градиентные, методы.

Большой класс квадратичных (квазиньютоновских) методов основан на использовании сопряженных направлений (см. [2], [3], [8]). Эти алгоритмы для случая минимизации выпуклой функции оказываются весьма эффективными, ибо, имея квадратичное окончание, они не требуют вычисления матрицы двух производных.

Иногда (см. [8]) итерации строятся по схеме

где Еединичная матрица. Скаляр подбирается так, чтобы матрица была положительно определенной и чтобы