Файл: Методы оптимизации в статистических задачах управления..pdf

получила развитие собственно математическая теория оптимиза­ ции в условиях помех. Центральное место в ней занимает группа

У (х) = F (х) + 1] (х).

Ошибки вычисления т] (х) являются центрированными случай­ ными величинами с ограниченной дисперсией:

М [г\ (х)] = 0 , М [т]2 (х)] = а2 (х) •< а2.

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

иудовлетворяются условия:

где через es обозначен п-мерный вектор, s-я компонента которого равна 1, а все остальные нулю [120]. Сходимость в среднеквадра­ тическом смысле и с вероятностью 1 выражается соответственно равенствами:

lim М [|х+ — х‘ I2] = 0 ; £->00

Р [lim X 1 = х+] = 1. £-> СО

Заметим, что из сходимости с вероятностью 1 следует сходимость в среднеквадратическом смысле.

127

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

со со

S = S а — о°. і=1 і=1

Условие (301) вводится для исключения регулярных состав­ ляющих при вычислении оценки частных производных в рекур­ рентном соотношении (298). Действительно, сопоставляя фор­ мулы (299) и (301), можно заключить, что

Наличие ошибок измерения г) приводит к тому, что в градиент­ ном методе при использовании постоянного шага ос итерационная точка X1 совершает случайное блуждание в окрестности точки минимума х+. Для сглаживания этих блужданий в методе стоха­ стической аппроксимации вводится дополнительное условие (300). Анализируя это условие совместно с условием (302), можно за­ ключить о необходимости выполнения равенства

lim а,- = 0. /->00

Очевидно, что ограничения (299)—(301) однозначно не опреде­ ляют выбора последовательностей {сс,-} и {с,}. Одним из возмож­ ных вариантов выбора этих последовательностей являются соот­

где а, b, g, f — произвольные положительные константы. Опреде­ ленная свобода в выборе параметров ос,- и с,- является естественным отражением произвола в выборе размера шага в градиентном методе. Изложенный алгоритм называется методом Кифера— Вольфовица.

128

Саксом [147] было показано, что при проведении эксперимен­ тов наличие асимметрии в выборе точек в формуле (298) приводит к появлению некоторых дополнительных погрешностей в вычисле­ нии оценки градиента и в конечном счете понижает скорость сходимости метода стохастической аппроксимации. Для исключе­ ния этой погрешности была предложена процедура

Саксу удалось доказать сходимость этого метода при тех же ограничениях (299)—(301) на последовательности, {а,} и {с,} и приблизительно при тех же требованиях к минимизируемой функции F (х), что и в методе Кифера—Вольфовица.

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

При анализе скорости сходимости градиентных методов было показано, что для случая квадратичной функции при отсутствии помех итерационная точка х1 стремится к точке минимума х+ со скоростью геометрической прогрессии, причем при плохо обусловленной матрице вторых производных знаменатель гео­

метрической прогрессии k — I близок к единице, так что

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

вательностей {а/} и {с;} даны в п. 11 данной главы. Существует несколько подходов к увеличению скорости схо­

димости методов стохастической аппроксимации. Исторически первым появился метод Кестена [136]. В этом методе предпола­ гается, что аргумент минимизируемой функции F (х) является скаляром. Ускорение сходимости достигается путем введения зависимости параметров а( от характера изменения приращений

чайных ошибок г] разумно брать малые значения а*. Кестен пред­ ложил использовать число перемен знака разности (х‘ — хг_1) в качестве признака, характеризующего степень удаленности х1 от х+. За основу берется соотношение (298) или (303) с учетом требований (299)—(301), причем значение параметра сь и щ на і-м шаге выбирается равным соответственно ct_x и а/_1( если напри-

мер, на двух предыдущих шагах приращение Ах‘ имело одина­ ковый знак. В противном случае производится некоторое умень­ шение параметров по сравнению с Сі_г и ос^.

В работе Фабиана [128] для ускорения процедуры Сакса предложен метод, основанный на соотношении

Для сходимости этого алгоритма необходимо, чтобы плотность вероятности р (»]) ошибки вычисления функции F (х) была сим­ метрична относительно точки г| = 0.

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

Вопросу ускорения сходимости методов стохастической аппро­ ксимации посвящен ряд работ [127, 89].

11.Применение метода стохастической аппроксимации

кзадаче минимизации квадратичной функции

снеизвестными параметрами

Рассмотрим практические результаты применения метода Сакса к минимизации квадратичной функции. Пусть минимизируемая функция F (х) представляется в виде

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

постоянную составляющую, не влияющую на положение мини­ мума, функцию F (х) можно записать:

F (х) = ~ x*Qx.

Применительно к этой функции итерационная процедура ме­ тода Сакса (303) в векторной форме будет иметь вид

*° = Е,

130