Простейший градиентный метод. Градиентный спуск
Метод релаксации
Алгоритм метода заключается в отыскании осевого направления, вдоль которого целевая функция уменьшается наиболее сильно (при поиске минимума). Рассмотрим задачу безусловной оптимизации
Для определения осевого направления в начальной точке поиска из области определяются производные , , по всем независимым переменным. Осевому направлению соответствует наибольшая по модулю производная .
Пусть – осевое направление, т.е. 
.
Если знак производной отрицательный, функция убывает в направлении оси, если положительный – в обратном направлении:
В точке вычисляют . По направлению убывания функции производится один шаг, определяется и в случае улучшения критерия шаги продолжаются до тех пор, пока не будет найдено минимальное значение по выбранному направлению. В этой точке вновь определяются производные по всем переменным, за исключением тех, по которой осуществляется спуск. Снова находится осевое направление наиболее быстрого убывания , по которому производятся дальнейшие шаги и т.д.
Эту процедуру повторяют до тех пор, пока не достигается оптимальная точка, при движении из которой по любому осевому направлению дальнейшего убывания не происходит. На практике критерием окончания поиска служит условие
которое при превращается в точное условие равенства нулю производных в точке экстремума. Естественно условие (3.7) может быть использовано только в том случае, если оптимум лежит внутри допустимой области изменения независимых переменных . Если же оптимум попадает на границу области , критерий типа (3.7) непригоден и вместо него следует применять положительности всех производных по допустимым осевым направлениям.
Алгоритм спуска для выбранного осевого направления может быть записан так
(3.8)
где -значение варьируемой переменной на каждом шаге спуска;
Величина k+1 шага, которая может изменяться в зависимости от номера шага:
– функция знака z;
Вектор точки, в которой последний раз производилось вычисление производных ;
Знак “+” в алгоритме (3.8) принимается при поиске max I, а знак “-” – при поиске min I.Чем меньше шаг h., тем больше количество вычислений на пути движения к оптимуму. Но при слишком большой величине h вблизи оптимума может возникнуть зацикливание процесса поиска. Вблизи оптимума необходимо, чтобы выполнялось условие h Простейший алгоритм изменения шага h состоит в следующем. В начале спуска задается шаг , равный например, 10% от диапазона d; изменения с этим шагом производится спуск по выбранному направлению до тез пор, пока выполняется условие для двух последующих вычислений При нарушении условия на каком-либо шаге направление спуска на оси изменяется на обратное и спуск продолжается из последней точки с уменьшенной вдвое величиной шага. Формальная запись этого алгоритма следующая: В результате использования такой стратегии ша спуска будет уменьшатся в районе оптимума по данному направлению и поиск по направлению можно прекратить, когда станет меньше E. Затем отыскивается новое осевое направление начальный шаг для дальнейшего спуска, обычно меньший пройденного вдоль предыдущего осевого направления. Характер движения в оптимуме в данном методе показан на рисунке 3.4. Рисунок 3.5 – Траектория движения к оптимуму в методе релаксации Улучшение алгоритма поиска по данному методу может быть достигнуто путем применения методов однопараметрической оптимизации. При этом может быть предложена схема решения задачи: Шаг 1. – осевое направление, Шаг 2. – новое осевое направление; Метод градиента
В этом методе используется градиент функции . Градиентом функции в точке Рисунок 3.6 – Градиент функции Направление градиента – это направление наиболее быстрого возрастания функции (наиболее крутого “склона” поверхности отклика). Противоположное ему направление (направление антиградиента) – это направление наибыстрейшего убывания (направление наискорейшего “спуска” величин ). Проекция градиента на плоскость переменных перпендикулярна касательной к линии уровня , т.е. градиент ортогонален к линиям постоянного уровня целевой функции (рис. 3.6). Рисунок 3.7 – Траектория движения к оптимуму в методе градиента В отличие от метода релаксации в методе градиента шаги совершаются в направлении наибыстрейшего уменьшения (увеличения) функции . Поиск оптимума производится в два этапа. На первом этапе находятся значения частных производных по всем переменным , которые определяют направление градиента в рассматриваемой точке. На втором этапе осуществляется шаг в направлении градиента при поиске максимума или в противоположном направлении – при поиске минимума. Если аналитическое выражение неизвестно, то направление градиента определяется поиском на объекте пробных движений. Пусть начальная точка. Дается приращение величина , при этом . Определяют приращение и производную Аналогично определяют производные по остальным переменным. После нахождения составляющих градиента пробные движения прекращаются и начинаются рабочие шаги по выбранному направлению. Причем величина шага тем больше, чем больше абсолютная величина вектора . При выполнении шага одновременно изменяются значения всех независимых переменных. Каждая из них получает приращение, пропорциональное соответствующей составляющей градиента или в векторной форме где – положительная константа; “+” – при поиске max I; “-” – при поиске min I. Алгоритм градиентного поиска при нормировании градиента (деление на модуль) применяется в виде Определяет величину шага по направлению градиента. Алгоритм (3.10) обладает тем достоинством, что при приближении к оптимуму длина шага автоматически уменьшается. А при алгоритме (3.12) стратегию изменения можно строить независимо от абсолютной величины коэффициента. В методе градиента каждый разделяется один рабочий шаг, после которого вновь вычисляются производные, определяется новое направление градиента и процесс поиска продолжается (рис. 3.5). Если размер шага выбран слишком малым, то движение к оптимуму будет слишком долгим из-за необходимости вычисления в очень многих точках. Если же шаг выбран слишком большим, в район оптимума может возникнуть зацикливание. Процесс поиска продолжается до тех пор, пока , , не станут близки к нулю или пока не будет достигнута граница области задания переменных. В алгоритме с автоматическим уточнением шага величину уточняют так, чтобы изменение направления градиента в соседних точках и
Критерии окончания поиска оптимума: где Поиск завершается при выполнении одного из условий (3.14) – (3.17). Недостатком градиентного поиска (так же и рассмотренных выше методов) является то, что при его использовании можно обнаружить только локальный экстремум функции . Для отыскания других локальных экстремумов необходимо производить поиск из других начальных точек. Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту -grad(/(x)), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным. Если нет дополнительной информации, то из начальной точки х (0 > лучше перейти в точку х (1) , лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска антиградиент -grad(/(x (^)) в точке х (к
получим итерационный процесс вида В координатной форме этот процесс записывается следующим образом: В качестве критерия останова итерационного процесса можно использовать либо условие (10.2), либо выполнение условия малости градиента Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага а
В методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг а^
обеспечивает убывание функции, т.е. выполнение неравенства Однако это может привести к необходимости проводить достаточно большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать рост функции либо привести к колебаниям около точки минимума. Требуется дополнительная информация для выбора величины шага, поэтому методы с постоянным шагом применяются на практике редко. Более надежны и экономичны (в смысле количества итераций) градиентные методы с переменным шагом, когда в зависимости от полученного приближения величина шага некоторым образом меняется. В качестве примера такого метода рассмотрим метод наискорейшего спуска. В этом методе на каждой итерации величина шага я* выбирается из условия минимума функции /(х) в направлении спуска, т.е. Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции /(х) убывает. Поэтому на каждой итерации необходимо решать задачу одномерной минимизации по я функции ф(я) =/(х (/г) - - agrad^x^))). Алгоритм метода наискорейшего спуска состоит в следующем. В методе наискорейшего спуска направление движения из точки х (*) касается линии уровня в точке х (* +1) . Траектория спуска зигзагообразная, и соседние звенья зигзага ортогональны друг другу. Действительно, шаг а^
выбирается путем минимизации по а
функции (а
). Необходимое условие минимума функции - = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках: Задачу минимизации функции ф(я) можно свести к задаче вычисления корня функции одной переменной g(a) =
Градиентные методы сходятся к минимуму со скоростью геометрической прогрессии для гладких выпуклых функций. У таких функций наибольшее и наименьшее собственные значения матрицы вторых производных (матрицы Гессе) мало отличаются друг от друга, т.е. матрица Н(х) хорошо обусловлена. Однако на практике минимизируемые функции часто имеют плохо обусловленные матрицы вторых производных. Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее, чем в других направлениях. Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума, может вообще нарушить сходимость процесса градиентного спуска. Поэтому градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х (0) находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции. Наконец, параметр m можно задавать постоянным на всех итерациях. Однако при больших значениях m процесс поиска может расходиться. Хорошим способом выбора m может быть его определение на первой итерации из условия экстремума по направлению градиента. На последующих итерациях m остается постоянным. Это еще более упрощает вычисления. Например, для функции при Вычисляем координаты х (1) : Для вычисления координат точки х (2) находим проекции градиента в точке х (1) : , тогда Данная последовательность также сходится. Шаговый градиентный метод Пусть дана сепарабельная функция и начальная точка Градиентные методы оптимизации относятся к численным методам поискового типа. Они универсальны, хорошо приспособлены для работы с современными цифровыми вычислительными машинами и в большинстве случаев весьма эффективны при поиске экстремального значения нелинейных функций с ограничениями и без них, а также тогда, когда аналитический вид функции вообще неизвестен. Вследствие этого градиентные, или поисковые, методы широко применяются на практике. Сущность указанных методов заключается в определении значений независимых переменных, дающих наибольшие изменения целевой функции. Обычно для этого двигаются вдоль градиента, ортогонального к контурной поверхности в данной точке. Различные поисковые методы в основном отличаются один от другого способом определения направления движения к оптимуму, размером шага и продолжительностью поиска вдоль найденного направления, критериями окончания поиска, простотой алгоритмизации и применимостью для различных ЭВМ. Техника поиска экстремума основана на расчетах, которые позволяют определить направление наиболее быстрого изменения оптимизируемого критерия. Если критерий задан уравнением то его градиент в точке (x 1 , x 2 ,…, x n) определяется вектором: Частная производная пропорциональна косинусу угла, образуемого вектором градиента с i-й осью координат. При этом Наряду с определением направления градиентного вектора основным вопросом, решаемым при использовании градиентных методов, является выбор шага движения по градиенту. Величина шага в направлении gradF в значительной степени зависит от вида поверхности. Если шаг слишком мал, потребуются продолжительные расчеты; если слишком велик, можно проскочить оптимум. Размер шага должен удовлетворять условию, при котором все шаги от базисной точки лежат в том же самом направлении, что и градиент в базисной точке. Размеры шага по каждой переменной x i вычисляются из значений частных производных в базовой (начальной) точке: где К - константа, определяющая размеры шага и одинаковая для всех i-х направлений. Только в базовой точке градиент строго ортогонален к поверхности. Если же шаги слишком велики в каждом i-м направлении, вектор из базисной точки не будет ортогонален к поверхности в новой точке. Если выбор шага был удовлетворительным, производная в следующей точке существенно близка к производной в базисной точке. Для линейных функций градиентное направление не зависит от положения на поверхности, для которой оно вычисляется. Если поверхность имеет вид и компонента градиента в i-м направлении равна Для нелинейной функции направление градиентного вектора зависит от точки на поверхности, в которой он вычисляется. Несмотря на существующие различия между градиентными методами, последовательность операций при поиске оптимума в большинстве случаев одинакова и сводится к следующему: а) выбирается базисная точка; б) определяется направление движения от базисной точки; в) находится размер шага; г) определяется следующая точка поиска; д) значение целевой функции в данной точке сравнивается с ее значением в предыдущей точке; е) вновь определяется направление движения и процедура повторяется до достижения оптимального значения. Алгоритм и программа распознавания образов
Применимость градиентных алгоритмов к классификации образов основана на том, функция штрафа (целевая функция) выбирается таким образом, чтобы она достигала минимальное значение при выполнении условия... Анодирование алюминия как объект автоматизированного проектирования
Рассмотрим процесс анодирования алюминия AD1 в растворе серной кислоты с добавлением соли сульфата меди. Данные находятся в таблицах 1,2,3,4 соответственно при плотности электролита 1.2,1.23,1.26 и 1.29 кг/м3... Задачи нелинейного программирования
Метод расчета мехатронной системы привода телескопа на основе равновесно-оптимальной балансировки
Модели и методы конечномерной оптимизации
Оптимизация производства по выпуску продукции на предприятии Nature Republic
Чтобы получить более полную характеристику достоинств и недостатков проектируемого объекта, нужно ввести больше критериев качества в рассмотрение. Как результат, задачи проектирования сложных систем всегда многокритериальные... Задача поиска экстремума функции одной переменной возникает при оптимизации целевой функции, зависящей от одной скалярной переменной. Такие задачи входят составной частью во многие итерационные методы решения задач многомерной оптимизации... Основные методы решения задач нелинейного программирования
В настоящее время разработано огромное число методов многомерной оптимизации, охватывающие почти все возможные случаи. Здесь рассматривается лишь несколько основных, считающихся классическими... Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных
Ненулевой антиградиент - f(x0) указывает направление, небольшое перемещение вдоль которого из х0 приводит к значению функции f меньшему, чем f(x0). Это замечательное свойство лежит в основе градиентных методов... Профессиональная CAM-система трехмерного моделирования литейных процессов
Методы условной оптимизации
Вначале рассмотрим методы поиска min f (x1,…,xn) при условиях (2.1).
Постановка задачи: Найти вектор, доставляющий минимум функции f (x1,x2,…,xn) при условиях, j=1,2,…,m. Другими словами, см. рисунок 2.20, требуется найти точку... Психологическая интуиция искусственных нейронных сетей
Как было показано в предыдущем параграфе данной главы, решение основных задач восстановления зависимостей достигается при помощи процедуры оптимизации функционала качества... Разработка интернет ресурса для магазина "Военная одежда"
Создание веб-приложений с использованием современных ORM-фреймворков
В качестве средств оптимизации будут рассмотрены:
1) предварительная загрузка (fetch=FetchType.EAGER)
2) пакетная выборка
3) JPQL запросы с использованием JOIN FETCH
Все они рассматривались ранее в разд. 4, однако стоит остановиться на каждом из них еще раз... При оптимизации методом градиента оптимум исследуемого объекта ищут в направлении наиболее быстрого возрастания (убывания) выходной переменной, т.е. в направлении градиента. Но прежде чем сделать шаг в направлении градиента, необходимо его рассчитать. Градиент можно рассчитать либо по имеющейся модели моделирование динамический градиентный полиномиальный где - частная производная по i-му фактору; i, j, k - единичные векторы в направлении координатных осей факторного пространства, либо по результатам n пробных движений в направлении координатных осей. Если математическая модель статистического процесса имеет вид линейного полинома, коэффициенты регрессии b i которого являются частными производными разложения функции y = f(X) в ряд Тейлора по степеням x i , то оптимум ищут в направлении градиента с некоторым шагом h i: пкфв н(Ч)= и 1 р 1 +и 2 р 2 +…+и т р т Направление корректируют после каждого шага. Метод градиента вместе с его многочисленными модификациями является распространенным и эффективным методом поиска оптимума исследуемых объектов. Рассмотрим одну из модификаций метода градиента - метод крутого восхождения. Метод крутого восхождения, или иначе метод Бокса-Уилсона, объединяет в себе достоинства трех методов - метода Гаусса-Зейделя, метода градиентов и метода полного (или дробного) факторного экспериментов, как средства получения линейной математической модели. Задача метода крутого восхождения заключается в том, чтобы шаговое движение осуществлять в направлении наискорейшего возрастания (или убывания) выходной переменной, то есть по grad y(X). В отличии от метода градиентов, направление корректируется не после каждого следующего шага, а при достижении в некоторой точке на данном направлении частного экстремума целевой функции, как это делается в методе Гаусса-Зейделя. В точке частного экстремума ставится новый факторный эксперимент, определяется математическая модель и вновь осуществляется крутое восхождение. В процессе движения к оптимуму указанным методом регулярно проводиться статистический анализ промежуточных результатов поиска. Поиск прекращается, когда квадратичные эффекты в уравнении регрессии становятся значимыми. Это означает, что достигнута область оптимума. Опишем принцип использования градиентных методов на примере функции двух переменных при наличии двух дополнительных условий: Этот принцип (без изменения) можно применить при любом числе переменных, а также дополнительных условий. Рассмотрим плоскость x 1 , x 2 (Рис. 1). Согласно формуле (8) каждой точке соответствует некоторое значение F. На Рис.1 линии F = const, принадлежащие этой плоскости, представлены замкнутыми кривыми, окружающими точку M * , в которой F минимально. Пусть в начальный момент значения x 1 и x 2 соответствуют точке M 0 . Цикл расчета начинается с серии пробных шагов. Сначала величине x 1 дается небольшое приращение; в это время значение x 2 неизменно. Затем определяется полученное при этом приращение величины F, которое можно считать пропорциональным значению частной производной (если величина всегда одна и та же). Определение частных производных (10) и (11) означает, что найден вектор с координатами и, который называется градиентом величины F и обозначается так: Известно, что направление этого вектора совпадает с направлением наиболее крутого возрастания величины F. Противоположное ему направление - это «наискорейший спуск», другими словами, наиболее крутое убывание величины F. После нахождения составляющих градиента пробные движения прекращаются и осуществляются рабочие шаги в направлении, противоположном направлению градиента, причем величина шага тем больше, чем больше абсолютная величина вектора grad F. Эти условия осуществляются, если величины рабочих шагов и пропорциональны полученным ранее значениям частных производных: где б - положительная константа. После каждого рабочего шага оценивается приращение величины F. Если оно оказывается отрицательным, то движение происходит в правильном направлении и нужно двигаться в том же направлении M 0 M 1 дальше. Если же в точке M 1 результат измерения показывает, что, то рабочие движения прекращаются и начинается новая серия пробных движений. При этом определяется градиент gradF в новой точке M 1 , затем рабочее движение продолжается по новому найденному направлению наискорейшего спуска, т. е. по линии M 1 M 2 , и т.д. Этот метод называется методом наискорейшего спуска/крутого восхождения. Когда система находится вблизи минимума, показателем чего является малое значение величины происходит переключение на более «осторожный» метод поиска, так называемый метод градиента. От метода наискорейшего спуска он отличается тем, что после определения градиента gradF делается лишь один рабочий шаг, а затем в новой точке опять начинается серия пробных движений. Такой метод поиска обеспечивает более точное установление минимума по сравнению с методом наискорейшего спуска, между тем как последний позволяет быстрее приблизиться к минимуму. Если в процессе поиска точка М доходит до границы допустимой области и хотя бы одна из величин М 1 , М 2 меняет знак, метод меняется и точка М начинает двигаться вдоль границы области. Эффективность метода крутого восхождения зависит от выбора масштаба переменных и вида поверхности отклика. Поверхность со сферическими контурами обеспечивает быстрое стягивание к оптимуму. К недостаткам метода крутого восхождения следует отнести: 1. Ограниченность экстраполяции. Двигаясь вдоль градиента, мы основываемся на экстраполяции частных производных целевой функции по соответствующим переменным. Однако форма поверхности отклика может изменяться и необходимо изменять направление поиска. Другими словами, движение на плоскости не может быть продолжительным. 2. Трудность поиска глобального оптимума. Метод применим для отыскания только локальных оптимумов.
(3.9)
; , если ;
называется вектор, проекциями которого на координатные оси являются частные производные функции по координатам (рис. 6.5)
.
, (3.10)
, (3.11)
; (3.12)
(3.13)
; (3.16)
; (3.17)
– норма вектора.
с проекциями градиентов 
методом наискорейшего спуска определен . Примем параметр постоянным на всех итерациях.
и т.д.
Этот метод разработан инженерами и заключается в том, что шаг по одной из переменных берется постоянным, а для других переменных он выбирается исходя из пропорциональности градиентов точках. Этим как бы масштабируют экстремальную поверхность, т.к. не по всем переменным сходимость одинакова. Поэтому выбором различных шагов для координат пытаются сделать скорость сходимости примерно одинаковой по всем переменным. . Зададимся постоянным шагом по координате х 1 , пусть Dх 1 =0,2. Шаг по координате х 2 находим из соотношения градиентов и шагов.Градиентный метод первого порядка
Градиентные методы оптимизации
Загрузка...
