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

3. Среднеквадратичная стабилизация оценок алгоритма

Обозначим Определим

константу К и параметр δ > 0 из условия

Пусть

Теорема 1. Пусть выполнены условия (A)—(G) на функции f и F, а так же величины α и β> 0:

Тогда оценки алгоритма (А) стабилизируются в среднеквадра­тичном смысле и справедлива оценка

(5)

Заметим, что, в частности, в Теореме 1 устанавливается ассимп-тотически эффективная граница среднеквадратичных невязок оце­нивания L = L/(1 — К).

Условия (A)-(C),(E)-(G) являются стандартными для дока­зательства состоятельности оценок алгоритмов стохастической ап­проксимации с возмущением на входе. Ранее факт среднеквад­ратичной стабилизации оценок алгоритма (4) был доказан при более жестких ограничениях Доказательство. Обозначим

В силу алгоритма (4) и условия (А) для квадрата нормы раз­ностиимеем оценку

(6)

1. В силу модели наблюдения (3) для последнего слагаемого имеем

Обозначим Еn{∙} условное математическое ожидание относи­тельно σ-алгебры, порождаемой случайными величинами

Применив к последней формуле Еn{∙}, используя добавив и отняви

получаем

(7)

Рассмотрим разность по знаком Еn{∙} в первом слагаемом (7). Учи­тывая разложение для по формуле Тейлора, последовательно выводим

при γ1 (0.1). В итоге для первого слагаемого в (7), применив (В), (С), (Е). получаем

Аналогичное соотношение получается и для второго слагаемого в (7) Для третьего слагаемого, в силу независимостиь пробного воз­мущенияполучаем:

В итоге,

2. Рассмотрим Используя разложение stepп на

слагаемые из предыдущею пункта, можно получить

3. Рассмотрим Разложив как в п.1. с использованием

свойств (С) и (D) получаем:

В итоге имеем:

Суммируя полученные выше оценки, учитывая вид Н, выводим

В силу неравенстваполучаем

Выберем . При таком выборе коэффициентов мыполучаем. Перейдя к безусловному

математическому ожиданию выводим (5).

Пример

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

Численный пример, рассматриваемый в данном разделе, иллю­стрирует решение именно этой задачи. Рассмотрим одномерный случай, когда модель дрейфа точки описывается формулой θп = θп-1 + ζ, где ζВ(-1,1) (ζ принимает значение 1 или -1 с веро­ятностью 0.5). Тогда будем рассматривать функцию F(x,w,n) = f(x, n) = (х — θп)2, которая определяет квадрат расстояния до точ­ки. Очевидно данная функция удовлетворяет условию теоремы. Из­мерения на каждом шаге производятся с дополнительным шумом уп = f(xп,n) + vn, где vn (-1,1). Помеха vn генерировалась по закону v2i = 1 —(i mod 3) и для четных шагов и v2i-1= 1 —3*(i mod 7) для нечетных. В этом случае параметры функции А = 1, В = 2, С = 1, D = 1/3, μ = 2. Тогда

В эксперименте были выбраны α = 1/12 и β = 1/3. При этом Н ≈2,30. Выбрав δ = 0,08, получаем К ≈ 0,86, L ≈ 9,43 и ≈ 69,91. Точка оптимума дрейфует, как показано на рис. 1 слева. Ошибка оценивания и асимптотическая граница показаны на рис. 1 справа.

Рис. 1: Экстремум θп (слева) и норма ошибки оценивания (справа).

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

10. Стратегия оптимизационного исследования

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

10.1. Построение модели

Процесс оптимизации с использованием модели можно рассматривать как метод отыскания оптимального решения для реальной системы без непосредственного экспериментирования с самой системой.

«Прямой путь», ведущий к оптимальному решению, заменяется «обходным», включающим построение и оптимизацию модели, а также преобразование полученных результатов в практически реализуемую форму. При формировании модели следует учитывать только важнейшие характеристики системы. Необходимо также сформулировать логически обоснованные допущения, выбрать форму представления модели, уровень её детализации и метод реализации на ЭВМ. Ни одну из моделей независимо от степени её детализации и сложности нельзя считать единственно «правильной». Модели можно упорядочить по степени адекватности описания поведения реальной системы в представляющей интерес области эксплуатации. Единственным критерием оценки модели может служить лишь достоверность полученных на модели прогнозов поведения реальной системы.

При разработке модели стремятся к тому, что иногда называют «принципом оптимальной неточности»: модель должна быть настолько детализирована, насколько это необходимо для целей исследования, для которого её создали. Существует единственный надёжный способ создания модели с оптимальным уровнем неточности, а именно метод постепенного совершенствования модели и методов оптимизации. Начав с самой простой модели, её последовательно доводят до такого уровня, когда точность полученного значения оптимума соответствует точности используемой в модели информации. Для того, чтобы получить результаты в заданные сроки и не проводить постепенного совершенствования модели, обычно подгоняют модель под оптимизационные методы, наиболее развитые к данному времени или освоенные специалистом, проводящим работу, или же использованные в предыдущем исследовании. При разработке модели следует также учитывать возможности и ограничения оптимизационных программ. Например, нельзя решить задачу НЛП размерности, соответствующей максимальной размерности решаемых задач ЛП.