В большинстве случаев задача оптимизации функции n переменных f(x) = (x1, x2,…, xn) на множестве X=En бывает сложнее задачи оптимизации функции одной переменной, так как с ростом размерности пространства переменных возрастают объём вычислений и сложность алгоритмов, а также затрудняется анализ поведения целевой функции.
Для решения задачи безусловного экстремума функции f(x) наиболее часто применяют приближенные методы, в основе которых лежит вычисление производных. Такие методы обычно называют градиентными.
Используя градиентные методы, можно найти решение любой задачи нелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно и глобальным. Градиентные методы могут быть подразделены на две группы.
К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов является метод Франка-Вульфа.
Ко второй группе относятся методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Из таких методов наиболее часто используется метод штрафных функций или метод Эрроу-Гурвица.
В зависимости от наивысшего порядка частных производных функции f(x) численные методы решения задачи безусловной оптимизации принято делить на три группы:
1. Методы нулевого порядка, использующие только информацию о значении функции f(x). К ним можно отнести, рассмотренные в главе 5, метод деления интервала пополам (дихотомии), золотого сечения, а также Розенброка, сопряжённых направлений, случайного поиска и др.
2. Методы первого порядка, использующие информацию о первых производных функции f(x). К ним можно отнести метод градиентного спуска с постоянным шагом, наискорейшего градиентного спуска, покоординатного спуска, Гаусс-Зйделя, Флетчера-Ривса, Дэвидона-Флетчера_Пауэла, кубической интерполяции.
3. Методы второго порядка, требующие для своей реализации знания вторых производных функции f(x). К ним можно отнести метод Ньютона-Рафсона.
Градиентный метод основан на простой идее. Если заранее известно, что функция ¦(Х) имеет в допустимой области единственный экстремум. В допустимой области необходимо взять произвольную точку Х(0) и с помощью градиента (антиградиента) определить направление, в котором ¦(Х) возрастает (убывает) с наибольшей скоростью (рисунок). Сделав небольшой “шаг” в найденном направлении, перейти в новую точку Х(1). Потом снова определить наилучшее направление для перехода в очередную точку Х(2) и т.д. Иначе говоря, надо построить последовательность точек Х(0) , Х(1) , Х(2) ,… так, чтобы она сходилась к точке экстремума Х*. Величина шага из точки Х(k) по направлению градиента Ѧ(Х(k)) (антиградиента -Ѧ(Х(k) ) определяется значением параметра l в уравнении прямой
Х(k+1) =Х(k) +Ѧ(Х(k))l
или
Х(k+1) =Х(k) +(-Ѧ(Х(k)))l, (1)
где k=0,1,2,3,… ,проходящей через Х(k) параллельно градиенту (антиградиенту). Значение l выбирают из соображений: перемещение по прямой сопровождается изменением функции ¦(Х) на величину Ѧ(Х), которая зависит от выбранного значения l. Значение l*, при котором приращение ∆¦ достигает наибольшей величины можно определить, используя необходимый признак экстремума ∆¦:
где (1) и (2) – значения частных производных и градиента в новой точке х(1) и исходной х(0).
При нахождении решения задач градиентными методами, в том числе и названными, итерационный процесс осуществляется до того момента, пока градиент функции ¦(х1, х2, х3,…, хn) в очередной точке х(k+1) не станет равным 0 или же пока ½¦(Х(k+1) ) - ¦(Х(k) )½ < e, где e - достаточно малое положительное число, характеризующее точность полученного решения.
