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

где hk — случайный равномерно распределенный на единичной сфере вектор, α>0 — фиксированная длина пробного шага. Метод может быть записан в виде

Используя результат упражнения 1, получаем

Из теоремы 2 следует, что при любом способе выбора γk метод случайного поиска не может сходиться быстрее, чем геометри­ческая прогрессия со знаменателем

(14)

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

сходится не быстрее прогрессии со знаменателем (п—1)/n.

Теорему 2 можно несколько уточнить для случая, когда R(х) линейна, а для помехи известна оценка снизу не только для дисперсии, но и для матрицы ковариаций. Pасматривается метод

(15)

где ξk независимы, х0 случайный вектор, A-1 существует и

(16)

a Гk — детерминированные матрицы n×n.

Теорема 3. В методе (15) при любых Гk справедлива оценка

В качестве приложения рассмотрим обобщение градиентного метода минимизации квадратичной функции

при наличии помех:

(18)

Применяя теорему 3, получаем, что при любых Гk

(19)

(20)

причем равенство в (19), (20) достигается при

(21)

Сопоставляя (20) с оценкой (13) п. 9.2 для градиентного метода, получаем, что при данных условиях выбор γk= 1/kl в гра­диентном методе является асимптотически оптимальным.

2. Оптимальные алгоритмы. До сих пор мы ограничивались довольно узким классом алгоритмов — линейными рекуррентными. Однако вопрос об оптимальности можно решать для гораздо бо­лее общего класса процедур. В ряде случаев можно установить потенциальные возможности любых (не обя­зательно рекуррентных или линейных) методов минимизации при наличии случайных помех. Основным инструментом здесь является известное в статистике неравенство Крамера — Рао (информационное неравенство).

Пусть функция f(x) квадратична:

(22)

а ее градиент вычисляется со случайной помехой ξ. Предполо­жим, что помехи ξ независимы и одинаково распределены (рань­ше мы такого предположения не делали). Пусть уже вычислены значения в некоторых точках х1,..., xk. Наконец, пусть матрицы А и А-1 известны. Тогда

Обозначим Тогда Величины zi известны (так как хi, ri и А-1 известны), а величины ηi независимы и одинаково распределены (ибо такими являются ξi). Таким образом, за­дача свелась к следующей. Заданы векторы zi = х*+ ηi, где ηi — реализации независимой, одинаково распределенной слу­чайной величины. Требуется по ним оценить х*.

Это — классическая задача оценки параметров, рассматри­ваемая в статистике. Для нее справедливо неравенство Краме­ра — Рао, утверждающее, что если ηi имеют плотность рη(z), эта плотность регулярна (т. е. справедливо равенство и существует фишеровская информационная матрица

(23)

то для любой несмещенной оценки k вектора х* по измерениям zi, i = 1, ..., k, имеет место неравенство

(24)

Иными словами, существует нижняя граница точности произ­вольных несмещенных оценок. Используя (24), приходим к следующему результату.

Теорема 4. Пусть помехи ξi имеют плотность р(z), причем p(z) регулярна и

существует, 0 < J< ∞. Тогда для любой несмещенной оценки k точки минимума х* функции (22), построенной по измерениям в k точках, справедливо неравенство

(25)

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

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

(26)

где Н > 0 — некоторая матрица, то получаем, что асимптоти­чески оптимальный выбор γk и Н таков:

(27)

при этом

(28)

Oтсюда получаем, что если ξi распре­делены нормально, то правая часть (25) совпадает с правой частью (28). Таким образом, для случая нормальных помех алгоритм (26), (27) является асимптотически оптимальным (не только среди линейных или рекуррентных алгоритмов). Для других распределений помехи алгоритм (26), (27), вообще го­воря, не оптимален. Более того, можно показать, что правая часть (25) строго меньше правой части (28) для любого распре­деления, отличного от нормального. В этом случае оптимальный алгоритм можно получить, введя нелинейность в итерационный процесс

(29)

где функцияи γk выбираются следующим образом:

(30)

Для нормальных помех метод (29), (30) переходит в (26), (27).

Можно показать, что при определенных условиях на p(z) распределение величины для метода (29), (30)

стремится к нормальному со средним 0 и матрицей ковариаций А-1JА-1. Сопоставляя это с правой частью (25), получаем, что метод (29), (30) является асимптотически оптимальным.

Практическая реализация метода (29), (30) затруднительна, так как в нем нужно знать матрицу А-1, а также плотность рас­пределения помехи. Мы не будем останавливаться на способах преодоления этих трудностей. Здесь более важен принципиаль­ный факт — возможность построения асимптотически оптималь­ного алгоритма решения задачи минимизации при наличии слу­чайных помех, причем этот алгоритм оказывается рекуррентным.

Подчеркнем еще, что все выводы здесь носили асимптотиче­ский характер. Оптимальный алгоритм для конечных k в случае нормальных помех дается выражением (21). Видно, что на на­чальных шагах Гk примерно постоянно: Гk ≈σ2U0A, а для больших k Гk убывает как k-1:.

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

9.6. Псевдоградиентный метод с возмущением на входе для нестационарной задачи безусловной оптимизации

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

Задачи оптимизации можно рассматривать в постановках с дис­кретным и непрерывным временем. Здесь мы ограничим­ся рассмотрением моделей первого типа. Пусть f(x,n) - функци­онал, который необходимо минимизировать в момент времени п (п N). для решения подобных про­блем детально рассматривал методы Ньютона и градиентный, которые применимы в случае дважды дифференцируемого функ­ционала при условии l < 2fk(x) < L. Оба метода полагаются на возможность прямого измерения градиента функционала в произ­вольной точке