Рассмотрим задачу безусловной минимизации дифференцируемой функции многих переменных Пусть приближение к точке минимума значение градиента в точке Выше уже отмечалось, что в малой окрестности точки направление наискорейшего убывания функции задается антиградиентом Это свойство существенно используется в ряде методов минимизации. В рассматриваемом Ниже градиентном методе за направление спуска из точки непосредственно выбирается Таким образом, согласно градиентному методу

Существуют различные способы выбора шага каждый из которых задает определенный вариант градиентного метода.

1. Метод наискорейшего спуска.

Рассмотрим функцию одной скалярной переменной и выберем в качестве то значение, для которого выполняется равенство

Этот метод, предложенный в 1845 г. О. Коши, принято теперь называть методом наискорейшего спуска.

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

Отметим, что на каждой итерации выбор шага предполагает решение задачи одномерной минимизации (10.23). Иногда эту операцию удается выполнить аналитически, например для квадратичной функции.

Применим метод наискорейшего спуска для минимизации квадратичной функции

с симметричной положительно определенной матрицей А.

Согласно формуле (10.8), в этом случае Поэтому формула (10.22) выглядит здесь так:

Заметим, что

Эта функция является квадратичной функцией параметра а и достигает минимума при таком значении для которого

Таким образом, применительно к минимизации квадратичной

функции (10.24) метод наискорейшего спуска эквивалентен расчету по формуле (10.25), где

Замечание 1. Поскольку точка минимума функции (10.24) совпадает с решением системы метод наискорейшего спуска (10.25), (10.26) может применяться и как итерационный метод решения систем линейных алгебраических уравнений с симметричными положительно определенными матрицами.

Замечание 2. Отметим, что где отношение Рэлея (см. § 8.1).

Пример 10.1. Применим метод наискорейшего спуска для минимизации квадратичной функции

Заметим, что Поэтому точное значение точки минимума нам заранее известно. Запишем данную функцию в виде (10.24), где матрица и вектор Как нетрудно видеть,

Возьмем начальное приближение и будем вести вычисления по формулам (10.25), (10.26).

I итерация.

II итерация.

Можно показать, что для всех на итерации будут получены значения

Заметим, что при Таким образом,

последовательность полученная методом наискорейшего спуска, сходится со скоростью геометрической прогрессии, знаменатель которой

На рис. 10.5 изображена именно та траектория спуска, которая была получена в данном примере.

Для случая минимизации квадратичной функции справедлив следующий общий результат .

Теорема 10.1. Пусть А - симметричная положительно определенная матрица и минимизируется квадратичная функция (10.24). Тогда при любом выборе начальною приближения метод наискорейшею спуска (10.25), (10.26) сходится и верна следующая оценка погрешности:

Здесь и Ладо - минимальное и максимальное собственные значения матрицы А.

Отметим, что этот метод сходится со скоростью геометрической прогрессии, знаменатель которой причем если их близки, то мало и метод сходится достаточно быстро. Например, в примере 10.1 имеем и поэтому Если же Ащах, то и 1 и следует ожидать медленной сходимости метода наискорейшего спуска.

Пример 10.2. Применение метода наискорейшего спуска для минимизации квадратичной функции при начальном приближении дает последовательность приближений где Траектория спуска изображена на рис. 10.6.

Последовательность сходится здесь со скоростью геометрической прогрессии, знаменатель которой равен т. е. существенно медленнее,

чем в предыдущем примерю. Так как здесь и полученный результат вполне согласуется с оценкой (10.27).

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

Замечание 2. Для квадратичной целевой функции (10.24) решение задачи одномерной минимизации (10.23) удается найти в виде простой явной формулы (10.26). Однако для большинства других нелинейных функций этого сделать нельзя и для вычисления методом наискорейшего спуска приходится применять численные методы одномерной минимизации типа тех, которые были рассмотрены в предыдущей главе.

2. Проблема "оврагов".

Из проведенного выше обсуждения следует, что градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при линии уровня близки к окружностям). Для таких функций и 1. Теорема 10.1, замечание 1, а также результат примера 10.2 указывают на то, что скорость сходимости резко падает при увеличении величины Действительно, известно, что градиентный метод сходится очень медленно, если поверхности уровня минимизируемой функции сильно вытянуты в некоторых направлениях. В двумерном случае рельеф соответствующей поверхности напоминает рельеф местности с оврагом (рис. 10.7). Поэтому такие функции принято называть овражными. Вдоль направлений, характеризующих "дно оврага", овражная функция меняется незначительно, а в других направлениях, характеризующих "склон оврага", происходит резкое изменение функции.

Если начальная точка попадает на "склон оврага", то направление градиентного спуска оказывается почти перпендикулярным "дну оврага" и очередное приближение попадает на противоположный "склон оврага". Следующий шаг в направлении ко "дну оврага" возвращает приближение на первоначальный "склон оврага". В результате вместо того чтобы двигаться вдоль "дна оврага" в направлении к точке минимума, траектория спуска совершает зигзагообразные скачки поперек "оврага", почти не приближаясь к цели (рис. 10.7).

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

Более подробную информацию о проблеме "оврагов" и "овражных" методах можно найти, например, в , .

3. Другие подходы к определению шага спуска.

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

Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.

Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .

Описание [ | ]

Усовершенствования [ | ]

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

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

Применение в искусственных нейронных сетях [ | ]

Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском или оперативным градиентным спуском . Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска.

Ссылки [ | ]

  • J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)

Литература [ | ]

  • Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
  • Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
  • Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
  • Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
  • Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
  • С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.

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

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

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

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

вычисляем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному:

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

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

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

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

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

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

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

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

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 1 = х 1* , х 2 = х 2* , …, х k = х k * , при которых функция отклика (у ) достигает экстремального значения у = ext (оптимума).

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

Рассмотрим сущность метода градиента на примере двухфакторной функции отклика y = f(x 1 , х 2 ). На рис. 4.3 в фак­торном пространстве изо­бражены кривые равных значений функции отклика (кривые уровня). Точке с координатами х 1 *, х 2 * соответствует экстремаль­ное значение функции от­клика у ext .

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

Градиент непрерывной однозначной функции y = f (x 1 , х 2) – это вектор, определяемый по направлению градиентом с координатами:

где i, j – единичные векторы в направлении осей координат х 1 и х 2 . Частные производные и характеризуют направление вектора.

Поскольку нам неизвестен вид зависимости y = f (x 1 , х 2), мы не можем найти частные производные , и опреде­лить истинное направление градиента.

Согласно методу градиента в какой-то части факторного пространства выбирается исходная точка (исходные уровни) х 1 0 , х 2 0 . Относительно этих исходных уровней строится сим­метричный двухуровневый план эксперимента. Причем интер­вал варьирования выбирается настолько малым, чтобы ли­нейная модель оказалась адекватной. Известно, что любая кривая на достаточно малом участке может быть аппрокси­мирована линейной моделью.

После построения симметричного двухуровневого плана решается интерполяционная задача, т.е. строится линейная модель:

и проверяется ее адекватность.

Если для выбранного интервала варьирования линейная мо­дель оказалась адекватной, то может быть определено на­правление градиента:

Таким образом, направление градиента функции отклика определяется значениями коэффициентов регрессии. Это означает, что мы будем двигаться в направлении градиента, если из точки с координатами ( ) перейдем в точку с координатами:

где m – положительное число, определяющее величину шага в на­правлении градиента.

Поскольку х 1 0 = 0 и х 2 0 = 0, то .

Определив направление градиента () и выбрав ве­личину шага m , осуществляем опыт на исходном уровне х 1 0 , х 2 0 .


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

Движение по градиенту продолжаем до тех пор, пока функция отклика не начнет уменьшаться. На рис. 4.3 движение по градиенту соответствует прямой, вы­ходящей из точки (х 1 0 , х 2 0). Она постепенно отклоняется от истинного направления градиента, показанного штриховой линией, вследствие нелинейности функции отклика.

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

Построив новую линейную модель , осуществляют регрессионный анализ. Если при этом провер­ка значимости факторов показывает, что хоть один коэф

фи­циент , значит, область экстремума функции откли­ка (область оптимума) еще не достигнута. Определяется новое направление градиента и начинается движение к обла­сти оптимума.

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

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

1) исходные уровни факторов (х j 0) следует выбирать воз­можно ближе к точке оптимума, если есть какая-то априор­ная информация о ее положении;

2) интервалы варьирования (Δх j ) надо выбирать такими, чтобы линейная модель наверняка оказалась адекватной. Границей снизу Δх j при этом является минимальное значе­ние интервала варьирования, при котором функция отклика остается значимой;

3) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факто­ров в нормированном виде

.

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

Метод Гаусса-Зейделя

Метод заключается в поочерёдном нахождении частных экстремумов целевой функции по каждому фактору. При этом на каждом этапе стабилизируют (k-1) факторов и варьируют только один i-ый фактор

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

Этот способ наиболее прост, нагляден, но движение к оптимуму длительно и метод редко приводит в оптимальную точку. В настоящее время он иногда применяется при машинном эксперименте.

Эти методы обеспечивают движение к оптимуму по прямой перпендикулярной к линиям равного отклика, т. е. в направлении градиента функции отклика.

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

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

Метод градиента (обычный) осуществляется по следующей схеме:

а) выбирают базовую точку;

б) выбирают шаги движения по каждому фактору;

в) определяют координаты пробных точек;

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

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


где H i -шаг движения по X i .

X i – координаты предыдущей рабочей точки.

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

Достоинства метода: простота, более высокая скорость движения к оптимуму.

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

а) Метод крутого восхождения (Бокса - Уилсона).

б) Принятие решений после крутого восхождения.

в) Симплексный метод оптимизации.

г) Достоинства и недостатки методов.

5.7.3 Метод крутого восхождения (Бокса- Уилсона)

Этот метод является синтезом лучших черт градиентных методов, метода Гаусса-Зейделя и методов ПФЭ и ДФЭ – как средства получения математической модели процесса. Решение задачи оптимизации данным методом выполняется так, чтобы шаговое движение осуществлялось в направлении наискорейшего возрастания (убывания) параметра оптимизации. Корректировка направления движения (в отличие от градиентных методов) производится не после каждого шага, а по достижению частного экстремума целевой функции. Далее в точках частного экстремума ставится новый факторный эксперимент, составляется новая математическая модель и вновь повторяется крутое восхождение до достижения глобального оптимума. Движение по градиенту начинают из нулевой точки(центра плана).

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

Где i,j,k-единичные векторы в направлении соответствующих координатных осей.

Порядок расчёта .

Исходными данными является математическая модель процесса, полученная любым способом (ПФЭ, ДФЭ и т.д.).

Расчеты проводят в следующем порядке:

а) уравнение регрессии лучше перевести в натуральный вид по формулам кодирования переменных:

где x i -кодированное значение переменной x i ;

X i - натуральное значение переменной x i ;

X i Ц -центральный уровень фактора в натуральном виде;

l i -интервал варьирования фактора x i в натуральном виде.

б) вычисляют шаги движения к оптимуму по каждому фактору.

Для этого вычисляют произведения коэффициентов уравнения регрессии в натуральном виде на соответствующие интервалы варьирования

B i *.l I ,

Затем выбирают из полученных произведений максимальное по модулю,а соответствующий этому произведению фактор принимают за базовый фактор(B a l a). Для базового фактора следует установить шаг движения, который рекомендуется задавать меньшим или равным интервалу варьирования базового фактоpa


Знак шага движения l a ’ должен совпадать со знаком коэффициента уравнения регрессии, соответствующего базовому фактору (B a). Величина шагов для других факторов вычисляется пропорционально базовому по формуле:

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

в) вычисляют функцию отклика в центре плана, т. е. при значениях факторов равных центральному уровню факторов, т. к. движение к оптимуму начинают из центра плана.

Далее производят вычисление параметра оптимизации, увеличивая значения факторов на величину соответствующего шага движения, если хотят получить Y max . В противном случае, если необходимо получить Y min , значения факторов уменьшают на величину шага движения.

Процедуру повторяют, последовательно увеличивая количество шагов до тех пор, пока не достигнут желаемого значения параметра оптимизации (Y). Каждый из факторов после g шагов будет иметь значение:

Если Y® max X i =X i ц +gl i ` ’

если Y® min .X i =X i ц -gl i ` . (5.36)