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

8.1. Градиентные методы В большинстве случаев задача оптимизации функции n переменных f (x) = (x ₁, x ₂, …, x_n) на множестве X = Eⁿ бывает сложнее задачи оптимизации функции одной переменной, так как с ростом размерности пространства переменных возрастают объём вычислений и сложность алгоритмов, а также затрудняется анализ поведения целевой функции.Для решения задачи безусловного экстремума функции f (x) наиболее часто применяют приближенные методы, в основе которых лежит вычисление производных. Такие методы обычно называют градиентными. Используя градиентные методы, можно найти решение любой задачи нелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно и глобальным. Градиентные методы могут быть подразделены на две группы.К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов является метод Франка-Вульфа. Ко второй группе относятся методы, при использовании которых исследуемые точки могут, как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Из таких методов наиболее часто используется метод штрафных функций или метод Эрроу-Гурвица. В зависимости от наивысшего порядка частных производных функции f (x) численные методы решения задачи безусловной оптимизации принято делить на три группы: 1. Методы нулевого порядка, использующие только информацию о значении функции f (x). К ним можно отнести, рассмотренные в главе 5, метод деления интервала пополам (дихотомии), золотого сечения, а также Розенброка, сопряжённых направлений, случайного поиска и др.2. Методы первого порядка, использующие информацию о первых производных функции f (x). К ним можно отнести метод градиентного спуска с постоянным шагом, наискорейшего градиентного спуска, покоординатного спуска, Гаусс-Зайделя, Флетчера-Ривса, Дэвидона-Флетчера Пауэла, кубической интерполяции.3. Методы второго порядка, требующие для своей реализации знания вторых производных функции f (x). К ним можно отнести метод Ньютона-Рафсона. Градиентный метод основан на простой идее. Если заранее известно, что функция ¦(х) имеет в допустимой области единственный экстремум. В допустимой области необходимо взять произвольную точку х ⁽⁰⁾ и с помощью градиента (антиградиента) определить направление, в котором ¦(х) возрастает (убывает) с наибольшей скоростью (рис. 8.1). Сделав небольшой “шаг” в найденном направлении, перейти в новую точку х ⁽¹⁾. Потом снова определить наилучшее направление для перехода в очередную точку х ⁽²⁾ и т.д. Иначе говоря, надо построить последовательность точек х ⁽⁰⁾, х ⁽¹⁾, х ⁽²⁾, … так, чтобы она сходилась к точке экстремума х *. Величина шага из точки х ^(k) по направлению градиента Ñ ¦(х ^(k)) (антиградиента -Ñ ¦(х ^(k)) определяется значением параметра l в уравнении прямой

х ^{(k +1)} = х ^(k) +Ñ ¦(х ^(k))l

или

х ^{(k +1)} = х ^(k) +(-Ñ ¦(х ^(k)))l, (8.1)

где k = 0, 1, 2, 3, …, проходящей через х ^(k) параллельно градиенту (антиградиенту).

Рис. 8.1. Графическое изображение градиентного метода

Значение l выбирают из соображений: перемещение по прямой сопровождается изменением функции ¦(х) на величину Ñ ¦(х), которая зависит от выбранного значения l. Значение l*, при котором приращение ∆ ¦ достигает наибольшей величины можно определить, используя необходимый признак экстремума ∆ ¦: d ∆ ¦ / d l = Ñ ¦(х ⁽¹⁾) ∙ Ñ ¦(х ⁽⁰⁾) = (¶¦ / ¶ х ₁)⁽¹⁾ ∙ (¶¦ / ¶ х ₁)⁽⁰⁾ = 0, (8.2)где (1) и (2) – значения частных производных и градиента в новой точке х ⁽¹⁾ и исходной х ⁽⁰⁾. При нахождении решения задач градиентными методами, в том числе и названными, итерационный процесс осуществляется до того момента, пока градиент функции ¦(х^{( 1)}, х^{( 2)}, х^{( 3)}, …, х^{( n )}) в очередной точке х ^{(k +1)} не станет равным 0 или же пока ½ ¦(х ^{(k +1)}) - ¦(х ^(k))½ < e, где e – достаточно малое положительное число, характеризующее точность полученного решения.