Содержание к диссертации
Введение
Глава 1. Полиэдральная аппроксимация множеств достижимости линейных управляемых систем 14
1.1. Полиэдральная аппроксимация выпуклых тел с частично гладкой границей 15
1.2. Метод расчета опорной функции множества достижимости линейной управляемой системы с гарантированной оценкой погрешности 29
1.3. Аппроксимация терминального множества достижимости с априорной и апостериорной оценками погрешности 41
1.4. Гарантированно внутренняя и гарантированно внешняя аппроксимации терминального множества достижимости 47
Глава 2. Методы многошаговой аппроксимации множеств достижимости с гарантированной оценкой погрешности 59
2.1. Метод крупных шагов для аппроксимации последовательности множеств достижимости 60
2.2. Построение гарантированно внутренней и гарантированно внешней аппроксимаций последовательности множеств достижимости 69
2.3. Использование метода крупных шагов для аппроксимации множеств достижимости непрерывно-дискретных систем 83
2.4. Метод движущейся паретовой границы в динамических задачах многокритериальной оптимизации 94
Глава 3. Реализация методов и экспериментальные расчеты 99
3.1. Реализация метода построения аппроксимации терминального множества достижимости линейной системы 99
3.2. Реализация метода построения многошаговой аппроксимации последовательности множеств достижимости 106
3.3. Реализация метода построения аппроксимации паретовой границы для динамической задачи многокритериальной оптимизации 115
Заключение 118
Список литературы
- Метод расчета опорной функции множества достижимости линейной управляемой системы с гарантированной оценкой погрешности
- Гарантированно внутренняя и гарантированно внешняя аппроксимации терминального множества достижимости
- Построение гарантированно внутренней и гарантированно внешней аппроксимаций последовательности множеств достижимости
- Реализация метода построения многошаговой аппроксимации последовательности множеств достижимости
Введение к работе
Математические методы оптимизации являются часто используемым средством компьютерной поддержки поиска эффективных решений сложных проблем. Среди таких методов все более важную роль играют методы многокритериальной оптимизации, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым решениям ([22]-[24], [29], [30]). Решением задачи многокритериальной оптимизации является множество решений, эффективных по Парето, и соответствующая (паретова) граница множества достижимых критериальных векторов.
В последнее время все большее внимание привлекают динамические задачи многокритериальной оптимизации, в которых требуется найти эффективные решения задач проектирования динамических систем. Методы анализа таких задач могут быть основаны на использовании методов оптимизации динамических систем, основы которых были заложены Л.С. Понтрягиным и его школой. Близость методов оптимизации динамических систем и многокритериальной оптимизации особенно ясно проявляется при сопоставлении методов аппроксимации множеств достижимости динамических систем, развиваемых в нашей стране наряду со школой Л.С. Понтрягина школами А.Б. Куржанского и Ф.Л. Черноусько, и методов аппроксимации паретовой (недоминируемой) границы в задачах многокритериальной оптимизации, разрабатываемых школой П.С. Краснощекова. Оба упомянутых класса методов основаны на аппроксимации многомерных множеств, так что результаты работ в одной области могут быть применены в другой. Этот факт использован в исследованиях группы А.В. Лотова, проводящихся в ВЦ РАН и ВМиК МГУ и направленных на аппроксимацию и визуализацию выпуклых множеств. Методы аппроксимации множеств достижимости для линейных управляемых систем, разработанные в 70-е годы прошлого века, были затем использованы в многокритериальном методе достижимых целей (МДЦ), в рамках которого аппроксимируется либо множество достижимых критериальных векторов, либо его оболочка Эджворта-Парето (ОЭП), т.е. максимальное множество, имеющее ту же паретову границу. В свою очередь, оптимальные методы полиэдральной аппроксимации ОЭП были в дальнейшем использованы для аппроксимации выпуклых множеств достижимости динамических систем.
Данная диссертационная работа посвящена развитию методов многокритериальной оптимизации, предназначенных для анализа и поиска эффективных решений в динамических системах на основе применения идей МДЦ. В рамках МДЦ человек изучает многокритериальную паретову границу с помощью ее интерактивной визуализации с использованием двумерных сечений аппроксимации ОЭП. Далее он указывает предпочтительную точку на паретовой границе и получает компромиссное Парето-эффективное решение. Такой подход показал свою полезность в задачах проектирования.
Применение МДЦ для поиска парето-эффективных решений экономических задач началось еще в семидесятых годах ([26]), а с середины восьмидесятых годов МДЦ используется для поиска парето-эффективных стратегий улучшения состояния окружающей среды ([29], [30]). Другой важной областью применения МДЦ является изучение возможных вариантов технических систем на предпроектной стадии процесса проектирования. Дальнейшее развитие МДЦ связано с его применением в сети Интернет, где метод может быть использован в системах электронной торговли, выбора экологических решений и т.д. ([58]).
Необходимо отметить, что ранее МДЦ, как правило, применялся для визуализации паретовой границы в статических задачах многокритериальной оптимизации, а при изучении динамических моделей рассматриваемые задачи сводились к задачам статического типа на основе аппроксимации множеств достижимости только в терминальный момент времени. В то же время, представляющие практический интерес динамические задачи многокритериальной оптимизации, в которых критерии могут зависеть от времени (например, время может являться одним из критериев задачи), ранее с помощью МДЦ не изучались. Как показано в диссертации, решающее значение для применения МДЦ в этом случае имеет наличие алгоритмов пошаговой аппроксимации множеств достижимости динамических систем во все моменты изучаемого временного интервала с гарантированной оценкой погрешности полученной аппроксимации. Таким образом, тема работы, направленной на решение этой задачи, является актуальной.
Данная диссертационная работа посвящена разработке, изучению и программной реализации методов анализа динамических задач многокритериальной оптимизации на основе пошаговой аппроксимации множеств достижимости динамических систем. При этом основное внимание уделяется оцениванию точности полученных аппроксимаций множеств достижимости динамических систем и ОЭП соответствующих задач многокритериальной оптимизации.
Математическая задача многокритериальной оптимизации выглядит следующим образом. Пусть задано некоторое пространство решений W и пусть критериальное пространство является -мерным линейным пространством R. Пусть задано X с W - множество возможных (допустимых) решений. Пусть связь между решениями и значениями критериев выбора решения устанавливается отображением / :W - Rd . Будем считать, что лицо, принимающее решение, (ЛПР) заинтересовано в уменьшении значений каждого из d критериев. В таком случае критериальная точка У є Rd доминирует (по Парето) другую критериальную точку у є Rd, если у у, т.е. у, yi, i=l, ..., d, и У Фу. Недоминируемая по Парето (в дальнейшем, просто недоминируемая) граница множества достижимых критериальных векторов Y = f{X), определяемая как множество недоминируемых точек у є Г, в этом случае имеет вид P(Y) = {yeY:{/eY:y y,y y} = 0}.
Множество P(Y) часто называют паретовой границей, оно характеризует совокупность компромиссов, разумных с точки зрения рассматриваемых критериев, и представляет наибольший интерес для ЛПР, заинтересованных в поиске эффективных решений проблемы. Оболочка Эджворта-Парето множества критериальных векторов имеет вид Y = Y + Rd+, где R неотрицательный ортант пространства Rd. Поскольку паретова граница ОЭП совпадает с паретовой границей множества Y = f(X), в многокритериальных методах ОЭП можно использовать вместо Y.
Методы поддержки принятия решения, основанные на многокритериальной оптимизации, тем или иным образом дают возможность отбора наиболее предпочтительной точки множества P(Y). Особенностью МДЦ является предварительная аппроксимация множества Y и дальнейшая визуализация его паретовой границы P(Y) с использованием двумерных сечений аппроксимации Y .
В диссертации в качестве множеств возможных решений рассматриваются множества достижимости линейной динамической системы
x = Ax + u(t), 0 t T, (0.1)
где t - время, х- п -мерный вектор фазовых координат, и - п -мерный вектор управляющих воздействий, А - матрица размера ггхп, на вектор управлений в каждый момент времени / є [0,Г] наложено ограничение
u(t)eU, (0.2)
где UczR" - заданный непустой выпуклый многогранник. Кроме того, считается заданным непустой выпуклый многогранник Х0 с: R" исходных состояний системы
х(0)еХ0. (0.3)
Как обычно, под множеством достижимости X(t ) системы (0.1)-(0.3) в некоторый момент времени t e[0,T] понимается множество концов x(t ) всех траекторий x(t), 0 t t , допустимых в силу системы. В силу линейности системы и выпуклости ограничений для аппроксимации множеств достижимости можно использовать методы полиэдральной аппроксимации выпуклых тел. На основе полученной аппроксимации множества достижимости X(t ) в момент времени / можно построить полиэдральную аппроксимацию множества достижимых критериальных векторов или его ОЭП в этот момент времени.
Таким образом, возникает следующая задача: пусть заранее по каким-то причинам выбрана последовательность моментов времени
О /, t2 ... tM Т. Построив последовательность многогранников
Хх, Х2,...,ХМ, аппроксимирующих в заданные моменты времени множества достижимости X{tx), X(t2),..., X(tM), мы можем далее с помощью методов полиэдральной аппроксимации построить аппроксимацию их ОЭП и визуализировать паретовы границы соответствующих множеств. Тем самым можно продемонстрировать зависимость паретовой границы от времени.
К настоящему времени были разработаны различные подходы к аппроксимации множеств достижимости, наиболее известными из которых являются эллипсоидальная аппроксимация и полиэдральная аппроксимация. Методы эллипсоидальной аппроксимации, основанные на аппроксимации отдельным эллипсоидом [40] или пересечением и объединением эллипсоидов, построенных на основе решения систем обыкновенных дифференциальных уравнений [57], [32] дают возможность дать оценку расположения множества достижимости. В отличие от методов эллипсоидальной аппроксимации, методы полиэдральной аппроксимации, предложенные Л.С. Понтрягипым в его предисловии к книге [34], позволяют осуществить аппроксимацию множества достижимости с любой степенью точности. Методы, основанные на идее Л.С. Понтрягина, используют измерение опорной функции множества достижимости. Несмотря на то, что было разработано несколько альтернативных подходов к построению полиэдральной аппроксимации множеств достижимости линейных динамических систем (см., например, [25], [27], [21], [56]), основным практическим средством полиэдральной аппроксимации остаются методы, использующие расчет опорной функции для направлений, выбираемых оптимальным образом.
Поскольку в МДЦ требуется аппроксимировать ОЭП с любой заранее заданной точностью на основе построенной аппроксимации множества достижимости, в данной работе используются методы полиэдральной аппроксимации множеств достижимости, основанные на расчете опорной функции. В книге [34] для расчета опорной функции множеств достижимости предложено использовать принцип максимума для терминальных задач оптимизации со свободным концом. Точность численного расчета опорной функции множеств достижимости линейных динамических систем на основе использования принципа максимума изучалась в работах [37], [13], в которых была доказана сходимость получаемой оценки к точному значению опорной функции. В данной диссертации дается гарантированная оценка погрешности расчета опорной функции. Как и следовало ожидать из работ [63], [45], погрешность расчета опорной функции стремится к нулю с квадратичной скоростью по шагу дискретизации по времени. Важно, что в данной диссертации рассчитывается не только скорость, но и константа сходимости, в формулу расчета которой входит число переключений функции оптимального управления, оцененное в работах [34], [55], [38]. Гарантированная оценка погрешности расчета опорной функции позволяет при использовании методов полиэдральной аппроксимации выпуклых компактных тел [29], [30], [58] конструктивно получить гарантированные внешние и внутренние оценки множеств достижимости линейной динамической системы с любой заданной степенью точности.
Как уже говорилось, методы, использующие расчет опорной функции, обычно направлены на аппроксимацию единственного множества достижимости в некоторый (обычно, конечный) момент времени. В многокритериальных проблемах, рассматриваемых в данной диссертации, требуется построение множеств достижимости в промежуточные моменты времени. В [28] был предложен метод укрупненных шагов, в котором множества достижимости в выбранные моменты времени строятся последовательно, последующее на основе предыдущего. В книге [30] было предложено использовать для этого расчет опорной функции, который для каждого следующего множества X(tk) основан на использовании аппроксимации предьщущего множества X(tk_{) (метод крупных шагов). До
настоящего времени метод крупных шагов не был реализован в связи с тем, что не была решена проблема построения оценки погрешности, привносимой из-за такого расчета опорной функции. Эта проблема была подчеркнута, например, в [58].
Гарантированные внешние и внутренние оценки множеств достижимости линейной динамической системы с любой заданной степенью точности, полученные в данной работе, позволили реализовать на практике метод крупных шагов. При этом осуществляется как апостериорное оценивание погрешности в процессе аппроксимации, так и априорное оценивание, позволяющее разумным образом выбрать параметры алгоритмов. Решение этой проблемы особенно важно в связи с возможностью использования последовательности множеств достижимости для анализа паретовой границы в динамических задачах многокритериальной оптимизации, имеющих важное прикладное значение. Кроме того, разработанная техника применима не только для систем типа (0.1)-(0.3), но и для непрерывно-дискретных систем, в которых в моменты времени t\,...,tM происходит импульсное воздействие или изменение закона движения. Этим определяется актуальность данной диссертационной работы.
Итак, диссертационная работа посвящена разработке и анализу методов полиэдральной аппроксимации последовательности множеств достижимости линейных автономных динамических систем с вычислением оценок погрешности аппроксимации и применению методов при решении динамических задач многокритериальной оптимизации на основе визуализации движущейся недоминируемой границы Парето. Цели диссертационной работы:
1) Разработать методы пошагового построения аппроксимации последовательности множеств достижимости для линейной динамической системы с вычислением погрешности аппроксимации, в том числе с автоматическим выбором шага аппроксимации по времени и точности полиэдральной аппроксимации. В рамках этой задачи потребовалось:
• получить оценки точности расчета значения опорной функции множества достижимости линейной управляемой системы;
• разработать методы аппроксимации терминального множества достижимости с априорной и апостериорной оценками погрешности;
• построить апостериорную оценку погрешности при пошаговой аппроксимации множеств достижимости;
• разработать метод априорного расчета значений параметров аппроксимации для достижения заданной точности аппроксимации.
2) Построить оценки скорости сходимости многогранников наилучшей аппроксимации для тел с частично гладкой границей.
3) Применить метод крупных шагов с оценками погрешности аппроксимации в задаче пошаговой аппроксимации множеств достижимости непрерывно-дискретных систем.
4) Разработать метод визуализации динамической границы Парето для задач многокритериальной оптимизации в случае линейных автономных управляемых систем.
5) Реализовать программное обеспечение для персональных компьютеров, основанное на разработанных методах и провести экспериментальные расчеты.
Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения.
Первая глава посвящена методам полиэдральной аппроксимации множества достижимости в терминальный момент времени с гарантированной точностью аппроксимации. Результаты этой главы создают основу для построения метода крупных шагов, которому посвящена глава 2. В §1.1 изучается полиэдральная аппроксимация выпуклых компактных тел (ВКТ) с частично гладкой границей. Показано, что для ВКТ, граница которых имеет гладкие участки с положительной гауссовой кривизной, последовательность многогранников наилучшей аппроксимации имеет скорость сходимости точности аппроксимации равную 0{т 21 п Х)), где п -размерность пространства, а т - число вершин аппроксимирующего многогранника. Далее показывается, что метод Уточнения Оценок, предложенный в [10] и являющийся наиболее исследованным методом полиэдральной аппроксимации ВКТ, порождает последовательность аппроксимирующих многогранников, имеющую оптимальную скорость сходимости для ВКТ с частично гладкой границей, в том числе и для множеств достижимости. Этот метод используется в диссертации при полиэдральной аппроксимации множеств достижимости. В §1.2 получена оценка точности расчета значения опорной функции множества достижимости линейной автономной управляемой системы. Найдена как скорость (квадратичная по шагу дискретизации по времени), так и константа сходимости погрешности аппроксимации. Кроме того, приведены примеры конкретизации гарантированной оценки на основе использования известных результатов по оценке числа переключений функции оптимального управления. В §1.3 - §1.4 предложены методы полиэдральной аппроксимации терминального множества достижимости с гарантированной оценкой погрешности на основе предложенного метода расчета опорной функции. Представлены методы построения как одного аппроксимирующего многогранника (§1.3), так и пары многогранников, состоящей из гарантированно внутреннего и гарантированно внешнего многогранников (§1.4). Для каждого метода приведена апостериорная оценка погрешности аппроксимации. Также исследован вопрос о том, какие значения параметров аппроксимации (шага разбиения временного отрезка для метода расчета опорной функции и точности полиэдральной аппроксимации) разумно выбирать для уменьшения вычислительных затрат при заданной точности аппроксимации.
Вторая глава посвящена многошаговой полиэдральной аппроксимации последовательности множеств достижимости линейной управляемой системы на основе метода крупных шагов с оценкой погрешности аппроксимации, а также методам аппроксимации ОЭП множества достижимых критериальных векторов некоторых классов динамических задач многокритериальной оптимизации. В §2.1 описан метод крупных шагов, предназначенный для аппроксимации последовательности множеств достижимости с гарантированной оценкой погрешности, в котором аппроксимация следующего множества достижимости строится на основе аппроксимации предыдущего множества достижимости. При этом сначала строится апостериорная оценка погрешности аппроксимации, а затем излагается метод построения априорной оценки погрешности, позволяющий осуществить автоматический расчет разумных значений параметров аппроксимации. При этом шаги разбиения временных отрезков в процессе расчета значений опорной функции и точности полиэдральной аппроксимации выбираются на основе минимизации вычислительных затрат, моделируемых с использованием некоторых оценок числа вычислений опорной функции ВКТ, требуемого для достижения заданной точности аппроксимации. В §2.2 представлены две модификации метода крупных шагов, предназначенные для построения двух последовательностей аппроксимирующих многогранников: гарантированно внутренней и гарантированно внешней. Для каждой модификации приведены апостериорные оценки погрешности аппроксимации, априорные оценки погрешности и разработаны формулы для выбора значений параметров аппроксимации, позволяющие при требуемой точности аппроксимации минимизировать вычислительные затраты с использованием упомянутой выше модели оценки числа вычислений опорной функции ВКТ. В §2.3 приведены модификации метода крупных шагов для непрерывно-дискретных задач. В частности, рассмотрена задача пошаговой аппроксимации множеств достижимости для систем, в которых в моменты времени tx t2 ... tM меняется правая часть дифференциального уравнения (0.1), а также имеют место импульсные линейные воздействия. Для всех классов задач приведены апостериорная оценка погрешности аппроксимации, априорная оценка погрешности и формулы для выбора значений параметров метода при заданной точности аппроксимации. В §2.4 приведен метод визуализации движущейся границы Парето, основанный на аппроксимации ОЭП с гарантированной точностью с использованием построенной последовательности множеств достижимости.
В третьей главе содержится описание программного обеспечения, реализующего методы, разработанные в первых двух главах, а также приведены примеры его применения для изучения модельных задач. В §3.1 описано программное обеспечение построения полиэдральной аппроксимации терминального множества достижимости для линейной системы на основе метода, описанного в §1.3. В программном обеспечении интегрированы реализованный диссертантом исполняемый модуль, основанный на методе, описанном в §1.2, программное обеспечение метода УО, разработанное О.Л.Черных, и программное обеспечение визуализации выпуклых многогранников, разработанное В.А. Бушенковым. В §3.2 описана программная реализация метода крупных шагов аппроксимации последовательности множеств достижимости с автоматическим выбором параметров метода и расчетом точности аппроксимации. В §3.3 описано программное обеспечение, позволяющее реализовать метод движущейся паретовой границы для одного класса динамических задач многокритериальной оптимизации.
В Заключении сформулированы результаты диссертационной работы, выносимые на защиту.
В приложении собраны графические иллюстрации работы программного обеспечения, описанного в главе 3.
По теме диссертации опубликовано 6 печатных работ [5]-[ 9], [44].
Основные результаты диссертации докладывались на Международной конференции студентов и аспирантов по фундаментальным наукам «Ломоносов 2004», секция ВМиК (Москва, апрель 2004 г.), на 4-й Московской международной конференции по исследованию операций (Москва, 21-25 сентября 2004 г.), на 1-й Международной конференции "Системный анализ и информационные технологии" (Переславль-Залесский, 12-16 сентября 2005 г.), на научных семинарах Вычислительного центра РАН, Института проблем механики РАН и кафедры Оптимального Управления факультета Вычислительной Математики и Кибернетики МГУ.
Автор искренне благодарен зав.кафедрой Системного Анализа ВМиК МГУ академику А.Б. Куржанскому за привлечение внимания автора к многошаговым методам, научному руководителю д.ф.-м.н. А.В. Лотову за постановки задач, обсуждение результатов и постоянное внимание к работе и д.ф.-м.н. Г.К. Каменеву за помощь в работе и ценные замечания.
Метод расчета опорной функции множества достижимости линейной управляемой системы с гарантированной оценкой погрешности
Свойство оптимальности МПА по числу вычислений опорной функции ВКТ особенно важно в тех задачах, где нахождение значений опорной функции занимает достаточно много времени. К такому классу задач относятся задачи построения множеств достижимости управляемых систем.
Из определения величины а(С) следует, что при любом s не а(С) существует такой константы constc, для которой выполнялось бы свойство (1.7). Поэтому из (1.1) следует, что при а(С) = (и-1)/2 МПА является оптимальным по порядку числа вершин для С, если он порождает последовательность {Рк }к=0, , для которой справедливо неравенство 5{С,Рк) С"$! п- О-8) ш(Р ) (
В настоящее время существует достаточно большое число МПА (см., например, обзоры в [53], [54], [15]). Вместе с тем, МПА, ориентированных на аппроксимацию ВКТ, заданных своей опорной функцией значительно меньше. Прежде всего необходимо отметить неадаптивный подход, который основан на расчете значений опорной функции аппроксимируемого множества на некоторой заданной сетке направлений (см., например, [36], [11], [33]). Однако, как показано в [62], никакой неадаптивный метод не может быть оптимальным по порядку числа вершин при аппроксимации негладких тел.
Описание адаптивных МПА, оптимальных по порядку числа вершин для тел с частично гладкой границей приведены в [58]. Отметим среди них метод «Уточнения Оценок» (УО), предназначенный для аппроксимации тел, заданных своей опорной функцией (см. [29]). Этот метод был исследован в [16], [17], где было показано, что для любого Се% он порождает последовательность со свойством (1.8) для числа вершин вписанных аппроксимирующих многогранников. Достоинство этого метода состоит в том, что для него была разработана устойчивая вычислительная схема ([41]). Метод был запрограммирован и использован во многих практических расчетах.
Метод УО состоит в следующем. Пусть требуется аппроксимировать выпуклое компактное множество С и задана желаемая точность аппроксимации є. На к-й итерации должен быть построен вписанный в тело С многогранник Р?єі? (С) в виде как множества решений системы линейных неравенств, так и списка вершин, для которых указана принадлежность к гиперграням (т.е. граням максимальной размерности) многогранника (так называемое двойное описание), и описанный многогранник Рск еУс(С), представленный в виде решений системы линейных неравенств. Обозначим через U(P) - множество единичных внешних нормалей гиперграней многогранника Р. Множество U(Ptk) можно считать заданным системой линейных неравенств, описывающей многогранник Рк. Тогда к +1 -я итерация метода УО состоит в следующем: Шаг 1: а) на основе измерения значений опорной функции находим направление ик є U{Pk) такое, что ик = arg max {g(u, С) - g(tt, Рк): и є U{P )}. Если \g(uk,C)-g(uk,P/L) є, то останавливаем работу метода, иначе переходим к п. б). б) Берем такую точку рк границы тела С, что для направления ик, найденного в п. а) шага 1, выполняется ик Рк =(" .О Шаг 2: в качестве очередных многогранников берем Р =conv{pk U }, pk+i _ pk pi X ; u x Uk pk При этом P 1 строится в виде множества решений системы линейных неравенств с помощью метода, предложенного в [41].
Описание метода закончено. Отметим, что метод УО позволяет аппроксимировать ВКТ с любой заданной степенью точности. Кроме того, на каждой итерации вычисляется текущая точность аппроксимации.
Адаптивный метод УО является оптимальным по порядку числа вершин для тел с ЫС)=(п-\)/2. Следовательно, по теореме 1.1 метод УО оптимален по порядку числа вершин для ВКТ с частично гладкой границей, рассмотренных в настоящей работе. Таким образом, его целесообразно применять для построения полиэдральной аппроксимации множества достижимости линейной динамической системы. Рассмотрим автономную линейную управляемую систему вида где х є R" - фазовая переменная, А - матрица размера пхп, U,X0 ей" -выпуклые многогранники. Обозначим через n(t) управление, под которым будем понимать измеримую функцию, удовлетворяющую включению n(t) є U почти всюду.
Гарантированно внутренняя и гарантированно внешняя аппроксимации терминального множества достижимости
Поскольку [/, Х0 - непустые выпуклые многогранники, то Х(Т) тоже непустой выпуклый многогранник. Кроме того, g(c,X(T)) = g(c,X(T)), для любого направления се Л", с = 1. В самом деле, согласно (1.15), (1.16), (1.17) для любого направления се R", с = 1 по свойствам опорной функции (см. [35]) + fJ-{g(cMti-i)U) + g(cMti)U))= c,x(T) = g(c,X(T)). (=i Будем считать, что существует константа Я, такая, что для всех ceR", с = 1 оптимальное управление u (t) задачи с,х(Т) - max имеет на отрезке [О, Г] не более Я, точек переключения. Тогда согласно формуле (1.23) и теореме 1.2 выполняется
В качестве многогранников X, Хы, Xext будем брать многогранники, аппроксимирующие множество X(Т), опорную функцию которого для любого направления мы можем рассчитать. Для построения X, Xint, Xext можно использовать, оптимальные методы полиэдральной аппроксимации выпуклых компактных тел ([29]). Данные методы аппроксимации не используют заранее заданную сетку направлений, по которым вычисляется значение опорной функции, а на каждой итерации рассчитывают опорную функцию для нового направления, используя информацию об аппроксимируемом теле и уже построенном аппроксимирующем многограннике. Эти методы позволяют строить для выпуклых компактных тел аппроксимирующие многогранники, имеющие любую заданную степень точности. Адаптивность методов приводит к их оптимальности по числу вершин, а также, в некоторых случаях, и по числу измерений опорной функции [29], [58]. В дальнейшем будем считать, что используется один из таких методов - метод УО.
Обозначим через Вх є R" шар единичного радиуса с центром в начале координат. Для множества С&! обозначим через r(C) = max{d 0:Bd(x)c:C,xeC} -радиус максимального вписанного в С шара, а через а(С) - асферичность множества С (минимальное отношение радиусов концентрических внешнего и внутреннего шаров).
Для множеств С и В обозначим С + В = [х є R" : х = х1 + х2, дг, є С, х2 е в). Заметим, что для выпуклого компактного тела С и 8 0 множество С + SB} является выпуклым компактным телом и, кроме того, g(c,C + SB{) = g(c,С)+ 5 для любого с є R", с = 1.
Лемма 1.4. Пусть Р - непустой выпуклый многогранник, a U(P) -множество единичных внешних нормалей его гиперграней. Если г(Р) б О, то (P)_s будет непустым выпуклым многогранником и (P)_S=F, где Р = f]{x: u,x g(u,P)-S}. иєІДР) Доказательство: Действительно, согласно (1.26) имеем (P)_sc f]{x: u,x g(u,P)-S}. ueU(P)
С другой стороны, рассмотрим любое ceR", с = 1. Значение g(c,P) достигается в одной из его вершин, обозначим ее через р . Пусть aj є U(P), \aj\ - Ь j = h—J, - нормали к гиперграням, проходящим через р . Тогда по теореме Фаркаша с = lXjaj, где Х} О, ]] Ау. = 1, и м 7-і g(c,Р) = с,р = J]Ajdj,P =YJХІ aj P = TjXjg(aJ p) 7=1 7=1 y=i Кроме того, так как У? - выпуклое множество, то по свойствам опорной функции gic,F) = g(t aj,F) j Xjg a F) Щ{арР)-8] = g{c,P)-5. 7=1 7=1 y=i Таким образом, F+SBl с Р и, следовательно, Р с (Р)_д.
Далее будем предполагать, что множество Х(Т) телесно. Отметим, что метод УО обнаруживает нетелесность аппроксимируемого множества. Тогда и Х(Т) при достаточно малом h также телесно и множество (X(T))_i непусто при достаточно малом ЕХ . Выбор соотношения погрешностей , и е2 зависит от относительных вычислительных затрат на измерение опорной функции и построение полиэдральной аппроксимации. При аппроксимации шаров различной размерности методом УО экспериментально была установлена зависимость числа вычислений значений опорной функции ms(C) от достигнутой точности аппроксимации е2.
Построение гарантированно внутренней и гарантированно внешней аппроксимаций последовательности множеств достижимости
Построение гарантированно внутренней и гарантированно внешней аппроксимаций последовательности множеств достижимости
В данном параграфе предложена модификация метода крупных шагов -построение двух последовательностей многогранников, аппроксимирующих последовательность множеств достижимости: гарантирован внутреннего и гарантированно внешнего. Для этого воспользуемся методами построения внутреннего и внешнего аппроксимирующего многогранника для терминального множества достижимости, предложенными в 1.4.
Через 8к будем обозначать оценку погрешности аппроксимации на к -ом шаге, к = \,...,М. Будем аппроксимировать последовательность множеств достижимости последовательностями внутренних т.е. Хкы с X(tk), и внешних \Xkext )к=х, т.е. Xkext з X(tk), многогранников так, чтобы М . Для к = О положим 80=0, ЛЫ - Л ext - Л 0
Рассмотрим к -ый шаг метода: перед началом к -ого шага уже получены внешний Хкех? з X(tk_x) и внутренний Хк х с X{tk_x) аппроксимирующие многогранники для множества X{tk_x) такие, что 8h(Хк х,Хк ) 8к-1. При этом 8h{Xk-\X{tk_,)) 8kA и 8h(XkJ,X(tk_,)) 8k_,. Рассмотрим выпуклый многогранник Хк 1 =—- —. Тогда 8h(Xk i,X(tk_i)) ——. Для аппроксимации множества X(tk) применим метод аппроксимации терминального множества достижимости к следующей системе Множество достижимости для системы (2.16) обозначим через X (tk k_x), а множество, опорную функцию которого мы рассчитываем при использовании дискретизации по времени через X{tk - .,). По замечанию eXUk k-l)S выполняется Sh(X (tk k_,),X(tk)) Ak,me Ак = = -.
Решение задачи 2. Вариант А. Также, как и в 1.4, вариант А, для вычисления значений опорной функции множества X\tk —tk_t) при внешней и внутренней аппроксимации будем брать разные шаги разбиения временного отрезка [tk.i,tk], соответственно А и A . При этом через Xe(tk - _,) будем обозначать множество, полученное для шага А , а через Xi(tkk_x) -множество, полученное для шага А . Применим сначала метод построения внутренней и внешней аппроксимации в котором метод УО применяется два раза: к множеству Xi(tk—tk_l) и к множеству Xe{tkk ]) + \Ak+sle)Bl. Построим внешний где е\е - погрешность измерения значений опорной функции множества X (tk —tk_x) при построении внешней аппроксимации на к-ом шаге, такой, что 5h \Xkal, Хе(tk - tk_x ) + [Ак + є\е ]в1) єке. Построим вписанный Р; с X,(tk -f t_,) такой, что 5"(Pin ,X.(tk - tk_,)) єк2і, и внутренний аппроксимирующий Xknt =( )_(Ді +г ) = f]{x: u x - (и Ры)-{\ +4% многогранники где skt - погрешность измерения значений опорной функции множества X (tk k_]) при построении внутренней аппроксимации на к-ом шаге.
Выбор соотношений погрешностей , ., є\е, єк2і и є\е, A: = 1,...,Л/, зависит от относительных вычислительных затрат на измерение опорной функции и построение полиэдральной аппроксимации, как для внешнего, так и для внутреннего аппроксимирующих многогранников, для всех крупных шагов. Обозначим через сок = co(Xknt). Следовательно, многогранники Л" ,, и Xkext являются гарантированно внутренней и гарантированно внешней оценками множества X(tk) для любого к = 1,...,М. к Для любого к = \,...,М обозначим d = Y[(u)(X iM) + a (P xt)), , , (a (XL) + со(РІ. ))su +є2і ,,. ., j = 1,...Д -1, dkk=l. Тогда 5k = /} mtJ \_ej lJ iLe - S, к = 1,..., M . Как обычно, 8k возрастает с увеличением к.
Апостериорная оценка погрешности. Задав значения hk - шагов разбиения временных отрезков \tk_x,tk] для расчета значений опорной функции и єи -точности аппроксимации методом УО на каждом крупном шаге k = l,...,M, получим, что
Априорная оценка погрешности. Пусть задана некоторая точность є и требуется заранее определить: с какой точностью єи нужно рассчитывать значения опорной функции множества достижимости X (tk - .,) в момент времени tk (т.е. на сколько частей Nk = — — разбивать временной отрезок [tk_x,tk]) К и с какой точностью є2к аппроксимировать множество X(tk - tk_]) методом УО на каждом шаге к = \,...,М , чтобы в момент времени tM выполнялось условие dh{X X ,) e. Выбор соотношений погрешностей еи и с2к, к = \,...,М, зависит от относительных вычислительных затрат на измерение опорной функции и построение полиэдральной аппроксимации для всех крупных шагов. Обозначим через сок = со(Х м) + со(Р ). Построим сначала эвристический метод. Предположим, что погрешности аппроксимации на каждом шаге должны вносить одинаковый вклад в общую
Реализация метода построения многошаговой аппроксимации последовательности множеств достижимости
Описываемое программное обеспечение предназначено для построения и визуализации полиэдральной аппроксимации множества достижимости автономной линейной управляемой системы (а также его проекций в координатные подпространства) на основе метода, описанного 1.3. В программном обеспечении интегрированы реализованный диссертантом модуль расчета опорной функции множества достижимости, разработанное О.Л.Черных программное обеспечение аппроксимации ВКТ с помощью метода УО и программное обеспечение визуализации выпуклых многогранников VISAN, разработанное В.А. Бушенковым. Пусть Х(Т) - множество достижимости системы (1.9) в момент времени Т. Обозначим через Х(Т)Х х проекцию множества Х{Т) на т- мерное координатное подпространство Ох]...хт пространства R".
В качестве входных данных для работы системы пользователь должен составить два файла. Первый файл содержит описание линейной динамической системы, а именно: размерность системы п ; номера переменных проекции (в случае построения проекции множества достижимости на координатное подпространство); длительность временного отрезка Т; число шагов разбиения временного отрезка ./V для расчета значений опорной функции; матрицу системы А ; вершины многогранника допустимых значений функции управления U; вершины многогранника возможных начальных состояний Х0.
Во втором файле инициализируются внутренние параметры программы и параметры аппроксимации, в том числе: максимальное число вершин аппроксимирующего многогранника; максимальная точность аппроксимации с помощью метода УО (в смысле, близком к метрике Хаусдорфа); ограничение на число граней аппроксимирующего многогранника.
При превышении указанных значений параметров аппроксимации процесс аппроксимации будет завершен.
В зависимости от заданных значений внутренних параметров результатом работы программы будут следующие файлы: файл, содержащий описание аппроксимирующего многогранника, который может быть визуализирован с помощью модуля VISAN; файл, содержащий векторы-направления, по которым вычислялось значение опорной функции в течение работы программы, и найденные по этим направлениям вершины аппроксимирующего многогранника; файл с историей процесса аппроксимации - информацией для каждой итерации метода УО о: достигнутой точности полиэдральной аппроксимации, количестве граней аппроксимирующего многогранника, количестве вершин аппроксимирующего многогранника, количестве обращений к вычислению опорной функции в течение данного сеанса (накопительной суммой).
Заметим, что программа определяет и печатает в файл с историей аппроксимации только погрешность є2 аппроксимации многогранника Х(Т) с помощью метода УО. Для верхней оценки погрешности расчета значений опорной функции множества є{, т.е. Sh(X(T),X(T)), справедлива формула (1.25).
Отметим также, что при заранее заданной точности аппроксимации є могут быть использованы формулы (1.30), (1.31) априорного расчета оптимальных (для выбранной модели вычислительных затрат) значений параметров є2 и N (количества шагов разбиения временного отрезка [0,Г]). Расчет был реализован в виде отдельного модуля, результатом работы которого является файл с рекомендуемыми значениями параметров аппроксимации. Рассчитанные значения затем могут быть подставлены в соответствующие исходные файлы программного обеспечения.
Заметим, что при выборе параметров алгоритма следует иметь в виду следующие факты, полученные теорией полиэдральной аппроксимации ВКТ. Пусть BR zR" - шар с радиусом R 0, обозначим через m(BR,e) минимальное число вершин многогранника, аппроксимирующего шар, (т.е. число вершин МНА) необходимое для достижения точности
