МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ, ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ ФУНКЦИИ
Лекция №6
МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ,
ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ ФУНКЦИИ
Будем рассматривать задачу безусловной оптимизации (4.1) предполагая, что функция непрерывно дифференцируема на . Для ее решения воспользуемся простейшими итерационными процедурами вида
, (6.1)
где направление убывания будем определять тем или иным способом с использованием информации о частных производных функции в точке . Если не является стационарной точкой, т.е. , то в этой точке существует бесконечное множество направлений убывания. Какому из них отдать предпочтение? Будем рассуждать так.
Согласно определению (4.2) дифференцируемой функции её приращение в точке выражается так
(6.2)
Если , то при достаточно малых главная часть приращения (6.2) будет определяться дифференциалом функции . С учетом неравенства Коши - Буняковского справедливо соотношение
,
причем, если , то правое неравенство обращается в равенство только при , а левое неравенство – только при , где . Отсюда ясно, что при направление наибыстрейшего возрастания функции в точке совпадает с направлением градиента , а направление наибыстрейшего убывания с направлением антиградиента .
Это свойство градиента и кладется в основу так называемых градиентных методов минимизации функции. Таким образом, при решении задачи (4.1) с помощью итерационной процедуры (6.1) в качестве направления убывания целесообразно выбирать направление антиградиента. Как и все итерационные методы, они предполагают выбор начального приближения – некоторой точки . Общих правил этого выбора нет. В тех случаях, когда известна какая-либо априорная информация об области расположения точки минимума, начальное приближение выбирают поближе к этой области.
Пусть начальная точка уже выбрана. Тогда градиентный метод заключается в построении последовательности точек по правилу
(6.3)
Число из (6.3) называют длиной шага или просто шагом градиентного метода. Если , то шаг можно выбрать так, чтобы . В самом деле, из равенства (6.2) имеем
при всех достаточно малых . Если , то - стационарная точка. В этом случае процесс (6.3) прекращается и, при необходимости, проводится дополнительное исследование поведения функции в окрестности точки для выяснения того, достигается ли в этой точке минимум функции или не достигается. В частности, если - выпуклая функция, то в стационарной точке всегда достигается минимум.
Существуют различные способы выбора величины в методе (6.3). В зависимости от способа выбора можно получить различные варианты градиентного метода. Далее рассмотрим из них наиболее употребительные на практике.
Метод градиентного спуска
В соответствии с основной идеей градиентного метода минимизирующая последовательность строится по правилу (6.3), т.е. в качестве направления убывания функции выбирается направление антиградиента (), которое, как показано выше, обеспечивает в малой окрестности точки наискорейшее убывание функции . В качестве длины шага в этом варианте градиентного метода находится какое-либо число , обеспечивающее условие монотонного убывания функции
. (6.4)
С этой целью задается какое-либо число . При этом для каждого проверяют условие монотонного убывания (6.4), и в случае его нарушения величину дробят до тех пор, пока не восстановится монотонность метода.
Приведем алгоритм одного из вариантов метода градиентного спуска.
Шаг 0. Задать параметр точности , начальный шаг , параметр алгоритма , выбрать , вычислить значение , положить .
Шаг 1. Найти градиент и проверить условие достижения заданной точности . Если оно выполняется, то перейти к шагу 6, иначе - к шагу 2.
Шаг 2. Найти новую точку в направлении антиградиента и вычислить .
Шаг 3. Проверить неравенство
, (6.5)
где - произвольно выбранная константа, одинаковая для всех итераций.
Шаг 4. Если неравенство (6.5) выполняется, то положить , , и перейти к шагу 1, иначе - перейти к шагу 3.
Шаг 5. Положить , где и перейти к шагу 2.
Шаг 6. Завершить вычисления, положив .
Замечание. Вблизи стационарной точки функции величина становится малой. Это может привести к замедлению сходимости последовательности . Поэтому в (6.3) вместо вектора антиградиента используют вектор единичной длины .
Обоснуем сходимость описанной итерационной процедуры, доказав возможность выбора длины шага , обеспечивающего сходимость последовательности к стационарной точке. Для этого на функцию кроме условия непрерывной дифференцируемости, приходится накладывать дополнительные более жесткие условия.
Теорема 6.1. Если функция ограничена снизу, ее градиент удовлетворяет условию Липшица, т.е.
(6.6)
с конечной константой при любых , а выбор производится описанным способом, то для процесса (6.3) норма градиента при , какова бы ни была начальная точка .
Д о к а з а т е л ь с т в о. По теореме о среднем
,
где . Тогда учитывая, что в рассматриваемой итерационной процедуре имеем
В силу неравенства Коши-Буняковского
и условия Липшица (6.6) имеют место неравенства
.
Учитывая, что , получаем
.
Из полученного соотношения видно, что существуют , при которых неравенство (6.5) справедливо. Для этого достаточно выбрать значение параметра , удовлетворяющее условию . Поскольку - ограниченная величина, а , то всегда можно это сделать.
Таким образом, если выбирать по указанному способу, то
. (6.7)
Отсюда с учетом того, что правило выбора при любом гарантирует (в качестве можно взять любую константу, не превосходящую )), следует, что при любом , если и что
. (6.8)
Далее поскольку функция ограниченна снизу и при любом , то при
(6.9)
Тогда из (6.8), (6.9) вытекает, что при .
Метод наискорейшего спуска
В методе наискорейшего спуска минимизирующая последовательность также строится по правилу . Однако величина шага находится в результате решения следующей вспомогательной задачи. На луче , выходящем из точки и направленным по антиградиенту, введем функцию одной переменной и определим из условия
(6.10)
Таким образом, на каждой итерации метода наискорейшего спуска в направлении антиградиента выполняется исчерпывающий спуск. Для решения вспомогательной задачи можно воспользоваться одним из методов одномерного поиска, например, методом поразрядного поиска.
Опишем алгоритм метода наискорейшего спуска.
Шаг 0. Задать параметр точности , выбрать , положить .
Шаг 1. Найти и проверить условие достижения заданной точности . Если оно выполняется, то перейти к шагу 3, иначе - к шагу 2.
Шаг 2. Определить шаг , решив вспомогательную задачу с использованием алгоритма поразрядного поиска. Найти очередную точку положить и перейти к шагу 1.
Шаг 3. Завершить вычисления, положив .
Замечание. Градиентный метод имеет простой геометрический смысл. Оказывается, очередная точка минимизирующей последовательности лежит на луче . Причем, если определяется из условия (6.10), т.е. когда по лучу осуществляется исчерпывающий спуск, то находится в точке касания луча с линией уровня, проходящей через эту точку (см. теорему 4.1 и рис. 4.1). Далее можно понять, что чем ближе линии уровня к окружности, тем быстрее сходится градиентный метод. В тех же случаях, когда линии (поверхности) уровня функции сильно вытянуты и функция имеет так называемый «овражный» характер, процедура градиентного спуска сходится очень медленно. Это означает, что малое изменение некоторых переменных приводит к резкому изменению значения функции. Эта группа методов характеризует «склон оврага». По остальным переменным, задающим направление «дна оврага», функция меняется незначительно. Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате точки последовательности , полученные градиентным методом, будут поочередно находиться то на одном, то на другом «склоне оврага». Если «склоны оврага» достаточно круты, то такие скачки «со склона на склон» точек могут сильно замедлить сходимость градиентного метода. Для ускорения сходимости итерационной процедуры при поиске минимума «овражной» функции можно предложить следующий эвристический прием, называемый овражным методом.
Овражный метод
Пусть в задаче безусловной оптимизации (4.1) функция носит овражный характер. Опишем простейший вариант овражного метода.
В начале поиска минимума «овражной функции» задаются две исходные точки , , из которых производят спуск с помощью какого-либо варианта градиентного метода и получают две точки , на «дне оврага». Затем строят новую точку , где – положительная постоянная, называемая овражным шагом. Вообще говоря, точка будет находиться на “склоне оврага”, поэтому, организовав спуск градиентным методом, получим следующую точку на “дне оврага”. Если таким образом построены точки , , то из точки
совершают спуск в следующую точку на «на дне оврага».
Эффективность овражного метода существенно зависит от выбора шага. Если шаг велик, то на крутых поворотах «оврага» точки могут слишком удаляться от «дна оврага» и спуск из точки в точку может потребовать большого объема вычислений. Кроме того, при больших на крутых поворотах может произойти выброс точки из «оврага», и правильное направление поиска точки минимума будет потеряно. Если же шаг слишком мал, то поиск может замедлиться и эффект от применения овражного метода может стать незначительным.
Скорость сходимости овражного метода может существенно возрасти, если величину овражного шага выбирать переменной, реагирующей на повороты «оврага». При этом желательно за счет увеличения овражного шага по возможности быстрее проходить прямолинейные участки на «дне оврага» на крутых поворотах «оврага» избежать выброса из «оврага» за счет уменьшения овражного шага. Кроме того, желательно добиться по возможности меньшего отклонения точек от «дна оврага» и тем самым сократить объем вычислений, требуемый на градиентный спуск из точки в точку . Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем информацию о «кривизне» желательно получать из результатов предыдущих итераций овражного метода.
Был предложен следующий способ выбрать овражного шага
, , (6.11)
где - угол между векторами и , определяемый условием
,
а постоянная является параметром алгоритма. Точка тогда определяется так:
.
Разность в равенстве (6.11) связана с «кривизной дна оврага» и, кроме того, указывает направление изменения «кривизны». В самом деле, при переходе с участков «дна оврага» малой «кривизны» на участки с большей «кривизной» будем иметь . Тогда в силу (6.11) , т.е. овражный шаг уменьшается, приспосабливается к повороту «дна оврага», что в свою очередь приводит к уменьшению выброса точки на «склон оврага». При переходе с участков «дна оврага» большой кривизны на участки с меньшей «кривизной», наоборот, , поэтому овражный шаг увеличится и появится возможность сравнительно быстро пройти участок с малой «кривизной», в частности, прямолинейные участки на «дне оврага». Если «кривизна дна оврага» на некоторых участках остается постоянной, то разность будет близка к нулю, и поиск минимума на таких участках будет проводиться с почти постоянным шагом, сформированным с учетом величины «кривизны» при выходе на рассматриваемый участок.
Параметр в равенстве (6.11) регулирует «чувствительность» метода к изменению «кривизны дна оврага». Правильный выбор этого параметра во многом определяет скорость движения по «оврагу».
Контрольные вопросы
1. Перечислите основные методы, использующие производные; укажите их достоинства и недостатки.
2. Дайте определение градиента функции многих переменных; как ориентирован относительно него любой вектор, задающий направление убывания функции?
3. Какие методы объединяются под названием градиентных методов.
4. Какая итерационная процедура лежит в основе градиентных методов?
5. Как выбирается длина шага в методе градиентного спуска?
6. Приведите описание алгоритма метода градиентного спуска?
7. Как осуществляется исчерпывающий спуск в направлении убывания?
8. Приведите описание алгоритма метода наискорейшего спуска?
9. Поясните геометрический смысл градиентных процедур.
10. В каком случае целесообразно использование овражного метода?
11. Опишите метод минимизации овражных функций.
PAGE 70
МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ, ИСПОЛЬЗУЮЩИЕ ПРОИЗВОДНЫЕ ФУНКЦИИ