На рис. 30 X[1] – исходная точка, n=2. На первой итерации поиск производится последовательно вдоль осей x1, x2, x1. Точки X[1], X[2], X[3] – точки минимума, найденные при последовательных одномерных поисках вдоль исходных направлений. На второй итерации одномерный поиск должен производиться из точки X[3] последовательно вдоль направлений x2, x1, а также вдоль направления, совпадающего с вектором X[1]–X[3], и так далее.

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

функции n переменных точка минимума X находится точно за n итераций.

4.5.4. Методы безусловной оптимизации первого и второго порядка

Градиентом дифференцируемой функции f(X) в точке X [k] называется n-мерный вектор f(X[k]), компоненты которого являются частными производными функции f(X), вычисленными в точке X[k]. Этот вектор перпендикулярен плоскости, проведенной через точку X[k], и касательной к поверхности уровня функции f(X), проходящей через точку X[k] (рис.31).

Рис. 31

102

Вектор-градиент направлен в сторону наискорейшего возрас-

тания функции в данной точке. Вектор – f(X[k]), противоположный градиенту, называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы поиска первого порядка, называемые также градиентными методами минимизации.

Очевидно, что если нет дополнительной информации, то из точки X[k] разумно перейти в точку X[k+1], лежащую в направлении антиградиента. Это приводит к итерационному процессу вида

X[k+1]=X[k]–ak . f(X[k]), где a>0 – шаг, k=0,1,2,...

В координатной форме этот процесс записывается следующим образом:

x	[k +1]= x [k]− a			∂f	X = X[k]	, i=0,1,...,n; k=0,1,2,...
				∂x
i	i	k
				i

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента

X[k +1]− X k ≤ ε , либо выполнение условия малости градиента

f (X[k +1]) ≤ γ . Здесь ε и γ – заданные малые величины. Возмо-

жен и комбинированный критерий, состоящий в одновременном выполнении указанных условий.

Градиентные методы отличаются друг от друга способами выбора величины шага ak .

Достаточно малый постоянный шаг ak обеспечит убывание целевой функции, однако при этом может потребоваться неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума. Из-за сложности получения необходимой информации для выбора величины шага, методы с постоянным шагом применяются на практике редко.

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

Наиболее простым в реализации и в то же время вполне эффективным является метод наискорейшего спуска.

103

Метод наискорейшего спуска. В соответствии с этим методом величина шага ak на каждой итерации выбирается из условия минимума функции f(X) в направлении антиградиента:

f (X[k]− ak f (X[k]))= min(f (X[k]− a f (X[k]))).

a >0

Общий алгоритм метода состоит в следующем:

1.Задают координаты начальной точки X[0], k=0.

2.Вычисляют значение градиента f(X[k]).

3. Выполняют одномерную минимизацию по a функции f(X[k]–a. f(X[k])).

4. Вычисляют координаты точки X[k+1].

5. Проверяют условие останова итерационного процесса. Если оно выполняется, вычисления прекращают. В противном случае продолжают вычисления с п. 2 при k=k+1.

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций, так как вектор антиградиента для таких функций, как правило, направлен в окрестность точки минимума (рис. 32). У таких функций наибольшее М и наименьшее m собст-

	венные значения матрицы Гессе	H =	∂2 f			(см. подразд. 2.2)
			∂x	∂x	j
			i

мало отличаются друг от друга (матрица Н хорошо обусловлена).

Рис. 32

104

Напомним, что собственными значениями матрицы являются

корни характеристического уравнения ∆n =0, где определитель ∆n находится в соответствии с формулой (1).

Однако в случае минимизации овражных функций скорость сходимости градиентных методов значительно снижается, так как направление вектора антиградиента существенно отклоняется от направления в точку минимума (рис. 33). Обнаружить такую ситуацию можно путем оценки обусловленности матрицы Гессе минимизируемой функции. Для овражной функции матрица Н плохо обусловлена (m/М<<1).

Рис. 33

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

Метод безусловной оптимизации второго порядка (метод Ньютона). Необходимое условие экстремума функции многих

105

переменных f(X) в точке X = (x1, x2 ,...xn ) может быть записано для ее градиента в этой точке f (X)= 0 .

Разложение f(X) в окрестности некоторой точки X[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде

f (X)= f (X[k])+ H (X[k])(X − X[k])= 0 ,

где Н(X) – матрица вторых производных (матрица Гессе) минимизируемой функции. Решение уравнения дает соотношение, кото-

рое может быть положено в основу поиска точки X :

X[k +1]= X[k]− H −1(X[k]) f (X[k]),

где H-1 – обратная матрица для матрицы Гессе, а H −1(X[k]) f (X[k])= p[k] – направление спуска. Отметим, что для

квадратичной функции f(X) рассматриваемая точность разложения в ряд Тейлора достаточна для достижения минимума за один шаг. Для других функций полученное выражение может быть основой итерационного процесса поиска минимума.

Величина шага вдоль направления р[k] полагается равной единице или может определяться аналогично рассмотренному выше варианту метода наискорейшего спуска путем одномерной минимизации вдоль данного направления.

Установлено, что последовательность X[k] сходится в точке X только в том случае, когда матрица Гессе целевой функции является положительно определенной на каждой итерации. Это условие может не выполняться как на начальных итерациях, если минимизируемая функция вблизи начальной точки X[0] существенно отличается от квадратичной зависимости, так и на конечных итерациях за счет накопления ошибок. Поэтому выполнение условия положительной определенности (критерия Сильвестра, подразд. 2.2) должно проверяться на каждой итерации. Если на k-м шаге матрица H не окажется положительно определенной или не удастся получить H -1, в большинстве модификаций данного метода H -1 заменяют единичной матрицей. Соответственно получается

р[k]= f(X[k]), и на рассматриваемом шаге метод Ньютона вырождается в метод наискорейшего спуска.

Количество вычислений на итерации методом Ньютона, как правило, значительно больше, чем в градиентных методах первого порядка. Это объясняется необходимостью вычисления и обраще-

106