Градиентный спуск. Обзор градиентных методов в задачах математической оптимизации
Градиентный метод и его разновидности относятся к самым распространенным методам поиска экстремума функций нескольких переменных. Идея градиентного метода заключается в том, чтобы в процессе поиска экстремума (для определенности максимума) двигаться каждый раз в направлении наибольшего возрастания целевой функции.
Градиентный метод предполагает вычисление первых производных целевой функции по ее аргументам. Он, как и предыдущие, относится к приближенным методам и позволяет, как правило, не достигнуть точки оптимума, а только приблизиться к ней за конечное число шагов.
Рис. 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;
Вкину немного своего экспириенса:)
Метод покоординатного спуска
Идея данного метода в том, что поиск происходит в направлении покоординатного спуска во время новой итерации. Спуск осуществляется постепенно по каждой координате. Количество координат напрямую зависит от количества переменных.
Для демонстрации хода работы данного метода, для начала необходимо взять функцию z = f(x1, x2,…, xn) и выбрать любую точку M0(x10, x20,…, xn0) в n пространстве, которая зависит от числа характеристик функции. Следующим шагом идет фиксация всех точек функции в константу, кроме самой первой. Это делается для того, чтобы поиск многомерной оптимизации свести к решению поиска на определенном отрезке задачу одномерной оптимизации, то есть поиска аргумента x1.
Для нахождения значения данной переменной, необходимо производить спуск по этой координате до новой точки M1(x11, x21,…, xn1). Далее функция дифференцируется и тогда мы можем найти значение новой следующий точки с помощью данного выражения:
После нахождения значения переменной, необходимо повторить итерацию с фиксацией всех аргументов кроме x2 и начать производить спуск по новой координате до следующей новой точке M2(x11,x21,x30…,xn0). Теперь значение новой точки будет происходить по выражению:
И снова итерация с фиксацией будет повторяться до тех пор, пока все аргументы от xi до xn не закончатся. При последней итерации, мы последовательно пройдем по всем возможным координатам, в которых уже найдем локальные минимумы, поэтому целевая функция на последний координате дойдет до глобального минимума. Одним из преимуществ данного метода в том, что в любой момент времени есть возможность прервать спуск и последняя найденная точка будет являться точкой минимума. Это бывает полезно, когда метод уходит в бесконечный цикл и результатом этого поиска можно считать последнюю найденную координату. Однако, целевая установка поиска глобального минимума в области может быть так и не достигнута из-за того, что мы прервали поиск минимума (см. Рисунок 1).
Рисунок 1 – Отмена выполнения покоординатного спуска
Исследование данного метода показали, что каждая найденная вычисляемая точка в пространстве является точкой глобального минимума заданной функции, а функция z = f(x1, x2,…, xn) является выпуклой и дифференцируемой.
Отсюда можно сделать вывод, что функция z = f(x1, x2,…, xn) выпукла и дифференцируема в пространстве, а каждая найденная предельная точка в последовательности M0(x10, x20,…, xn0) будет являться точкой глобального минимума (см. Рисунок 2) данной функции по методу покоординатного спуска.
Рисунок 2 – Локальные точки минимума на оси координат
Можно сделать вывод о том, что данный алгоритм отлично справляется с простыми задачами многомерной оптимизации, путём последовательно решения n количества задач одномерной оптимизации, например, методом золотого сечения.
Ход выполнения метода покоординатного спуска происходит по алгоритму описанного в блок схеме (см. Рисунок 3). Итерации выполнения данного метода:
Изначально необходимо ввести несколько параметров: точность Эпсилон, которая должна быть строго положительной, стартовая точка x1 с которой мы начнем выполнение нашего алгоритма и установить Лямбда j;
Следующим шагом будет взять первую стартовую точку x1, после чего происходит решение обычного одномерного уравнения с одной переменной и формула для нахождения минимума будет, где k = 1, j=1:
Теперь после вычисления точки экстремума, необходимо проверить количество аргументов в функции и если j будет меньше n, тогда необходимо повторить предыдущий шаг и переопределить аргумент j = j + 1. При всех иных случаях, переходим к следующему шагу.
Теперь необходимо переопределить переменную x по формуле x (k + 1) = y (n + 1) и попытаться выполнить сходимость функции в заданной точности по выражению:
Теперь от данного выражения зависит нахождение точки экстремума. Если данное выражение истинно, тогда вычисление точки экстремума сводится к x*= xk + 1. Но часто необходимо выполнить дополнительные итерации, зависящие от точности, поэтому значения аргументов будет переопределено y(1) = x(k + 1), а значения индексов j =1, k = k + 1.
Рисунок 3 – Блок схема метода покоординатного спуска
Итого, у нас имеется отличный и многофункциональный алгоритм многомерной оптимизации, который способен разбивать сложную задачу, на несколько последовательно итерационных одномерных. Да, данный метод достаточно прост в реализации и имеет легкое определение точек в пространстве, потому что данной метод гарантирует сходимость к локальной точке минимума. Но даже при таких весомых достоинствах, метод способен уходить в бесконечные циклы из-за того, что может попасть в своего рода овраг.
Существуют овражные функции, в которых существуют впадины. Алгоритм, попав в одну из таких впадин, уже не может выбраться и точку минимума он обнаружит уже там. Так же большое число последовательных использований одного и того же метода одномерной оптимизации, может сильно отразиться на слабых вычислительных машинах. Мало того, что сходимость в данной функции очень медленная, поскольку необходимо вычислить все переменные и зачастую высокая заданная точность увеличивает в разы время решения задачи, так и главным недостатком данного алгоритма – ограниченная применимость.
Проводя исследование различных алгоритмов решения задач оптимизации, нельзя не отметить, что огромную роль играет качество данных алгоритмов. Так же не стоит забывать таких важных характеристик, как время и стабильность выполнения, способность находить наилучшие значения, минимизирующие или максимизирующие целевую функцию, простота реализации решения практических задач. Метод покоординатного спуска прост в использовании, но в задачах многомерной оптимизации, чаще всего, необходимо выполнять комплексные вычисления, а не разбиение целой задачи на подзадачи.
Метод Нелдера - Мида
Стоит отметить известность данного алгоритма среди исследователей методов многомерной оптимизации. Метод Нелдера – Мида один из немногих методов, который основанный на концепции последовательной трансформации деформируемого симплекса вокруг точки экстремума и не используют алгоритм движения в сторону глобального минимума.
Данный симплекс является регулярным, а представляется как многогранник с равностоящими вершинами симплекса в N-мерном пространстве. В различных пространствах, симплекс отображается в R2-равносторонний треугольник, а в R3 - правильный тетраэдр.
Как упоминалось выше, алгоритм является развитием метода симплексов Спендли, Хекста и Химсворта, но, в отличие от последнего, допускает использование неправильных симплексов. Чаще всего, под симплексом подразумевается выпуклый многогранник с числом вершин N+1, где N – количество параметров модели в n -мерном пространстве.
Для того, чтобы начать пользоваться данным методом, необходимо определиться с базовой вершиной всех имеющихся множества координат с помощью выражения:
Самым замечательным в этом методе то, что у симплекса существуют возможности самостоятельно выполнять определенные функции:
Отражение через центр тяжести, отражение со сжатием или растяжением;
Растяжение;
Сжатие.
Преимуществу среди этих свойств отдают отражению, поскольку данный параметр является наиболее опционально – функциональным. От любой выбранной вершины возможно сделать отражение относительно центра тяжести симплекса по выражению:.
Где xc - центр тяжести (см. Рисунок 1).
Рисунок 1 – Отражение через центр тяжести
Следующим шагом необходимо провести расчет аргументов целевой функции во всех вершинах отраженного симплекса. После этого, мы получим полную информацию о том, как симплекс будет вести себя в пространстве, а значит и информацию о поведении функции.
Для того чтобы совершить поиск точки минимума или максимума целевой функции с помощью методов использующих симплексы, необходимо придерживаться следующей последовательности:
На каждом шаге строиться симплекс, в каждой точке которого, необходимо произвести расчет всех его вершин, после чего отсортировать полученные результаты по возрастанию;
Следующий шаг – это отражение. Необходимо провести попытку получить значения нового симплекса, а путём отражения, у нас получиться избавиться от нежелательных значений, которые стараются двигать симплекс не в сторону глобального минимума;
Чтобы получить значения нового симплекса, из полученных отсортированных результатов, мы берем две вершины с наихудшими значениями. Возможны такие случаи, что сразу подобрать подходящие значения не удастся, тогда придется вернуться к первому шагу и произвести сжатие симплекса к точке с самым наименьшим значением;
Окончанием поиска точки экстремума является центр тяжести, при условии, что значение разности между функциями имеет наименьшие значения в точках симплекса.
Алгоритм Нелдера – Мида так же использует эти функции работы с симплексом по следующим формулам:
Функция отражения через центр тяжести симплекса высчитывается по следующему выражению:
Данное отражение выполняется строго в сторону точки экстремума и только через центр тяжести (см. Рисунок 2).
Рисунок 2 – Отражение симплекса происходит через центр тяжести
Функция сжатия вовнутрь симплекса высчитывается по следующему выражению:
Для того, чтобы провести сжатие, необходимо определить точку с наименьшим значением (см. Рисунок 3).
Рисунок 3 – Сжатие симплекса происходит к наименьшему аргументу.
Функция отражения со сжатием симплекса высчитывается по следующему выражению:
Для того, чтобы провести отражение со сжатием (см. Рисунок 4), необходимо помнить работу двух отдельных функций – это отражение через центр тяжести и сжатие симплекса к наименьшему значению.
Рисунок 4 - Отражение со сжатие
Функция отражения с растяжением симплекса (см. Рисунок 5) происходит с использованием двух функций – это отражение через центр тяжести и растяжение через наибольшее значение.
Рисунок 5 - Отражение с растяжением.
Чтобы продемонстрировать работу метода Нелдера – Мида, необходимо обратиться к блок схеме алгоритма (см. Рисунок 6).
Первостепенно, как и в предыдущих примерах, нужно задать параметр искаженности ε, которая должна быть строго больше нуля, а также задать необходмые параметры для вычисления α, β и a. Это нужно будет для вычисления функции f(x0), а также для построения самого симплекса.
Рисунок 6 - Первая часть метода Нелдера - Мида.
После построения симплекса необходимо произвести расчет всех значений целевой функции. Как и было описано выше про поиск экстремума с помощью симплекса, необходимо рассчитать функцию симплекса f(x) во всех его точках. Далее производим сортировку, где базовая точка будет находиться:
Теперь, когда базовая точка рассчитана, а также и все остальные отсортированы в списке, мы производим проверку условия достижимости по ранее заданной нами точности:
Как только данное условие станет истинным, тогда точка x(0) симплекса будет считаться искомой точкой экстремума. В другом случае, мы переходим на следующий шаг, где нужно определить новое значение центра тяжести по формуле:
Если данное условие выполняется, тогда точка x(0) будет являться точкой минимума, в противном случае, необходимо перейти на следующий шаг в котором необходимо произвести поиск наименьшего аргумента функции:
Из функции необходимо достать самую минимальное значение аргумента для того, что перейти к следующему шагу выполнения алгоритма. Иногда случается проблема того, что несколько аргументов сразу имеют одинаковое значение, вычисляемое из функции. Решением такой проблемы может стать повторное определение значения аргумента вплоть до десятитысячных.
После повторного вычисления минимального аргумента, необходимо заново сохранить новые полученные значения на n позициях аргументов.
Рисунок 7 - Вторая часть метода Нелдера - Мида.
Вычисленное из предыдущей функции значение необходимо подставить в условие fmin < f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
Исследования данного алгоритма показывают, что методы с нерегулярными симплексами (см. Рисунок 8) еще достаточно слабо изучены, но это не мешает им отлично справляться с поставленными задачами.
Более глубокие тесты показывают, что экспериментальным образом можно подобрать наиболее подходящие для задачи параметры функций растяжения, сжатия и отражения, но можно пользоваться общепринятыми параметрами этих функций α = 1/2, β = 2, γ = 2 или α = 1/4, β = 5/2, γ = 2. Поэтому, перед тем как отбрасывать данный метод для решения поставленной задачи, необходимо понимать, что для каждого нового поиска безусловного экстремума, нужно пристально наблюдать за поведением симплекса во время его работы и отмечать нестандартные решения метода.
Рисунок 8 - Процесс нахождения минимума.
Статистика показала, что в работе данного алгоритма существует одна из наиболее распространенных проблем – это вырождение деформируемого симплекса. Это происходит, когда каждый раз, когда несколько вершин симплекса попадают в одно пространство, размерность которого не удовлетворяет поставленной задачи.
Таким образом, размерность во время работы и заданная размерность закидывают несколько вершин симплекса в одну прямую, запуская метод в бесконечный цикл. Алгоритм в данной модификации еще не оснащен способом выйти из такого положения и сместить одну вершину в сторону, поэтому приходится создать новый симплекс с новыми параметрами, чтобы такого в дальнейшем не происходило.
Еще одной особенностью обладает данный метод – это некорректной работой при шести и более вершинах симплекса. Однако, при модификации данного метода, можно избавиться от этой проблемы и даже не потерять при этом скорости выполнения, но значение выделяемой памяти заметно повысится. Данный метод можно считать циклическим, поскольку он полностью основан на циклах, поэтому и замечается некорректная работа при большом количестве вершин.
Алгоритм Нелдера – Мида по праву можно считать одним из наилучших методов нахождения точки экстремума с помощью симплекса и отлично подходит для использования его в различные рода инженерных и экономических задачах. Даже не смотря на цикличность, количество памяти он использует очень малое количество, по сравнение с тем же методом покоординатного спуска, а для нахождения самого экстремума требуется высчитывать только значения центра тяжести и функции. Небольшое, но достаточное, количество комплексных параметров дают этому методу широкое использование в сложных математических и актуальных производственных задачах.
Симплексные алгоритмы – это край, горизонты которого еще мы не скоро раскроем, но уже сейчас они значительно упрощают нашу жизнь своей визуальной составляющей.
P.S. Текст полностью мой. Надеюсь кому-нибудь данная информация будет полезной.
Лекция № 8
Градиентные методы решения задач нелинейного программирования. Методы штрафных функций. Приложения нелинейного программирования к задачам исследования операций.
Задачи без ограничений. Градиентным методом можно решать, вообще говоря, любую нелинейную задачу. Однако при этом находится лишь локальный экстремум. Поэтому целесообразнее применять этот метод при решении задач выпуклого программирования, в которых любой локальный экстремум, является одновременно и глобальным (см. теорему 7.6).
Будем рассматривать задачу максимизации нелинейной дифференцируемой функции f (x ). Суть градиентного поиска точки максимума х * весьма проста: надо взять произвольную точку х 0 и с помощью градиента , вычисленного в этой точке, определить направление, в котором f (х ) возрастает с наибольшей скоростью (рис. 7.4),
а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x i . Потом снова определить наилучшее направление для перехода в очередную точку х 2 и т. д. На рис. 7.4 поисковая траектория представляет собой ломаную х 0 , x 1 , х 2 ... Таким образом, надо построить последовательность точек х 0 , x 1 , х 2 ,...,x k , ... так, чтобы она сходилась к точке максимума х *, т. е. для точек последовательности выполнялись условия
Градиентные методы, как правило, позволяют получать точное решение за бесконечное число шагов и только в некоторых случаях - за конечное. В связи с этим градиентные методы относят к приближенным методам решения.
Движение из точки х k в новую точку x k+1 осуществляется по прямой, проходящей через точку х k и имеющей уравнение
(7.29)
где λ k - числовой параметр, от которого зависит величина шага. Как только значение параметра в уравнении (7.29) выбрано: λ k =λ k 0 , так становится определенной очередная точка на поисковой ломаной.
Градиентные методы отличаются друг от друга способом выбора величины шага - значения λ k 0 параметра λ k . Можно, например, двигаться из точки в точку с постоянным шагом λ k = λ, т. е. при любом k
Если при этом окажется, что 
, то следует возвратиться в точку и уменьшить значение параметра, например до λ
/2.
Иногда величина шага берется пропорциональной модулю градиента.
Если ищется приближенное решение, то поиск можно прекратить, основываясь на следующих соображениях. После каждой серии из определенного числа шагов сравнивают достигнутые значения целевой функции f (x ). Если после очередной серии изменение f (x ) не превышает некоторого наперед заданного малого числа , поиск прекращают и достигнутое значение f (x ) рассматривают как искомый приближенный максимум, а соответствующее ему х принимают за х *.
Если целевая функция f (x ) вогнутая (выпуклая), то необходимым и достаточным условием оптимальности точки х * является равенство нулю градиента функции в этой точке.
Распространенным является вариант градиентного поиска, называемый методом наискорейшего подъема. Суть его в следующем. После определения градиента в точке х к
движение вдоль прямой 
производится до точки х к+
1 , в которой достигается максимальное значение функции f
(х
) в направлении градиента . Затем в этой точке вновь определяется градиент, и движение совершается по прямой в направлении нового градиента до точки х к+
2 , в которой достигается максимальное в этом направлении значение f
(x
). Движение продолжается до тех пор, пока не будет достигнута точка х
*, соответствующая наибольшему значению целевой функции f
(x
). На рис. 7.5 приведена схема движения к оптимальной точке х
* методом наискорейшего подъема. В данном случае направление градиента в точке х k
является касательным к линии уровня поверхности f
(х
) в точке х к+
1 , следовательно, градиент в точкех к+
1 ортогонален градиенту (сравните с рис. 7.4).
Перемещение из точки х k в точку сопровождается возрастанием функции f (x ) на величину
Из выражения (7.30) видно, что приращение является функцией переменной , т. е. . При нахождении максимума функции f (x) в направлении градиента ) необходимо выбирать шаг перемещения (множитель ), обеспечивающий наибольшее возрастание приращению функции, именно функции . Величина , при которой достигается наибольшее значение , может быть определена из необходимого условия экстремума функции :
(7.31)
Найдем выражение для производной, дифференцируя равенство (7.30) по как сложную функцию:
Подставляя этот результат в равенство (7.31), получаем
Это равенство имеет простое геометрическое истолкование: градиент в очередной точке х к+ 1 , ортогонален градиенту в предыдущей точке х к .
построены линии уровня этой поверхности. С этой целью уравнение приведено к виду (x 1 -1) 2 +(x 2 -2) 2 =5-0,5f , из которого ясно, что линиями пересечения параболоида с плоскостями, параллельными плоскости x 1 Оx 2 (линиями уровня), являются окружности радиусом . При f =-150, -100, -50 их радиусы равны соответственно
, а общий центр находится в точке (1; 2). Находим градиент данной функции:
I шаг . Вычисляем:
На рис. 7.6 с началом в точке х 0 =(5; 10) построен вектор 1/16, указывающий направление наискорейшего возрастания функции в точке х 0 . На этом направлении расположена следующая точка . В этой точке .
Используя условие (7.32), получаем
или 1-4=0, откуда =1/4. Так как , то найденное значение является точкой максимума . Находим x 1 =(5-16/4; 10-32/4)=(1; 2).
II шаг . Начальная точка для второго шага x 1 =(1; 2). Вычисляем =(-4∙1 +4; -4∙2+8)=(0; 0). Следовательно, х 1 =(1; 2) является стационарной точкой. Но поскольку данная функция вогнутая, то в найденной точке (1; 2) достигается глобальный максимум.
Задача с линейными ограничениями. Сразу же отметим, что если целевая функция f (х ) в задаче с ограничениями имеет единственный экстремум и он находится внутри допустимой области, то для поиска экстремальной точки х * применяется изложенная выше методика без каких-либо изменений.
Рассмотрим задачу выпуклого программирования с линейными ограничениями:
(7.34)
Предполагается, что f (х ) является вогнутой функцией и имеет непрерывные частные производные в каждой точке допустимой области.
Начнем с геометрической иллюстрации процесса решения задачи (рис. 7.7). Пусть начальная точка х
0 расположена внутри допустимой области. Из точки х
0 можно двигаться в направлении градиента , пока f
(x
) не достигнет максимума. В нашем случае f
(x
) все время возрастает, поэтому остановиться надо в точке х
, на граничной прямой. Как видно из рисунка, дальше двигаться в направлении градиента нельзя, так как выйдем из допустимой области. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выводит из допустимой области, а с другой - обеспечивает наибольшее возрастание f
(x
). Такое направление определит вектор , составляющий с вектором наименьший острый угол по сравнению с любым другим вектором, выходящим из точки x i
и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения 
. В данном случае вектор указывающий наивыгоднейшее направление, совпадает с граничной прямой.
 |
Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает f (x ); в нашем случае - до точки х 2 . Из рисунка видно, что далее следует перемещаться в направлении вектора , который находится из условия максимизации скалярного произведения
, т. е. по граничной прямой. Движение заканчивается в точке х
3 , поскольку в этой точке завершается оптимизационный поиск, ибо в ней функция f
(х
) имеет локальный максимум. Ввиду вогнутости в этой точке f
(х
) достигает также глобального максимума в допустимой области. Градиент в точке максимума х
3 =х
* составляет тупой угол с любым вектором из допустимой области, проходящим через х 3
, поэтому скалярное произведение будет отрицательным для любого допустимого r k
, кроме r
3 , направленного по граничной прямой. Для него скалярное произведение =0, так как и взаимно перпендикулярны (граничная прямая касается линии уровня поверхности f
(х
), проходящей через точку максимума х
*). Это равенство и служит аналитическим признаком того, что в точке х
3 функция f
(x
) достигла максимума.
Рассмотрим теперь аналитическое решение задачи (7.33) - (7.35). Если оптимизационный поиск начинается с точки, лежащей в допустимой области (все ограничения задачи выполняются как строгие неравенства), то перемещаться следует по направлению градиента так, как установлено выше. Однако теперь выбор λ k в уравнении (7.29) усложняется требованием, чтобы очередная точка оставалась в допустимой области. Это означает, что ее координаты должны удовлетворять ограничениям (7.34), (7.35), т. е. должны выполняться неравенства:
(7.36)
Решая систему линейных неравенств (7.36), находим отрезок допустимых значений параметра λ k , при которых точка х k +1 будет принадлежать допустимой области.
Значение λ k * , определяемое в результате решения уравнения (7.32):
При котором f (x ) имеет локальный максимум по λ k в направлении, должно принадлежать отрезку . Если же найденное значение λ k выходит за пределы указанного отрезка, то в качестве λ k * принимается . В этом случае очередная точка поисковой траектории оказывается на граничной гиперплоскости, соответствующей тому неравенству системы (7.36), по которому при решении системы получена правая конечная точка . отрезка допустимых значений параметра λ k .
Если оптимизационный поиск начат с точки, лежащей на граничной гиперплоскости, или очередная точка поисковой траектории оказалась на граничной гиперплоскости, то для продолжения движения к точке максимума прежде всего необходимо найти наилучшее направление движения С этой целью следует решить вспомогательную задачу математического программирования, а именно- максимизировать функцию
при ограничениях
для тех t , при которых
где 
.
В результате решения задачи (7.37) - (7.40) будет найден вектор , составляющий с градиентом наименьший острый угол.
Условие (7.39) говорит о том, что точка принадлежит границе допустимой области, а условие (7.38) означает, что перемещение из по вектору будет направлено внутрь допустимой области или по ее границе. Условие нормализации (7.40) необходимо для ограничения величины , так как в противном случае значение целевой функции (7.37) можно сделать сколь угодно большим Известны различные формы условий нормализации, и в зависимости от этого задача (7.37) - (7.40) может быть линейной или нелинейной.
После определения направления находится значение λ k *
для следующей точки 
поисковой траектории. При этом используется необходимое условие экстремума в форме, аналогичной уравнению (7.32), но с заменой на вектор , т. е.
(7.41)
Оптимизационный поиск прекращается, когда достигнута точка x k *
, в которой 
.
Пример 7.5. Максимизировать функцию при ограничениях
Решение. Для наглядного представления процесса оптимизации будем сопровождать его графической иллюстрацией. На рис 7.8 изображено несколько линий уровня данной поверхности и допустимая область ОАВС, в которой следует найти точку х *, доставляющую максимум данной функции (см. пример 7 4).
Начнем оптимизационный поиск, например с точки х 0 =(4, 2,5), лежащей на граничной прямой АВ x 1 +4x 2 =14. При этом f (х 0)=4,55.
Найдем значение градиента
в точке x 0 . Кроме того, и по рисунку видно, что через допустимую область проходят линии уровня с пометками более высокими, чем f (x 0)=4,55. Словом, надо искать направление r 0 =(r 01 , r 02) перемещения в следующую точку x 1 более близкую к оптимальной. С этой целью решаем задачу (7.37) - (7.40) максимизации функции при ограничениях
 |
Поскольку точка х 0 располагается только на одной (первой) граничной прямой (i =1) x 1 +4x 2 =14, то условие (7.38) записывается в форме равенства.
Система ограничительных уравнений этой задачи имеет только два решения (-0,9700; 0,2425) и (0,9700;-0,2425) Непосредственной подстановкой их в функцию T 0 устанавливаем, что максимум Т 0 отличен от нуля и достигается при решении (-0,9700; 0,2425) Таким образом, перемещаться из х 0 нужно по направлению вектора r 0 =(0,9700; 0,2425), т е по граничной прямой ВА.
Для определения координат следующей точки x 1 =(x 11 ; x 12)
(7.42)
необходимо найти значение параметра , при котором функция f (x ) в точке x
откуда =2,0618. При этом =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х 1 (2; 3).
Если продолжить оптимизационный поиск, то при решении очередной вспомогательной задачи (7.37)- (7.40) будет установлено, что Т 1 =
, а это говорит о том, что точка x 1 является точкой максимума х* целевой функции в допустимой области. Это же видно и из рисунка в точке x 1 одна из линий уровня касается границы допустимой области. Следовательно, точка x 1 является точкой максимума х*. При этом f
max =f
(x
*)=5,4.
 |
Задача с нелинейными ограничениями. Если в задачах с линейными ограничениями движение по граничным прямым оказывается возможным и даже целесообразным, то при нелинейных ограничениях, определяющих выпуклую область, любое как угодно малое перемещение из граничной точки может сразу вывести за пределы области допустимых решений, и возникнет необходимость в возвращении в допустимую область (рис. 7.9). Подобная ситуация характерна для задач, в которых экстремум функции f (x ) достигается на границе области. В связи с этим применяются различные
способы перемещения, обеспечивающие построение последовательности точек, расположенных вблизи границы и внутри допустимой области, или зигзагообразное движение вдоль границы с пересечением последней. Как видно из рисунка, возврат из точки x 1 в допустимую область следует осуществлять вдоль градиента той граничной функции , которая оказалась нарушенной. Это обеспечит отклонение очередной точки х 2 в сторону точки экстремума х*. Признаком экстремума в подобном случае будет коллинеарность векторов и .
Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
Наиболее простой в реализации из всех методов локальной оптимизации. Имеет довольно слабые условия сходимости, но при этом скорость сходимости достаточно мала (линейна). Шаг градиентного метода часто используется как часть других методов оптимизации, например, метод Флетчера - Ривса .
Описание [ | ]
Усовершенствования [ | ]
Метод градиентного спуска оказывается очень медленным при движении по оврагу, причём при увеличении числа переменных целевой функции такое поведение метода становится типичным. Для борьбы с этим явлением используется, суть которого очень проста. Сделав два шага градиентного спуска и получив три точки, третий шаг следует сделать в направлении вектора, соединяющего первую и третью точку, вдоль дна оврага.
Для функций, близких к квадратичным, эффективным является метод сопряжённых градиентов .
Применение в искусственных нейронных сетях [ | ]
Метод градиентного спуска с некоторой модификацией широко применяется для обучения перцептрона и в теории искусственных нейронных сетей известен как метод обратного распространения ошибки . При обучении нейросети типа «персептрон» требуется изменять весовые коэффициенты сети так, чтобы минимизировать среднюю ошибку на выходе нейронной сети при подаче на вход последовательности обучающих входных данных. Формально, чтобы сделать всего один шаг по методу градиентного спуска (сделать всего одно изменение параметров сети), необходимо подать на вход сети последовательно абсолютно весь набор обучающих данных, для каждого объекта обучающих данных вычислить ошибку и рассчитать необходимую коррекцию коэффициентов сети (но не делать эту коррекцию), и уже после подачи всех данных рассчитать сумму в корректировке каждого коэффициента сети (сумма градиентов) и произвести коррекцию коэффициентов «на один шаг». Очевидно, что при большом наборе обучающих данных алгоритм будет работать крайне медленно, поэтому на практике часто производят корректировку коэффициентов сети после каждого элемента обучения, где значение градиента аппроксимируются градиентом функции стоимости, вычисленном только на одном элементе обучения. Такой метод называют стохастическим градиентным спуском или оперативным градиентным спуском . Стохастический градиентный спуск является одной из форм стохастического приближения. Теория стохастических приближений даёт условия сходимости метода стохастического градиентного спуска.
Ссылки [ | ]
- J. Mathews. Module for Steepest Descent or Gradient Method. (недоступная ссылка)
Литература [ | ]
- Акулич И. Л. Математическое программирование в примерах и задачах. - М. : Высшая школа, 1986. - С. 298-310.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация = Practical Optimization. - М. : Мир, 1985.
- Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М. : Энергоатомиздат, 1972.
- Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М. : МИФИ, 1982.
- Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М. : МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М. : Наука, 1970. - С. 575-576.
- С. Ю. Городецкий, В. А. Гришагин. Нелинейное программирование и многоэкстремальная оптимизация. - Нижний Новгород: Издательство Нижегородского Университета, 2007. - С. 357-363.
При оптимизации методом градиента оптимум исследуемого объекта ищут в направлении наиболее быстрого возрастания (убывания) выходной переменной, т.е. в направлении градиента. Но прежде чем сделать шаг в направлении градиента, необходимо его рассчитать. Градиент можно рассчитать либо по имеющейся модели
моделирование динамический градиентный полиномиальный
где - частная производная по 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. Трудность поиска глобального оптимума. Метод применим для отыскания только локальных оптимумов.