научная статья по теме АЛГОРИТМ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ С ПРОБНЫМ ВОЗМУЩЕНИЕМ НА ВХОДЕ В НЕСТАЦИОНАРНОЙ ЗАДАЧЕ ОПТИМИЗАЦИИ Автоматика. Вычислительная техника

Текст научной статьи на тему «АЛГОРИТМ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ С ПРОБНЫМ ВОЗМУЩЕНИЕМ НА ВХОДЕ В НЕСТАЦИОНАРНОЙ ЗАДАЧЕ ОПТИМИЗАЦИИ»

Автоматика и телемеханика, №11, 2009

РЛСЯ 02.50.Sk, 02.60.Pn

(Санкт-Петербургский государственный университет)

АЛГОРИТМ СТОХАСТИЧЕСКОЙ АППРОКСИМАЦИИ С ПРОБНЫМ ВОЗМУЩЕНИЕМ НА ВХОДЕ В НЕСТАЦИОНАРНОЙ ЗАДАЧЕ ОПТИМИЗАЦИИ

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

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

Задачи оптимизации можно рассматривать в постановках с дискретным и непрерывным временем. В настоящей статье ограничимся рассмотрением моделей первого типа. Пусть /(х,п) - функционал, который необходимо минимизировать в момент времени п (п € В [3] для решения подобных проблем детально рассматриваются методы Ньютона и градиентный, которые применимы в случае дважды дифференцируемого функционала при условии г < У^ /(х, п) < Д. Оба метода полагаются на возможность прямого измерения градиента функционала в произвольной точке.

В реальном мире измерения всегда подразумевают наличие помех. Иногда теоретически обоснованные алгоритмы на практике не дают состоятельных оценок точки экстремума. Устойчивость алгоритма к помехам очень важна практически во всех инженерных приложениях. Для решения задач в условиях помех в 50-е гг. ХХ в. появляются методы стохастической аппроксимации Роббинса-Монро и Кифера-Воль-фовица, история развития которых детально описана в [2-4]. Общий подход для поиска экстремума, используемый в алгоритмах стохастической аппроксимации, может быть формализован следующим образом:

(1) дп+\ = вп — ап дп(0п),

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

Алгоритмы стохастической аппроксимации с пробным одновременным возмущением на входе и с одним или двумя на каждой итерации зашумленными измерениями минимизируемой функции появились в работах различных исследователей в конце 80-х, - начале 90-х гг. ХХ в. [5-9]. В англоязычной литературе такие алгоритмы получили название Simultaneous Perturbation Stochastic Approximation (SPSA) [8]. Эти алгоритмы известны состоятельностью оценок при почти произвольных помехах наблюдения [2], которые должны быть только в некотором смысле ограничены и независимы на каждой итерации с пробным случайным возмущением на входе. Более того, количество измерений исследуемой функции на одной итерации составляет всего одно или два и не зависит от размерности d пространства состояний. При этом алгоритмы имеют оптимальный порядок асимптотической скорости сходимости (по числу итераций) [7], что позволяет говорить о существенном повышении скорости сходимости в многомерном случае (d ^ 1) по сравнению с классическими алгоритмами, оценивающими градиент через конечную разность, у которых количество измерений на каждом шаге прямо пропорционально d.

Алгоритмы стохастической аппроксимации первоначально обосновывались в условиях минимизации стационарных функционалов. В [3] приведена версия алгоритма градиентного спуска для нестационарного случая и доказана состоятельность этого алгоритма в некотором смысле. Дальнейшее развитие эти идеи получили в [1] для более общего случая. В [2] было предложено использовать для оптимизации нестационарных функционалов алгоритмы типа стохастической аппроксимации с пробным одновременным возмущением на входе, которые могли бы быть более эффективными, так как эти алгоритмы полагаются только на одно или два измерения на каждом шаге, а поэтому способны быстрее адаптироваться к изменениям функционала. Кроме того, как уже отмечалось, эти алгоритмы более устойчивы к помехам. В [10] реализация этой идеи была четко формализована и получены предварительные точные результаты о ее применимости.

В настоящей работе рассмотрим применение алгоритма стохастической аппроксимации с пробным одновременным возмущением на входе для задачи оптимизации нестационарного функционала. В разделе 2 будет детально описана постановка задачи оптимизации, существенно более общая, чем в [1, 3]: о минимизируемом функционале будет предполагаться не два, а один раз дифференцируемость, не будет предполагаться возможность прямого измерения градиента, а помехи наблюдения могут быть почти произвольными. В разделе 3 формулируется алгоритм, в разделе 4 - утверждение о стабилизируемости среднеквадратичной невязки оценок, доказательство которого вынесено в Приложение. В разделе 5 работоспособность ал-

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

2. Постановка задачи

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

(2) уп = F (х„ ,w. ,п)+ v.,

где xn - известные (выбираемые) точки, в которых производятся наблюдения (план эксперимента), wn - независимые случайные величины, выражающие неконтролируемую неопределенность, заданные на некотором вероятностном пространстве П и имеющие одинаковое, вообще говоря, неизвестное распределение Pw(-), vn - искажения в наблюдениях (могут быть и неслучайные).

Рассмотрим задачу минимизации нестационарного функционала среднего риска:

(3) /(x,n)= EwF(x,w,n)= / F(x,w,n)Pw(dw) ^ min.

Требуется оценить вп - точку минимума функции /(х,п), изменяющуюся с течением времени:

Для характеристики поведения оценок точек минимума нестационарного функционала (3) введем два определения.

Определение 1. Последовательность оценок вп точек минимума вп стабилизируется в среднеквадратичном смысле, если существует такое С > 0, что

Здесь и далее Е - символ математического ожидания.

Определение 2. Число Ь называется асимптотической границей среднеквадратичных невязок оценивания, если для последовательности оценок точек минимума вп выполняется:

Далее будем рассматривать задачу о построении последовательности стабилизирующихся оценок при следующих условиях.

Л. Функции /(-,п) сильно выпуклые по первому аргументу для каждого п:

В. Уп и Уад градиент Vf (-,ад,п) удовлетворяет условию Липшица с константой М:

(х, ад, п) — Vf (у, ад, п) \\ < М\\х — у \\, и для градиента выполняется следующее свойство.

С. Локальное свойство Лебега: Ух € Ж^ и Уп 3 окрестность ихп и функция Фх(ю,п) : ЕтФх(ад,п) < те такие, что Ух' € ихп (х,ад, п)|| < Фх(ю,п). Б. Скорость дрейфа точки минимума ограничена условиями:

Уп ||0п - 0п-1|< А, Ет(вп/ш,п)\2 < В,

ЕШ1,Ш2 (х, №1 , п) - ^ (х,'Ш2 ,п - 1)|2 < С ||х - Оп—2 ||2 + О.

Е. Для помех наблюдения vn выполнены условия

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

Заметим, что последнему условию удовлетворяют детерминированные, но ограниченные последовательности .

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

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

где £п является ограниченной случайной величиной. Подобное условие предполагается ив [3], а в [1] это условие незначительно ослаблено. Среднеквадратичная стабилизируемость оценок алгоритма поиска минимума в условиях Б означает применимость его к широкому классу различных задач.

3. Алгоритм оценивания

Пусть - последовательность пробных одновременных возмущений, подаваемых на вход алгоритма оценивания, является некоторой реализацией последовательности независимых бернуллиевских случайных векторов из ЖД у которых каждая

1 , 1 компонента независимо принимает с вероятностями — значения, равные ±—-¡=.

Выберем некоторый начальный вектор во € ЖЛ Будем оценивать последовательность точек минимума последовательностью , определяемой алгоритмом стохастической оптимизации с пробным одновременным возмущением на входе, который имеет следующий вид:

х2п = в2п—2 + ¡Дп, х2п —1 = в2п —2 - ¡Дп

Для обоснования среднеквадратичной стабилизации оценок алгоритма (4) будем считать, что:

Е. Случайные величины Дп (рандомизация входа алгоритма) и №2п,

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

📎📎📎📎📎📎📎📎📎📎