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

9. Влияние помех на поведение методов безусловной минимизации

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

9.1. Источники и типы помех

1. Источники помех. В реальных задачах применить методы минимизации «в чистом виде» нельзя — ситуация неизбежно ослож­няется наличием разного рода ошибок и погрешностей. Пере­числим некоторые из причин их возникновения.

В простейшем случае, когда минимизируемая функция и ее градиент заданы формулами, ошибки возникают вследствие по­грешностей вычисления, связанных с округлением при выполне­нии арифметических действий на ЭВМ. В результате f(xk), f(xk) и т. д. вычисляются с некоторой ошибкой, т. е. вместо вектора f(xk) мы получаем вектор sk = f(xk)+rk. Здесь по­меха rk является детерминированной (ошибки округления в ЭВМ не носят случайного характера) и можнo оценить ее уро­вень ||rk||≤ε, так как законы образования погрешностей округ­ления хорошо изучены. Величину ε обычно можно считать по­стоянной (не зависящей от xk) и, как правило, не слишком боль­шой. В случае необходимости ε можно уменьшить, производя вычисления с двойной точностью.

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

Нередко (особенно в задачах адаптации, обучения, распозна­вания и т. д.) проблема оптимизации ставится следующим обра­зом. Нужно минимизировать детерминированную функцию f(x)

типа среднего риска:

(1)

где функция Q(x, ω) известна, однако распределение Р(ω) не задано. Дана лишь выборка ω1,..., ωk из этого распределения. Тогда точное вычисление f(x) и f(x) в принципе невозможно. В качестве приближенного значения этих величин можно взять

(2)

или более просто

Q(x, ωk) и xQ(x, ωk). (3)

В этом случае значения функции и градиента содержат случай­ную помеху. Если брать в качестве приближений для f(xk) и f(xk) величины Q(xk, ωk) и xQ(xk, ωk), то помехи будут не­зависимы в различных точках.

Аналогичная ситуация возникает в методе Монте-Карло, когда задача заключается в минимизации f(x) вида (1) и рас­пределение Р(ω) известно, однако вычисление интеграла (1) слишком трудоемко. Тогда можно точные значения f(x) и f(x) заменить выборочными значениями, как и выше.

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

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

2. Типы помех. Как мы видели выше, ошибки при вычисле­нии функции и градиента могут иметь различное происхождение и различную природу. Несколько упрощая реальную ситуацию, можно выделить следующие основные типы помех. Всюду ниже речь идет о вычислении градиента, когда вместо точного значе­ния f(xk) нам доступен вектор

sk = f(xk) + rk (4)

где rk — помехи. Случай приближенного вычисления f(x) иссле­дуется аналогично.

а) Абсолютные детерминированные помехи удовлетворяют условию

||rk||≤ε, (5)

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

б) Относительные детерминированные помехи удовлетво­ряют условию

(6)

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

в) Абсолютные случайные помехи. Предположим, что по­мехи rk случайны, независимы при различных х, центрированы и имеют ограниченную дисперсию:

(7)

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

г) Относительные случайные помехи обладают теми же свойствами, что и в п в), однако их дисперсия убывает по мере приближения к точке минимума:

(8)

Hа практике часто встречаются и другие типы помех например случайные помехи с систематической ошибкой (||Мk||≤ε) или случайные ограниченные помехи (Мrk = 0, ||rk||≤ε). Однако их можно рассматривать как комбинацию основных типов, описанных выше. Поэтому мы ограничимся этими наиболее важными классами помех. Иногда (особенно в теоретических работах) предполагают, что уровень помех εk зависит от номера итерации и εk→0 при k→∞, Такое предпо-

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

9. 2. Градиентный метод при наличии помех

1. Постановка задачи. Рассмотрим градиентный метод мини­мизации дифференцируемой функции f(x) на Rn в ситуации, ко­гда градиент вычисляется с ошибкой:

(1)

Относительно помех rk будут делаться предположения об их принадлежности одному из классов, описанных выше. Функция f(x) будет предполагаться сильно выпуклой (с константой L) и с градиентом, удовлетворяющим условию Липшица (с кон­стантой L) — этот класс функций наиболее важен. Нас будет интересовать поведение обычного градиентного ме­тода γk≡γ при наличии помех, а также вопрос о целесообраз­ном выборе длины шага в условиях помех. Обоснование мето­дов будет вестись с помощью общих теорем.

2. Абсолютные детерминированные помехи.

Теорема 1. ПустьТогда найдется > 0

такое, что при 0 < γ < в методе (1) будет

(2)

гдепри ε→0, х* — точка минимума f(x).

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

(3)

Учитывя, что (3) дифференцируема и имеет результат

,

который удовлетворяет условию Липшица с кон­стантой 1, получаем

где а, b — некоторые константы, причем а→0 при ε→0.

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