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

о

Московский Государственный Университет им. М.В. Ломоносова

□□3481487

На правах рукописи

УА

Жулин Степан Сергеевич

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

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

<с1

О

■

ъ

Москва - 2009

003481487

Работа выполнена на кафедре оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова

Научный руководитель: кандидат технических наук,

доцент Бойков Владимир Георгиевич

Официальные оппоненты: член-корреспондент РАН,

доктор физико-математических наук Ушаков Владимир Николаевич

кандидат физико-математических наук Ткачев Сергей Борисович

Ведущая организация: Московский Авиационный Институт

(государственный технический университет) г. Москва

Защита диссертации состоится " 3 " 2009 г. в 15.30

на заседании диссертационного совета Д 501.001.43 при Московском государственном университете им. М. В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, второй учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат диссертации разослан " " 2009 г.

Ученый секретарь

диссертационного совета,

доктор физико-математических наук,

профессор

Е. В. Захаров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

Простейшими численными методами решения нелинейных задач, основанными на принципе максимума, являются итерационные методы последовательных приближений и проекции градиента. Одним из их недостатков является узкая применимость — задачи со свободным правым концом и фиксированным временем. Существует много модификаций этих методов, которые в сочетании с методом штрафов расширяют класс решаемых задач и улучшают результирующую точность. Более серьезным их недостатком яа!яется плохая сходимость и необходимость в хорошем начальном приближении.

Задачи оптимального управления в большинстве постановок сводятся к краевой задаче для принципа максимума. Это дает возможность построить универсальный метод решения, основанный на автоматическом сведении и дальнейшем применении численного метода решения краевых задач. Однако здесь нельзя не учитывать специфику краевых задач для принципа максимума, а именно, часто присутствующую негладкость яля разрывность правой части расширенной системы ОДУ, во избежание возможных неприятностей необходимо применять адекватные методы сглаживания. H.H. Моисеев, Р.П. Федоренко и другие ученые сходятся в том, что наиболее адекватными и точными методами решения задач оптимального управления являются методы решения соответствующих краевых задач (П-систем), признавая в то же время, что при таком подходе не всегда удается получить решение классическими методами (например, методом Ньютона). Это обуславливает необходимость развития численных методов в данном направлении.

Обзор численных методов. Разработка численных методов оптимального управления бурно развивается с 60-х годов прошлого века, с того момента, как был сформулирован принцип максимума Л.С. Понтрягина и принцип динамического программирования Р. Беллмана. Как уже упоминалось, основные трудности при решении задач оптимального управления вызваны необходимостью решать краевую задачу, разрывностью правой части системы, большой размерностью систем, наличием различных типов ограничений, в т.ч. на управление и фазовые координаты, множественностью локальных экстремумов. Для преодоления тех или иных трудностей, а также учета особенностей различных задач, создано большое количество численных методов.

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

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

2. прямые методы, включающие градиентные методы, основанные на формуле приращения для первой вариации функционала;

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

4. методы последовательных приближений, основанные на процедурах линеаризации и вариации управлений;

5. методы штрафных функционалов или расширенной функции Лагранжа.

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

Отдельно остановимся на численных методах решения краевых задач, возникающих в результате применения принципа максимума, (П-систем), как имеющим непосредственное отношение к теме данной работы.

К решению краевых задач существует несколько кардинально отличных подходов.

Первый подход заключается в том, что на любой итерации точно удовлетворяются дифференциальные связи, а значения невязок по краевым условиям являются переменной, значение которой является искомым. Такой подход получил название стрельбы (Shooting method). Достоинством такого подхода является невысокая размерность решаемого уравнения (не превышающая число краевых условий). Полученное уравнение относительно краевых невязок можно решать любым из стандартных методов (метод скорейшего спуска, метод сопряженных градиентов, метод Ньютона и его обобщения). Одни из первых работ по применению модификаций метода Ньютона в задачах оптимального управления были выполнены В.К. Исаевым и В.В. Сониным1. В начале 60-х годов ряд вариационных задач динамики космических аппаратов был решен В.Н. Лебедевым, который также широко использовал различные модификации метода Ньютона. Как отмечается H.H. Моисеевым, несмотря ни на какие модификации, применение метода Ньютона невозможно без удовлетворительного начального приближения. Эту проблему призван разрешить метод продолжения решения по параметру. Для решения задач оптимального управления сочетание этого подхода и метода продолжения по параметру было предложено С.Н. Авва-кумовым и Ю.Н. Киселевым2. Более подробное описание метода будет дано в следующих секциях.

Второй подход заключается в отыскании решения среди множества тех функций, которые удовлетворяют краевым условиям. Такие решения можно находить методами, основанными на переносе граничных условий — методами прогонки. Эта идея высказывалась независимо рядом авторов (В.Н. Лебедев, H.H. Моисеев, Р.П. Федоренко и др.), на ее основе были предложены разнообразные схемы решения вариационных задач.

Третий подход заключается как в отказе от точного выполнения краевых условий, так и дифференциальных связей. Метод заключается в минимизации интегрального функционала, включающего в себя невязки по краевым и дифференциальным связям. Он был предложен A.B. Балакришнаном и получил название эпсилон-метода.

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

- позволяет построить метод, пригодный для решения задач оптимального управления в большинстве постановок (например, с нефиксированным временем, с различными типами ограничений);

- позволяет сильно ослабить требования к начальному приближению по сравнению с методом Ньютона и его модификациями;

1 Исаев В.К., Сонин В.В. Об одной модификации метода Ньютона численного решения краевых задач // Журнал вычислительной математики и математической физики. 1963. Т.З, №6.

2 Avvakumov S.N., Kiselev Yu.N. Boundary value problem for ordinary differential equations with applications to optimal control // Spectral and Evolution Problems. 2000. Vol 10. Simferopol, Ukraine.

- возможен целый ряд модификаций и обобщений метода для решения особо сложных задач;

- метод основывается на стандартных, хорошо изученных процедурах решения задачи Коши.

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

Идея применения продолжения по параметру для исследования решений нелинейных уравнений восходят к работам У. Леверье (1886) и А. Пуанкаре (1892). По-видимому, впервые для численного решения уравнений метод продолжения был применен бельгийским математиком М. Лэем (Lahaye, 1934) для случая одного уравнения. Для движения вдоль кривой решений он использовал дискретное продолжение посредством метода Ньютона. Позже Лаэй рассмотрел также и системы уравнений. В более эффективном дифференциальном виде метод сформулировал Д.Ф. Давиденко3 и применил его к широкому классу задач, таких, как обращение матриц, вычисление определителей, вычисление собственных значений матриц, решение интегральных уравнений. По-видимому, эту же идею дифференцирования по параметру применяли несколько ранее для решения частных задач В.А. Фок (1946) и B.C. Кирия (1951), а немного позже H.A. Шидловская (1958). Впоследствии, метод продолжения по параметру был применен для решения краевых и простейших вариационных задач В.Е. Шаманским4, Робертсом и Шипмэном (1967). В конце 70-х, начале 80-х годов Келлером и Перселлом были предложены варианты метода продолжения, обладающие глобальной сходимостью при достаточно слабых предположениях.

Крупный вклад в развитие метода внесли Э.И. Григолюк, В.И. Шалашилин и Е.Б. Кузнецов5, их работы являются одними из наиболее основательных отечественных трудов по методу продолжения. С 80-х годов метод продолжения в приложении к задачам оптимального управления развивается С.Н. Аввакумовым, Ю.Н. Киселевым и М.В. Орловым6.

В последней четверти ХХв. существенный вклад в развитие и популяризацию метода внесли зарубежные математики Олгоуэр и Георг. Благодаря их великолепной работе7, рассматриваемая тема получила сильный толчок к развитию.

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

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

3Давиденко Д.Ф. О приближенном решении систем нелинейных уравнений // Укр. мат. журнал. 1953. Т.5. №2.

4Шаманский В.Е. Методы численного решения краевых задач на ЭЦВМ. Киев: Наукова Думка, 196

6Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решения по параметру и наилучшая параме ризация. М.: Эдиториал УРСС, 1999.

"Аввакумов С.Н., Киселев Ю.Н., Орлов М.В. Методы решения задач оптимального убавления i основ? принципа максимума Понтрягина // Труды МИ РАН. 1995. Т.211.

7AUgower E.L., Georg К. Introduction to numerical continuation methods. Berlin: Springer, 1990.

программными средствами их численного решения.

Из отечественных разработок стоит отметить диалоговую систему оптимизации ДИ-СО8, а также пакеты прикладных программ МАПР и КОНУС9.

В ДИСО применяется технология решения задач управления с использованием численных методов нелинейного программирования. Согласно технологии, разработанной под руководством проф. Ю.Г. Евтушенко, вычисление градиентов ведется с помощью интегрирования прямой и сопряженной систем по согласованным разностным схемам, что позволяет повысить точность аппроксимации непрерывной системы без увеличения размерности задачи нелинейного программирования. Система оснащена развитыми диалоговыми средствами для управления вычислительным процессом и организации многометодного режима решения задачи.

Пакеты МАПР и КОНУС ориентированы на решение разных классов задач оптимального управления и больших задач линейного программирования. В пакет МАПР входят численные методы, использующие фундаментальные свойства непрерывных управляемых систем. В сравнении с методами редукции задач управления к задачам математического программирования эти методы позволяют получить более точное и качественное решение для некоторых классов задач оптимального управления.

На кафедре Оптимального Управления ВМиК МГУ разработано несколько интересных пакетов: ТАХИОН, ТАЙМЕР10, ПОНТРЯГИН, имеющих графический интерфейс, предназначенные для решения линейных задач оптимального управления, использующие метод потенциалов и другие эффективные численные методы.

Среди зарубежных разработок последнего времени, преобладает форма пакета-расширения для Matlab. Наиболее популярными среди таких пакетов являются

1. RIOTS9511,

2. MISER312,

3. DIDO13,

4. TOMLAB/GPOCS14,

5. TOMLAB/SOCS15,

6. также можно в этот список включить FORTRAN/C библиотеку DIRCOL16.

"Грачев Н.И., Евтушенко Ю.Г. Библиотека программ для решения задач оптимального управления // Журнал вычислительной математики и математической физики. 1979. Т.19, jV>2.

9Тятюшкин А.И. Численные методы и программные средства оптимизации управляемых систем. Новосибирск: Наука. Сиб. отд-ние, 1992.

10Рябов А.Ю., Орлов М.В. Графический пакет ТАЙМЕР для решения линейной задачи быстродействия. М.: Центр Диалог, МГУ. 1992.

"Schwartz A.L. Theory and implementation of numerical methods based on Runge-Kutta integration for solving optimal control problems. Ph.D. Dissertation, Dept. of Electrical Engineering, University of California, Berkeley, 19Э6.

12Jennings L.S., Fisher M.E., Teo K.L., Goh C.J. MISER3 optimal control software: theory and user manual. 2002.

I3M. Ross. Users Manual For DIDO: A MATLAB Application Package for Solving Optimal Control Problems // Naval Postgraduate School, Monterey, CA, Tech. Rep. 0401.0, Feb. 2004.

14Rao A.V. Users Manual for GPOCS: A MATLAB Implementation of the Gauss Pseudospectral Method for Solving Multiple-Phase Optimal Control Problems. Feb. 2008.

15Betts J.T. SOCS: the sparse optimal control software family. Boeing, Tech. Rep., 1996.

16Stryk O. DIRCOL: a direct collocation method for the numerical solution of optimal control problems. 1999.

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

Пакет RIOTS95 выделяется из этого списка тем, что использует подход итеративного интегрирования в редукции задачи, в отличие от метода аппроксимации Галеркина (также известного, как "collocation method"). Это обуславливает преимущества в скорости решения (благодаря меньшей размерности редуцированной задачи), точности и достоверности результатов. К недостаткам RIOTS95 можно отнести ограниченную возможность решения задач с фазовыми ограничениями, а также присутствие лишь частного вида ограничений на управление.

Пакет MISER3(flocryneH также в виде FORTRAN-библиотеки) интересен тем, что позволяет использовать несколько алгоритмов-подпрограмм для решения задачи квадратичного программирования (FFSQP, MINOSS и NPSOL). К недостаткам можно отнести простую интерполяцию управления кусочно-линейными функциями.

Крайне интересными являются пакеты DIDO и TOMLAB/GPOCS, в них используется кусочная интерполяция фазовых и управляющих переменных с помощью полиномов Лежандра и квадратурных формул Гаусса-Лобатто. Используемый метод интерполяции, называемый псевдоспектральным методом Лежандра, применяемый в моделировании потока жидкости, обладает хорошими свойствами для задач оптимального управления. В DIDO используется нелинейный решатель SNOPT, в TOMLAB/GPOCS — один из решателей TOMLAB/SNOPT, /KNITRO, /NPSOL или /CONOPT.

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

Метод DIRCOL является основоположником методов, используемых в пакетах 2-5, соответствующая библиотека является широко используемой.

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

Для достижения цели были поставлены следующие задачи:

• построение теоретически обоснованного численного метода решения нелинейных конечномерных алгебраических уравнений с широкой областью сходимости;

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

• адаптация метода для особенностей возникающих уравнений, таких как отсутствие гладкости;

• автоматизация решения задачи вплоть до задания пользователем математической постановки и требуемой точности;

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

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

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

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

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

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

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

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

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

На основе предложенного метода разработан программный комплекс для решения задач оптимального управления с линейной и нелинейной динамикой, с функционалами интегрального и терминального вида, с различными типами краевых условий, геометрическими ограничениями на управление и смешанными ограничениями. Програмный комплекс предоставляет возможности для обработки полученных результатов, а также вывода их в графическом и табличном виде. Разработанный программный комплекс востребован в учебном и научном процессе и успешно используется на кафедре Оптимального Управления ВМиК МГУ.

Публикации и апробация работы. По теме диссертации опубликовано 8 печатных работ [1]-[8], в том числе работа [5] представлена в журнале «Дифференциальные уравнения», входящем в перечень ведущих рецензируемых изданий ВАК РФ. Основные результаты доложены на Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов-2003» [7]; на XIV Международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2007» [8]; на научном семинаре кафедры оптимального управления ВМиК МГУ под руководством академика РАН Ю.С. Осипова и профессора М.С. Никольского, а также на научном семинаре отдела Динамических систем ИММ УрО РАН г.Екатеринбург под руководством член-корр. РАН В.Н. Ушакова.

Структура и объем диссертации. Настоящая диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации — 149 страниц, включая 35рисунков. Библиография содержит 133 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается проблема решения нелинейного уравнения

Ф(р) = 0, где р 6 ЗГ, Ф : R" -> К". (1)

Вводится функция гомотопии — непрерывно дифференцируемая [С\-гладкая) функция

Я(р,/0, Я:К"+1-М", (2)

удовлетворяющая условиям Н(р, 0) = д(р), Н(р, 1) = Ф(р).

В частности рассматривается гомотопия Ньютона, имеющая вид

Н<р,р) = *(р)-(1-ц)ФЫ- (3)

В качестве достаточного условия существования кривой гомотопии используется следующая теорема.

Теорема.Пусть ноль — регулярное значение функции Н. Тогда существует С\-гладкая кривая (p(s),ft(s)) : H(p(s), n(s)) =0, s 6 R.

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

Предположение. Пусть V/u, е [0,1] существует решение уравнения Н(р. /¿) = 0

р = р{ц), 0</i< 1, (4)

причем функция p(ß) является гладкой на [0,1] и удовлетворяет, начальному условию

КО) =Ро,

а вдоль решения (4) существует непрерывный отличный от нуля градиент функции Ф

, «¿Ф , „

det -т-^0. dp

Продифференцируем по //. уравнение H(p(ji).ii) = 0, что эквивалентно Ф(р(/с.)) = (1 - /х)Ф(р0), получим:

f ^—*(*). (5)

¿Р dß

с учетом условия р(0) = р0 получим задачу Коши:

[ Ф =_ < dß [dp { рМ1д=О =РО. 0 < Ai < 1.

Ф(ро). (б)

У тверждение. При сделанном предположении задача поиска корня исходной системы уравнений эквивалентна решению задачи Коши (6) р, = р(р.) |(1=1.

Автором предлагается эффективный метод аппроксимации кривой, учитывающий неточности вычисления функции, матрицы Якоби, погрешности интегрирования и машинные ошибки округления, — метод продолжения по параметру с коррекцией Ньютоновского типа.

Входные данные

1. роб®^! // Начальное приближение

2. Л = 1/5, где 5 е К; // Размер шага

3. £о > 0, г: > 0. // Константы аппроксимации

Алгоритм метода продолжения с коррекцией

1. Выбрать )>0 € К" так, что для 60 — Ф(ро) ~ "о выполнено ||й"о|| < £о^2/3;

2. к = 0; цк = 0;

3. Цк+1 = /«* + /г;

4. Выбрать А)ь 6 Кл,хлг так, что для Ак = Ф'(рк)-Ак выполнено ||Дк|| < е^Ь, и ||Д4|| <

Нф'ЫН;

5. Вычислить Д из системы линейных уравнений А^/к = —г»о!

6- дл+1 =р* + Л/*;

7. Выбрать 6 так, что для 4 = Ф^+х) - ^ выполнено < ецЛ.2/3; ц

8. вычислить Нк = ук — (1 — Цк)ъ'0\

9. Вычислить из СЛУ А^+х = IIк]

10. рк+1 = дк+г - ;

11. к = к + 1; если к < 5 перейти к шагу 3;

12. Конец; результат: р<?.

Доказана основная теорема о качестве аппроксимации кривой гомотопии предложенным методом продолжения при неточном вычислепии значения функции Ф(у.) и ее мат-/ рицы Якоби Ф'(р). /

Теорема 1. Пусть Ур 6 [0,1] существует р*(ц) — решение уравнения Н(р,1х). = Ф(р) — (1 — /л)Ф(ро) = 0. Предположим, что существует компактная окрестность Р множества Цигр^РЧ/")» состоящая только из регулярных точек функции Ф (р). Тогда существуют константы Со, ^г и максимальный размер шага ктах такие, что для последовательности {рк,Цк)> построенной алгоритмом продолжения с коррекцией, выполнено условие:

IIП(рк, цк)|| < 2еХ, при 0 < /). < Нтах, . (7)

и последовательность рк не выходит из Р.

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

17 ^и п , ® е А': К" х М" ^ К". (8)

К(х(а),х(Ь)) = 0,

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

£ = /0М), х(и)=р, (9)

где t* 6 [а, Ь] — произвольный фиксированный момент времени.

Тогда решение краевой задачи сводится к решению уравнения Ф(р) =0, где

Ф(р) = А'(х(р, а),х{р,Ь)), (10)

(¿Ф1-1

Применяя метод продолжения по параметру, получим задачу Коши, называемую внешней задачей:

йр

.РМи0=Р0' 0 < /л < 1, 12

(и)

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

Утверждение. Решение краевой задачи (8) эквивалентно решению задачи Коши (И)

Р* = рМ

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

Лемма 1.(о применимости метода продолжения с коррекцией к краевой задаче для ОДУ) Пусть функции F(',~) и К(-,-) являются непрерывно дифференцирушыми по совокупности аргументов. Пусть решение задачи Коши x{p,t) существует на отрезке [о, Ь] в необходимой окрестности корня р,. Пусть для функции Ф(р) выполнено предположение регулярности. Тогда для уравнения Ф(р) = 0, эквивалентного краевой задаче 8, выполнены условия теоремы 1, для него возможно применение метода продолжения с коррекцией.

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

1. ра 6 // Начальное приближение

2. h = 1/5, где S 6 N; // Размер шага

3. е0 > 0, £i > 0. // Константы аппроксимации

Алгоритм метода продолжения с коррекцией для задач с параметром

1. к = 0; iik= 0;

2. jUifc+i = № + /(■;

3. Выбрать vk е так, что для 5к = Ф^Рь Wt) + Ф(ро>0) - vk выполнено ||5fc|| < £0h\

4. Выбрать Ак е RN*N так, что для Ак = Ф'р(рк,цк) - Ак выполнено ЦД^Ц < гф и ||Д*|| < ||ф;(м)||;

5. Вычислить Д из системы линейных уравнений Akfk — —vk; 6- tft+i =Pk + hfk;

7. Выбрать Hk £ так, что для 4 = Я(д*+1> Wt+i) ~ Пк выполнено ||б*|| < e0h2/3;

8. Вычислить из СЛУ AfcSfc+i = Нк\

9. Рк+1 = Qk+i - Sfc+i;

10. к — к + 1; если к < S перейти к шагу 2;

11. Конец; результат: ps.

Доказана следующая теорема о качестве аппроксимации кривой гомотопии методом продолжения с коррекцией.

Теорема 2. Пусть Vp е [0,1] существует p*{ß) — решение уравнения H(p,/j) = Ф(р. /¿) — (1 —/¿)Ф(р0.0) = 0. Предположим, что существует компактная окрестность Р множества Ц^од] (?*(/')>/')> состоящая только из регулярных точек функции Ф(р, //.). Тогда существуют константы со, £i и максимальный размер шага hmax такие, что для последовательности {pk<ßk)> построенной алгоритмом продолжения с-коррекцией, выполнено условие:

\\H{pk.jik)\\ <г0Л2, при 0 < Л < Л maxi (12)

и последовательность (рьм) we выходит из Р.

Этот алгоритм и соответствующее утверждение позволяют эффективно решать задачи с малым параметром за один проход алгоритма продолжения.

Как известно, в частности при больших интервалах времени [а, Ь], задача Коши может быть неустойчивой, а локальная константа Липшица функции Ф в уравнении Ф(р) = 0 может быть очень велика. Из-за указанной проблемы, H.H. Моисеев17 делает вывод о невозможности решения некоторых задач посредством такого подхода (следует заметить, что в указанной работе используется классический метод Ньютона). При использовании метода продолжения эта проблема стоит не так остро, так как наличие сходимости не зависит в явном виде от вида функции. Тем не менее, в плохих случаях даже задача выбора корректного начального приближения, для которого решение задачи Коши существует на всем отрезке, является очень сложной.

Для устранения указанных недостатков предлагается следующий т.н. многоточечный подход редукции краевой задачи к нелинейному уравнению. Такой подход известен в зарубежной литературе под названием «multiple shooting». Идея его была положена Мор-рисоном, Райли и Занканаро (1962), которые предложили под этим названием метод для частного вида краевых задач. В рассматриваемом автором виде метод был предложен, насколько известно автору, Осборном (M.R. Osborne, 1968). В русскоязычной литературе метод исследовался Монастырным П.И., Кигурадзе И.Т., Самойленко A.M., Ронто Н.И.

Отрезок времени [а, Ь] разбивается на s частей a — tь..., i^+i = b. Вектор переменных составляется из я точек искомой траектории р = {pi = x(ti),... = .т(/я)}.

Обозначим x'(p,t) решение задачи Коши

* = /( * А *(b)=Pi- (13)

В функцию Ф к краевым условиям добавляются условия непрерывности траектории в моменты времени t¡:

Ф (р) =

(Щх'М^рЛ))^

h )~Р2,

V х*-г{р,1,)-ре, J

(14)

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

"Моисеев H.H. Числегшые методы в теории оптимальных систем. М.: Наука, 1971.

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

Суть описанного подхода заключается в том, чтобы отказаться от сохранения непрерывности в моментах í¡. В конечном решении пределы справа и слева в этих точках стянутся и условия непрерывности будут выполнены с заданной точностью. В следующей теореме доказано, что при наличии разрывного решения, полученного с использованием многоточечного подхода, можно получить непрерывное решение (траекторию) того же порядка точности.

Теорема 3. Существует г* такое, что для любого е < s* и р* = (pj,... ,р*), удовлетворяющего ЦФ(р*)Ц < г, выполнено \\K(xi(p*,a).x1(p*,b))\\ < С-е, где С - некоторая положительная константа для заданной краевой задачи.

Здесь в качестве непрерывной траектории взята функция х1 (р*. t), т.е. начальное условие для задачи Коши х(о) = р\.

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

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

х = f(x.u,t), i £ Г. и 6 U С 1Г.

1(0) е xQ. х(Т) е Хи (1о)

, Т -* min.

управление и(-) принадлежит классу кусочно-непрерывных функций. Начальное А'0 и терминальное Хх множества — выпуклые компакты(в т.ч. точки), заданные соответствующими опорными функциями с(Х,£) = тах(х,£). Область управления U- — гладкий

х€А*

выпуклый компакт.

Запишем функцию Гамильтона-Понтрягина

Н(х,ф,иЛ) = (f(x,u.t),i/>). (16)

Предположение. Существует единственный максимизатор функции Гамильтона-Понтрягина

и*{х,фЛ) = axgmax Н(х,ф, u,t). (17)

u£ll

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

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

системой дает систему ОДУ краевой задачи для принципа максимума:

¿ = (18)

ф = -Н^{х.ф,и*{ x.ib,t).t). Краевые условия получаются из условий трансверсальности:

а;(0) = с'(Аго, ф( 0)), *(Г) = c'(Xi, —ф(Т)), (19)

в частном случае точек они выглядят так:

х(0) = хо, х(Т)=х1.

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

хт — Т- Щ{х, ф, и'(х, ф,т),т), Фг = -т ■ Нх{х, ф, и'(х, ф, г), т), Тг = о, г 6 [0,1].

Для устранения неоднозначности, связанной с инвариантностью к умножению сопряженной переменной на константу, требуется принять условие нормировки сопряженной переменной на одном из концов отрезка. Таким образом, имеем 2п + 1 ДУ и столько же краевых условий.

Для задач с другими типами функционалов меняются краевые условия и функция Гамильтона-Понтрягина.

Для применения метода продолжения по параметру, описанного в предыдущей секции, к поставленным краевым задачам необходимо выполнение некоторых условий. Требуется существование непрерывных производных /„, (/о)ю, /х.ц, (/о)х„, а также (м*)х и (и')ф.

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

н'и(х,ф,г)фо

можно найти аналитический вид максимизатора

(21)

Лемма 2. (о применимости метода продолжения с коррекцией к краевой задаче принципа максимума) Пусть функция /(•, •, •) является дважды непрерывно дифференцируемой по совокупности аргументов, а также существует единственный непрерывно дифференцируемый максимизатор «*(•, •. •), известный точно (аналитически). Пусть выполнены условия гладкости множеств Хо, А'1. Пусть также выполнены условия леммы 1 о существовании решения задачи Коши и регулярности функции Ф(р). Тогда для краевой задачи принципа максимума возможно применение леммы 1, т.е. к ней можно применить метод продолжения с коррекцией. Для аффинных по управлению задач требование Ст.-гладкости -и* можно заменить требованием гладкости области управления.

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

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

модифицированной гомотопии Ньютона, а параметр сглаживания и выражается через параметр гомотопии р, 6 [0,1]:

где щ — начальное значение параметра сглаживания, щ — конечное значение равное требуемой точности решения.

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

Лемма 3. (о применимости метода продолжения с коррекцией к краевой задаче принципа максимума в ЗОУ со сглаженной областью управления) Пусть выполнены предположения леммы 2, максимизатор и* является непрерывно дифференцируемым по V, а также выполнено условие регулярности. Тогда поиск экстремали Понтрягина в задаче оптимального управления с малым значением параметра сглаживания и^ можно произвести с помощью решения параметризованной краевой задачи методом продолжения с коррекцией (теорема 2).

Замечание. Для аффинных по управлению задач требование Сх-гладкости и* можно заменить требованием гладкости сглаженной области управления й(ц) Уц, и С\-гладкости по V ее опорной функции

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

До этого момента сведение задачи ОУ к краевой задаче для принципа максимума и дальнейшее решение ее методом продолжения по параметру производилось в предположении, что максимизатор функции Гамильтона-Понтрягина задан аналитически. Многие реальные задачи являются нелинейными по управлению, и в большинстве из них найти его не представляется возможным. Для таких случаев автором предлагается методика численного нахождения максимизатора с аналитическим вычислением его производных.

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

Лемма 4. (о применимости метода продолжения с коррекцией к нелинейной по управлению задаче с неточным вычислением максимизатора) Пусть выполнены предполооке-ния леммы 2 за исключением аналитичности вычисления максимизатора. Тогда при надлежащем выборе точности вычисления максимизатора и вычислении его производных предложенным алгоритмом — к решению краевой задачи принципа максимума для нелинейных по управлению задач возможно применение метода продолжения с коррекцией (леммы 1).

В последней секции данной главы рассматриваются аффинные задачи со смешанными

ограничениями в следующей постановке

'x = f(x,v ,u,t), íe[o,r], д(х, v, и, t) = 0, d(g) = d(v). hi{x,nJ)< 0, l<í<d(ft.), . A'(p)=0, р=(.г0,жг), (22)

иеС/, J(ti) —> min,

и

.реР, (x,v,u,t)eQ,

где Р С R2", Q с R1+n+r — открытые множества, задающие «жизненное пространство» задачи. Пусть входящие функции имеют афинный вид

f(x, V, и, í) = fo(x, t)v + fi (х, t)u + f2{x, i), t)(: r, v,«, t) = ,f?o (x, /)" + <7i(®. 0« + *). h¡(x,u,t) = (ri¡(x,t),u) + rni(x,t).

Входящие функции принадлежат следующим классам

*(•) е Ж7([0, Г]), «(.).«(0е£оо([0,П).

Здесь присутствуют вектор управлений и, ограниченный компактом Г/, а также вектор управлений ?>, обремененный лишь функциональными ограничениями д = 0.

Предполагается, что решение поставленной задачи существует и единственно, а также, что ограничения совместны в некоторой окрестности решения. Для данной задачи применяется специальное необходимое условие оптимальности, частный случай теоремы (44, стр. 126)18. С помощью него задача оптимального управления сводится к краевой задаче (П-системе), которую можно трактовать как некоторое уравнение относительно начального значения расширенной переменной.

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

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

A;S,:(A) = 0. 9;(А) < 0, A¡ £0. I А^0,

1 < i < d(h),

где

ff¿(A) = I a- ]Г Xjfij J \ +m¡.

V i<j<«/co / /

"Дмитрук A.B., Милютин A.A., Осмоловский Н.П. Принцип максимума в оптимальном управлени М.: Ищ-во механико-математического факультета МГУ, 2004.

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

2. Вычисление матрицы Якоби дифференциального оператора, что требует решения задачи Коши для уравнения первой вариации, в которое входит производная мак-симизатора и множителей Лагранжа, соответствующих смешанным ограничениям. Рассмотрены три случая сочетания активности типов ограничений, произведены соответствующие дифференциальные выкладки. В случае активности обоих типов ограничений, полученная формула для производных имеет вид:

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

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

В третьей главе подробно описывается разработанный автором программный комплекс «Система ОрИтиБ», в котором реализуются предложенные методы.

«Система Ор^шив» представляет собой универсальную программную сред)' для исследования различных прикладных задач в области математического анализа, обыкновенных дифференциальных уравнений (ОДУ), оптимального управления (ОУ) и дифференциальных игр (ДИ). Принимая во внимание то, что в широком распространении не существует сколько-нибудь универсального средства решения задач оптимального управления, автор решил сделать основной ориентацией системы Орйтив именно возможность решения наиболее широкого класса задач ОУ. Наряду с универсальностью, одной из идеологий системы является удобство работы пользователя и минимизация затрат с его стороны, что позволяет эффективно использовать Ор^тиэ как при решении прикладных задач, так и в учебном процессе.

Документ Ор^тив состоит из набора базовых объектов, введенных пользователем и текста программы на командном языке, посредством которой производятся все основные действия. Ключ к универсальности заключается в том, что любой оператор или команда языка совершает некоторые действия над набором базовых объектов документа. Под этим понимается то, что все входные и выходные данные для команды являются базовыми объектами системы. Это позволяет легко манипулировать данными и представлять их в нужной форме для той или иной задачи, а также сохранять и загружать документ без решения задачи заново.

Структура основных модулей программного комплекса:

• Optimus.exe — основной исполнимый модуль, содержащий документальную среду, графический интерфейс, командный язык;

• NumMethods.dll — библиотека базовых объектов, компилятора функций и численных методов;

• LinAIg.dll — библиотека линейной алгебры;

• LinAlgSSE2.dll — библиотека линейной алгебры с поддержкой набора векторных инструкций Б8Е2;

• ОгарЬ.осх — АсЦуеХ-объект двумерных графиков и таблиц;

• Огар1Ш.осх — Ас^уеХ-объект трехмерных графиков.

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

• уравнение и система уравнений,

• краевая задача,

• построение картины синтеза оптимальных траекторий,

• задачи теории дифференциальных игр,

• задачи оптимального управления,

• задача конструирования регуляторов.

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

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

1) удовлетворения краевых условий (невязка),

2) удовлетворения дифференциальных связей (точность внутренней задачи Коши),

3) точность метода продолжения (точность внешней задачи Коши).

Алгоритм состоит из следующих основных этапов и работает полностью автоматически. Этапы символьных вычислений:

1. составление функции Гамильтона-Понтрягина;

2. определение аффинности задачи по управлению;

3. сглаживание опорной функции области управления (в случае присутствия аффинности и негладкости);

Рис. 1: Процедура и основные блоки решения ЗОУ

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

5. составление расширенной системы дифференциальных уравнений;

6. составление краевых условий.

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

Этапы численных расчетов:

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

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

3. итерационное решение краевой задачи с малым параметром сглаживания для достижения заданной итоговой точности (невязки).

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

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

В задачах 3, 6,11,13,14 применяется автоматическое сглаживание (секция 3.1). Задачи 1, 2, 4, 5, 7 - 10, 12, нелинейны по управлению, при их решении используются результаты секции 3.2. Задачи 13, 14 содержат смешанные ограничения, используется алгоритм, предложенный в секции 3.3.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Жулин С.С. Численное решение задач оптимального управления с помощью Системы Optimus // Проблемы динамического управления: Сборник научных трудов ВМиК МГУ им. М.В.Ломоносова /под ред. Ю.С. Осипова, A.B. Кряжимского, — М.: Издательский отдел факультета ВМиК МГУ. 2005. Вып. 1, С. 158-165.

[2] Жулин С.С. Применение метода продолжения по параметру для решения сложных задач оптимального управления // Сборник статей молодых ученых факультета ВМиК МГУ, — М.: Издательский отдел факультета ВМиК МГУ; МАКС-Пресс.

2006. Вып. 3. С. 65-76.

[3] Жулин С.С. Метод продолжения по параметру и его приложение к задачам оптимального управления // Вычислительные методы и программирование. 2007. Т. 8. С. 205-217 (http://num-meth.srcc.msu.ru/).

[4] Жулин С.С. Численное решение П-систем для задач оптимального управления с фазовыми и смешанными ограничениями // Сборник статей молодых ученых факультета ВМиК МГУ, — М.: Издательский отдел факультета ВМиК МГУ; МАКС-Пресс.

2007. Вып. 4. С. 48-56.

[5] Жулин С.С. Метод продолжения по параметру для поиска экстремали в задаче оптимального управления // Дифференциальные уравнения. 2007. Т. 43, №11. С. 14601469.

[6j Жулин С.С. Метод продолжения по параметру с коррекцией и его приложения // Прикладная математика и информатика. Сборник статей, — М.: Издательский отдел факультета ВМиК МГУ. 2009. №30. С. 55-94.

[7] Жулин С.С. Система Optimus, численное решение задач оптимального управления / / Материалы Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов-2003», секция «Вычислительная математика и кибернетика». — М.: Издательский отдел факультета ВМиК МГУ; МАКС-Пресс, 2003. С. 6.

[8] Жулин С.С. Метод продолжения по параметру в задачах оптимального управления // «Ломоносов-2007»: XIV Международная конференция студентов, аспирантов и молодых ученых; секция «Вычислительная математика и кибернетика»: Тезисы докладов. — М.: Издательский отдел факультета ВМиК МГУ; МАКС-Пресс, 2007. С. 28.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 06.10.2009 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 70 экз. Заказ 531. Тел. 939-3890. ТелУФакс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Введение

1 Метод продолжения по параметру и его модификации для решения краевых задач для ОДУ

1.1 Обзор численных методов.

1.2 Обзор программных комплексов.

1.3 Теория гомотопии

1.4 Численная аппроксимация кривой гомотопии.

1.5 Метод продолжения с коррекцией.

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

1.7 Многоточечный подход.

2 Алгоритмы решения некоторых классов задач оптимального управления на основе необходимых условий оптимальности

2.1 Сведение задачи поиска экстремали к краевой задаче

2.2 Применение к нелинейным по управлению задачам.

2.3 Аффинные задачи со смешанными ограничениями.

3 Программный комплекс «Система Optimus»

3.1 Назначение и структура.

3.2 Интерфейс

3.3 Базовые объекты.

3.4 Инструментарий.

3.5 Классы задач, решаемые Системой Optimus

3.5.1 Уравнение и система уравнений

3.5.2 Краевая задача.

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

3.5.4 Задачи теории дифференциальных игр.

3.5.5 Задачи оптимального управления

3.5.6 Задача конструирования регуляторов.

3.6 Процедура решения задачи оптимального управления методом продолжения по параметру

4 Примеры решения задач с помощью Системы Optimus

4.1 Химический реактор.

4.2 Модельная задача 1 из /28/.

4.3 Триинтегратор.

4.4 Серводвигатель.

4.5 Брахистохрона.

4.6 Перевод объекта на круговую орбиту.

4.7 Летательный аппарат.

4.8 Объект в вертикальной плоскости.

4.9 Перевод космического аппарата на орбиту Марса.

4.10 Мостовой кран.

4.11 Прижимное устройство прокатного стана.

4.12 Ракета.

4.13 Ротор с ограниченной мощностью.

4.14 Манипулятор промышленного робота.

Актуальность темы

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

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

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

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

Для достижения цели были поставлены следующие задачи:

• построение теоретически обоснованного численного метода решения нелинейных конечномерных алгебраических уравнений с широкой областью сходимости;

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

• адаптация метода для особенностей возникающих уравнений, таких как отсутствие гладкости;

• автоматизация решения задачи вплоть до задания пользователем математической постановки и требуемой точности;

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

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

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

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

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

Достоверность полученных результатов подтверждается теоремами, леммами, строгими аналитическими выкладками, а также результатами расчетов (глава 4, стр. 102).

Научная новизна работы

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

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

Практическая значимость работы

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

На основе предложенного метода разработан программный комплекс для решения задач оптимального управления с линейной и нелинейной динамикой, с функционалами интегрального и терминального вида, с различными типами краевых условий, геометрическими ограничениями на управление и смешанными ограничениями. Програмный комплекс предоставляет возможности для обработки полученных результатов, а также вывода их в графическом и табличном виде. Разработанный программный комплекс востребован в учебном и научном процессе и успешно используется на кафедре Оптимального Управления ВМиК МГУ.

Структура и объем работы

Настоящая диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации — 149 страниц, включая 35 рисунков. Библиография содержит 133 наименования.

Выход fas

Gamma he hype* £:dscfve rt n verse поппаЬге set iv'exp вос±гопез

•ас Апе»

Klf ' хШэбпзн грунм^ии ww команды, содержащей кпо^евое croaqjf X - рЮнапда дги решепия задачи ептимагъпого управления Л

Слраега

Q' Вставлять все как хоыентг^адй п f M't'fr*

Рис. 3.5. Панели вставки символов и ключевых слов

Позиция Тип символа

А1 .D5 малые греческие буквы

Е5 знак дифференцирования

Аб .D10 большие греческие буквы

ЕЮ набла

All знак стремления

А12 знак бесконечности

D11 . Е13 показатели степени (верхние индексы)

А14 . Е15 индексы элементов векторов (нижние индексы)

Символы с А1 по D10 могут использоваться в идентификаторах объектов.

Заключение

На основании результатов настоящей диссертационной работы сделаны следующие выводы:

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

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

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

В качестве развития настоящей работы в дальнейшем предполагается исследовать возможности развития предложенных алгоритмов на более широкие классы задач:

• задачи с особыми режимами,

• нелинейные по управлению задачи с фазовыми и смешанными ограничениями,

• задачи с фазовыми ограничениями глубины 1 и более.

1. Аввакумов С.Н. Гладкая аппроксимация выпуклых компактов // Труды Института математики и механики УрО РАН. Екатеринбург. 1996. Т.4. С. 184-200.

2. Аввакумов С.Н. Решение гладкой линейной задачи быстродействия методом продолжения по параметру с обратной связью. // Некотор. вопр. вычисл. мат., мат. физ. и прогр. обеспеч. — М.: Изд-во Моск. ун-та. 1988. С. 52-54.

3. Аввакумов С.Н., Киселев Ю.Н. Некоторые алгоритмы оптимального управления // Труды Института Математики и Механики УрО РАН. Екатеринбург. 2006. Т.12. №. С. 1-15.

4. Аввакумов С.Н., Киселев Ю.Н., Орлов М.В. Методы решения задач оптимального управления на основе принципа максимума Понтрягина // Труды Математического Института им. В.А. Стеклова РАН. 1995. Т.211. С. 3-31.

5. Антоник В.Г., Срочко В.А. Решение задач оптимального управления // Журнал вычислительной математики и математической физики. 1992. Т.32, т. С. 979-991.

6. Арутюнов А.В. К теории принципа максимума в задачах оптимального управления с фазовыми ограничениями // ДАН СССР. 1989. Т.304, т. с. п-14.

7. Арушанян О.В., Залеткин С.Ф. Численное решение обыкновенных дифференциальных уравнений па Фортране. — М.: Изд-во Моск. унта, 1990.

8. Асеев С.М. К теории необходимых условий оптимальности для задач с фазовыми ограничениями // Труды математического Института им. В.А. Стеклова РАН. 1998. Т.220. С. 35-44.

9. Атанс М., Фалб П. Оптимальное управление. — М.: Машиностроение, 1968.

10. Афанасьев А.П. Продолжение траекторий в оптимальном управлении. — М.: Эдиториал УРСС. — Труды Института Системного Анализа РАН. 2005. Т.17.

11. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. — М.: БИНОМ Лаборатория знаний, 2003.

12. Беллман Р. Динамическое программирование. — М.: Издательство иностранная литература, 1960.

13. Беллман Р., Калаба Р. Квазилинеаризация и нелинейные краевые задачи. М.: Мир, 1968.

14. Болдырев В.И. Метод кусочно-линейной аппроксимации для решения задач оптимального управления / / Дифференциальные уравнения и процессы управления. 2004. №1. С. 28-123(http://www.neva.ru/journal).

15. Болтянский В.Г. Математические методы оптимального управления. — М.: Наука, 1969.

16. Брайсон А., Хо Ю. Прикладная теория оптимального управления. — М.: Мир, 1972.

17. Васильев О.В. Методы оптимизации в функциональных пространствах. Иркутск: Изд-во Иркутского Университета, 1979.

18. Васильев О.В., Терлецкий В.А. Оптимальное управление краевой задачей // Труды Математического Института им. В.А. Стеклова РАН. 1995. Т.211. С. 121-130.

19. Васильев Ф.П. Методы оптимизации. — М.: Факториал пресс, 2002.

20. Васильев Ф.П. Методы решения экстремальных задач. — М.: Наука, 1981.

21. Васильев Ф.П. Численные методы решения экстремальных задач. — М.: Наука, 1988.

22. Габасов Р., Кириллова Ф.М. Качественная теория оптимальных процессов. — М.: Наука, 1971.

23. Гамкрслидзе Р.В. Оптимальные процессы управления при ограниченных фазовых координатах // Изв. АН СССР, сер. мат. 1960. Т.24, №3. С. 315-365.

24. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.

25. Гиндес В.Б. Один метод последовательных приближений для решения линейных задач оптимального управления // Журнал вычислительной математики и математической физики. 1970. Т.10, №1. С. 216-223.

26. Грачев Н.И., Евтушенко Ю.Г. Библиотека программ для решения задач оптимального управления // Журнал вычислительной математики и математической физики. 1979. Т.19, №2. С. 367-387.

27. Грачев Н.И., Фильков А.Н. Алгоритмические основы оптимизации управляемых систем с разрывной правой частью. — М.: ВЦ АН СССР, 1988.

28. Грачев Н.И., Фильков А.Н. Решение задач оптимального управление в системе ДИСО. М.: ВЦ АН СССР, 1986.

29. Григолюк Э.И., Шалашилин В.И. Проблемы нелинейного деформирования. — М.: Наука, 1988.

30. Давиденко Д.Ф. Об одном новом методе решения систем нелинейных уравнений // Доклады АН СССР. 1953. Т.88. С. 601-602.

31. Давиденко Д.Ф. О приближенном решении систем нелинейных уравнений // Украинский мат. журнал. 1953. Т.5. №2. С. 196-206.

32. Демьянов В.Ф., Рубинов A.M. Приближенные методы решения экстремальных задач. JL: Изд-во Ленинградского Государственного Университета, 1968.

33. Дикусар В.В. Задачи на экстремум при наличии ограничений // Со-росовский Образовательный Журнал. 1999. №1. С. 117-123.

34. Дикусар В.В., Милютин А.А. Качественные и численные методы в принципе максимума. — М.: Наука, 1989.

35. Дикусар В.В., Кошька М., Фигура А. Метод продолжения по параметру при решении краевых задач в оптимальном управлении // Дифференциальные уравнения. 2001. Т.37, №4. С. 453-457.

36. Дмитрук А.В., Милютин А.А., Осмоловский Н.П. Принцип максимума в оптимальном управлении. — М.: Изд-во механико-математического факультета МГУ, 2004.

37. Дубовицкий А.Я., Милютин А.А. Задачи на экстремум при наличии ограничений // Журнал вычислительной математики и математической физики. 1965. Т.5, т. С. 395-453.

38. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. — М.: Наука, 1982.

39. Евтушенко Ю.Г., Жадан В.Г. Барьерно-проективные и барьерно-ныотоновские численные методы оптимизации (случай нелинейного программирования). — М.: ВЦ АН СССР, 1991.

40. Ермольев Ю.М., Гуленко В.П. О численных методах решения задач оптимального управления // Кибернетика. 1966. NQ1. С. 72-78.

41. Жулин С.С. Применение метода продолжения по параметру для решения сложных задач оптимального управления // Сборник статей молодых ученых факультета ВМиК МГУ, — М.: Издательский отдел факультета ВМиК МГУ; МАКС-Пресс. 2006. Вып. 3. С. 65-76.

42. Жулин С.С. Метод продолжения по параметру и его приложение к задачам оптимального управления // Вычислительные методы и программирование. 2007. Т. 8. С. 205-217 (http://num-meth.srcc.msu.ru/).

43. Жулин С.С. Численное решение П-систем для задач оптимального управления с фазовыми и смешанными ограничениями // Сборник статей молодых ученых факультета ВМиК МГУ, — М.: Издательский отдел факультета ВМиК МГУ; МАКС-Пресс. 2007. Вып. 4. С. 48-56.

44. Жулин С.С. Метод продолжения по параметру для поиска экстремали в задаче оптимального управления // Дифференциальные уравнения. 2007. Т. 43, №11. С. 1460-1469.

45. Жулин С.С. Метод продолжения по параметру с коррекцией и его приложения // Прикладная математика и информатика. Сборник статей, — М.: Издательский отдел факультета ВМиК МГУ. 2009. №30. С. 55-94.

46. Исаев В.К., Сонин В.В. Об одной модификации метода Ньютона численного решения краевых задач // Журнал вычислительной математики и математической физики. 1963. Т.З, №6. С. 1114-1116.

47. Кирия B.C. Движение тел в сопротивляющихся средах // Труды Тбилисского гос. ун-та, №44, 1951, С. 1-20.

48. Киселев Ю.Н. Оптимальное управление. — М.: Изд-во МГУ, 1988.

49. Киселев Ю.Н. Построение точных решений для нелинейной задачи оптимального быстродействия специального вида // Фундаментальная и прикладная математика. 1997. Т.З, Вып. 3. С. 847-868.

50. Киселев Ю.Н. Схема продолжения по параметру в нелинейной задаче быстродействия // Вестник Моск. ун-та, Сер. 15. 1990. №2. С. 51-52.

51. Киселев Ю.Н., Аввакумов С.Н., Орлов М.В. Оптимальное управление. Линейная теория и приложения: Учебное пособие. — М.: МАКС Пресс, 2007. 272 с.

52. Киселев Ю.Н., Орлов М.В. Численные алгоритмы линейных быстродействий // Журнал вычислительной математики и математической физики. 1991. Т.31, №12. С. 1763-1771.

53. Киселев Ю.Н, Орлов М.В. Метод потенциалов в линейной задаче быстродействия // Дифференциальные Уравнения. 1996. Т.32, №1. С. 44-51.

54. С. Д. Красников, Е. Б. Кузнецов. Параметризация численного решения нелинейных краевых задач // Матем. моделирование. 2006. Т.18, №9. С. 3-16.

55. Красносельский М.А., Вайникко Г.М., Забрейко П.П., Рутицкий Я.В., Стеценко В.Я. Приближенное решение операторных уравнений. — М.: Наука, 1969.

56. Красовский Н.Н. Теория управления движением. — М.: Наука, 1968.

57. Кротов В.Ф., Гурман В.И. Методы и задачи оптимального управления. — М.: Наука, 1973.

58. Кузнецов Е.Б. Наилучшая параметризация при построении кривых //Ж. вычисл. матем. и матем. физ. 2004. Т.44, №9. С. 1540—1551.

59. Ли Э.В., Маркус Л. Основы теории оптимального управления. — М.: Наука, 1972.

60. Моисеев Н.Н. Численные методы в теории оптимальных систем. — М.: Наука, 1971.

61. Моисеев Н.Н. Элементы теории оптимальных систем. — М.: Наука, 1975.

62. Ортега Дж., Рейнболт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975.

63. Полак Э. Численные методы оптимизации. Единый подход. — М.: Мир, 1974.

64. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. — М.: Наука, 1969.

65. Пуанкаре А. О кривых, определяемых дифференциальными уравнениями. — M.-JL: ГИЗ технико-теоретической литературы, 1947.

66. Розоноэр Л.И. Принцип максимума JI.C. Понтрягина в теории оптимальных систем I—III // Автоматика и телемеханика. 1959. Т.20. №10, С. 1320-1334. №11, С. 1441-1458. №12, С. 1561-1578.

67. Рябов А.Ю., Орлов М.В. Графический пакет ТАЙМЕР для решения линейной задачи быстродействия. — М.: Центр Диалог, МГУ. 1992.

68. Срочко В.А. Итерационные методы решения задач оптимального управления. — М.: Физматлит, 2000.

69. Стрекаловский А.С. О невыпуклых задачах оптимального управления // Вестник Моск. ун-та. Сер. 15. 1993. №1. С. 9-13.

70. Стрекаловский А.С. Поиск глобального решения в невыпуклых задачах оптимизации. Дис. д-ра физ.-мат. наук. — Иркутск, 1992.

71. Стрекаловский А.С. Элементы невыпуклой оптимизации. РАН, сиб. отд. Ин-т динамики систем и теории управления. — Новосибирск: Наука, 2003.

72. Табак Д., Кус Б. Оптимальное управление и математическое программирование. — М.: Наука, 1975.

73. Тихонов А.Н., Галкин В.Я., Заикин П.Н. О прямых методах решения задач оптимального управления // Журнал вычислительной математики и математической физики. 1967. Т.7, №2. С. 416-423.

74. Тятюшкин А.И. Численные методы и программные средства оптимизации управляемых систем. — Новосибирск: Наука. Сиб. отд-ние, 1992.

75. Федоренко Р.П. Приближенное решение задач оптимального управления. — М.: Наука, 1978.

76. Филиппов А.Ф. Дифференциальные уравнения с разрывной правой частью. — М.: Наука, 1985.

77. Фок В.А. Дифракция волн вокруг земной поверхности. — M.-JL: изд. АН СССР, 1946.

78. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи. — М.: Мир, 1999.

79. Хапаев М.М. Сингулярные дифференциальные уравнения в задачах управления и минимизации // Труды Математического Института им. В.А. Стеклова РАН. 1995. Т.211. С. 411-418.

80. Хофер Э., Лундерштедт Р. Численные методы оптимизации. — М.: Машиностроение, 1981.

81. Черноусько Ф.Л., Баничук Н.В. Вариационные задачи механики и управления. Численные методы. — М.: Наука, 1973.

82. Шалашилин В.И. Метод продолжения по параметру и его применение к задаче больших прогибов непологой круговой арки // Изв. АН СССР. Механика тверд, тела. 1979. №4. С. 178-184.

83. Шалашилин В.И., Кузнецов Е.Б. Метод продолжения решения по параметру и наилучшая параметризация. — М.: Эдиториал УРСС, 1999.

84. Шаманский В.Е. Методы численного решения краевых задач на ЭЦВМ. — Киев: Наукова Думка, 1966.

85. Шидловская Н.А. Применение метода дифференцирования по параметру к решению нелинейных уравнений в банаховых пространствах // Уч. зап. Львовского гос. ун-та, сер. матем. н., 1958, №33, С. 3-17.

86. Allgower E.L., Bates D.J., Sommese A.J., Wampler C.W. Solution of polynomial systems derived from differential equations // Computing. 2006. V.76, №. P. 1-10.

87. Allgower E.L., Georg K. Introduction to numerical continuation methods. Berlin, New York: Springer-Verlag, 1990. (Reprinted as volume 45 of Classics in Applied Mathematics. SIAM, Philadelphia, PA, 2003).

88. Allgower E.L., Georg K. Numerically stable homotopy methods without an extra dimension. 1988.

89. Balakrishnan A.V. On a new computing technique in optimal control // SIAM Journal on Control. 1968. V.6, №2. P. 149-173.

90. Bates D.J. Theory and applications in numerical algebraic geometry. Ph.D. Dissertation, University of Notre Dame, Indiana, 2006. (http://www.nd.edu/~dbatesl/preprints/batesthesis.pdf).

91. Bates D.J., Sommese A.J., Wampler C.W. Multiprecision path tracking // Submitted to SIAM J. Numer. Anal, (http: //www.nd.edu/~dbatesl / preprints/amp. pdf).

92. Betts J.T. SOCS: the sparse optimal control software family. Boeing, Tech. Rep., 1996.

93. Bonnard В., Caillau J-B. Introduction to nonlinear optimal control. Lecture notes, Formation en Automatique a Paris Graduate Paris School on Control, 2005.

94. Bonnard В., Caillau J-B., Dujol R. Continuation methods and single input time optimal orbital transfer. Institut de Mathematiques de Bourgogne, Preprint, 2006. http: / / math.u-bourgogne.fr/topo/prepub/continuation.pd£

95. Bosarge W. Infinite dimensional iterative methods and applications. IBM Houston Sci. Center Rept 320. Houston, Texas, 1968.

96. Catinas E. The inexact, inexact perturbed and quasi-Newton methods are equivalent models // Mathematics of Computation. 2004. V.74, №249. P.291-301.

97. Clarke F.H. The maximum principle under minimal hypoteses // SIAM Journal on Control and Optimization. 1976. V.14, №2. P. 1078-1091.

98. Decarolis F., Mayer R., Santamaria M. Homotopy Continuation Methods: An Algorithm for the Fixed Point and Newton Homotopy Methods with Some Examples, The University of Chicago, Preprint, 2005.

99. Dembo R.S., Eisenstat S.C., Steihaug T. Inexact Newton methods // SIAM J. Numer. Anal. 1982. V.19, P. 400-408.

100. Dunlavy D.M., O'Leary D.P. Homotopy optimization methods for global optimization. 2005. Preprint. (http://www.cs.umd.edu/~oleary/tr/4773.pdf).

101. Ehtamo H., Raivio Т., Hamalainen R.P. A continuation method for minimum time problems. Helsinki University of Technology, Systems Analysis Laboratory Research Report, E3 March 2000.

102. Gamkrelidze R.V. On some extremal problems in the theory of differential equations with applications to the theory of optimal control // SIAM Journal on Control. 1965. V.3. P. 106-128.

103. Gergaud J., Haberkorn T. Homotopy method for mininum consumption orbit transfer problem // ESAIM Control Opt. and Calc. of Var. 2006. V.40, №.

104. Hartl R.F., Sethi S.P., Vicson R.G. A survey of the maximum principles for optimal control problems with state constraints // SIAM Review. 1995. V.37, №. P. 181-218.

105. Jennings L.S., Fisher M.E., Teo K.L., Goh C.J. MISER3 optimal control software: theory and user manual. 2002. (http: / / www.cado.uwa.edu.au / miser/manual.html).

106. Keller H.B. Global homotopies and Newton methods // Recent advances in numerical analysis. New York, London: Academic Press. 1978. P. 73-94.

107. Kelley C.T. Iterative methods of optimization. SIAM: Frontiers in Applied Mathematics 18. 1999.

108. Kelley C.T., Sachs E.W. Approximate quasi-Newton method // Mathematical programming. 1990. V.48, №1. P. 41-70.

109. Klatte D., Kummer B. Nonsmooth equations in optimization. Kluwer Academic Publishers, 2002.

110. Lahaye M.E. Solution of system of transcendental equations // Acad. Roy. Belg. Bull. CI. Sci. 1948. V.5. P. 805-822.

111. Lange K. Optimization. New York: Springer-Verlag, 2004.

112. Makowski K., Neustadt L.W. Optimal control problems with mixed control-phase variable equality and inequality constraints // SIAM Journal on Control. 1974. V.12, №. P. 184-228.

113. Martinez J.M. Quasi-inexact-Newton methods with global convergence for solving constrained nonlinear systems. Nonlinear Analysis, Theory, Methods and Applications 30. P. 1-8.

114. Morini B. Convergence behaviour of inexact Newton methods // Mathematics of Computation. 1999. V.68, №228. P.1605-1613.

115. Morrison D.D., Riley J.D., Zancanaro J.F. Multiple shooting method for two-point boundary value problems // Communications of ACM. 1962. P. 613-614.

116. Nocedal J., Wright S.J. Numerical optimization. Springer-Verlag, 1999.

117. Percell P. Note on a global homotopy // Numer. Funct. Anal. Optim. 1980. №. P. 99-106.

118. Polak E. An historical survey of computational methods in optimal control // SIAM Review. 1973. V.15, №2. P. 553-584.

119. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical recipes in C. Cambridge University Press, 1992.

120. Rao A.V. Users Manual for GPOCS: A MATLAB Implementation of the Gauss Pseudospectral Method for Solving Multiple-Phase Optimal Control Problems. Feb. 2008.

121. Roberts S., Shipman J. Continuation in shooting methods for two-point boundary value problems //J. Math. Anal. Appl. 1967. V.18, P. 45-58.

122. Rockafellar R.T. Augumented Lagrange multiplier functions and duality in nonconvex programming // SIAM Journal on Control. 1974. V.12, №2. P. 268-285.

123. M. Ross. Users Manual For DIDO: A MATLAB Application Package for Solving Optimal Control Problems / / Naval Postgraduate School, Monterey, CA, Tech. Rep. 0401.0, Feb. 2004. http://tomlab.biz/docs/DIDOManualPRl.pdf

124. Saigal R., Todd M.J. Efficient acceleration techniques for fixed point algorithms // SIAM Journal on Numerical Analysis. 1978. V.15, №5. P. 997-1007.

125. Stryk О. DIRCOL: a direct collocation method for the numerical solution of optimal control problems. 1999. (http://www.sim.informatik.tu-darmstadt.de/sw/dircol/dircol pub.html).

126. Watson L.T. Numerical linear algebra aspects of globally convergent homotopy methods // SIAM Review. 1986. V.28, №4. P. 529-545.

127. Watson L.T. Theory of globally convergent probability-one homotopies for nonlinear programming // SIAM Journal on Optimization. 2000. V.ll. P. 761-780.

128. 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).