Метод обобщенных стохастических градиентов [c.181]
Метод обобщенных стохастических градиентов, предложенный в работах [106 — 109], не предполагает дифференцируемости целевой функции задачи и не требует задания статистических характеристик случайных параметров условий задачи. Метод стохастических градиентов является общим методом стохастической аппроксимации (см. гл. 15). [c.181]
Метод стохастических градиентов может быть использован также для решения нелинейной двухэтапной стохастической задачи. [c.181]
Применение метода обобщенных стохастических градиентов основано на следующих соображениях. [c.181]
Численные методы анализа многоэтапных стохастических задач в жесткой постановке весьма громоздки, и с увеличением размерности управлений и числа этапов трудоемкость решения задач быстро растет. Методы динамического программирования перестают быть эффективными уже при размерности состояний системы, равной трем. Методы, основанные на схемах блочного программирования, применимы лишь при конечном (относительно небольшом) числе реализаций наборов параметров условий задачи. Метод стохастического градиента неконструктивен при числе этапов, большем двух. Теоретически корректный метод случайного поиска, предложенный в [ПО], связан с большими вычислительными трудностями. [c.202]
В частных случаях, рассмотренных в гл. 8, для вычисления Xi — решения задачи первого этапа — имеются конструктивные приемы. В общем случае, когда задача первого этапа оказывается выпуклой и область K=Ki П Kz ее определения задана явно, можно вычислить xi по методу стохастического градиента [107]. Знание je i=J i позволяет сократить число этапов в исходной задаче на единицу. Параметры условий полученной таким образом задачи зависят от реализации MI. В некоторых задачах специальной структуры параметрические методы исключают необходимость в решении множества задач, определяемых возможными реализациями он. В общем случае требуются весьма громоздкие вычисления. Для некоторого набора реализаций он, выбор которого обусловлен структурой задачи, следует, используя, например, метод стохастических градиентов, вычислить узлы сетки (таблицы). значений x z( i), по которой можно восстановить с требуемой точностью значения составляющих x z(u)i) для произвольной реализации он. Этот процесс может быть продолжен. Однако с увеличением числа этапов трудоемкость вычислений и требования к памяти чрезвычайно быстро растут. При немалых п представляется более перспективным сведение многоэтапной задачи к вычислению апостериорных решающих правил одноэтапных задач. Если восстановление априорных решающих правил исходной задачи по апостериорным решающим правилам одноэтапной задачи связано со значительными вычислительными трудностями, целесообразно после вычисления x i рассматривать второй этап задачи (6.7) — (6.9) (при каждой реализации oi) как одноэтапную-задачу с апостериорными решающими правилами. [c.254]
Оптимальное решающее правило х задачи первого этапа вычисляется, например, по методу стохастических градиентов. Переход к априорным оптимальным решающим правилам х ( шь-1) исходной многоэтапной задачи (7.1) — (7.3) производится по формулам (6.10). В рассматриваемом примере они имеют вид [c.260]
Для решения последней задачи может быть использован метод стохастических градиентов [c.376]
Заметим, что в [304] рассматривается более сложная задача безусловной минимизации сложной функции R(f(x), x) без ограничений по наблюдениям искаженных ошибками компонент вектор-функции f, их градиентов, функции У и ее градиента. Предполагается, что ошибки наблюдения независимы между собой и имеют нулевое математическое ожидание. Для решения задачи предлагается алгоритм градиентного типа. Однако условия сходимости соответствующей схемы стохастической аппроксимации в [304] не приводятся. [c.376]
Известны строгие математические методы решения задач оптимизации (например, симплекс-метод и распределительный метод для линейных задач, метод градиента для задач нелинейных, методы Беллмана для задач динамического планирования и т. д.). Но в аудите эти методы в настоящее время не применимы в силу неразработанности формальных или стохастических (вероятностных) зависимостей между варьируемыми факторами, с одной стороны, параметрами оптимизации и ограничивающими функциями — с другой. Поэтому приближение к оптимальности достигается, как это предусмотрено общероссийским стандартом Планирование аудита , эмпирически — вариантностью планирования, выявлением в ходе планирования областей повышенного риска, корректированием принятых решений в ходе проверки. [c.137]
Как уже отмечалось, метод обобщенных стохастических градиентов не требует дифференцируемости целевой функции эквивалентной детерминированной задачи. Здесь мы рассмотрим возможный вариант применения метода возможных направлений к решению двух-этапной задачи линейного стохастического программирования. Использование и обоснование этого метода требует существования и непрерывности градиента целевой функции эквивалентной детерминированной задачи. В 4 гл. 6 указывалось, что для этого достаточно, чтобы вероятностная мера была абсолютно непрерывна относительно меры Лебега. Как и при изложении других методов, будем предполагать возможность вычисления всех математических ожиданий, значения которых используются в излагаемом ниже алгоритме. [c.189]
Случайный вектор уп, удовлетворяющий условию (4.5), называется стохастическим квазиградиентом функции f(x) в точке хп. Если а 1, bn=szQ, то уп называется стохастическим обобщенным градиентом, а если f(x) непрерывно дифференцируема — стохастическим градиентом. [c.359]
Ермольев Ю. М., Не Крылова 3. В. Метод стохастических градиентов и его применение. — В кн. Теория оптимальных решений , Киев, ИК АН УССР, 1967, с. 24—47. [c.385]
Базовой идеей всех алгоритмов обучения является учет локального градиента в пространстве конфигураций для выбора траектории быстрейшего спуска по функции ошибки. Функция ошибки, однако, может иметь множество локальных минимумов, представляющих суб-оптимальные решения. Поэтому градиентные методы обычно дополняются элементами стохастической оптимизации, чтобы предотвратить застревание конфигурации сети в таких локальных минимумах. Идеальный метод обучения должен найти глобальный оптимум конфигурации сети4. [c.45]
Разработан ряд стохастических методов решения поставленной оптимизационной задачи распараллеливания вычислений. В первом методе — стохастическом методе попарной оптимизации подграфов — поиск оптимального решения осуществляется за счет взаимного (стохастического) переноса вершин между различными парами подграфов графа алгоритма. Второй метод — метод Монте-Карло случайного блуждания вершин графа алгоритма по подграфам — основан на отождествлении вершин графа алгоритма с некоторыми частицами, совершающими случайные блуждания по областям-подграфам в потенциальном силовом поле, роль потенциала которого играет минимизируемый функционал. Наиболее вероятное состояние подобной системы частиц соответствует минимуму потенциала —-и, следовательно, является искомым решением. Поиск такого состояния осуществляется методом Монте-Карло с использованием специальной процедуры имитации отжига . Третий метод — стохастический метод наискорейшего спуска — основан на использовании дискретного аналога градиента минимизируемого функционала. Все разработанные методы реализованы программно и являются частью системы программ PARALLAX. Проведено тестирование созданных программ и сравнение их работы на простейших примерах. [c.166]