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

Более экономный способ заключается в пересчете аппрокси­мации после каждого нового измерения. Опишем схему подобных методов на упрощенной модели Пусть можно предпо­лагать, что функция f(x), х Rп, аффинна в некоторой области: f(x)≈ (a, х) + β и уже вычислены ее значения с помехой в k (k≥n+1) точках: где ηі — случайные независимые помехи, Рассмотрим (п+1)-мерные векторы и запишем измерения в виде уі = (с*, zі) + ηі. Найдем оценку для с* методом наименьших квадратов, т. е.

(12)

Этому методу можно придать рекуррентную форму — новое измерение в точке может быть учтено с помощью следующей формулы:

(13)

Таким образом, на каждом шаге не нужно заново вычислять оценку для аппроксимирующей функции, решая систему линей­ных уравнений (12), а достаточно использовать простую рекур­рентную формулу (13). Оценка ck может быть использована для реализации шага спуска: и проверки согласованности линейной модели функции с измере­ниями. Разумеется, в реальных задачах линейная модель функ­ции правомерна лишь локально, и метод минимизации должен включать «забывание» информации, полученной на ранних ите­рациях.

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

9.5. Оптимальные методы при наличии помех

1. Потенциальные возможности итеративных методов при на­личии помех. Для детерминированных «невозмущенных» задач, как мы видели, существует множество методов, каждому из которых присуща своя скорость сходимости. Так, для гладких сильно выпуклых функций метод тяжелого шарика сходится быстрее градиентного, метод сопряженных градиентов — быст­рее метода тяжелого шарика, метод Ньютона — еще более быстро и т. д. Вопрос об оптимальном в смысле скорости схо­димости методе здесь весьма сложен. Оказывается, наличие по­мех в определенном смысле упрощает ситуацию — оно ограничи­вает возможности любых методов минимизации. В этом случае существует некая предельная скорость сходимости, которая не может быть превзойдена. Тот метод, для которого эта предель­ная скорость достигается, естественно считать оптимальным.

Начнем с результатов, устанавливающих потенциальные возможности по скорости сходимости произвольных итератив­ных алгоритмов (не обязатпьно связанных с минимизацией) при наличии случайных помех Рассмотрим итерационный про­цесс в Rп:

(1)

где γk≥0 — детерминированные скалярные множители, R(х) — некоторая функция, а ξk — случайные помехи, предполагаю­щиеся независимыми и центрированными Начальное приближение х0 может быть либо детерминированным, либо случайным, в последнем случае предполагается, что М||х0||2 <∞ и х0, ξi независимы. Предположим, что существует единственная точка х* такая, что R(x*) = 0 и R(x) удовлетворяет условию линейного роста:

(2)

Теорема 1. Пусть для всех k

(3)

Тогда при сделанных выше предположениях для любого ме­тода (1)

(4)

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

Доказательство. Оценим условное математическое ожи­дание

Отсюда

Стоящая справа кусочно-квадратичная функция достигает ми­нимума по γk при От­сюда получаем

или, обозначая Таким образом,

Из теоремы 1 следует, что любой метод вида (1) при сделан­ных выше предположениях не может сходиться быстрее 1/(a+bk), или асимптотически — быстрее O(1/k).

Приведем некоторые примеры использования этого резуль­тата. Pассмотрим градиентный метод мини­мизации f(x):

(5)

при абсолютных случайных помехах:

(6)

(обратите внимание, что здесь знак неравенства для дисперсии помех изменен на обратный по сравнению с 9.2). Предположим, что f(x) имеет точку минимума х*, а градиент f(x) удовлетво­ряет условию Липшица с константой L. Тогда мы находимся в условиях применимости теоремы 1, и из нее следует, что при любом выборе γk для метода (5) справедлива оценка

(7)

Иначе говоря, никакой вариант градиентного метода при наличии абсолютных случайных помех не может сходиться быстрее O(1/k) (точнее, Заметим, что для градиентного метода с γk = γ/k было т. е. он асимптотически оптимален по порядку ско­рости сходимости. Более точно вопрос об оптимальности гра­диентного метода будет исследован далее.

Рассмотрим теперь метод Ньютона при наличии помех. Бу­дем считать, что матрица [2f(xk)]-1 вычисляется точно, а гра­диент содержит аддитивную случайную помеху ξk. В этом слу­чае метод Ньютона (модифицированный за счет введения пара­метра, задающего длину шага) принимает вид

(8)

Относительно помех ξk будем считать, что они независимы и

(9)

Можно показать, что в условиях теоремы о сходимо­сти «невозмущенного» метода Ньютона детерминированная часть процесса (8) (т. е. в окрестности решения удовлетворяет условию Липшица, а случайная часть имеет дисперсию, ограниченную снизу. Таким образом, ме­тод (8) также не может сходиться быстрее, чем со скоростью O(1/k). Иначе говоря, наличие случайных помех уничтожает преимущества быстро сходящихся методов минимизации.

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

Теорема 2. Пусть выполнены, предположения, сформули­рованные в начале параграфа, и для всех k

(10)

Тогда для любого метода (1)

(11)

В качестве первого примера использования теоремы 2 рас­смотрим градиентный метод при случайных относительных по­мехах. Пусть f(x) дифференцируема, существует точка мини­мума х*, f(x) удовлетворяет условию Липшица с константой L, а помеха в определении градиента независима при различных k и удовлетворяет условиям Тогда в методе (5) при любых γk выполняется неравенство (11). Иными словами, градиентный метод при случайных относитель­ных помехах не может сходиться быстрее, чем со скоростью гео­метрической прогрессии.

Вторым примером может служить метод случайного поиска. Пусть f(x) — квадратичная функция:

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

(13)