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

Мы не выписывали выше точных значений констант (величин р, γ, q), интересуясь лишь качественной картиной процесса. Рассмотрим эти значения указаны для случая квадратич­ной функции.

Пусть

Тогда в методе (1) будет

Используя известную лемму, получим оценку В частности, при γ = 2/(L + l) отсюда следует

3. Относительные детерминированные помехи.

Теорема 2. ПустьТогда

найдется >0 такое, что при 0 < γ < метод (1) сходится к х* со скоростью геометрической прогрессии.

Доказательство. Возьмем в качестве функции Ляпу­нова Тогда

Таким образом, градиентный метод устойчив к относитель­ным ошибкам, если их уровень менее 100%. Причина этого оче­видна— всякое направление, составляющее с антиградиентом острый угол, является направлением убывания f(x) и может быть использовано в качестве направления движения вместо градиента.

4. Абсолютные случайные помехи. Пусть помехи rk случайны, независимы,

Теорема 3. Найдется >0 такое, что при γk ≡ γ, 0 < γ < в методе (1)

Если

тоЕсли же

(6)

то хk→х* п. н. Наконец, еслито

(7)

Доказательство. Возьмем V(х) = f(x) — f *. Тогда

Мы увидим далее (теорема 4), что вышеприведенные оценки не завышены, поэтому теорема 3 дает основания для следую­щих выводов. Во-первых, обычный вариант градиентного ме­тода (с γk≡γ) при наличии аддитивных случайных помех не сходится к точке минимума, а приводит лишь в окрестность ми­нимума. Размеры этой области тем меньше, чем меньше γ. Во-вторых, выбирая убывающие γk, можно сделать метод сходя­щимся в том или ином вероятностном смысле (в среднем при γk →0 и почти наверное при

В-третьих, скорость сходимости при этом довольно медленна (порядка О(1/k)). Как мы увидим в дальнейшем, более высокой скорости сходимости нельзя добиться ни при каком выборе γk.

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

(8)

Будем считать, что начальное приближение х0 случайно и сим­метрично распределено вокруг

Теорема 4. При любом 0 < γ < 2/L, γk≡γ в методе (1) при условиях (8) для величины

(9)

справедливы соотношения

(10) (11) Еслито

(12)

Величина || В (γ) || минимальна при γ = 1/l,

(13)

5. Относительные случайные помехи. Пусть помехи rk такие же, как в предыдущем пункте, но их дисперсия удовлетворяет условию

M|| rk ||≤α||f(x)||2. (14)

Теорема 5. При любом α существует такое, что при γk≡γ, 0< γ < методе (1) будет

(15)

Мы видим, что наличие случайных относительных помех лю­бого уровня не приводит к нарушению сходимости.

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

9. 3. Другие методы минимизации при наличии помех

1. Метод Ньютона. Вопрос о поведении метода Ньютона при наличии помех значительно более сложен, чем тот же во­прос для градиентного метода. Дело в том, что в этом методе может быть несколько источников помех (вычисление f(x), 2f(x), обращение 2f(x)) и их природа может быть различна (например, случайные ошибки в вычислении градиента и си­стематические в обращении матрицы). Мы не будем стараться рассмотреть все возможные ситуации, а остановимся на не­скольких характерных примерах, интересуясь лишь качествен­ным анализом процесса.

Пусть в результате всех вычислений (градиента, гессиана, решения системы линейных уравнений) получается вектор, от­личающийся от истинного:

(1)

где rk — помеха, и делается шаг

(2)

Предположим, что помеха может содержать систематическую ошибку:

(3)

Как мы знаем, метод Ньютона сходится локально в некоторой области U. Ясно, что если в больше диаметра U, то сходимости заведомо нет — при любом х0, сколь угодно близком к х*, процесс выходит из U. Таким образом, возникает ситуация, кото­рой не было в градиентном методе: при достаточно высоком уровне абсолютных помех метод Ньютона может вести себя бессмысленным образом (например, ||хk — х*|| может возра­стать) при любом х0.

Возникновение систематических ошибок в методе Ньютона неизбежно, даже если f(x) и 2 f (x) вычисляются точно. Дело в том, что если число обусловленности μ точки минимума велико (а именно тогда применение метода Ньютона наи­более целесообразно), то матрица 2f(xk) оказывается плохо обусловленной. Поэтому результат решения системы линейных уравнений 2({xk)z=f(xk) для определения шага метода от­личается от точного решения вследствие ошибок округления в ЭВМ. Это отличие (для плохо обусловленных систем) может быть значительным и приводит к развалу метода Ньютона.

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

(4)

причем матрицы А и A-1 вычисляются точно, а градиент содер­жит случайную ошибку:

(5) Рассмотрим метод

(6)

являющийся обобщением метода Ньютона за счет введения па­раметра γk. Как мы увидим в дальнейшем, этот метод ни при каком способе выбора γk не может сходиться быстрее чем O(1/k). Но скорость сходимости такого же по­рядка может обеспечить гораздо более простой градиентный метод. Таким образом, здесь теряется основное преимущество метода Ньютона — его высокая скорость сходимости. Аналогич­ная ситуация возникает при наличии относительной ошибки. Если, например, градиент вычисляется с относительной ошиб­кой, то метод Ньютона может сходиться лишь со скоростью геометрической прогрессии. Лишь при высокой точности вычислений метод Ньютона со­храняет свои преимущества.