автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Выпуклый анализ в задачах стохастического оптимального управления

Введение

Глава 1. Элементы выпуклого анализа

Абстрактная задача выпуклого программирования (ЗВП)

Существование решения ЗВП с конечным числом ограничений и его вид

Ограничения существенные и несущественные Парето-оптимальные решения Уравнение динамического программирования как ЗВП

Алгоритм решения ЗВП при аффинных ограничениях

Основные результаты главы

Глава 2. Задачи стохастического оптимального управления

Описание управляемой модели

Свойства пространства стратегических мер

Методы выпуклого анализа

Марковские модели: меры замещения и их свойства Модели с ограничениями на управление Основные результаты главы

Глава 3. Задачи с функциональными ограничениями

Постановка задачи

Разрешимость задачи, необходимые и достаточные условия оптимальности, существенность ограничений, свойства множества Парето и алгоритм решения

Вид оптимальной стратегии

Построение оптимальных стратегий

Выпуклые модели

Неатомические модели Основные результаты главы

Глава 4. Линейно-квадратичные системы

Модель с конечным горизонтом Однородная дисконтированная модель Однородная модель со средними потерями Основные результаты главы

Глава 5. Примеры и приложения

Система массового обслуживания с управляемой интенсивностью

Стохастическая модель макроэкономики Управляемая эколого-экономическая система Модель страхования Стохастическая задача стабилизации Оптимизация затрат на рекламу Основные результаты главы

Теория управляемых случайных процессов была подготовлена работами А. Вальда [292, 293] в конце 40-х годов. Первые определения управляемых случайных процессов приведены С. Карлином [216] и Р. Беллманом [131], но возникновение самостоятельной теории следует отнести к концу 50-х годов, когда появились известные монографии Р. Беллмана [132] и P.A. Ховарда [210]. Достаточно полное представление о современном состоянии вопроса можно получить из монографий [6, 8, 17, 29, 41, 50, 53, 69, 82, 84, 86, 89, 95, 111, 134, 148, 157, 160, 166, 186, 195, 222, 223, 240, 257, 282] и обзоров [72, 105, 123, 197, 215, 229, 284]. Приведенный ниже краткий обзор не претендует на полноту, тем более что настоящая работа не лежит в русле динамического программирования.

Большинство работ по стохастическому оптимальному управлению в 60-е - 80-е годы базируется на идеях Р.Беллмана [13, 29, 132, 134], которые успешно используются в детерминированных моделях [4], при поиске путей на графе [58], при решении дифференциальных уравнений [13] и во многих других случаях. Если в [131] изучались конечные модели, то уже JI.Дубине и Л.Сэвидж [170] рассматривали процессы с произвольными борелевскими пространствами состояний и управлений. Наиболее законченный вид имеет классическая теория "полунепрерывных" моделей, хотя отдельные авторы начинали исследовать общие измеримые модели [282].

Имеется большое число различных задач стохастического оптимального управления: с конечным неслучайным временем жизни (то есть с "конечным горизонтом"), с дисконтированием, со средими потерями, с неполной информацией, задачи оптимальной остановки и т.д. По типу случайного процесса можно выделить марковские и немарковские последовательности (т.е. случай дискретного времени), скачкообразные [38, 59, 62, 70, 103, 104], диффузионные [8, 41, 50, 89, 186] процессы и прочие. Настоящая работа посвящена моделям с дискретным временем при полной информации, поэтому остановимся на подобных управляемых процессах более подробно.

Если управляемый случайный процесс развивается в дискретном времени и задан стохастическим ядром, не зависящим от прошлых состояний, то его называют марковским процессом принятия решений; марковская модель называется однородной, если ее характеристики не зависят от времени.

Дисконтированные модели изучались Д.Блекуэллом [141, 142], Р.Штраухом [281], А.Маитрой [230] и другими авторами: получено уравнение Беллмана, сформулированы необходимые и достаточные условия оптимальности, очерчен достаточный класс стратегий (стационарные селекторы), решены конкретные примеры. В диссертации селектором для краткости называется нерандомизированная стратегия управления; под стационарностью понимается независимость от времени.

В отличие от моделей с интегральными функционалами, в полунепрерывной модели со средними потерями может не существовать решения задачи оптимального управления (см. соответствующий пример в [29], с.213-214). В этом случае обычно накладываются дополнительные условия типа эргодичности при любом стационарном селекторе. Хорошо проработан случай, когда существует "каноническая система". Это направление было инициировано статьей А.А.Юшкевича [101]. В случае конечных пространств такая система существует всегда [29], с.203; кроме того, она существует в моделях с минорантой (там же). Если пространства X, А конечны, то решение канонической системы уравнений можно построить с помощью процедуры усовершенствования Ховарда [29, 210]. В монографии [210] утверждалось лишь, что построенный селектор является наилучшей стратегией среди стационарных. Позднее С.Дерман [164] и О.В.Висков и А.Н.Ширяев [14] независимо доказали, что он действительно является наилучшим среди всех стратегий.

У истоков теории с неполной информацией стояли Р.Беллман [130], Е.Б.Дынкин [27], Т.Йошикава, Й.Савариги [268] А.Н.Ширяев [97, 98], А.А.Юшкевич [102]. В конечном счете обычно удается построить новую более сложную управляемую модель с полной информацией, решение которой дает ответ для исходной задачи с неполными данными. Это так называемый байесовский подход. Другое направление здесь связано с адаптивным управлением [86, 125, 152].

Из ученых, внесших весомый вклад в классическую теорию стохастического оптимального управления (при дискретном времени) нельзя не упомянуть также В.И.Аркина и И.В.Евстигнеева [6], В.В.Баранова [10, 11], Д.Бертсекаса и С.Шрива [134], П.Варайю [287], И.И.Гихмана и А.В.Скорохода [17], Н.В.Крылова [48, 49], Г.Дж.Куш-нера [222], Э.Л.Пресмана и И.М.Сонина [82], Г.Роббинса [157], М.Шела [269, 270, 271, 272].

Уже начиная с 60-х годов при исследовании конечных моделей со средними потерями применяется метод линейного программирования [162, 163, 164, 205, 215, 235, 245]. Связь процедуры Ховарда (для решения канонической системы) с симплекс-методом обсуждается в [240]. Исследование дисконтированной модели также можно свести к задаче линейного программирования (в дальнейшем - ЗЛП). Первыми статьями на эту тему являются работы [161,191], которые послужили толчком для возникновения в 80-х годах нового направления в стохастическом оптимальном управлении, основанного на идеях абстрактного выпуклого анализа. Дальнейшему развитию этого направления и посвящена настоящая работа.

Собственно говоря, теория выпуклого программирования (в частности линейного) долгое время развивалась, почти не пересекаясь с методом динамического программирования и стохастическим оптимальным управлением. Попутно отметим, что в детерминированной теории оптимальных процессов дело обстоит иначе, так как здесь широкое распространение получил принцип максимума Понтрягина, целиком основанный на идеях выпуклого анализа [2]. А в стохастическом случае основным инструментом является метод динамического программирования, хотя и принцип максимума тоже известен достаточно давно [6, 7].

Определенный итог в области конечномерного выпуклого анализа был подведен в известной монографии [259]. Но уже в конце 50-х годов [124] становится ясно, что многие идеи легко переносятся на бесконечномерный случай (гильбертовы и произвольные топологические линейные пространства). В частности, сохраняются методы исследования задач выпуклого программирования: аппарат субдифференциалов, теория двойственности, метод множителей Лагранжа и теорема Куна-Таккера. Указанные подходы изложены, например, в [54, 228, 260]. Некоторые успехи имеются и при использовании этих методов для невыпуклых задач [56, 280].

Выпуклый анализ и в особенности теория двойственности достаточно широко используются при решении задач фильтрации и оценивания параметров в моделях с неполной информацией [53, 85, 236]. Естественным образом и достаточно давно они применяются в теории игр [246], в том числе стохастических и дифференциальных [96, 111]. Для задач стохастического оптимального управления эти методы начали применяться с конца 80-х годов. Литературный обзор результатов, полученных в этом направлении, содержится в работе автора [72].

Важнейшей заслугой В.Боркара является введение понятия "меры замещения" (примерно так можно перевести термин "occupation measure"). Оказывается, при определенных условиях функционал средних потерь можно представить в виде интеграла от функции потерь на одном шаге по некоторой мере. Совокупность всех таких мер при различных стратегиях (эргодических мер замещения) образует выпуклый компакт. В итоге получаем типичную задачу выпуклого программирования: найти эргодическую меру замещения, дающую минимальное значение интеграла от заданной непрерывной функции. Этот подход, использованный в [146, 147], нашел много последователей, так как очень быстро стало ясно, что он работоспособен в задачах с функциональными ограничениями. Практически во всех работах В.Боркара [146, 147, 148, 149] пространство состояний счетно, а модель полунепрерывна. Счетные модели аналогичным образом исследовались другими авторами в [108, 111, 119, 123, 208, 222] (пространство управлений либо конечно, либо счетно, либо компактно). Работы [122, 166, 169, 207, 296] были посвящены полностью конечным моделям. Пристальное внимание к моделям с дискретным множеством состояний объясняется их важностью применительно к теории массового обслуживания. Использование этого же подхода для моделей с произвольными борелевскими пространствами изложено в [201]. Модели со средними потерями при функциональных ограничениях изучали Е.Альтман [107, 108, 111, 112, 114, 115, 116, 117, 118, 119, 120, 285], С.Дерман [166, 169], А.Хордийк и Л.Калленберг [207, 211, 214, 215], А.Маковски и А.Шварц [229, 231, 232, 233, 275] и другие авторы [87, 135, 274, 294, 295]; вариант "эргодического" управления рассмотрен в [123, 148, 149, 263]. Во всех указанных работах, за исключением [233], рассматривались дискретные модели (в дальнейшем так называются модели с конечным или счетным пространством состояний). Примеры решения конкретных задач с ограничениями при средних потерях содержатся в [107, 108, 114, 115, 119, 177, 209, 229, 233, 241, 274, 275]. В своей массе они относятся к теории массового обслуживания. В отличие от классических однокритериальных задач, класса стационарных селекторов здесь не достаточно: решение дается либо стационарной рандомизированной стратегией, либо взвесью (выпуклой комбинацией) стационарных селекторов, либо нестационарным (как правило, немарковским) селектором. В статьях [87, 116, 117, 118] предложены методы построения оптимальной адаптивной стратегии в условиях неполной информации.

Подход с позиций выпуклого анализа к дисконтированным моделям использован в [108, 109, 147, 148, 151, 166, 197, 198, 200, 202, 203, 206, 214, 215]: функционал потерь выражается интегралом от функции потерь на одном шаге по дисконтированной мере замещения. За исключением [198, 200, 202], изучались дискретные модели. Задачи с дисконтированием при функциональных ограничениях исследовали Е.Альтман [107, 108, 111, 112, 113, 116, 118], В.Боркар [148], Е.Файнберг [179, 180, 181], А.Маковски и А.Шварц [233], А.Хордийк и Л.Калленберг [206, 214, 215] и другие авторы [52, 94, 273, 283, 290]. В основном они также сосредоточили внимание на конечных или счетных моделях. На примере дисконтированных моделей достаточно легко продемонстрировать, что соотношения, выражающие принцип Беллмана (в пространстве функций от состояния), и формулировка исходной задачи с позиций выпуклого анализа (в пространстве мер замещения) являются взаимно двойственными. Это же наблюдение имеет место и в моделях со средними потерями, и во всех прочих случаях (конечный горизонт и т.д.). Подобного рода двойственность в последние годы привлекает особое внимание Дж.Лассерра и

О.Хернандез-Лерма [200, 201, 202]. Примеры решения конкретных задач с ограничениями при дисконтировании можно найти в [111, 181]. В отличие от классических однокритериальных задач класса стационарных селекторов здесь не достаточно: решение дается либо стационарной рандомизированной стратегией, либо взвесью стационарных селекторов; больше того, оно зависит от начального распределения состояний.

Подход с позиций выпуклого анализа к общим моделям с суммарными потерями (в частности, при конечном времени жизни) использован в [109, 110, 147, 148, 167, 172, 214]. Соответствующие задачи при функциональных ограничениях исследовали Е.Альтман [109, 110, 111], В.Боркар [148], С.Дерман [167], Е.Файнберг и А.Шварц [179], А.Хордийк и Л.Калленберг [206, 214, 215], а также Г.Кушнер [222]. В основном шла речь о дискретных моделях. Примеры (относящиеся к области линейно-квадратичных систем) можно найти в [31, 227]; некоторые численные методы в случае конечных пространств обсуждались в [90, 91]. В общей ситуации решение задач с функциональными ограничениями в неоднородной марковской модели дается либо рандомизированной марковской стратегией, либо взвесью марковских селекторов. Кроме того, решение существенно зависит от начального распределения состояний.

Понятно, что использование методов выпуклого анализа предполагает глубокое исследование пространств стратегических мер и мер замещения. В этом отношении трудно переоценить результаты, полученные М.Шелом [269] и его последователями [127, 244], установившими компактность пространства стратегических мер для полунепрерывных моделей.

Возникающие в итоге задачи выпуклого программирования на пространствах мер представляют собой интересный и нетривиальный объект исследования с точки зрения вычислительной математики, особенно в случае неконечных моделей. Некоторые результаты в этом направлении содержатся в [90, 91, 108, 111, 238, 290]. Чувствительность решения к исходным данным обсуждалась в [107, 111, 112, 113, 118].

В целом, из изучения приведенных обзорных материалов следует:

1) Методы выпуклого анализа в стохастическом оптимальном управлении используются лишь в течение последних десяти лет.

2) В подавляющем большинстве работ изучались дискретные модели (с конечным или счетным множеством состояний).

3) Первый этап исследования заключается в формулировке задачи оптимального управления в виде задачи выпуклого программирования: найти меру из заданного выпуклого множества Т>, дающую минимальное значение интеграла от заданной функции потерь на одном шаге. (Возможно, при ограничениях-неравенствах.)

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

5) Третий этап заключается в описании достаточного класса стратегий. Так как интеграл - линейная операция, его экстремум достигается в крайней точке множества допустимых мер. В случае оптимизационной задачи без функциональных ограничений получаем достаточность селекторов (марковских или стационарных в соответствующих моделях). Если же имеются ограничения, то с помощью теоремы Каратеодори устанавливается достаточность конечных взвесей селекторов. (Число слагаемых на единицу больше числа ограничений.)

6) В задаче с функциональными ограничениями справедлива теорема Куна-Таккера при весьма общих предположениях (условие Слей-тера и пр.), которая дает необходимые и достаточные условия оптимальности и устанавливает соотношение двойственности.

7) Четвертый серьезный этап состоит в разработке численных методов решения сформулированной и аналитически исследованной задачи выпуклого программирования.

8) Наконец, в задаче с несколькими функционалами качества исследуется существенность ограничений, строится множество Парето и т.д.

Изложенную схему можно реализовать по-разному даже для одной и той же задачи. Например, можно по-разному вводить топологию на пространстве мер Т>. Чаще всего рассматривается классическая слабая топология, но иногда удобны и другие типы (например, слабо-сильная [269]); впрочем, в настоящей работе всегда фиксируется именно слабая сходимость мер. Следует сразу же отметить, что в задачах без ограничений методы выпуклого анализа не дают ничего принципиально нового по сравнению с методом динамического программирования, который, как уже отмечалось, является формально двойственным. Напротив, в задачах с функциональными ограничениями метод динамического программирования использовать трудно, а методы выпуклого анализа остаются работоспособными.

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

1) Разработка алгоритма решения задачи выпуклого программирования с аффинными ограничениями, работоспособного в абстрактных топологических линейных пространствах.

2) Доказательство двойственности метода динамического программирования (в пространстве функций состояния) и метода выпуклого анализа (в пространстве мер замещения) для общих борелевских моделей.

3) Исследование пространств стратегических мер и мер замещения: доказательство выпуклости и компактности, изучение множества крайних точек и пр.

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

5) Разработка конструктивных методов решения задач с функциональными ограничениями.

6) Решение задач оптимального управления для линейно-квадратичных систем с функциональными ограничениями.

7) Использование разработанных теоретических методов для решения практических содержательных задач из различных областей (теория массового обслуживания, экономика, экология, техника).

Указанным вопросам посвящены работы автора [59]-[80], [248]-[256]. Основные результаты диссертации докладывались и обсуждались на научных семинарах ГосИФТП, МГИЭМ, МАИ, МГУ, ЦЭМИ, МИРАН, Strathclyde University (Glasgow), SOSSO-INRIA (Paris), а также на 11-м Всемирном конгрессе IFAC [250], 1-й и 2-й Всероссийских школах по стохастическим методам [65, 67], 3-й Европейской конференции по теории управления (ЕСС) [251]. Доклады по теме настоящей работы включены в труды XI Всесоюзного совещания по проблемам управления [77], 13-го Всемирного конгресса IFAC [252], 3-й, 4-й и 5-й Всероссийских школ по стохастическим методам [71, 74, 80], 4-й Европейской конференции по теории управления (ЕСС) [254], 15-го Всемирного конгресса IMACS [255].

Диссертационная работа состоит из введения, пяти глав основных исследований и заключения. В первой главе приводятся известные факты выпуклого анализа в удобной формулировке и доказываются лишь несложные, достаточно очевидные утверждения. Новыми являются алгоритм решения задачи выпуклого программирования с аффинными ограничениями и анализ уравнения Беллмана с позиций теории двойственности.

5.7. Основные результаты главы 5

1. Проведено всестороннее исследование простой системы массового обслуживания с управляемой интенсивностью. На этом примере, представляющем собой задачу оптимального управления с функциональными ограничениями, проиллюстрированы все теоретические результаты разделов 2.4.2, 3.2, 3.3, 3.4.2, 3.5. За исключением выпуклой модификации, ответом во всех вариантах задачи является рандомизированная стратегия управления (марковская или стационарная), которая зависит от начального распределения состояний в случае дисконтированных функционалов потерь. Аналогичные наблюдения имеют место и во всех других задачах, изложенных в настоящей главе. Напротив, при решении классических задач оптимизации без ограничений достаточно ограничиться нерандомизированными стратегиями, не зависящими от начального распределения.

2. Сформулированы и решены две задачи оптимального управления эколого-экономическими системами макроуровня. Подобные задачи обычно являются многокритериальными: как минимум, существуют экономические и экологические показатели. Построение приемлемых решений проведено методом введения ограничений; разработанные в предыдущих главах формальные методы позволили получить оптимальные (или квазиоптимальные) стратегии управления экономической подсистемой.

3. Построена и исследована простая модель страхования с выплатой дивидендов и двумя показателями качества: среднее время жизни и суммарный объем выплаченных дивидендов.

4. Рассмотрена классическая задача стабилизации технической системы с двумя показателями качества: расходы на управление и штраф за отклонение объекта от расчетного положения. Построение приемлемых решений проведено методом введения ограничений.

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

6. Для всех рассмотренных моделей построено множество Парето (неулучшаемых решений в многокритериальной задаче).