Современные методы решения задачи оптимального управления в экономике

Полный текст

Научная новизна исследования

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

Введение

Оптимальное управление – это применение математических принципов к заданной динамической системе с целью определения ее входных параметров, позволяющих оптимизировать функционирование системы за счет минимизации или максимизации ее выходных параметров, описывается в виде заданного индекса производительности, полностью удовлетворяя заданным ограничениям системы. Другими словами, для данной динамической системы с заданными ограничениями оптимальное управление стремится максимизировать или минимизировать индекс производительности этой системы с использованием математических методов. Для описания этой задачи оптимизации используется термин «задача оптимального управления» (ЗОП). Принцип оптимального управления был впервые предложен русским математиком Львом Семеновичом Понтрягиным в 1950-х годах, а затем сформулирован в виде Принципа максимума Понтрягина, который Понтрягин и его ученики использовали для поиска метода управления динамической системой, переходящей из одного состояния в другое при наличии заранее заданных ограничений состояния или входных элементов управления. Позже в своей статье 1969 года Дорфман [1] вывел метод решения задачи оптимального управления, рассмотрев экономический аспект проблемы.

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

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

1. $x\left(t\right)$ – функция состояния, описывающая поведение системы, $u$;
2. $u\left(t\right)$– функция управления, направляющая эволюцию системы от одного шага к другому.

Поиску путей решения задачи оптимального управления наиболее эффективным способом посвящено множество различных работ [2–7]. Однако эти методы либо не позволяют достичь аналитического решения задачи оптимального управления, либо метод оказывается слишком сложным для решения. На этом фоне исследователи обратились к численным методам решения задачи оптимального управления, основываясь на Принципе максимума Понтрягина. Здесь численные методы делятся на два типа: прямые методы и косвенные методы. Принцип максимума Понтрягина приводит к краевой и нелинейной задаче. В косвенном методе необходимо извлекать необходимые условия оптимальности в аналитическом виде, что часто трудно решить. Кроме того, область сходимости косвенного метода невелика, и, таким образом, в некоторых случаях, если начальное предположение выбрано неправильно, метод не будет сходиться. Поэтому для исследования численного поведения задачи оптимального управления используется прямой метод. Этот метод преобразует задачу оптимального управления в задачу алгебраической оптимизации.

Ниже приводится стандартная постановка задачи оптимального управления.

Задача оптимального управления: Определить состояние (эквивалентно, траектория или путь), $x\left(t\right)\in {\mathrm{ℝ}}^n$, управление $u\left(t\right)\in {\mathrm{ℝ}}^m$, вектор статических параметров $p\in {\mathrm{ℝ}}^q$, начальное время, $t_0\in \mathrm{ℝ}$, и терминальное время, $t_f\in \mathrm{ℝ}$ (где $t\in \left[t_0, t_f\right]$ — независимая переменная), которая оптимизирует индекс производительности

$J=\Phi \left[x\right(t_0), t_0,x(t_f),t_f;\text{ p}]+{\int }_{t_0}^{t_f}L\left[x\right(t),\text{u}(t),t;\text{ p}]dt$ (1)

с учетом динамических ограничений (т. е. ограничения дифференциального уравнения),

$\dot{x}\left(t\right)=f\left[x\right(t), \text{u}(t), t; \text{p}]$ (2)

ограничения пути

${\text{C}}_{\min }\le \text{C} [ x(t), \text{u}(t), t; p]\le {\text{C}}_{\max }$ (3)

и граничные условия

${\mathrm{\Phi }}_{min}\le \mathrm{\Phi }[ x(t_0), t_0, x(t_f), t_f; p]\le {\mathrm{\Phi }}_{max}$ (4)

Состояние, управление и статический параметр могут быть записаны в компонентной форме как

$x\left(t\right)=\left[\begin{array}{c}{x}_1\left(t\right)\\ ⋮\\ x_n\left(t\right)\end{array}\right]$; $\mathbf{u}\left(t\right)=\left[\begin{array}{c}{u}_1\left(t\right)\\ ⋮\\ u_m\left(t\right)\end{array}\right]$; $p=\left[\begin{array}{c}{p}_1\\ ⋮\\ p_q\end{array}\right]$.

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

 

Рисунок – Три основных компонента оптимального управления и класс методов, использующих каждый компонент [8]

Figure – Three main components of optimal control and a class of methods using each component [8]

 

Дифференциальное уравнение (2) описывает динамику системы, а индекс производительности измеряет «качество» траектории. Когда желательно минимизировать индекс производительности, более низкое значение $J$ «лучше»; наоборот, когда желательно максимизировать индекс производительности, более высокое значение $J$ «лучше».

Обычно задачу оптимального управления разбивают на этапы  и фазы связаны или связаны каким-то значимым образом. Многофазная задача оптимального управления ставится следующим образом. Оптимизировать стоимость

$J=\sum _{k=1}^p{J}^{\left(k\right)}$ (6)

[где стоимость на каждом этапе, $J^{\left(k\right)}, (k=1,... ,P)$,  имеет вид, указанный в уравнении (1)] с учетом динамических ограничений

${\dot{x}}^{\left(k\right)}\left(t\right) =f\left[x^{\left(k\right)}\right(t), {\text{u}}^{\left(k\right)}(t), t; {\text{p}}^{\left(k\right)}],$ (7)

граничные условия,

${\mathrm{\Phi }}_{\min }^{\left(\mathrm{k}\right)}\le {\mathrm{\Phi }}^{\left(\mathrm{k}\right)}\left({\mathrm{x}}^{\left(\mathrm{k}\right)} \left({\mathrm{t}}_{{}_0}^{\left(\mathrm{k}\right)}\right) , {\mathrm{t}}_{{}_0}^{\left(\mathrm{k}\right)},{\mathrm{x}}^{\left(\mathrm{k}\right)} ({\mathrm{t}}_{{}_{\mathrm{f}}}^{\left(\mathrm{k}\right)}\text{),} {\text{p}}^{\left(\mathrm{k}\right)}\text{, }{\mathrm{t}}_{{}_{\mathrm{f}}}^{\left(\mathrm{k}\right)}\right)\le {\mathrm{\Phi }}_{\max }^{\left(\mathrm{k}\right)},$ (8)

алгебраические ограничения пути

${\text{C}}_{{}_{\min }}^{\left(k\right)} \le {\text{C}}^{\left(k\right)} [ x^{\left(k\right)}(t), {\text{u}}^{\left(k\right)}(t), t; p^{\left(k\right)}] \le {\text{C}}_{{}_{\max }}^{\left(k\right)}$ (9)

и ограничения связи

${\text{L}}_{\min }^{\left(s\right)}\le \text{ L }\left(x^{\left(l_s\right)}\left(t_f^{\left(l_s\right)}\right),{\text{ u}}^{\left(l_s\right)}\left(t_f^{\left(l_s\right)}\right),{\text{ p}}^{\left(l_s\right)},t_f^{\left(l_s\right)};{\text{ x}}^{\left(r_s\right)}\left(t_f^{\left(r_s\right)}\right){\text{, u}}^{\left(r_s\right)}\left(t_f^{\left(r_s\right)}\right){\text{, p}}^{\left(r_s\right)}\text{, }{t}_f^{\left(r_s\right)}\right)\le {\text{ L}}_{\max }^{\left(s\right)}.$ (10)

В уравнении (10) параметр S – количество пар фаз, которые необходимо соединить, $r_s\in \left[1,..., S\right]$ и $l_s\in \left[1,... , S\right]$ – правые фазы и левые фазы, соответственно, пар связей, $r_s\ne l_s$ (означает, что фаза не может быть связана сама с собой), и $s\in \left[1,... , S\right]$ [8].

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

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

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

1. Численное решение системы дифференциальных уравнений и функций интегрирования;
2. Косвенным методом, сочетая как:
   
   1. численное решение системы дифференциальных уравнений и функций интегрирования;
   2. численное решение систем нелинейных уравнений, а;
3. Прямым методом, сочетая как
   
   1. численное решение системы дифференциальных уравнений и функций интегрирования;
   2. численное решение методом нелинейной оптимизации.

Мы рассмотрим вышеперечисленные методы каждый по очереди.

1. Численное решение системы дифференциальных уравнений и функций интегрирования

Рассмотрим начальную задачу (initial-value problem или IVP)

$\dot{x}=f\left(x\left(t\right),t\right),x\left(t_0\right)=x_0$ (11)

Кроме того, рассмотрим временной интервал $\left[t_i, t_{i+1}\right]$ , в течение которого желательно получить решение дифференциального уравнения. Другими словами, учитывая значение состояния в $t_i$, $x\left(t_i\right)\equiv x_i$, желательно получить состояние в $t_{i+1}$, $x\left(t_{i+1}\right)\equiv x_{i+1}$. Интегрируя уравнение (11), мы можем записать

$x_{i+1}\text{= }{x}_i+{\int }_{t_i}^{t_{i+1}}\dot{x}\left(s\right)ds=x_i+{\int }_{t_i}^{t_{i+1}}f\left(x\left(s\right),s\right)ds$ (12)

Существует два подхода к решению дифференциального уравнения: шаг по времени (time-marching) и коллокация. В таблице ниже представлены основные характеристики этих подходов.

 

Таблица – Методы, используемые для численного решения дифференциальных уравнений [9–15]

Table – Metods user for the numerical solution of differential equations [9–15]

 

При использовании подхода коллокации уравнение

$\dot{X}\left({\tau }_j\right)=f\left(x\left({\tau }_j\right),{\tau }_j\right),\left(j=\mathrm{1,...,}K\right)$ (13)

называется условием коллокации, потому что приближение к производной устанавливается равным правой части дифференциального уравнения, вычисляемого в каждой из промежуточных точек $\left({\tau }_1,... , {\tau }_K\right)$.

Существуют три основных категории методов коллокации.

1. Методы Гаусса – где ни одна из конечных точек $t_k$ или $t_{k+1}$ не является точкой коллокации.
2. Методы Radau – где не более одной из конечных точек $t_k$ или $t_{k+1}$ является точкой коллокации.
3. Методы Лобатто – где обе конечные точки $t_k$ и $t_{k+1}$ являются точками коллокации.

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

${\zeta }_j=\dot{X}\left({\tau }_j\right)-f\left(x\left({\tau }_j\right),{\tau }_j\right)$ (14)

Ограничения дефектов затем могут быть объединены в матрицу в виде

$Z=\left[\begin{array}{c}{\zeta }_1\\ ⋮\\ {\zeta }_M\end{array}\right]$ (15)

где $Z$ – функция коэффициентов $\left(a_0^{\left(k\right)}, ..., a_K^{\left(k\right)}\right)$, $\left(k-1, ..., K\right)$. Затем цель состоит в том, чтобы определить значения этих коэффициентов, которые приводят к $Z=0$.

2. Интеграция функций

Поскольку цель состоит в том, чтобы решить задачу оптимального управления, необходимо аппроксимировать функцию стоимости уравнения (1). Обычно стоимость аппроксимируется с помощью квадратуры, которая согласуется с численным методом решения дифференциального уравнения. Например, если для решения дифференциального уравнения используется прямое правило Эйлера, стоимость также будет аппроксимирована с использованием прямого интегрирования Эйлера. В случае метода ортогональной коллокации правило интегрирования представляет собой правило квадратуры с ортогональным расположением, например, если используются точки Лежандра-Гаусса, то стоимость Лагранжа аппроксимируется с использованием квадратуры Гаусса. Требование согласованности при аппроксимации дифференциальных уравнений и стоимости можно рассматривать и по-другому. Любая задача Больца может быть преобразована в задачу Майера путем добавления состояния $x_n + 1$ and adding the differential equation и добавления дифференциального уравнения

${\dot{x}}_{n+1}=L\left[x\left(t\right),u\left(t\right),t;p\right]$ (16)

с начальным условием

$x_{n+1}\left(t_0\right)=0$ (17)

Тогда функция стоимости уравнения (1) будет представлена в форме Майера как

$J=\varnothing \left[x\left(t_0\right), t_0, x\left(t_f\right), t_f, \mathrm{p}\right]+x_{n+1}\left(t_f\right)$ (18)

Затем общая схема будет использоваться для решения расширенной системы дифференциальных уравнений

$\begin{array}{c}\dot{x}\left(t\right)=f\left[x\left(t\right),\text{ u}\left(t\right),t;\text{ p}\right]\\ {\dot{x}}_{n+1}=L\left[x\left(t\right),\text{ u}\left(t\right),t;\text{ p}\right]\end{array}$ (19)

Преобразуя обратно к форме Больца, квадратурная аппроксимация к члену

${\int }_{t_0}^{t_f}L\left[x\left(t\right),\text{ u}\left(t\right),t;\text{ p}\right]dt$ (20)

в уравнении (1) должна быть та же самая, что и схема, используемая для решения системы дифференциальных уравнений, приведенной в уравнении (19).

Нелинейная оптимизация

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

Определить вектор переменных решения $z\in R^n$, которые минимизируют функцию стоимости

$f\left(z\right)$ (21)

с учетом алгебраических ограничений

$g\left(z\right)=0$ (22)

$h\left(z\right)\le 0$ (23)

где $g\left(z\right)\in {\mathrm{ℝ}}^m$ и $h\left(z\right)\in {\mathrm{ℝ}}^p$. Условия оптимальности первого порядка задачи нелинейной оптимизации, данные в уравнениях (21) и (22), также известные как условия Каруша–Куна–Таккера [9–15], задаются как

$g_i\left(z\right)=0, (i=1, ..., m)$, (24)

$h_i\left(z\right)\le 0, (i=1, ..., p)$, (25)

$v_i\ge 0, (i=1, ..., p)$, (26)

$v_i{h}_i\left(z\right)=0, (i=1, ..., p)$, (27)

$\nabla f\left(\text{z}\right)+\sum _{i=1}^m{\lambda }_i\nabla g_i\left(\text{z}\right)+\sum _{i=1}^p{\nu }_i\nabla h_i\left(\text{z}\right)=0$

Затем эти оптимизации решаются с помощью:

1. градиентных методов;
2. эвристических методов оптимизации.

Заключение

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

Об авторах

Юлия Валерьевна Матвеева

Самарский национальный исследовательский университет имени академика С.П. Королева

Email: dr.ymatveeva@ssau.ru
ORCID iD: 0000-0003-4755-226X

кандидат экономических наук, доцент кафедры менеджмента и организации производства

Россия, г. Самара

Марлвин Татенда Чигванда

Самарский национальный исследовательский университет имени академика С.П. Королева

Автор, ответственный за переписку.
Email: marlvin.chigwanda@gmail.com
ORCID iD: 0000-0001-9707-6033

аспирант кафедры менеджмента и организации производства

Россия, г. Самара

Список литературы

Дополнительные файлы