The parameter continuation method and its application to optimal control problems

Authors

  • S.S. Zhulin

Keywords:

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

Abstract

The parameter continuation (homotopy) method for solving nonlinear equations and its numerical implementation are considered. An approach to the application of the continuation method for finding the Pontryagin extremals in optimal control problems is described and studied. Some techniques of expansion of this approach to control-nonlinear optimal control problems and to problems with nonsmooth control domains are proposed. The algorithms described in this paper were numerically implemented when developing the «Optimus» software package.

New computational technologies

Downloads

Published

2007-06-04

Issue

Vol. 8 (2007): Issue 2.

Section

Section 1. Numerical methods and applications

Author Biography

S.S. Zhulin

Lomonosov Moscow State University,
Faculty of Computational Mathematics and Cybernetics

References

  1. Аввакумов С.Н. Гладкая аппроксимация выпуклых компактов // Тр. Ин-та матем. и механ. УрО РАН. Екатеринбург. 1996. 4. 184-200.
  2. Аввакумов С.Н. Решение гладкой линейной задачи быстродействия методом продолжения по параметру с обратной связью // Некоторые вопросы вычислит. матем., матем. физ. и прогр. обеспеч. М.: Изд-во Моск. ун-та, 1988. 52-54.
  3. Аввакумов С.Н., Киселев Ю.Н. Некоторые алгоритмы оптимального управления // Тр. Ин-та матем. и механ. УрО РАН. Екатеринбург. 2006. 12, № 2. 1-15.
  4. Аввакумов С.Н., Киселев Ю.Н., Орлов М.В. Методы решения задач оптимального управления на основе принципа максимума Понтрягина // Тр. Матем. ин-та им. В.А. Стеклова РАН. 1995. 211. 3-31.
  5. Арушанян О.Б., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений на Фортране. М.: Изд-во Моск. ун-та, 1990.
  6. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Физматлит, 2000.
  7. Беллман Р., Калаба Р. Квазилинеаризация и нелинейные краевые задачи. М.: Мир, 1968.
  8. Болдырев В.И. Метод кусочно-линейной аппроксимации для решения задач оптимального управления // Дифференциальные уравнения и процессы управления. 2004. № 1. 28-123 (http://www.neva.ru/journal).
  9. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления. М.: Мир, 1972.
  10. Васильев О.В. Методы оптимизации в функциональных пространствах. Иркутск: Изд-во Иркутского ун-та, 1979.
  11. Васильев Ф.П. Методы оптимизации. М.: Факториал, 2002.
  12. Григолюк Э.И., Шалашилин В.И. Проблемы нелинейного деформирования. М.: Наука, 1988.
  13. Давиденко Д.Ф. Об одном новом методе решения систем нелинейных уравнений // Докл. АН СССР. 1953. 88. 601-602.
  14. Давиденко Д.Ф. О приближенном решении систем нелинейных уравнений // Украинский матем. журнал. 1953. 5, № 2. 196-206.
  15. Дикусар В.В., Кошька М., Фигура А. Метод продолжения по параметру при решении краевых задач в оптимальном управлении // Дифференциальные уравнения. 2001. 37, № 4. 453-457.
  16. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.
  17. Жулин С. C. Численное решение задач оптимального управления с помощью системы Optimus // Проблемы динамического управления: Сб. научн. трудов ф-та ВМиК МГУ им. М.В. Ломоносова / Под ред. Ю.С. Осипова, А.В. Кряжимского. Вып. 1. М.: Издательский отдел факультета ВМиК МГУ, 2005. 158-165.
  18. Исаев В.К., Сонин В.В. Об одной модификации метода Ньютона численного решения краевых задач // Ж. вычислит. матем. и матем. физики. 1963. 3, № 6. 1114-1116.
  19. Кирия В. Движение тел в сопротивляющихся средах // Тр. Тбилисского ун-та. 1951. № 44. 1-20.
  20. Киселев Ю.Н. Оптимальное управление. М.: Изд-во Моск. ун-та, 1988.
  21. Киселев Ю.Н. Схема продолжения по параметру в нелинейной задаче быстродействия // Вестн. Моск. ун-та. Сер. 15. 1990. № 2. 51-52.
  22. Красносельский М.А., Вайникко Г.М., Забрейко П.П., Рутицкий Я.Б., Стеценко В.Я. Приближенное решение операторных уравнений. М.: Наука, 1969.
  23. Ли Э.Б., Маркус Л. Основы теории оптимального управления. М.: Наука, 1972.
  24. Моисеев Н.Н. Численные методы в теории оптимальных систем. М.: Наука, 1971.
  25. Ортега Дж., Рейнболт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975.
  26. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Наука, 1969.
  27. Федоренко Р.П. Приближенное решение задач оптимального управления. М.: Наука, 1978.
  28. Фок В.А. Дифракция волн вокруг земной поверхности. М.; Л.: Изд. АН СССР, 1946.
  29. Черноусько Ф.Л., Баничук Н.В. Вариационные задачи механики и управления. Численные методы. М.: Наука, 1973.
  30. Шалашилин В.И. Метод продолжения по параметру и его применение к задаче больших прогибов непологой круговой арки // Изв. АН СССР. Механ. твердого тела. 1979. № 4. 178-184.
  31. Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решения по параметру и наилучшая параметризация. М.: Эдиториал УРСС, 1999.
  32. Шаманский В.Е. Методы численного решения краевых задач на ЭЦВМ. Киев: Наукова Думка, 1966.
  33. Шидловская Н.А. Применение метода дифференцирования по параметру к решению нелинейных уравнений в банаховых пространствах // Уч. зап. Львовского ун-та. Сер. матем. наук. 1958. № 33. 3-17.
  34. Allgower E.L., Bates D.J., Sommese A.J., Wampler C.W. Solution of polynomial systems derived from differential equations // Computing. 2006. 76, N 1. 1-10.
  35. Allgower E.L., Georg K. Introduction to numerical continuation methods. Berlin-New York: Springer-Verlag, 1990.
  36. Allgower E.L., Georg K. Numerically stable homotopy methods without an extra dimension // Proc. of SIAM-AMS Summer Seminar on Computational Solution of Nonlinear Systems of Equations. Ft. Collins (USA), 1988. 1-13.
  37. Avvakumov S.N., Kiselev Yu.N. Boundary value problem for ordinary differential equations with applications to optimal control // Proc. of the Tenth Crimean Autumn Mathematical School. Spectral and Evolution Problems. Vol. 10. Simferopol, 2000. 1-5.
  38. Bonnard B., Caillau J., Dujol R. Continuation methods and single input time optimal orbital transfer. Preprint. Institut de Mathematiques de Bourgogne. Bourgogne, 2006 (http://math.u-bourgogne.fr/topo/prepub/continuation.pdf).
  39. Bosarge W. Infinite dimensional iterative methods and applications. Report 320. IBM Houston Sci. Center. Houston, 1968.
  40. Catinas E. The inexact, inexact perturbed and quasi-Newton methods are equivalent models // Mathematics of Computation. 2004. 74, N 249. 291-301.
  41. Decarolis F., Mayer R., Santamaria M. Homotopy continuation methods: An algorithm for the fixed point and Newton homotopy methods with some examples. Preprint. The University of Chicago. Chicago, 2005.
  42. Dunlavy D.M., O’Leary D.P. Homotopy optimization methods for global optimization. 2005 (http://www.cs.umd.edu/dsize ildephantoma oleary/tr/4773.pdf).
  43. Ehtamo H., Raivio T., Hamalainen R.P. A continuation method for minimum time problems. Systems Analysis Laboratory Research. Report E3. Helsinki University of Technology. Helsinki, 2000.
  44. Gergaud J., Haberkorn T. Homotopy method for mininum consumption orbit transfer problem // ESAIM Control Opt. and Calc. of Var. 2006. 12, N 2. 294-310.
  45. Keller H.B. Global homotopies and Newton methods // Recent Advances in Numerical Analysis. New York-London: Academic Press, 1978. 73-94.
  46. Kelley C.T., Sachs E.W. Approximate quasi-Newton method // Mathematical Programming. 1990. 48, N 1. 41-70.
  47. Lahaye M.E. Solution of system of transcendental equations // Acad. Roy. Belg. Bull. Cl. Sci. 1948. 5. 805-822.
  48. Martinez J.M. Quasi-inexact-Newton methods with global convergence for solving constrained nonlinear systems // Nonlinear Analysis, Theory, Methods, and Applications. 1997. 30. 1-8.
  49. Morini B. Convergence behaviour of inexact Newton methods // Mathematics of Computation. 1999. 68, N 228. 1605-1613.
  50. Nocedal J., Wright S.J. Numerical optimization. Berlin: Springer-Verlag, 1999.
  51. Percell P. Note on a global homotopy // Numer. Funct. Anal. Optim. 1980. N 2. 99-106.
  52. Roberts S., Shipman J. Continuation in shooting methods for two-point boundary value problems // J. Math. Anal. Appl. 1967. 18. 45-58.
  53. Watson L.T. Numerical linear algebra aspects of globally convergent homotopy methods // SIAM Review. 1986. 28, N 4. 529-545.
  54. Watson L.T. Theory of globally convergent probability-one homotopies for nonlinear programming // SIAM J. on Optimization. 2000. 11. 761-780.
  55. Weiser M. Function space complementarity methods for optimal control problems. Dissertation Eingereicht am Fachbereich Mathematik und Informatik der Freien Universitat. Berlin, 2001 (http://www.diss.fu-berlin.de/2001/189/ index.html).