Лекция №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) вытекает, что при .