Надо, однако, учитывать, что многие экономические процессы в действительности носят нелинейный и стохастический характер и их аппроксимация линейными зависимостями (линеаризация), упрощая расчеты, существенно [c.173]
Книга посвящена одному из важных разделов современной теории сложных систем — изучению количественных методов управ ления, планирования и проектирования в условиях неполной информации. В книге с единых позиций обсуждаются три группы математических методов методы прогнозирования поведения сложных систем, методы управления в условиях риска и неопределенности (стохастическое программирование) и методы адаптации и обучения (стохастическая аппроксимация). [c.2]
Решающие правила и характеристики решающих распределений могут определяться как непосредственно по статистическим характеристикам исходной информации, так и в результате итеративного процесса обучения по последовательным реализациям наборов случайных параметров условий задачи. Формальный аппарат итеративного совершенствования решающих правил и характеристик решающих распределений представляет собой естественное обобщение стохастической аппроксимации. В задачах немалых размеров рациональный выбор начального приближения для решающих правил и решающих распределений, основанный, как правило, на неформальных содержательных соображениях, является важнейшим условием получения удовлетворительного приближения за приемлемое время. [c.6]
Методы адаптации представляют собой достаточно общий итеративный процесс решения задач стохастического программирования — процесс совершенствования решающих правил или статистических характеристик решающих распределений — по последовательным реализациям наборов случайных параметров условий задач. Формальная основа методов адаптации — различные обобщения схемы стохастической аппроксимации. [c.15]
Задача (8.18) решается известными методами выпуклого программирования (при заданных статистических характеристиках Мцк случайных величин rij) или с помощью процедур стохастической аппроксимации по последовательным реализациям случайных параметров условий задачи. [c.120]
В [147] получены условия оптимальности для задач вида (3.7) — (3.9). Они позволяют построить методы вычисления апостериорных решающих распределений для стохастических задач достаточно общего вида. При заданном распределении ш решающие распределения могут быть построены с помощью методов, обобщающих методы возможных направлений. В случаях, когда можно наблюдать реализацию со, для построения апостериорных решающих распределений предлагаются итеративные вычислительные схемы, обобщающие методы стохастической аппроксимации. [c.141]
В (148] и 306] условия оптимальности решения стохастических задач с фиксированным функциональным видом априорных решающих распределений использованы для построения адаптивных алгоритмов вычисления набора а искомых параметров распределения. При некоторых предположениях можно доказать, что такие итеративные алгоритмы, основанные на идеях стохастической аппроксимации, позволяют по последовательным реализациям случайных параметров условий задачи получить последовательность векторов ап, сходящуюся к оптимальному [c.144]
Метод обобщенных стохастических градиентов, предложенный в работах [106 — 109], не предполагает дифференцируемости целевой функции задачи и не требует задания статистических характеристик случайных параметров условий задачи. Метод стохастических градиентов является общим методом стохастической аппроксимации (см. гл. 15). [c.181]
В стохастических задачах, в которых имеются основания полагать все случайные элементы набора (А, Ъ, с) сгруппированными относительно своих средних значений и можно считать оптимальный базис не зависящим от случайных реализаций условий задачи, практически приемлемой процедурой вычисления (L ) является нормальная аппроксимация. [c.298]
Стохастическая аппроксимация — сравнительно молодая математическая дисциплина, проблематика которой представляет значительный интерес для теоретической статистики, для решения экстремальных задач в условиях неполной информации и для разнообразных приложений в естественных и технических науках. Статистики видят в стохастической аппроксимации новую процедуру выбора решений по ограниченной выборке. Для исследователей биологов, химиков или медиков стохастическая аппроксимация является экономным методом использования результатов наблюдений для практических выводов. Специалисты по автоматическому регулированию видят в стохастической аппроксимации общий подход к анализу разнообразных схем и моделей распознавания, идентификации, обучения и адаптации. Мы рассмотрим стохастическую аппроксимацию совсем с иной точки зрения. [c.341]
Стохастическая аппроксимация в широком смысле слова представляет собой общий метод решения условных экстремальных задач при неполной информации об исходных данных. Мы будем рассматривать стохастическую аппроксимацию как общий итеративный метод решения задач стохастического программирования по последовательным реализациям случайных наборов параметров условий задачи. Такой подход к стохастической аппроксимации влияет известным образом и на ее проблематику и направления развития. [c.341]
К методам второго класса отнесем итеративные методы, порождаемые стохастической аппроксимацией и ее естественными модификациями — методы постепенного совершенствования плана, основанные на последовательном предъявлении независимых наборов реализаций случайных параметров условий. [c.342]
Общий вид итеративной процедуры стохастической аппроксимации представляется соотношением [c.342]
Классические схемы стохастической аппроксимации представляют собой, таким образом, итеративные методы градиентного типа. На каждом шаге процесса происходит сдвиг в случайном направлении, определяемом реализованными значениями случайных исходных данных и схемой отдельной итерации. На одних шагах мы приближаемся к искомому оптимуму, на других удаляемся от него. Однако процедуры стохастической аппроксимации гарантируют большую вероятность сдвига в нужном направлении, чем в нежелательном. В среднем за каждую итерацию происходит сдвиг в требуемом направлении. За большое число итераций в соответствии с законом больших чисел обеспечивается почти наверное приближение к искомой оптимальной точке (если она единственна). Для того чтобы добраться до оптимума из сколь угодно удаленной от него начальной точки и при этом обеспечить достаточное количество итераций, необходимое для проявления закона больших чи- [c.342]
Чтобы после некоторого числа шагов, проведенных в окрестности искомой точки, не выйти из нее, необходимо потребовать стремления к нулю шага ап при п— оо. Таким образом, на классические методы стохастической аппроксимации можно смотреть как на итеративные методы (градиентного типа) решения безусловной экстремальной стохастической задачи [c.342]
В настоящей главе кратко излагаются основные схемы стохастической аппроксимации и обсуждаются обобщения теории и методов, позволяющие строить итеративные вычислительные процедуры решения задач стохастического программирования. [c.343]
Рассматривая рекуррентное соотношение (1.1), как разностное уравнение, отвечающее дискретным моментам п=1, 2,. .., можно перейти к непрерывному случаю, заменив соотношение (1.1) дифференциальным уравнением. Параграф 8 посвящен условиям сходимости непрерывных процедур стохастической аппроксимации. [c.343]
Одномерная стохастическая аппроксимация 2.1°. В 1929 г. в [201] для отыскания корня уравнения [c.344]
В настоящей главе под стохастической аппроксимацией подразумевается теория и итеративные методы решения задач стохастического программирования по последовательным реализациям наборов случайных параметров условий задачи. [c.345]
Теорема 2.2. Пусть хп — процесс стохастической аппроксимации типа (2.16), в — действительное число, для которого можно подобрать функцию т](е), определенную на множестве положительных чисел, такую, что если s>0, х — >s и /г>т](е), то [c.347]
Рассмотрим еще одну общую схему стохастической аппроксимации, предложенную Дворецким [92]. Итеративная процедура Дворецкого имеет вид [c.347]
Доказательство сходимости процесса Дворецкого основано на том, что случайные ошибки наблюдения можно рассматривать как аддитивный шум, наложенный на детерминированный процесс аппроксимации. Отсюда возможность раздельного рассмотрения детерминированной и стохастической составляющих процесса (2.17). [c.348]
Одним из важных предположений, лежащих в основе классических схем стохастической аппроксимации, является допущение об отсутствии систематических ошибок (о равенстве нулю математического ожидания ошибок наблюдений). Если это условие не выполняется, процесс может сходиться совсем не к точке оптимума (соответственно не к корню уравнения). Другим существенным допущением является сходимость [c.348]
Положим fn(x)=f(x — en + 6i), n = 2, 3,. . ., где вп — единственный максимум fn(x). Определим следующий процесс стохастической аппроксимации [c.350]
Многомерная стохастическая аппроксимация [c.351]
Естественно, что стохастическая аппроксимация как итеративный метод решения задач стохастического программирования представляет интерес только в многомерном случае. Это, однако, не единственный аргумент в пользу многомерных модификаций процедур стохастической аппроксимации. Различные причины заставляют конструктора в процессе проектирования и создания экспериментального образца сложной системы довольствоваться не наилучшими решениями. Однако при испытаниях системы возникает возможность совершенствовать ее качество, подбирая экспериментальным образом . значения регулируемых параметров и оценивая при этом величину показателя эффективности системы. Ошибки измерений и отсутствие информации о виде функциональной зависимости показателя качества системы от измеряемых параметров усложняют истолкование и использование экспериментальных данных для доводки образца. Опытные инженеры интуитивно используют для совершенствования систем по результатам испытаний схемы типа многомерной стохастической аппроксимации. Задача теории — оценить допустимый диапазон применения этих методов, модифицировать их, упростить вычисления и ускорить сходимость. [c.351]
Утверждения, доказанные в [9], содержат основные результаты о сходимости рассмотренных выше процессов стохастической аппроксимаций, правда, с существенной оговоркой результаты, модифицированные для ограниченного множества X. Предположение о том, что траектория процесса аппроксимации не выходит за пределы ограниченного множества X, упрощает как формулировки, так и доказательства теорем о сходимости итеративных процессов. В [9], однако, не указаны условия, при которых можно гарантировать, что хп остается при любом" п внутри некоторого ограниченного множества. [c.357]
В 1заключительной, 16-й главе стохастическая аппроксимация и ее обобщения рассматриваются как общие итеративные методы решения 6 [c.6]
Обзор работ по специальной задаче стохастического программирования — задаче фильтрации и прогноза — и по итеративным методам стохастического программирования, связанным со стохастической аппроксимацией, приведены соответственно в гл. 14 и 15 настоящей монографии. Попытки получения общего подхода к различным схемам стохастического программирования предпринимались в работах И. Лемари [183], Д. Б. Юдина (352, 353], Ю. М. Ермольева [105, 107]. [c.18]
При наличии статистических характеристик Мц случайных параметров условий задачи простая задача (7.11) квадратичного программирования решается без труда. В случае, когда значения Mi заранее не известны, оптимальные значения Я г вычисляются по последовательным реализациям случайной величины gtfj с помощью итерационной процедуры стохастической аппроксимации, учитывающей ограничения Яг О. Оптимальный план х исходной задачи вычисляется через составляющие А,, решения двойственной задачи (7.11) по формуле [c.115]
Условия, при которых классические процедуры стохастической аппроксимации сходятся к искомому экстремуму, требуют выпуклости или по крайней мере одноэкстремальности функции -Мш (со, х) по х. Это значит, что для использования стохастической аппроксимации в качестве итеративного метода решения задач стохастического программирования необходимо модифицировать классические схемы применительно к задачам условной оптимизации и отказаться от требования выпуклости или одноэкстремальности Мщ<р (ш, х). [c.343]
Чтобы расширить круг задач стохастического программирования, для которых стохастическая аппроксимация может служить итеративным методом решения, целесообразно также отказаться от рассмотрения ошибок наблюдения как аддитивного шума, наложенного на детер-. минированный процесс аппроксимации. На. этом предположении основано доказательство сходимости большинства вычислительных схем стохастической аппроксимации. Некоторые задачи стохастического программирования (см., например, 5 гл. 14 Обобщенные задачи фильтрации и прогноза ) требуют разработки итеративных процессов оптимизации функционалов вида / (Мш<р (ю, х)) на некотором множестве X. Итеративные процессы решения некоторых классов двухэтапных задач стохастического программирования должны обеспечить последовательную условную оптимизацию функционалов вида M JR М (ш,, о>2, хг,х2), [c.343]
В 2 рассматриваются классические схемы одномерной стохастической аппроксимации и некоторые их модификации. Основное внимание здесь уделяется итеративным процедурам решения безусловной экстремальной задачи вида (1.2). Параграф 3 посвящен условиям сходимости многомерных процессов стохастической аппроксимации. Помимо классических схем здесь излагаются и результаты, полученные в последние годы.. В 4 приводится обзор обобщений схем стохастической аппроксимации на случай решения условных экстремальных задач. Только в этом случае стохастическая аппроксимация может рассматриваться как итеративный метод стохастического программирования. В 5 исследуется важный для приложений вопрос о скорости сходимости и возможных путях ускорения сходимости процессов стохастической аппроксимации. Процедуры, рассмотренные в 6 и 7, позволяют в ряде случаев отказаться от основных допущений, на которых основаны классические схемы стохастической аппроксимации, — от одноэкстремальности целевого функционала задачи и несмещенности оценок наблюдаемых случайных величин. [c.343]
Под классической схемой стохастической аппроксимации мы будем понимать итеративные схемы типа процедур Роббинса — Монро и Кифера— Вольфовица и различные их модификации. [c.345]
Бурхгольдер [46] рассмотрел более общий процесс стохастической аппроксимации, из которого следуют процессы Роббинса — Монро и Кифера — Вольфовица. [c.346]
Теорема 2.4. При перечисленных условиях динамическая схема (2.30) стохастической аппроксимации обеспечивает сходимость в сред-неквадратическом хп—8И к нулю. При этом [c.350]
Работа Бунке [45] дает основания для различных обобщений стохастической аппроксимации. В [45] приведена общая схема построения случайной последовательности, сходящейся к данному числу. Используя частные варианты этой схемы, удается получить случайные последовательности, аппроксимирующие медиану функции распределения, корень уравнения f(x)=a, максимум функции f(x), где f(x)- — однозначно определяемая медиана случайной величины у (со, х). [c.351]
Т. Блум [31], Ж. Сакс [244] и другие обобщили схемы стохастической аппроксимации на многомерный случай. Кратко опишем не только многомерный аналог процедуры Кифера — Вольфовица оптимизации одноэкстремальной функции регрессии, но и многомерный аналог схемы Роббинса — Монро. Оба эти процесса могут быть использованы для построения итеративных методов решения задач стохастического программирования (см. 7). [c.351]
Условия сходимости случайных процессов, определяемых схемами стохастической аппроксимации, можно рассматривать как условия устойчивости (в том или ином вероятностном смысле) решений стохастических разностных (или дифференциальных) уравнений. Поэтому для исследования сходимости итеративных процедур стохастической аппроксимации естественно использовать методы анализа устойчивости решений стохастических уравнений, в частности, аналоги прямого метода Ляпунова. В этом направлении ряд результатов получены Т. Морозаном [208], Э. М. Браверманом и Л. И. Розоноэром [36] и (для непрерывных процедур стохастической аппроксимации) Р. 3. Хась-минским [295]. ( [c.354]
Общие результаты по многомерной (конечно-мерной или бесконечно-мерной) дискретной стохастической аппроксимации получены Э. М. Браверманом и Л. И. Розонозром [36]. Рассматривается процесс, определяемый рекуррентными соотношениями вида [c.355]