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

§ 0.1. Общее описание проблемы

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

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

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

§ 0.2. Формулировка темы работы. Актуальность

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

Как известно [7,8,14,22,35,37,50,66] основным методам решения задач оптимального управления с фазовыми и смешанными ограничениями являются: прямые методы (спуск в пространстве управлений), метод вариации фазовых переменныхметод штрафных функцийметод приращения функционалапринцип максимума.

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

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

Как правило, возникающая в этом случае краевая задача требует решения трех основных проблем:

— задачи Коши для обыкновенных дифференциальных уравнений;

— задачи нелинейного программирования (для каждой расчетной точки t);

— поиск нулей трансцендентных функций.

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

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

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

Как известно, принцип максимума для простейшей нелинейной задачи оптимального управления был сформулирован Понтрягиным J1.C. и обоснован Болтянским В. Г. [54,55]. С тех пор появилось значительное число работ, посвященных использованию принципа максимума в различных задачах оптимального управления [58,49,68]. Приведем краткое изложение основных, полученных в них результатов.

Наиболее глубокие и серьезные теоретические исследования проблемы были проведены в работах Милютина А. А. и Дубовицкого А. Я. [5,25,29,30,48]. В этих работах теория принципа максимума была распространена на широкий класс задач с фазовыми и смешанными ограничениями (в том числе и нерегулярными). По существу, теоретическая проблема получения необходимых условий первого порядка для указанных задач в этих работах полностью решена. Однако с практической точки зрения при решении задач Коши в схемах основанных на этих условиях возникают дополнительные проблемы, которые требуют применения специальных методов. Прежде всего это, так называемая, жесткость задачи Коши, являющаяся отражением того факта, что в рассматриваемом объекте протекают разнотемповые процессы. Выделение жестких систем уравнения в отдельный класс вызвано трудностями их численного интегрирования классическими явными методами. Оказалось, что малый шаг интегрирования, используемый для временных интервалов с большими по модулю производными, не может быть увеличен для других интервалов, хотя производные там становятся существенно меньше. Для устранения указанного ограничения были предложены различные методы [9,31,40,45,20,46,33,49], однако и в настоящее время проблема численного решения жестких систем остается актуальной. Это связано с увеличением классов решаемых задач, общностью их постановки и разнообразием численных методов.

Работы по созданию численных методов ведутся в двух направлениях. Первое направление связано с применением неявных схем (Ваннер Г., Хайрэр Э., Федоренко Р. П. и др. 59,63,68,61]). Другое направление связано с расширением границ применимости явных схем (Лебедев В.И., Шалашилин В. И., Кузнецов Е. Б., Дикусар В. В. и др. 65,43,41,26,27]) Отметим также и скрытые формы проявления жесткости. Например, большой класс гладких оптимизационных конечномерных задач с трудом поддается решению традиционными методами первого и второго порядка из-за овражного рельефа поверхностей уровней. Исследования этого явления показали, что трудности связанные с жесткостью системы, описывающих траекторию наискорейшего спуска могут существенно осложнить применение принципа максимума [56,64,33].)

Для предварительной оценки определения геометрии оптимальной траектории используют метод приращения функционала, а также дискретизацию исходной непрерывной задачи. В результате получается задача нелинейного программирования большой размерности. Важным частным случаем такой задачи является задача линейного программирования (ЛП). Возможностям использования нелинейного и линейного программирования для решения задач оптимального управления посвящено значительное количество исследований, в числе которых [4,13,14,16,17,21,23,34,38,42,51,53,57], содержащие полезные для практики результаты.

Евтушенко Ю.Г. и Жадан Ю. Д. [34,36] распространили идеи проектирования градиента и метода барьерных функций на общие задачи нелинейного программирования. Несколько вариантов метода было реализовано программно и включено в библиотеку ДИСО. Следует отметить, что метод внутренней точки для задач ЛП [3] следует из работ Евтушенко Ю. Г. и Жадана Ю. Д. как частный случай, что подтверждается публикацией вышеупомянутых авторов в 1973 году. Отметим, что при решении задач оптимального управления методы дискретизации приводят к задачам ЛП большой размерности, которые как правило, плохо обусловлены. Для такого рода задач применяют специальные методы регуляризации (Бакушинский А.Б., Гончарский Л. В., Васильев Ф. П. и др.). В работах Мангасарьяна и его сотрудников [2] основное внимание уделялось нахождению нормальных решений в задачах ЛП. Левиков А. А., Умнов А. Е. сводили задачу ЛП к задачам нелинейной параметрической [44,63]. Для задач квадратичного и линейного программирования применяются конечные и итеративные методы (Поляк Б.Т., Афанасьев А. П., Дикусар В. В., и др. [10,6]). Основные трудности решения указанных задач связаны с их плохой обусловленностью.

Отметим, что при решении ряда задач оптимального управления с фазовыми и смешанными ограничениями принцип максимума вырождается, т. е. становится тривиальным. Последнее означает, что для исследования задачи необходимо применять методы высших порядков [1,18,19,28,67]. Многие авторы рассматривали этот вопрос в плане расширения границ применимости принципа максимума в вырожденных задачах. Их результаты в основном связаны с теоремами существования принципа максимума для вырожденного случая. В их числе следует указать работу Дикусара В. В. 24], который применил методы регуляризации структуры ограничений, что позволило распространить принцип максимума на вырожденные задачи.

Наконец, представляется необходимым отметить наиболее интересные результаты использования принципа максимума для решения прикладных задач оптимального управления с фазовыми и смешанными ограничениями [15,32,39,52,60,62].

§ 0.3. Цель работы и предлагаемый подход к решению

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

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

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

Основные полученные результаты состоят в следующем.

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

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

3. Для предлагаемой схемы реализована, экономичная с точки зрения затрат вычислительных ресурсов, программная реализация для ПЭВМ класса IBM-PC.

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

§ 0.4. Методы исследования

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

§ 0.5. Объем и структура диссертации

Диссертация содержит 104 страницы текста, включая рисунки. Текст разделен на введение, 3 главы, заключение, приложение и список литературы из 76 наименований.

Основные результаты проведенного диссертационного исследования следующие:

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

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

3. Для предлагаемой схемы выполнена, экономичная с точки зрения затрат вычислительных ресурсов, программная реализация для ПЭВМ класса IBM-PC.

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