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

, где ||…|| - норма вектора.

Определим следующее направление

Выберем γ0 и γ1 так, чтобы вектора S(0), S(1) и S(2) были С-сопряжены.

Самостоятельно доказать, что все γi=0 для i=0…k-2.

Если функция квадратична, то для нахождения минимума нужно найти N-1 направлений и провести N одномерных поисков вдоль прямой.

Метод Поллака-Ребьера

В предыдущем методе:

·  функция квадратична;

·  нет погрешностей при поиске по прямой.

 Метод основан на точной процедуре поиска вдоль прямой (точно находим α(k)), но целевая функция может быть общего вида.

,

где

Квазиньютоновские методы

В этих методах обратная матрица Гессе аппроксимируется другой матрицей – метрикой. Метрика изменяется на каждой итерации и поэтому методы так же называются методами с переменной метрикой.

A(k) – матрица п×п - метрика.

A(k+1)= A(k)+ Aс(k), где Aс(k) корректирующая матрица.

Нужно построить последовательность A(0), A(1), A(2)… и так далее, которая давала бы приближение к обратной матрице Гессе.

Метод Дэвидона- Флетчера - Пауэлла

; A(0)=I

Обеспечивает убывание целевой функции от итерации к итерации.

Самостоятельно показать, что .

Метод Бройдена-Флетчера-Шенно

Метод обладает слабой по сравнению с ДФП чувствительностью к погрешности одномерного поиска.

7.3. Обобщённый алгоритм

Схожесть градиентных методов позволяет построить обобщённый алгоритм.

  1.  Задать п – число переменных, M – максимальное число итераций; x(0) – начальное приближение; ε1 - параметр окончания работы градиентного алгоритма; ε2 - параметр окончания одномерного поиска. k=0.

2.  Вычислить .

3.  Если , то xk=x* иначе, если , то xk=x*. Перейти к п. 4.

4.  Вычислить S(x(k)), используя различные способы вычисления.

5.  Если , то прейти к п. 6, иначе

6.  Решить задачу одномерного поиска и найти α(k) используя ε2

7.  Найти

8.  Если f(x(k +1))> f(x(k)), то xk=x*, иначе перейти к п. 9.

9.  Если , то xk=x*, иначе k=k+1, перейти к п. 2.

Свойства сходимости методов

Определение. Метод называется сходящися, если неравенство

выполняется на каждой итерации, где ε(k) = x(k)-x*.

  Определение. Алгоритм обладает сходимостью порядка r, если отношение

выполняется (конечно). Если r=1, то алгоритм обладает линейной скоростью сходимости. Если ещё при этом C=0, то алгоритм обладает суперлинейной скоростью сходимости. Если r=2, то скорость квадратичная.

8. Методы оптимизации овражных функций

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

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

такую, что

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

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

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

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

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

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

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

то число r называется размерностью оврага функции J(х) при xG .

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

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

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

8.1. Метод покоординатного спуска

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

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