Modern methods for solving the optimal control problem in economics


Cite item

Abstract

The modern formulation of the optimal control problem is given, following which a survey of the methods currently applied in solving the optimal control problem in economics is conducted, with a focus given to numerical methods. The most important problems in the application of numerical methods in solving the optimal control problem are given and explained. The article then lists and explains the most common computational methods of solving the optimal control problem that are being applied in today’s economic sphere, how far these methods go in terms of achieving their objectives and providing solutions, the difficulties in implementing these methods, and the associated limitations. The latest developments in software and programs that are beginning to be used by mainly economists in solving some of the most common optimal control problems are listed, and their advantages and limitations are explained. Lastly, a general analysis of some of the next-generation methods and the future of the optimal control problem in general is made.

Full Text

Введение

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

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

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

  • – функция состояния, описывающая поведение системы, и;
  • – функция управления, направляющая эволюцию системы от одного шага к другому.

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

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

Задача оптимального управления: Определить состояние (эквивалентно, траектория или путь), , управление , вектор статических параметров , начальное время, , и терминальное время,  (где  — независимая переменная), которая оптимизирует индекс производительности

 

 

 

(1)

 

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

 

 

 

       (2)

 

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

 

 

 

       (3)

 

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

 

 

 

       (4)

 

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

 

 

; ; .

       (5)

 

Косвенные методы

 

 

Системы нелинейных уравнений

Дифференциальные уравнения и интегрирование функций

 

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

 

Прямые методы

   

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

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

 

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

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

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

 

 

 

     (6)

[где стоимость на каждом этапе, ,  имеет вид, указанный в уравнении (1)] с учетом динамических ограничений

 

 

 

       (7)

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

 

 

 

       (8)

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

 

 

 

       (9)

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

 

 

 

(10)

 

В уравнении (10) параметр S – количество пар фаз, которые необходимо соединить,  и  – правые фазы и левые фазы, соответственно, пар связей,  (означает, что фаза не может быть связана сама с собой), и  [8].

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

 

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

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

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

а) численное решение системы дифференциальных уравнений и функций интегрирования;

б) численное решение систем нелинейных уравнений, а;

  1. Прямым методом, сочетая как

а) численное решение системы дифференциальных уравнений и функций интегрирования;

б) численное решение методом нелинейной оптимизации.

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

 

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

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

 

 

.

    (11)

Кроме того, рассмотрим временной интервал  , в течение которого желательно получить решение дифференциального уравнения. Другими словами, учитывая значение состояния в , , желательно получить состояние в , . Интегрируя уравнение (11), мы можем записать

 

 

 

     (12)

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

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

 

 

 

     (13)

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

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

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

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

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

 

 

.

 

     (14)

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

 

,

     (15)

 

где  – функция коэффициентов ,  . Затем цель состоит в том, чтобы определить значения этих коэффициентов, которые приводят к .

 

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

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

 

 

 

     (16)

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

 

 

 

     (17)

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

 

 

 

     (18)

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

 

 

.

 

(19)

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

 

 

 

     (20)

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

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

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

 

Определить вектор переменных решения zÎRn, которые минимизируют функцию стоимости

 

 

     (21)

 

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

 

 

 

     (22)

 

 

 

     (23)

 

где  и . Условия оптимальности первого порядка задачи нелинейной оптимизации, данные в уравнениях (21) и (22), также известные как условия Каруша–Куна–Таккера [9–15], задаются как

 

,

 

     (24)

 

,

 

     (25)

 

,

 

     (26)

 

,

 

     (27)

 

.

     (28)

 

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

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

 

     Заключение

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


     

×

About the authors

Yuliya V. Matveeva

Samara National Research University

Author for correspondence.
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, 34, Moskovskoye shosse, Samara, 443086, Russian Federation

Marlvin T. Chigwanda

Samara National Research University

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

postgraduate student of the Department of General and Operations Management

Russian Federation, 34, Moskovskoe shosse, Samara, 443086, Russian Federation

References

  1. Dorfman R. An Economic Interpretation of Optimal Control Theory. American Economic Review, 1969, vol. 59, issue 5, pp. 817–831. URL: https://econpapers.repec.org/article/aeaaecrev/v_3a59_3ay_3a1969_3ai_3a5_3ap_3a817-31.htm.
  2. Bakke V. A maximum principle for an optimal control problem with integral constraints. Journal of Optimization Theory and Applications, 1974, vol. 13, issue 1, pp. 32–55. DOI: https://doi.org/10.1007/BF00935608.
  3. Belbas S. Iterative schemes for optimal control of Volterra integral equations. Nonlinear Analysis, 1999, vol. 37, pp. 57–79.
  4. Belbas S. A new method for optimal control of Volterra integral equations. Applied Mathematics and Computation, 2007, vol. 189, pp. 1902–1915. DOI: http://doi.org/10.1016/j.amc.2006.12.077.
  5. Berkani S., Manseur F., Maidi A. Optimal control based on the variational iteration method. Computers & Mathematics with Applications, 2012, vol. 64, issue 4, pp. 604–610. Available at: http://dx.doi.org/10.1016/j.camwa.2011.12.066.
  6. Carlier G., Tahraoui R. On some optimal control problems governed by a state equation with memory. ESAIM Control Optimization and Calculus of Variations, 2008, vol. 14, issue 4, pp. 725–743. DOI: http://dx.doi.org/10.1051/cocv:2008005.
  7. Dai R., Cochran J.E. Wavelet collocation method for optimal control problems. Journal of Optimization Theory and Applications, 2009, vol. 143, pp. 265–278. DOI: http://doi.org/10.1007/S10957-009-9565-9.
  8. Rao Anil (2010). A Survey of Numerical Methods for Optimal Control. Advances in the Astronautical Sciences, 2010, vol. 135, issue 1, pp. 495–528. Available at: https://www.researchgate.net/publication/268042868_A_Survey_of_Numerical_Methods_for_Optimal_Control.
  9. Bazaraa M.S., Sherali H.D., Shetty C.M. Nonlinear Programming: Theory and Algorithms. 3rd edition. New Jersey: Wiley-Interscience, 2006. Available at: https://books.google.ru/books?id=nDYz-NIpIuEC&printsec=frontcover&hl=ru#v=onepage&q&f=false.
  10. Bertsekas D. Nonlinear Programming. Belmont, Massachusetts: Athena Scientific Publishers, 2004. Available at: http://www.athenasc.com/nonlinbook.html.
  11. Boyd S., Vandenberghe L. Convex Optimization. Cambridge, United Kingdom: Cambridge University Press, 2004. 730 p. Available at: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf.
  12. Nocedal J., Wright S. Numerical Optimization. New York: Springer-Verlag, 2nd edition, 2006. Available at: https://books.google.ru/books?id=7wDpBwAAQBAJ&printsec=frontcover&hl=ru#v=onepage&q&f=false.
  13. Gill P.E., W. Murray W., Saunders M.A., Wright M.H. User’s Guide for NPSOL (Version 4.0): A FORTRAN Package for Nonlinear Programming. Department of Operations Research, Stanford University, January 1986. DOI: http://doi.org/10.21236/ada169115.
  14. Biegler L.T., Ghattas O., Heinkenschloss M., Bloemen Waanders B.v. (Eds.) Large-Scale PDE Constrained Optimization. In: Lecture Notes in Computational Science and Engineering, vol. 30. Berlin: Springer-Verlag, 2003. DOI: http://doi.org/10.1007/978-3-642-55508-4.
  15. Betts J.T. Practical Methods for Optimal Control Using Nonlinear Programming. Philadelphia: SIAM Press, 2001. DOI: http://doi.org/10.1115/1.1483351.

Copyright (c) 2023 Vestnik of Samara University. Economics and Management

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies