Градиентные методы

Лекция № 8

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

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

Будем рассматривать задачу максимизации нелинейной дифференцируемой функции f (x). Суть градиентного поиска точки максимума х * весьма проста: надо взять произвольную точку х ₀ и с помощью градиента , вычисленного в этой точке, определить направление, в котором f (х) возрастает с наибольшей скоростью (рис. 7.4),

Рис. 7.4

а затем, сделав небольшой шаг в найденном направлении, перейти в новую точку x_i. Потом снова определить наилучшее направление для перехода в очередную точку х ₂ и т. д. На рис. 7.4 поисковая траектория представляет собой ломаную х ₀, x ₁, х ₂... Таким образом, надо построить последовательность точек х ₀, x ₁, х ₂,..., x _k,... так, чтобы она сходилась к точке максимума х *, т. е. для точек последовательности выполнялись условия

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

Движение из точки х_k в новую точку x_k+1 осуществляется по прямой, проходящей через точку х_k и имеющей уравнение

(7.29)

где λ_k — числовой параметр, от которого зависит величина шага. Как только значение параметра в уравнении (7.29) выбрано: λ_k=λ_k⁰, так становится определенной очередная точка на поисковой ломаной.

Градиентные методы отличаются друг от друга способом выбора величины шага — значения λ_k⁰ параметра λ_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)

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

(7.31)

Найдем выражение для производной, дифференцируя равенство (7.30) по как сложную функцию:

Подставляя этот результат в равенство (7.31), получаем

(7.32)

Это равенство имеет простое геометрическое истолкование: градиент в очередной точке х_{к+ 1}, ортогонален градиенту в предыдущей точке х_к.

Пример 7.4. Определить максимум функции , начав оптимизационный поиск с точки .

Решение. Будем сопровождать решение задачи графической иллюстрацией (рис. 7.6). По данному уравнению параболоида вращения

построены линии уровня этой поверхности. С этой целью уравнение приведено к виду (x ₁-1)²+(x₂-2)²=5-0,5 f, из которого ясно, что линиями пересечения параболоида с плоскостями, параллельными плоскости x ₁О x ₂ (линиями уровня), являются окружности радиусом . При f =-150, -100, -50 их радиусы равны соответственно , а общий центр находится в точке (1; 2). Находим градиент данной функции:

.

I шаг. Вычисляем:

На рис. 7.6 с началом в точке х ₀=(5; 10) построен вектор 1/16, указывающий направление наискорейшего возрастания функции в точке х ₀. На этом направлении расположена следующая точка . В этой точке .

Используя условие (7.32), получаем

или 1-4=0, откуда =1/4. Так как , то найденное значение является точкой максимума . Находим x ₁=(5-16/4; 10-32/4)=(1; 2).

II шаг. Начальная точка для второго шага x ₁=(1; 2). Вычисляем =(-4∙1 +4; -4∙2+8)=(0; 0). Следовательно, х ₁=(1; 2) является стационарной точкой. Но поскольку данная функция вогнутая, то в найденной точке (1; 2) достигается глобальный максимум.

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

Рассмотрим задачу выпуклого программирования с линейными ограничениями:

(7.33)

(7.34)

(7.35)

где .

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

Начнем с геометрической иллюстрации процесса решения задачи (рис. 7.7). Пусть начальная точка х ₀ расположена внутри допустимой области. Из точки х ₀ можно двигаться в направлении градиента , пока f (x) не достигнет максимума. В нашем случае f (x) все время возрастает, поэтому остановиться надо в точке х, на граничной прямой. Как видно из рисунка, дальше двигаться в направлении градиента нельзя, так как выйдем из допустимой области. Поэтому надо найти другое направление перемещения, которое, с одной стороны, не выводит из допустимой области, а с другой — обеспечивает наибольшее возрастание f (x). Такое направление определит вектор , составляющий с вектором наименьший острый угол по сравнению с любым другим вектором, выходящим из точки x_i и лежащим в допустимой области. Аналитически такой вектор найдется из условия максимизации скалярного произведения . В данном случае вектор указывающий наивыгоднейшее направление, совпадает с граничной прямой.

Таким образом, на следующем шаге двигаться надо по граничной прямой до тех пор, пока возрастает f (x); в нашем случае — до точки х ₂. Из рисунка видно, что далее следует перемещаться в направлении вектора , который находится из условия максимизации скалярного произведения , т. е. по граничной прямой. Движение заканчивается в точке х ₃, поскольку в этой точке завершается оптимизационный поиск, ибо в ней функция f (х) имеет локальный максимум. Ввиду вогнутости в этой точке f (х) достигает также глобального максимума в допустимой области. Градиент в точке максимума х ₃= х * составляет тупой угол с любым вектором из допустимой области, проходящим через х₃, поэтому скалярное произведение будет отрицательным для любого допустимого r_k, кроме r ₃, направленного по граничной прямой. Для него скалярное произведение =0, так как и взаимно перпендикулярны (граничная прямая касается линии уровня поверхности f (х), проходящей через точку максимума х *). Это равенство и служит аналитическим признаком того, что в точке х ₃ функция 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.

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

(7.37)

при ограничениях

(7.38)

для тех t, при которых

(7.39)

(7.40)

где .

В результате решения задачи (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).

Начнем оптимизационный поиск, например с точки х ₀=(4, 2,5), лежащей на граничной прямой АВ x ₁+4 x ₂=14. При этом f (х ₀)=4,55.

Найдем значение градиента

в точке x ₀ . Кроме того, и по рисунку видно, что через допустимую область проходят линии уровня с пометками более высокими, чем f (x ₀)=4,55. Словом, надо искать направление r ₀=(r ₀₁, r ₀₂) перемещения в следующую точку x ₁ более близкую к оптимальной. С этой целью решаем задачу (7.37) — (7.40) максимизации функции при ограничениях

Поскольку точка х ₀ располагается только на одной (первой) граничной прямой (i =1) x ₁+4 x ₂=14, то условие (7.38) записывается в форме равенства.

Система ограничительных уравнений этой задачи имеет только два решения (-0,9700; 0,2425) и (0,9700;-0,2425) Непосредственной подстановкой их в функцию T ₀ устанавливаем, что максимум Т ₀ отличен от нуля и достигается при решении (-0,9700; 0,2425) Таким образом, перемещаться из х ₀ нужно по направлению вектора r ₀=(0,9700; 0,2425), т е по граничной прямой ВА.

Для определения координат следующей точки x ₁=(x ₁₁; x ₁₂)

(7.42)

необходимо найти значение параметра , при котором функция f (x) в точке x ₁ достигает возможно большего значения. Но сначала найдем интервал допустимых значений параметра , при которых точка x ₁ будет принадлежать допустимой области. Система (7.36) в данном случае имеет вид

(7.43)

Первое ограничение мы опустили, поскольку точка x ₁ лежит на прямой АВ. Решая систему (7.43), устанавливаем, что следует искать в полуинтервале (0; 4,1237] (заметим, что нас интересуют только не отрицательные значения параметра ). Найдем значение , при котором достигается наибольшее возрастание приращения функции, вы званное перемещением из точки x ₀ в точку x ₁. В соответствии с условием (7.41)

,

откуда =2,0618. При этом =-0,3999<0. Значит,=2,0618. По формуле (7.42) находим координаты новой точки х₁ (2; 3).

Если продолжить оптимизационный поиск, то при решении очередной вспомогательной задачи (7.37)— (7.40) будет установлено, что Т₁=, а это говорит о том, что точка x₁ является точкой максимума х* целевой функции в допустимой области. Это же видно и из рисунка в точке x₁ одна из линий уровня касается границы допустимой области. Следовательно, точка x₁ является точкой максимума х*. При этом f _max= f (x *)=5,4.

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

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

Дата добавления: 2014-01-07