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

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

(8)

причем помехи rk взаимно независимы. Как можно показать, метод тяжелого шарика с постоянными коэффицентами

(9)

в такой ситуации не сходится к х* = A-1b, а приводит лишь в область вокруг х*. Поэтому рассмотрим метод с переменными коэффициентами, который удобно записать в форме

(10)

Наряду с ним рассмотрим градиентный метод

(11)

Ограничимся коэффициентами вида

(12)

Теорема 1. При любом выборе α, β метод (10), (12) схо­дится асимптотически не быстрее (в смысле величины

чем метод (11) с γk = 1/(kl).

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

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

Примерно такова же ситуация с методом сопряженных гра­диентов. Полный анализ его поведения при наличии помех очень сложен. При этом разные его варианты по-разному реагируют на ошибки. Можно показать, что при абсолютных и относительных помехах метод сопряженных градиентов вблизи минимума теряет преимущества перед градиентным. Лишь если помехи удовлетворяют условию типа (7), то метод сопряженных градиентов сохраняет свои достоинства.

3. Другие методы. Квазиньютоновские методы очень чувстви­тельны к ошибкам вычисления градиента. Действительно, в них восстанавливается матрица А = 2f(x) по измерениям гра­диента:

(13)

Если шаги малы (xi+1 близко к хi), а измерения f(xi) содер­жат ошибки, то матрица восстанавливается плохо. Для задач со случайными аддитивными помехами с этим эффектом можно бороться путем увеличения числа измерений — нужно восстанав­ливать не по п значениям f(x), как в детерминированном слу­чае, а по N > п замерам. При этом можно выписать рекуррент­ные формулы,. Для не­случайных помех такой прием, вообще говоря, не приводит к повышению точности.

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

Однако нужно помнить, что возможности всех методов, осно­ванных на квадратичной аппроксимации, весьма ограничены в задачах с помехами — даже знание точной матрицы вторых про­изводных не спасает положения.

9.4. Прямые методы

1. Постановка задачи. Пусть в произвольной точке хk изме­ряется значение f(xk) с ошибкой ηk. По-прежнему будем гово­рить об абсолютной (относительной) детерминированной ошибке, если и об абсолютной

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

2. Разностные методы при случайных помехах. Рассмотрим методы некоторые методы в ситуации со случайными помехами. Начнем с наиболее типичного примера — метода Кифера — Вольфовица (метода разностной аппроксимации гра­диента):

(1)

eі — координатные орты. Здесь и далее

(2)

причем случайные ошибки η независимы в различных точках и

(3)

Обсудим вопрос о выборе пробных и рабочих шагов αk, γk. Обозначим

где gk — систематическая, a ξk — случайная ошибки. Если f(x) дважды дифференцируема, a 2f(x) удовлетворяет условию Липшица, то в соответствии с известной леммой

(4)

Для случайной составляющей погрешности оценки градиента имеем

(5)

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

Теорема 1. Пусть f(x) сильно выпукла и дважды диффе­ренцируема, 2({x) удовлетворяет условию Липшица, выпол­нено (3) и для αk, γk справедливы соотношения

(6)

Тогда в методе (1) Если при этом и γ достаточно велико, то

Можно получить аналогичный результат для несимметрич­ной разностной аппроксимации градиента при менее жестких предположениях о гладкости f(x).

Таким образом, при наличии аддитивных случайных помех в измерении функции для сходимости следует и пробные, и ра­бочие шаги стремить к 0, причем пробные шаги следует умень­шать медленнее. Асимптотическая скорость сходимости зависит от выбора αk, γk гладкости f(x) и вида разностной аппроксима­ции, однако она не превосходит О(k-s), s < 1. Эти же выводы справедливы и для более общих алгоритмов.

Приведем более точные оценки скорости сходимости для квадратичной функции при постоянных аддитивных помехах:

(7)

где помехи η независимы в различных точках. Сопоставим ме­тод Кифера — Вольфовица (градиентный)

и метод случайного поиска

где hk — случайный вектор, равномерно распределенный на еди­ничной сфере (и не зависящий от η). Поскольку для квадра­тичной функции систематическая ошибка в разностной аппрок­симации градиента равна 0 при любом αk, здесь не нужно стремить αk к 0. Будем считать, что в (8) и (9) αk ≡α > 0. Используя изветную теорему, нетрудно доказать, что в методе (8) при γk = γ/k, γ > 1/(2l)

Отсюда следует, что если брать γk в (8) в п раз большим, чем в (9), то п шагов метода (9) будут асимптотически экви­валентны одному шагу метода (8). Учитывая, что трудоемкость мотода (8) в п раз больше, чем метода (9), получаем, что в данной ситуации методы (8) и (9) эквивалентны по их асимпто­тической эффективности. Этот вывод не зависит от обусловленности или каких-либо других свойств А.

Отметим в заключение, что к асимптотическим оценкам типа приведенных в теореме 1, следует относиться с большой осто­рожностью. Например, выбор αk = γk -1/6 означает, что нужно сделать миллион итераций, чтобы уменьшить пробный шаг в 10 раз. Поэтому практически счет будет происходить при по­стоянном αk.

3. Другие методы. Для задач с помехами перестают быть работоспособными все методы, построенные на одномерных ми­нимизациях (например, методы сопряженных направлений), поскольку такую минимизацию нельзя осуществить. Бо­лее перспективными являются методы, в которых строится не­локальная аппроксимация функции по ее значениям в ряде то­чек (типа симплексного поиска или метода барицентрических координат). Влияние помех сказывается в том, что эти методы перестают работать в окрестности минимума, где уровень помех сравним с приращениями функции. Если помехи случайны и центрированы, то методы можно модифицировать так, что они останутся работоспособными и в указанной обла­сти. Общая идея такой модификации — использовать большее число точек для построения аппроксимации функции, чем в де­терминированном случае. Это позволяет усреднять помехи и по­лучать все более точную аппроксимацию. Например, в симп­лексном методе можно многократно проводить вычисления функции в каждой вершине симплекса, сопоставляя точность оценки значений функции с их разностью в различных вер­шинах.