Modern methods for solving the optimal control problem in economics

Full Text

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

Стремительный рост цифровизации и применение цифровых методов искусственного интеллекта в экономической сфере привели к развитию новых численных методов решения задачи оптимального управления, использующих возможности вычислительных и математических программ для поиска решений экономических задач, которые ранее считались слишком сложными для решения даже с помощью численных методов. Эта работа важна тем, что она дает представление о современных численных методах, основанных на используемом компьютерном программном обеспечении, исследует некоторые из основных преимуществ и выгод и анализирует, как эти методы могут быть улучшены в будущем. Таким образом, эта работа послужит основой для дальнейшего развития методов следующего поколения (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. эвристических методов оптимизации.

Заключение

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

About the authors

Yuliya V. Matveeva

Samara National Research University

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

Candidate of Economics, associate professor of the Department of General and Operations Management

Russian Federation, Samara

Marlvin T. Chigwanda

Samara National Research University

Author for correspondence.
Email: marlvin.chigwanda@gmail.com
ORCID iD: 0000-0001-9707-6033

postgraduate student of the Department of General and Operations Management

Russian Federation, Samara

References

Supplementary files