Методы первого порядка

Градиентный метод. Будем рассматривать задачу (3.5.2), предполагая, что функция непрерывно дифференцируема на. Выражение для дифференциала функции

является скалярным произведением векторов и, т.е..

Вектор называют градиентом функциии обозначают иногдаgrad(читается «набла»).

Понятие градиента удобно использовать для краткой записи производной по направлению , где. Имеем

Производная по направлению обладает следующим свойством: . Для доказательства воспользуемся неравенством Коши – Буняковского для скалярного произведения векторов:

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

Это свойство градиента лежит в основе ряда итерационных методов минимизации функций, одним из которых является градиентный метод. Как и другие итерационные методы, градиентный метод предполагает выбор начального приближения – некоторой точки . Общих правил выбора точкинет, однако при наличии соответствующих априорных данных начальное приближение стараются выбрать поближе к области расположения точки (или точек) минимума целевой функции задачи.

Будем считать, что некоторая начальная точка уже выбрана. Градиентный метод заключается в построении последовательностив соответствии с выражением

(3.5.23)

Здесь – шаговый множитель. Если, то шагможно выбрать так, чтобы было выполнено условие. Действительно,

при всех достаточно малых . Если, то– стационарная точка. В этом случае процесс (3.5.23) прекращается, и при необходимости проводится дополнительное исследование поведения функции в окрестности точкис целью выяснения, является ли эта точка точкой минимума функции. Если– выпуклая функция на, то в стационарной точке всегда достигается минимум.

В зависимости от способа выбора величины в (3.5.23) можно получить различные варианты градиентного метода. Рассмотрим некоторые наиболее употребительные из них.

1). На луче , направленном по антиградиенту, введем функцию одной переменной

(3.5.24)

и определим в виде

(3.5.25)

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

Пусть дана квадратичная функция

(3.5.26)

где – симметрическая положительно определенная матрица,. Функция (3.5.26) сильно выпукла на, при этоми метод (3.5.23) в данном случае записывается в виде:

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

и формулу (3.5.24), в которой величине соответствует, получим

При из условиянаходим

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

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

(3.5.27)

или из условий

(3.5.28)

В выражениях (3.5.27), (3.5.28) , а величиныхарактеризуют погрешность выполнения условий (3.5.25): чем ближек нулю илик единице, тем меньше расхождение между, найденным из условий (3.5.27), (3.5.28) и значением, определяемым условиями (3.5.25).

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

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

3). Если функция непрерывно дифференцируема наи градиентудовлетворяет условию Липшица

(3.5.29)

причем константа известна, то в (3.5.23) в качествеможет быть взято любое число, удовлетворяющее условиямгде– положительные числа, являющиеся параметрами метода. В частности, приполучим метод (3.5.23) с постоянным шагом.

4). Возможен выбор из условия

(3.5.30)

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

5). Возможно априорное задание величин , исходя из условий

Например, в качестве можно взять, где, а числоудовлетворяет неравенству. Тогда приполучим. Такой выборв (3.5.23) прост для реализации, но не гарантирует выполнения условия монотонностии в общем случае не обеспечивает быстрой сходимости.

6). В тех случаях, когда заранее известна величина , в (3.5.23) можно принять– это абсцисса точки пересечения прямойс касательной к кривойв точке.

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

Пусть градиент функции удовлетворяет условию Липшица с постоянной, т.е.

(3.5.31)

Тогда градиентный метод (3.5.23) с постоянным шаговым множителем , удовлетворяющим условию, сходится к стационарным точкам функции.

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

(3.5.32)

Заменив в выражении (3.5.32) на,на, получим

(3.5.33)

Разложение (3.5.33) указывает на справедливость формулы:

(3.5.34)

Для функции одной переменной можно записать:

Полагая в последнем выражении и используя (3.5.34), получим:

(3.5.35)

Использование выражения (3.5.35) позволяет записать:

Отсюда, с учетом (3.5.31) и неравенства Коши – Буняковского, следует:

(3.5.36)

Соотношение (3.5.36) позволяет записать:

Здесь использована формула (3.5.23) с учетом , а также условие. Используя полученный результат, запишем:

(3.5.37)

где – значение функциив стационарной точке. Из (3.5.37) следует, что последовательностьмонотонна и ограничена. Следовательно, она является сходящейся, что позволяет записать:

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

Метод скорейшего спуска имеет следующий геометрический смысл: точка , определяемая соотношениями (3.5.23), (3.5.25), лежит на лучев точке его касания линии уровня (при– поверхности уровня), а сам лучперпендикулярен к линии уровня– см. рис. 3.5.1. Действительно, пусть– некоторое параметрическое уравнение линии уровня, т.е.

Рис. 3.5.1. Геометрическая интерпретация метода скорейшего спуска

, причем . Тогда . В частности, приимеем. Это означает, что градиент (или антиградиент)перпендикулярен к касательному направлению поверхности уровняв точкеили, иначе говоря, лучперпендикулярен к. Из (3.5.24) с учетом (3.5.25) приполучаем. Но вектор

перпендикулярен к в точке, поэтому последнее равенство означает, что направлениеи, следовательно, лучявляются касательными к линии уровняв точке.

Чем ближе линии уровня к окружности, тем лучше сходится метод скорейшего спуска. Теоретические исследования и численные эксперименты подтверждают, что метод скорейшего спуска и другие варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня функциисильно вытянуты и функция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции – эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно. Если точка находится на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате приближения, получаемые градиентным методом, будут поочередно находиться то на одном, то на другом «склоне оврага». Если «склоны оврага» достаточно круты, то такие скачки со «склона на склон» точекмогут сильно замедлить сходимость градиентного метода.

Для ускорения сходимости при поиске минимума «овражной» функции разработаны «овражные» модификации градиентного метода, смысл которых состоит в отыскании и уточнении направления «оврага» и дальнейшем продвижении в этом направлении. Одна из таких модификаций заключается в следующем. В начале поиска задаются две точки , из которых производят спуск с помощью какого-либо варианта градиентного метода, и получают две точкина «дне оврага». Затем полагают, где– положительная постоянная, называемая «овражным» шагом. Из точки, которая находится на «склоне оврага», производят спуск с помощью градиентного метода и определяют следующую точкуна «дне оврага». Если уже известны точки, то из точкисовершают спуск с помощью градиентного метода и находят следующую точкуна «дне оврага».

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

Метод проекции градиента. Пусть рассматривается задача

(3.5.38)

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

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

Пусть – некоторое начальное приближение. Далее последовательностьстроится по правилу

(3.5.39)

где . Если– выпуклое замкнутое множество и способ выборав (3.5.39) задан, то последовательностьоднозначно определяется выражением (3.5.39). В частности, приметод (3.5.39) превращается в градиентный метод.

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

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

(3.5.40)

где – выпуклое замкнутое множество и функции, непрерывно дифференцируемы на. Пусть– начальное приближение,. Предположим, что-е приближениепри некоторомуже известно. Введем функцию

(3.5.41)

и множество

(3.5.42)

Пусть . В качестве-го приближениявозьмем решение следующей задачи минимизации:

(3.5.43)

Поскольку функция (3.5.41) сильно выпукла, множество (3.5.42) выпукло и замкнуто, задача (3.5.43) имеет решение, притом единственное. Задачу (3.5.43) необязательно решать точно: достаточно найти точку из условий

(3.5.44)

Рассмотренный вариант метода линеаризации обычно используют в тех случаях, когда определение точки из (3.5.44) не требует слишком большого объема вычислений. Отметим также, что задача (3.5.43) равносильна задаче

так как . Это значит, что точное решениезадачи (3.5.43) представляет собой проекцию точкина множество, а точкаиз (3.5.44) является приближением для. Отсюда следует, что если в (3.5.40) ограниченияотсутствуют (), тои метод линеаризации превратится в метод проекции градиента.