Градиентные методы. Понятие градиента и его вычисление

Градиентный метод первого порядка

Градиентные методы оптимизации

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

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

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

Если критерий задан уравнением

то его градиент в точке (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, однако стоит остановиться на каждом из них еще раз...

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

Например, для функции при с проекциями градиентов методом наискорейшего спуска определен . Примем параметр постоянным на всех итерациях.

Вычисляем координаты х (1) :

Для вычисления координат точки х (2) находим проекции градиента в точке х (1) : , тогда

и т.д.

Данная последовательность также сходится.

Шаговый градиентный метод

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

Пусть дана сепарабельная функция и начальная точка . Зададимся постоянным шагом по координате х 1 , пусть Dх 1 =0,2. Шаг по координате х 2 находим из соотношения градиентов и шагов.

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

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

Рис. 4.11.

Рис. 4.12.

(двумерный случай)

Вначале выбирают начальную точку Если в одномерном случае (см. подпараграф 4.2.6) из нее можно было

сдвинуться только влево или вправо (см. рис. 4.9), то в многомерном случае число возможных направлений перемещения бесконечно велико. На рис. 4.11, иллюстрирующем случай двух переменных, стрелками, выходящими из начальной точки А, показаны различные возможные направления. При этом движение по некоторым из них дает увеличение значения целевой функции по отношению к точке А (например, направления 1-3), а по другим направлениям приводит к его уменьшению (направления 5-8). Учитывая, что положение точки оптимума неизвестно, считается наилучшим то направление, в котором целевая функция возрастает быстрее всего. Это направление называется градиентом функции. Отметим, что в каждой точке координатной плоскости направление градиента перпендикулярно касательной к линии уровня, проведенной через ту же точку.

В математическом анализе доказано, что составляющие вектора градиента функции у =/(*, х 2 , ..., х п) являются ее частными производными по аргументам, т.е.

&ад/(х 1 ,х 2 ,.= {ду/дху,ду/дх 2 , ...,ду/дх п }. (4.20)

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

У" с координатами:

1§гас1/(х (0)),

или в векторной форме

где X - постоянный или переменный параметр, определяющий длину рабочего шага, ?і>0. На второй итерации снова вычисляют

вектор градиента уже для новой точки.У, после чего по анало-

гичной формуле переходят в точку х^ > и т.д. (рис. 4.12). Для произвольной к- й итерации имеем

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

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

длина рабочего шага - расстояние между соседними точками х^

их 1 " - окажется пропорциональном модулю вектора градиента. Можно, наоборот, на каждой итерации выбирать X таким, чтобы длина рабочего шага оставалась постоянной.

Пример. Требуется найти максимум функции

у = 110-2(лг, -4) 2 -3(* 2 -5) 2 .

Разумеется, воспользовавшись необходимым условием экстремума, сразу получим искомое решение: х ] - 4; х 2 = 5. Однако на этом простом примере удобно продемонстрировать алгоритм градиентного метода. Вычислим градиент целевой функции:

grad у = {ду/дх-,ду/дх 2 } = {4(4 - *,); 6(5 - х 2)} и выбираем начальную точку

Л*» = {х}°> = 0; 4°> = О}.

Значение целевой функции для этой точки, как легко подсчитать, равно у[х^ j = 3. Положим, X = const = 0,1. Величина градиента в точке

Зс (0) равна grad y|x^j = {16; 30}. Тогда на первой итерации получим согласно формулам (4.21) координаты точки

х 1) = 0 + 0,1 16 = 1,6; х^ = 0 + 0,1 30 = 3.

у(х (1)) = 110 - 2(1,6 - 4) 2 - 3(3 - 5) 2 = 86,48.

Как видно, оно существенно больше предыдущего значения. На второй итерации имеем по формулам (4.22):

• 1,6 + 0,1 4(4 - 1,6) = 2,56;

Как мы уже отметили, задача оптимизации – это задача отыскания таких значений факторов х 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) значение шага (т ) при движении по градиенту выбирают таким образом, чтобы наибольшее из произведений не превышало разности верхнего и нижнего уровней факто­ров в нормированном виде

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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