Метод обобщенных стохастических градиентов, предложенный в работах [106 — 109], не предполагает дифференцируемости целевой функции задачи и не требует задания статистических характеристик случайных параметров условий задачи. Метод стохастических градиентов является общим методом стохастической аппроксимации (см. гл. 15). [c.181]
Чтобы после некоторого числа шагов, проведенных в окрестности искомой точки, не выйти из нее, необходимо потребовать стремления к нулю шага ап при п— оо. Таким образом, на классические методы стохастической аппроксимации можно смотреть как на итеративные методы (градиентного типа) решения безусловной экстремальной стохастической задачи [c.342]
В [277] предлагается метод стохастической аппроксимации точки, определяющей минимум функции регрессии f(x) на множестве -G — = х g(x) .Q]. Здесь схема стохастической аппроксимации сочетается с методом штрафных функций.. [c.357]
Условия сходимости непрерывных процедур стохастической аппроксимации гораздо жестче, чем для дискретного случая. Здесь ограничения накладываются не только на функцию регрессии f(x), но и на случайный процесс y(t, x). В этом принципиальное различие между непрерывными и дискретными методами стохастической аппроксимации. [c.376]
Логинов Н. В. Методы стохастической аппроксимации. — Автоматика и телемеханика , 1966, № 4, с. 185—204. [c.388]
Книга посвящена одному из важных разделов современной теории сложных систем — изучению количественных методов управ ления, планирования и проектирования в условиях неполной информации. В книге с единых позиций обсуждаются три группы математических методов методы прогнозирования поведения сложных систем, методы управления в условиях риска и неопределенности (стохастическое программирование) и методы адаптации и обучения (стохастическая аппроксимация). [c.2]
Методы адаптации представляют собой достаточно общий итеративный процесс решения задач стохастического программирования — процесс совершенствования решающих правил или статистических характеристик решающих распределений — по последовательным реализациям наборов случайных параметров условий задач. Формальная основа методов адаптации — различные обобщения схемы стохастической аппроксимации. [c.15]
Задача (8.18) решается известными методами выпуклого программирования (при заданных статистических характеристиках Мцк случайных величин rij) или с помощью процедур стохастической аппроксимации по последовательным реализациям случайных параметров условий задачи. [c.120]
Стохастическая аппроксимация — сравнительно молодая математическая дисциплина, проблематика которой представляет значительный интерес для теоретической статистики, для решения экстремальных задач в условиях неполной информации и для разнообразных приложений в естественных и технических науках. Статистики видят в стохастической аппроксимации новую процедуру выбора решений по ограниченной выборке. Для исследователей биологов, химиков или медиков стохастическая аппроксимация является экономным методом использования результатов наблюдений для практических выводов. Специалисты по автоматическому регулированию видят в стохастической аппроксимации общий подход к анализу разнообразных схем и моделей распознавания, идентификации, обучения и адаптации. Мы рассмотрим стохастическую аппроксимацию совсем с иной точки зрения. [c.341]
Стохастическая аппроксимация в широком смысле слова представляет собой общий метод решения условных экстремальных задач при неполной информации об исходных данных. Мы будем рассматривать стохастическую аппроксимацию как общий итеративный метод решения задач стохастического программирования по последовательным реализациям случайных наборов параметров условий задачи. Такой подход к стохастической аппроксимации влияет известным образом и на ее проблематику и направления развития. [c.341]
К методам второго класса отнесем итеративные методы, порождаемые стохастической аппроксимацией и ее естественными модификациями — методы постепенного совершенствования плана, основанные на последовательном предъявлении независимых наборов реализаций случайных параметров условий. [c.342]
Классические схемы стохастической аппроксимации представляют собой, таким образом, итеративные методы градиентного типа. На каждом шаге процесса происходит сдвиг в случайном направлении, определяемом реализованными значениями случайных исходных данных и схемой отдельной итерации. На одних шагах мы приближаемся к искомому оптимуму, на других удаляемся от него. Однако процедуры стохастической аппроксимации гарантируют большую вероятность сдвига в нужном направлении, чем в нежелательном. В среднем за каждую итерацию происходит сдвиг в требуемом направлении. За большое число итераций в соответствии с законом больших чисел обеспечивается почти наверное приближение к искомой оптимальной точке (если она единственна). Для того чтобы добраться до оптимума из сколь угодно удаленной от него начальной точки и при этом обеспечить достаточное количество итераций, необходимое для проявления закона больших чи- [c.342]
В настоящей главе кратко излагаются основные схемы стохастической аппроксимации и обсуждаются обобщения теории и методов, позволяющие строить итеративные вычислительные процедуры решения задач стохастического программирования. [c.343]
В настоящей главе под стохастической аппроксимацией подразумевается теория и итеративные методы решения задач стохастического программирования по последовательным реализациям наборов случайных параметров условий задачи. [c.345]
Естественно, что стохастическая аппроксимация как итеративный метод решения задач стохастического программирования представляет интерес только в многомерном случае. Это, однако, не единственный аргумент в пользу многомерных модификаций процедур стохастической аппроксимации. Различные причины заставляют конструктора в процессе проектирования и создания экспериментального образца сложной системы довольствоваться не наилучшими решениями. Однако при испытаниях системы возникает возможность совершенствовать ее качество, подбирая экспериментальным образом . значения регулируемых параметров и оценивая при этом величину показателя эффективности системы. Ошибки измерений и отсутствие информации о виде функциональной зависимости показателя качества системы от измеряемых параметров усложняют истолкование и использование экспериментальных данных для доводки образца. Опытные инженеры интуитивно используют для совершенствования систем по результатам испытаний схемы типа многомерной стохастической аппроксимации. Задача теории — оценить допустимый диапазон применения этих методов, модифицировать их, упростить вычисления и ускорить сходимость. [c.351]
В литературе по стохастической аппроксимации наметились два подхода к анализу скорости сходимости итеративных методов. Первый подход (см., например, [322]) основан на непосредственном изучении асимптотического поведения моментов т( . При втором подходе (см. [244]) асимптотические свойства оценок изучаются при помощи аппарата типа центральной предельной теоремы теории вероятностей. [c.362]
Стохастическое управление - это еще одна общая схема для решения задач общего характера. Он применим к тем задачам, где можно реально оперировать в пространстве состояний, т.е. к задачам с тремя или четырьмя (самое большое) переменными. Как и при стохастическом программировании, трудно сгенерировать доверительные пределы. Ошибки моделирования могут также возникать из-за аппроксимации в пространстве состояний. Трудность в точном определении общих ограничений на процесс сужает область приложений метода стохастического контроля. Однако метод имеет концептуальное превосходство над стохастическим программированием (в тех случаях, когда метод может быть реализован на практике), [c.21]
Основа концепции имитационного инструментария, с помощью которого можно проводить структурный анализ и имитационное моделирование, заключается в механизмах, позволяющих агрегировать элементарные процессы и устанавливать между ними функциональные связи (причинно-следственные, информационные, финансовые и иные). Ниже предлагается сетевая концепция, существенно отличающаяся от аналитического аппарата, рассмотренного в литературе по теории массового обслуживания, использующая удачные результаты теории стохастических сетей и численные методы, основанные на диффузной аппроксимации процессов массового обслуживания. [c.40]
Принципы аппроксимации и последовательного приближения в классе стохастических задач предоставляют широкое поле для маневра и выбора конкретного метода в конкретной задаче. [c.71]
Требование одноэкстремальности функции регрессии ограничивает область приложения классических методов стохастической аппроксимации. В частности, для того чтобы использовать процедуры стохастической аппроксимации в качестве итеративных методов стохастиче- [c.368]
В 1заключительной, 16-й главе стохастическая аппроксимация и ее обобщения рассматриваются как общие итеративные методы решения 6 [c.6]
Обзор работ по специальной задаче стохастического программирования — задаче фильтрации и прогноза — и по итеративным методам стохастического программирования, связанным со стохастической аппроксимацией, приведены соответственно в гл. 14 и 15 настоящей монографии. Попытки получения общего подхода к различным схемам стохастического программирования предпринимались в работах И. Лемари [183], Д. Б. Юдина (352, 353], Ю. М. Ермольева [105, 107]. [c.18]
Условия, при которых классические процедуры стохастической аппроксимации сходятся к искомому экстремуму, требуют выпуклости или по крайней мере одноэкстремальности функции -Мш (со, х) по х. Это значит, что для использования стохастической аппроксимации в качестве итеративного метода решения задач стохастического программирования необходимо модифицировать классические схемы применительно к задачам условной оптимизации и отказаться от требования выпуклости или одноэкстремальности Мщ<р (ш, х). [c.343]
Чтобы расширить круг задач стохастического программирования, для которых стохастическая аппроксимация может служить итеративным методом решения, целесообразно также отказаться от рассмотрения ошибок наблюдения как аддитивного шума, наложенного на детер-. минированный процесс аппроксимации. На. этом предположении основано доказательство сходимости большинства вычислительных схем стохастической аппроксимации. Некоторые задачи стохастического программирования (см., например, 5 гл. 14 Обобщенные задачи фильтрации и прогноза ) требуют разработки итеративных процессов оптимизации функционалов вида / (Мш<р (ю, х)) на некотором множестве X. Итеративные процессы решения некоторых классов двухэтапных задач стохастического программирования должны обеспечить последовательную условную оптимизацию функционалов вида M JR М (ш,, о>2, хг,х2), [c.343]
В 2 рассматриваются классические схемы одномерной стохастической аппроксимации и некоторые их модификации. Основное внимание здесь уделяется итеративным процедурам решения безусловной экстремальной задачи вида (1.2). Параграф 3 посвящен условиям сходимости многомерных процессов стохастической аппроксимации. Помимо классических схем здесь излагаются и результаты, полученные в последние годы.. В 4 приводится обзор обобщений схем стохастической аппроксимации на случай решения условных экстремальных задач. Только в этом случае стохастическая аппроксимация может рассматриваться как итеративный метод стохастического программирования. В 5 исследуется важный для приложений вопрос о скорости сходимости и возможных путях ускорения сходимости процессов стохастической аппроксимации. Процедуры, рассмотренные в 6 и 7, позволяют в ряде случаев отказаться от основных допущений, на которых основаны классические схемы стохастической аппроксимации, — от одноэкстремальности целевого функционала задачи и несмещенности оценок наблюдаемых случайных величин. [c.343]
Т. Блум [31], Ж. Сакс [244] и другие обобщили схемы стохастической аппроксимации на многомерный случай. Кратко опишем не только многомерный аналог процедуры Кифера — Вольфовица оптимизации одноэкстремальной функции регрессии, но и многомерный аналог схемы Роббинса — Монро. Оба эти процесса могут быть использованы для построения итеративных методов решения задач стохастического программирования (см. 7). [c.351]
Условия сходимости случайных процессов, определяемых схемами стохастической аппроксимации, можно рассматривать как условия устойчивости (в том или ином вероятностном смысле) решений стохастических разностных (или дифференциальных) уравнений. Поэтому для исследования сходимости итеративных процедур стохастической аппроксимации естественно использовать методы анализа устойчивости решений стохастических уравнений, в частности, аналоги прямого метода Ляпунова. В этом направлении ряд результатов получены Т. Морозаном [208], Э. М. Браверманом и Л. И. Розоноэром [36] и (для непрерывных процедур стохастической аппроксимации) Р. 3. Хась-минским [295]. ( [c.354]
Задачи стохастического программирования представляют собой условные экстремальные задачи. Поэтому подход к стохастической аппроксимации как к системе итеративных методов стохастического программирования требует обобщения процедур, разработанных для без-1 условных экстремальных задач, на случай задач с ограничениями. В [9] этот вопрос обходится, поскольку здесь с самого начала предполагается, что рассматриваемые итеративные алгоритмы не выводят траектории процесса из некоторого ограниченного замкнутого множества. В [304] предложены алгоритмы стохастической аппроксимации для условных экстремальных задач, в которых ограничения представляют собой равенства, содержащие функции регрессии некоторых величин, зависящих от искомого набора параметров. Алгоритмы используют классические схемы стохастической аппроксимации применительно к функции Лаграижа условной экстремальной задачи. Однако условия сходимости в [304] не сформулированы. [c.357]