Основы теории оптимизации (стр. 36 )

а функция f(x) монотонно убывает:

Доказательство. Подставим в формулу градиента функции

и воспользуемся (6):

Суммируя неравенства

(9)

по k от 0 до s, получаем

Поскольку α > 0 в силу (8), то

при всех s, т. е.Отсюда

Покажем, что все условия этой теоремы существенны. Нару­шения условия (6) могут быть двух типов. Во-первых, функция f(x) может быть недостаточно гладкой в какой-либо точке. Пусть, например, Эта функция дифференцируема, но ее градиент не удовлетворяет условию Лип­шица, так как при ||x||→0. В этом случае будет при малых ||хk||, т. е. шаг в методе (5) получается большим и моно­тонность убывания f(x) нарушается. Во-вторых, (6) не выпол­няется для функций, растущих быстрее квадратичной. Пусть, например,

тогда

при . При этом для всякого γ>0 можно указать такое х0, что метод (5), примененный к функции с начальным приближением х0, расходится, по­скольку будет

Если не выполнено условие (7), то функция f(x) не дости­гает минимума и градиент в методе (5) не обязан стремиться к 0 (например, если f(x) линейна: f(x)=(c, x), то

Наконец, выбирать γ, нарушая условие (8), вообще говоря, также нельзя, что видно на примере функции xR1. Действительно, если γ ≥ 2/L, то в методе (5) для этой функции будет

при любом х0.

С другой стороны, при сделанных в теореме 1 предположе­ниях нельзя доказать ничего большего, например, сходимость последовательности хk. Примером может служить

Эта функция удовлетворяет условиям теоремы и при любом х0 ≠ 0 будет

Если потребовать, чтобы множество было

ограничено, то из хk можно выбрать подпоследовательность, сходящуюся к некоторой стационарной точке х*. Однако точка х* не обязана быть точкой локального или глобального мини­мума. В частности, градиентный метод (5) (или даже (1) с про­извольным выбором γk), начатый из некоторой стационарной точки х0, останется в этой точке: хk — х0 для всех k. Иными словами, градиентный метод «застревает» в любой стационар­ной точке — точке максимума, минимума или седловой. Что же касается поиска глобального минимума, то градиентный метод «не отличает» точек локального минимума от глобального и никакой гарантии сходимости к глобальному минимуму он не дает.

Наконец, в условиях теоремы 1 скорость сходимости f(xk) к 0 может быть очень медленной. Например, для f(х)= 1/х при х ≥1 (вид f(x) при х < 1 безразличен) метод (5) при γ=1, х0 = 1 принимает вид при этом можно показать, что

Рассмотрим поведение градиентного метода для более уз­кого класса функций — сильно выпуклых. Естественно, здесь удается доказать более сильные результаты, чем в теореме 1 - именно, сходимость итераций хk к точке глобального минимума со скоростью геометрической прогрессии.

Нам понадобится несколько неравенств, относящихся к дифференцируемым, выпуклым и сильно выпуклым функциям.

Лемма 1. Пусть f(x) дифференцируема, f(x) удовлетво­ряет условию Липшица с константой Y и f(x) ≥f* для всех х.

Тогда

(10)

Доказательство. Сделаем из точки х шаг градиентного метода с γ = 1/L. Тогда (см. (9))

Лемма 2. Пусть f(x) выпукла и дифференцируема, a f(x) удовлетворяет условию Липшица с константой L. Тогда

(11)

Доказательство. Докажем (11) лишь для дважды диф­ференцируемых функций. Тогда

где матрица симметрична и неотрицательно определена, т. е. A≥0. Кроме того, ||A||≤L, так как , для всех х в силу условия Липшица на градиент. Поэтому

Лемма 3. Пусть f(x)— дифференцируемая сильно выпук­лая (с константой l) функция, х* — ее точка минимума (она существует). Тогда

Теорема 2. Пусть f(x) дифференцируема на Rn, ее гра­диент удовлетворяет условию Липшица с константой L и f(x) является сильно выпуклой функцией с константой l. Тогда при 0 < γ < 2/L метод (5) сходится к единственной точке глобаль­ного минимума х* со скоростью геометрической прогрессии:

(12)

Доказательство. Выполнены все условия теоремы 1, по­этому справедливо неравенство (9):

Используем лемму 3:

Отсюда

Поскольку и следовательно, f(xk)→f(x*). Из неравенства

f(x)≥f(x*)+l||x-x*||2/2

следует

Рассмотрим еще более узкий класс функций — сильно вы­пуклых дважды дифференцируемых.

Теорема 3. Пусть f(x) дважды дифференцируема и

(13)

для всех х. Тогда при

(14)

Величина q минимальна и равна

(15)

Доказательство. По формуле

определяем

где в силу (13) Поэтому

Для всякой симметричной матрицы А имеем