Sequential importance sampling algorithms for dynamic stochastic programming

В статье дается исчерпывающее изложение последовательных алгоритмов выборки по значимости для задач динамического (многоступенчатого) стохастического программирования, основанных на ожидаемом значении совершенной информации. Обсуждается как теория, так и вычислительные алгоритмы. При общих предположениях показано, что процесс ожидаемого значения совершенной информации (EVPI-процесс) и маргинальный EVPI-процесс (супремум-норма условного ожидания его обобщенной производной) являются неупреждающими неотрицательными супермартингалами. Эти процессы используются как критерии значимости в классе выборочных алгоритмов, рассматриваемых в статье. Если в вершине дерева сценариев выборочной задачи их значения пренебрежимо малы, то сценарии, являющиеся потомками этой вершины, при следующей итерации заменяются единственным сценарием. С другой стороны, большие значения ведут к увеличению числа сценариев, являющихся потомками данной вершины. Получены оценки для свойств малых выборок и асимптотических свойств выборочной задачи, даваемые описанными алгоритмами. Оценки первого типа численно исследованы в контексте задачи финансового планирования. Наконец, в работе описано, над чем ведется работа в настоящее время и что предполагается исследовать в дальнейшем. Библ. – 49 назв.