Овражных функций методы минимизации

- численные методы отыскания минимумов функций многих переменных. Пусть задана ограниченная снизу дважды непрерывно дифференцируемая по своим аргументам функция [img: http://localhost:8080/file/031603-228.jpg] для к-рой известно, что при нек-ром векторе [img: http://localhost:8080/file/031603-229.jpg] [img: http://localhost:8080/file/031603-230.jpg] ([img: http://localhost:8080/file/031603-231.jpg] - знак транспонирования) она принимает наименьшее значение. Требуется построить последовательность векторов такую, что [img: http://localhost:8080/file/031603-233.jpg] [img: http://localhost:8080/file/031603-232.jpg] Существует много методов, позволяющих получить указанную последовательность векторов. Однако общим недостатком большинства алгоритмов является резкое ухудшение их свойств в случаях, когда поверхности уровня минимизируемой функции [img: http://localhost:8080/file/031603-234.jpg] имеют структуру, сильно отличающуюся от сферической. В этом случае нек-рую область [img: http://localhost:8080/file/031603-235.jpg], в к-рой норма вектора-градиента [img: http://localhost:8080/file/031603-236.jpg] существенно меньше, чем в остальной части пространства, наз. дном оврага, а саму функцию - овражной функцией. Если размерность пространства аргументов минимизируемой функции больше двух, то структура поверхностей уровня овражных функций может оказаться весьма сложной. Появляются (т-к)-мерные овраги, где число кизменяется от 1 до т-1. В трехмерном пространстве, напр., возможны одномерные и двумерные овраги. Функции овражного типа локально характеризуются плохой обусловленностью матриц двух производных (матриц Гессе) [img: http://localhost:8080/file/031603-237.jpg] что приводит к сильному изменению функции [img: http://localhost:8080/file/031603-238.jpg] вдоль направлений, совпадающих с собственными векторами матрицы Гессе для больших собственных чисел, и к слабому изменению вдоль других направлений, отвечающих малым собственным значениям матрицы Гессе. Большинство известных методов оптимизации позволяет достаточно быстро попадать на дно оврага, приводя иногда к существенному уменьшению значения функции J(х)по сравнению с его значением в начальной точке (спуск на дно оврага). Однако далее процесс резко замедляется и практически останавливается в нек-рой точке из Q, к-рая может быть расположена очень далеко от истинной точки минимума. Дважды непрерывно дифференцируемая по своим аргументам функция J(х)наз. овражной функцией (см. [1]), если существует нек-рая область [img: http://localhost:8080/file/031603-239.jpg], где собственные значения матрицы Гессе [img: http://localhost:8080/file/031603-240.jpg], упорядоченные в любой точке [img: http://localhost:8080/file/031603-241.jpg] по убыванию модулей, удовлетворяют неравенствам [img: http://localhost:8080/file/031603-242.jpg] Степень овражности характеризуется числом [img: http://localhost:8080/file/031603-243.jpg] Если собственные значения [img: http://localhost:8080/file/031603-244.jpg] в области Gудовлетворяют неравенствам [img: http://localhost:8080/file/031603-245.jpg] то число r наз. размерностью оврага функции [img: http://localhost:8080/file/031603-246.jpg] при [img: http://localhost:8080/file/031603-247.jpg] (см. [1]). Системы дифференциальных уравнений, описывающие траекторию спуска овражной функции [img: http://localhost:8080/file/031603-248.jpg], [img: http://localhost:8080/file/031603-249.jpg] являются жесткими дифференциальными системами. В частности, когда функция J(х)сильно выпуклая и матрица Гессе положительно определена (все ее собственные значения строго больше нуля), неравенства (1) совпадают с известным требованием плохой обусловленности матрицы Гессе [img: http://localhost:8080/file/031603-250.jpg] В этом случае спектральное число обусловленности совпадает со степенью овражности. Метод покоординатного спуска (см. [2]) [img: http://localhost:8080/file/031603-251.jpg] несмотря на простоту и универсальность, в овражной ситуации эффективен лишь в редких случаях ориентации оврагов вдоль координатных осей. Предложена (см. [2]) модернизация метода (4), состоящая в использовании процедуры вращения осей координат так, чтобы одна из осей была направлена вдоль [img: http://localhost:8080/file/031603-252.jpg] после чего начинается поиск на (k+1)-м шаге. Такой подход приводит к тому, что одна из осей имеет тенденцию выстраиваться вдоль образующей дна оврага, позволяя в ряде случаев весьма успешно проводить минимизацию функций с одномерными оврагами. В случае многомерных оврагов метод непригоден. Схема метода наискорейшего спуска задается разностным уравнением [img: http://localhost:8080/file/031603-253.jpg] где [img: http://localhost:8080/file/031603-254.jpg] выбирается из условия [img: http://localhost:8080/file/031603-255.jpg] Для сильно выпуклой овражной функции, в частности квадратичной [img: http://localhost:8080/file/031603-256.jpg] последовательность [img: http://localhost:8080/file/031603-257.jpg] построенная алгоритмом (5), сходится к точке минимума функции [img: http://localhost:8080/file/031603-258.jpg] по закону геометрия, прогрессии (см. [3]) [img: http://localhost:8080/file/031603-259.jpg] где С=const, [img: http://localhost:8080/file/031603-260.jpg] Так как для овражной функции [img: http://localhost:8080/file/031603-261.jpg] и сходимость практически отсутствует. Аналогичная картина наблюдается и для простой градиентной схемы (см. [4]) [img: http://localhost:8080/file/031603-262.jpg] Ускорение ее сходимости основано на использовании результатов предыдущих итераций для уточнения дна оврага. Может быть использован (см. [4] [5]) градиентный метод (7) с вычислением на каждой итерации отношения [img: http://localhost:8080/file/031603-263.jpg] Когда оно устанавливается около нек-рого постоянного значения [img: http://localhost:8080/file/031603-264.jpg], делается большой ускоряющий шаг согласно выражению [img: http://localhost:8080/file/031603-265.jpg] Далее из точки xk+1 продолжается спуск градиентным методом до следующего ускоряющего шага. Различные версии метода параллельных касательных (см. [4] - [6]) основаны на выполнении ускоряющего шага вдоль направления [img: http://localhost:8080/file/031603-266.jpg] задаваемого точками [img: http://localhost:8080/file/031603-267.jpg] в градиентном методе. В методе "тяжелого шарика" (см. [4]) очередное приближение имеет вид [img: http://localhost:8080/file/031603-268.jpg] Вметоде оврагов (см. [7]) предлагается провести локальные спуски градиентным методом (7) из двух случайно выбранных исходных точек, а затем выполнить ускоряющий шаг по направлению, задаваемому двумя полученными на дне оврага точками. Все эти методы немногим сложнее градиентного метода (7) и построены на его основе. Ускорение сходимости получается для одномерных оврагов. В более общих случаях многомерных оврагов, где сходимость этих схем резко замедляется, приходится обращаться к более мощным методам квадратичной аппроксимации, в основе к-рых лежит метод Ньютона [img: http://localhost:8080/file/031603-269.jpg] Точка минимума функции (6) удовлетворяет системе линейных уравнений [img: http://localhost:8080/file/031603-270.jpg] и при условии абсолютной точности всех вычислений для квадратичной функции метод Ньютона независимо от степени овражности (2) и размерности оврагов приводит к минимуму за один шаг. На самом деле, при больших числах обусловленности k(D)при ограниченной разрядности вычислений задача получения решения (9) может быть некорректной, и небольшие деформации элементов матрицы Dи вектора [img: http://localhost:8080/file/031603-271.jpg] могут приводить к большим вариациям [img: http://localhost:8080/file/031603-272.jpg] При умеренных степенях овражности в выпуклой ситуации метод Ньютона часто оказывается более предпочтительным по скорости сходимости, чем другие, напр, градиентные, методы. Большой класс квадратичных (квазиньютоновских) методов основан на использовании сопряженных направлений (см. [2], [3], [8]). Эти алгоритмы для случая минимизации выпуклой функции оказываются весьма эффективными, ибо, имея квадратичное окончание, они не требуют вычисления матрицы двух производных. Иногда (см. [8]) итерации строятся по схеме [img: http://localhost:8080/file/031603-273.jpg] где Е- единичная матрица. Скаляр [img: http://localhost:8080/file/031603-274.jpg] подбирается так, чтобы матрица [img: http://localhost:8080/file/031603-275.jpg] была положительно определенной и чтобы [img: http://localhost:8080/file/031603-276.jpg] Существует ряд аналогичных подходов (см. [8]), основанных на получении строго положительно определенных аппроксимаций матрицы Гессе. При минимизации овражных функций такие алгоритмы оказываются малоэффективными из-за трудностей в подборе параметров [img: http://localhost:8080/file/031603-277.jpg] и т. д. Выбор этих параметров основан на информации о величине наименьших по модулю собственных значений матрицы Гессе, а при реальных вычислениях и большой степени овражности эта информация сильно искажена. Более целесообразно обобщение метода Ньютона на случай минимизации овражных функций проводится на базе непрерывного принципа оптимизации. Функции J(х)ставится в соответствие дифференциальная система (3), интегрируемая системным методом (см. Жесткая дифференциальная система). Алгоритм минимизации принимает вид [img: http://localhost:8080/file/031603-278.jpg] Предложен [1] алгоритм минимизации овражной функции, основанный на использовании свойств жестких систем. Пусть функция [img: http://localhost:8080/file/031603-279.jpg] в окрестности [img: http://localhost:8080/file/031603-280.jpg] аппроксимируется квадратичной функцией (6). Матрица Dи вектор [img: http://localhost:8080/file/031603-281.jpg] вычисляются, напр., с помощью конечно-разностной аппроксимации. Из представления элементов матрицы [img: http://localhost:8080/file/031603-282.jpg] где [img: http://localhost:8080/file/031603-283.jpg] -ортонормированный базис собственных векторов D, следует, что неточное измерение этих элементов искажает информацию о малых собственных значениях плохо обусловленной матрицы, а следовательно, приводит к некорректности задачи минимизации функции (6). Вместе с тем система дифференциальных уравнений спуска для овражной функции (6) [img: http://localhost:8080/file/031603-284.jpg] имеет решение, в к-ром в силу условия (1) слагаемые с сомножителями [img: http://localhost:8080/file/031603-285.jpg] оказывают влияние лишь на малом начальном отрезке длиной [img: http://localhost:8080/file/031603-286.jpg] Другими словами, компоненты вектора х(t)удовлетворяют равенству [img: http://localhost:8080/file/031603-287.jpg] быстро переходящему в стационарную связь [img: http://localhost:8080/file/031603-288.jpg] где [img: http://localhost:8080/file/031604-1.jpg] - компоненты вектора, удовлетворяющие равенству (12). Это свойство используется в алгоритме. Выражая j-ю компоненту вектора [img: http://localhost:8080/file/031604-2.jpg], к-рой соответствует максимальная компонента вектора [img: http://localhost:8080/file/031604-3.jpg], через остальные компоненты, вместо функции [img: http://localhost:8080/file/031604-4.jpg], получают новую функцию с аргументом размерности [img: http://localhost:8080/file/031604-5.jpg]: [img: http://localhost:8080/file/031604-6.jpg] По функции (13) с помощью конечноразностной аппроксимации находится новая матрица [img: http://localhost:8080/file/031604-7.jpg] порядка (т-1) и вектор [img: http://localhost:8080/file/031604-8.jpg] Здесь важно не только и не столько понижение размерности пространства поиска, сколько уменьшение степени овражности, т. к. при минимизации новой функции в подпространстве, ортогональном вектору u1, большое собственное значение уже не оказывает влияния на вычислительный процесс. Самым существенным моментом здесь является требование получения [img: http://localhost:8080/file/031604-9.jpg] по функции (13), а не по матрице Dи вектору [img: http://localhost:8080/file/031604-10.jpg]. Коэффициенты связи (12) находят степенным методом, как коэффициенты любого уравнения системы [img: http://localhost:8080/file/031604-11.jpg] Если степень овражности не понижается или понижается незначительно, то процесс исключения координат вектора хпродолжается рекурсивно до необходимого ее уменьшения.