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

 Пусть требуется найти наи­меньшее значение целевой функции и = f(x₁,x_2…,x_n). В качестве начального приближения выберем в n - мерном пространстве некоторую точку M₀ с координатами х₁⁽⁰⁾ , х₂⁽⁰⁾ , ... ,х_n⁽⁰⁾. Зафиксируем все координаты функции и, кроме первой. Тогда v(x₁) = f(x_l t х₂⁽⁰⁾,..., x_n⁽⁰⁾ ) — функция одной переменной x₁. Первый шаг процесса оптимизации состоит в спус­ке по координате x₁ в направлении убывания функции v от точки М₀ до некоторой точки M₁ (x₁⁽¹⁾, х₂⁽⁰⁾,..., x_n⁽⁰⁾ ). Если функция f  дифференци­руемая, то значение х₁⁽⁰⁾ может быть найдено как

Здесь а₁⁽¹⁾>0 — некоторый шаг. Соотношение (6.17) определяет дви­жение в сторону уменьшения значений функции v (если только шаг а₁⁽¹⁾ не слишком велик, в противном случае его нужно уменьшить). Действи­тельно, пусть df / dx₁(M₀) > 0. Тогда с ростом х₁ функция v возрастает, а (6.17) определяет движение в сторону уменьшения х₁.

Значение х₁⁽¹⁾ можно найти и иначе. А именно, можно решить одно­мерную задачу оптимизации для функции v(x₁). Тогда функция v в точ­ке M₁ примет наименьшее значение, т. е. функция и примет в этой точке наименьшее значение по координате xi при фиксированных остальных координатах.

Зафиксируем теперь все координаты, кроме х₂, и рассмотрим функцию этой переменной w(x₂)=f(x₁⁽¹⁾, х₂, х₃⁽⁰⁾,… ,x_n⁽⁰⁾ . Снова осуществляем спуск, теперь по координате x₂, в сторону убывания функции wот точки

M₁ до точки М₂ (х₁⁽¹⁾ , х₂⁽¹⁾, х₃⁽⁰⁾ ,..., х_n⁽⁰⁾).

Значение x₂⁽¹⁾ можно найти либо как

либо, решив задачу одномерной оптимизации для функции w(x₂).

Аналогично проводится спуск по координатам х₃, х₄,… , х_п, а затем процедура снова повторяется от х₁ до х_п и т. д. В результате этого процесса получается последовательность точек M₀, М₁, ... , в которых значения целевой функции составляют монотонно убывающую последовательность

f (М₀) ≥ f (М₁) ≥ ...

В качестве критерия завершения итерационного процесса можно ис­пользовать условия близости значений проектных параметров или целе­вой функции на двух последовательных итерациях. Однако под итерацией здесь следует понимать всю процедуру спуска по координатам от х₁ до х_п. Таким образом, близость проектных параметров можно трактовать как выполнение условий (4.21) - (4.23), а близость значений целевой функции как выполнение условия

 

М етод покоординатного спуска сводит задачу о нахождении наимень­шего значения функции многих переменных к многократному спуску в сторону уменьшения значений функции по каждому проектному пара­метру. Данный метод легко проиллюстрировать геометрически для случая функции двух переменных z= f(x,y), описывающей некоторую поверх­ность в трехмерном пространстве. На рис 6.5 нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка М₀(Х₀,У₀) описывает начальное приближение. Проводя спуск по координате х, попадем в точку M₁(x₁,y₀). Далее, двигаясь па­раллельно оси ординат, придем в точку M₂(X₁, y₁) и т. д.

 

 

 

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

Переходя на математический язык, заключаем, что направление наиско­рейшего спуска соответствует направлению наибольшего убывания функ­ции. Из курса математики известно, что направление наибольшего возраста­ния функции двух переменных u = f(x,y) характеризуется ее градиентом

где e₁, e₂ — единичные векторы (орты) в направлении координатных осей. Следовательно, направление, противоположное градиентному, укажет на­правление наибольшего убывания функции. Методы, основанные на выбо­ре пути оптимизации с помощью градиента, называются градиентными. Идея метода градиентного спуска состоит в следующем. Выбираем неко­торую начальную точку , и вычисля­ем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному:

 

В результате приходим в точку M₁ (x⁽¹⁾), значение функции в которой обыч­но меньше первоначального (а⁽¹⁾ > 0). Если это условие не выполнено, т. е. значение функции не изменилось либо даже возросло, то нужно уменьшить шаг а⁽¹⁾ . В новой точке процедуру повторяем: вычисляем градиент и снова делаем шаг в обратном к нему направлении:

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

Метод градиентного спуска обладает тем же недостатком, что и метод покоординатного спуска: при наличии оврагов на поверхности сходимость метода очень медленная.

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

Формулы для частных производных можно получить в явном виде лишь в том случае, когда целевая функция задана аналитически. В противном случае эти производные вычисляются с помощью численного дифферен­цирования:

При использовании градиентного спуска в задачах оптимизации ос­новной объем вычислений приходится обычно на вычисление градиента целевой функции в каждой точке траектории спуска. Поэтому целесооб­разно уменьшить количество таких точек без ущерба для самого реше­ния. Это достигается в некоторых методах, являющихся модификациями градиентного спуска. Одним из них является метод наискорейшего спус­ка. Согласно этому методу, после определения в начальной точке направ­ления, противоположного градиенту целевой функции, решают одномер­ную задачу оптимизации, минимизируяфункцию вдоль этого направления. А именно, минимизируется функция

 

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

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

Проиллюстрируем метод наискорейшего спуска на рис. 6.8 для случая функции двух переменных z=f(x,y) и отметим некоторые его геомет­рические особенности.

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

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

Советуем читателю для лучшего понимания метода наискорейшего спуска составить алгоритм, аналогичный представленному на рис. 6.7 для метода покоординатного спуска.