Основы теории оптимизации (стр. 79 )

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

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

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

последовательность {xk}построенная алгоритмом (5), сходится к точке минимума функции x* по закону геометрической прогрессии

где С=const,

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

Аналогичная картина наблюдается и для простой градиентной схемы

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

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

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

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

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

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

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

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

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

Иногда итерации строятся по схеме

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

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

Более целесообразно обобщение метода Ньютона на случай минимизации овражных функций проводится на базе непрерывного принципа оптимизации. Функции J(х) ставится в соответствие дифференциальная система (3), интегрируемая системным методом (см. Жесткая дифференциальная система). Алгоритм минимизации принимает вид

Предложен алгоритм минимизации овражной функции, основанный на использовании свойств жестких систем. Пусть функция J(x) в окрестности x0 аппроксимируется квадратичной функцией (6). Матрица D и вектор b вычисляются, например, с помощью конечно-разностной аппроксимации. Из представления элементов матрицы

где

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

имеет решение, в котором в силу условия (1) слагаемые с сомножителями оказывают влияние лишь на малом начальном отрезке длиной . Другими словами, компоненты вектора х(t) удовлетворяют равенству

быстро переходящему в стационарную связь

где - компоненты вектора, удовлетворяющие равенству (12). Это свойство используется в алгоритме. Выражая j-ю компоненту вектора , которой соответствует максимальная компонента вектора и1, через остальные компоненты, вместо функции J(x), получают новую функцию с аргументом размерности (т-1):

По функции (13) с помощью конечноразностной аппроксимации находится новая матрица порядка ( т-1) и вектор Здесь важно не только и не столько понижение размерности пространства поиска, сколько уменьшение степени овражности, т. к. при минимизации новой функции в подпространстве, ортогональном вектору u1, большое собственное значение уже не оказывает влияния на вычислительный процесс. Самым существенным моментом здесь является требование получения по функции (13), а не по матрице D и вектору b. Коэффициенты связи (12) находят степенным методом, как коэффициенты любого уравнения системы

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

Сравнение методов многомерной безусловной оптимизации

Существуют два пути сравнения: теоретическое исследование сходимости и численные эксперименты.

Метод Пауэлла - суперлинейная скорость сходимости.

Метод Коши - линейная скорость.

Метод Ньютона - квадратичная.

Методы сопряжённых градиентов - линейная скорость сходимости.

Квазиньютоновские - квадратичная скорость.

В результате численных экспериментов Химмельблау («Нелинейное программирование») методы распределяются по количеству вычислений значений функции, устойчивости, машинному времени. Устойчивость характеризует ширину круга задач (успешно решаемых).

Лучшие методы: ДФП, Пауэлла, Бройдена-Флетчера-Шенно.

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

Выводы:

1) превосходство квазиньютоновских методов при решении задач с функциями общего вида;

2) на эти методы точность вычислений на ЭВМ оказывает большее влияние, чем на методы сопряжённых градиентов.

  Функция Розенброка:

f(x) = 100(x2-x12)2+(1-x1)2

(общепринятая тестовая)  f(1,1) = 0  (минимум)

Комбинация метода Коши и метода деления пополам обеспечивает наибольшую точность при больших затратах машинного времени. Самая эффективная с точки зрения вычисления значений функции - комбинация Бройдена-Флетчера-Шенно и кубической аппроксимации.