Содержание к диссертации
Введение
1 Алгоритм проектирования точки на множество на основе эллипсоидов 10
1.1 Постановка задачи 10
1.2 Описание численного метода 10
1.3 Скорость сходимости метода 13
1.4 Модификация метода (промежуточная одномерная оптимизация) 20
1.5 Некоторые примеры расчетов 24
1.5.1 Квадратичная скорость сходимости 24
1.5.2 Случай зацикливания 25
1.5.3 Пример использования метода с промежуточной одномерной оптимизацией 25
1.5.4 Сравнение с методом проектирования на основе потенциала 27
1.5.5 Применение метода для решения задачи оптимального управления с терминальным функционалом 29
2 Ньютоновский алгоритм проектирования с гарантированной сходимостью 31
2.1 Предварительные замечания 31
2.2 Описание численного метода 31
2.3 Сходимость метода 32
2.4 Скорость сходимости метода 41
3 Алгоритм решения задачи захвата точки семейством выпуклых множеств 45
3.1 Постановка задачи 45
3.2 Описание численного метода 45
3.3 Сходимость численного метода 46
3.4 Скорость сходимости метода 49
3.5 Некоторые примеры расчетов 58
4 Алгоритм решения задачи быстродействия на основе проектирования начального состояния на соприкасающиеся эллипсоиды 60
4.1 Описание численного метода 60
4.2 Скорость сходимости метода : 61
4.3 Некоторые примеры расчетов 70
4.4 Решение задачи управления линейным динамическим объектом 73
4.5 Замечания об эффективности метода 77
5 Ньютоновский алгоритм решения задачи быстродействия с гарантированной сходимостью 79
5.1 Описание численного метода 79
5.2 Сходимость метода 80
5.3 Скорость сходимости метода 85
Приложения 92
- Модификация метода (промежуточная одномерная оптимизация)
- Применение метода для решения задачи оптимального управления с терминальным функционалом
- Скорость сходимости метода
- Сходимость численного метода
Введение к работе
Теория оптимального управления, развитая на рубеже пятидесятых и шестидесятых годов группой выдающихся советских ученых во главе с Л.С.Понтрягиным [1], получила всеобщее признание как фундаментальное теоретическое достижение и нашла широкое применение в приложениях.
Первоначальный импульс для развития теории оптимального управления возник в связи с задачей наискорейшего перевода управляемого объекта из одного состояния в другое (задача быстродействия). Как отмечает Р.П.Федоренко в [2], сам способ формулировки проблемы в наиболее адекватных терминах был поначалу предметом исследования, и во многом благодаря удачному решению этого вопроса были достигнуты столь значительные результаты. Сначала была полностью построена теория оптимального управления для линейных динамических систем, доказательство этих результатов принадлежит Р.В.Гамкрелидзе; доказательство образующего стержень теории принципа максимума Понтрягина для нелинейного случая принадлежит В.Г.Болтянскому [3]. Большой вклад в развитие и разработку теоретических и прикладных аспектов математической теории оптимального управления внесли Н.Н.Красовский, Р.Беллман, Л.Нейштадт, Дж.Итон, Р.П.Федоренко, Ф.П.Васильев, Б.Н.Пшеничный, Р.Габасов, Ф.М.Кириллова, А.А.Белолипецкий и другие.
Линейный характер поведения динамического объекта определяет "выпуклость" задачи и позволяет провести исследование в весьма удобном виде, что приводит к получению компактно формулируемых результатов. Рассмотрение гладких задач можно признать удачным выбором формулировки проблемы, позволяющей перейти к построению эффективных вычислительных алгоритмов. Математическая постановка гладких задач оптимального управления в терминах опорной функции области управления, а также обоснование целесообразности такой постановки предложены Ю.Н.Киселевым [4]. Исследование взаимосвязи гладких и негладких задач проведено Ю.Н.Киселевым и С.Н.Аввакумовым, а также предложены алгоритмы "сглаживания" задачи [5]. Большую практическую экспериментальную и исследовательскую работу в этом направлении выполнил М.В.Орлов [6], [7].
Л.С.Понтрягин подчеркивал прикладной характер и практическую направленность математической теории оптимального управления. Большие возможности для практического использования полученных результатов предоставляет стремительно развивающаяся современная вычислительная техника. В этой связи возникает необходимость в совершенствовании методов решения задач, имеющихся в данной области, разработке новых идей и подходов, проведении исследовательской работы теоретического и экспериментального характера.
Данная диссертационная работа посвящена разработке и исследованию новых методов решения линейных задач с гладкой областью управления. В качестве критериев качества управления рассматриваются оптимальность по быстродействию и минимизация расстояния до целевой точки.
К числу отправных исследований нужно отнести результаты, полученные Ю.Н.Киселевым: конструкцию соприкасающегося эллипсоида, предложенную для аппроксимации гладких выпуклых компактов [8], идею и методы "одномерной оптимизации", также высказанные в других формах, в частности, Дж.Итоном и В.Г.Болтянским, теорему о квадратичной скорости сходимости метода проектирования начального состояния на изохрону, изложенную в [4], специальную параметризацию начального значения сопряженной переменной, предложенную в работе [9].
Основой для исследованных в работе методов решения задач оптимального управления служат эллипсоиды, построенные специальным образом. Эллипсоидальные кон- струкции применялись ранее для аппроксимации множеств достижимости управляемых систем. Этой проблематике посвящены работы Ф.Л.Черноусько [10], А.Б.Куржанского и П.Варайя [11, 12]. Предложенные эллипсоидальные аппроксимации ставят своей целью прежде всего оценку возможных фазовых состояний динамической системы; использованная в данной работе конструкция имеет иное предназначение. На основе квадратичного порядка аппроксимации границы множества достижимости (управляемости) соприкасающимся эллипсоидом строятся алгоритмы решения задач оптимального управления, обладающие квадратичной скоростью сходимости.
Геометрический смысл гладкости выпуклого компактного множества состоит в существовании в любой его граничной точке соприкасающегося невырожденного эллиптического параболоида. Соприкасающиеся параболоиды рассмотрены, например, в [13], [14]. В [4] излагается та же конструкция применительно к границе гладких выпуклых компактов. Соприкасающийся параболоид локально приближает исходный компакт, являясь неограниченным множеством. Для локальной аппроксимации гладких компактов Ю.Н.Киселевым предложена более совершенная конструкция - соприкасающийся эллипсоид [8]. Гладкий выпуклый компакт Лі Г(К") с опорной функцией <т(ф) = с(Лі,ф) имеет соприкасающийся эллипсоид (р) — (Л1,р) в любом направлении р Є К?, р Ф 0, который определяется опорной функцией с((р), Ф) = (о(р), ф) + у/ф*В(р)ф, а(р) = |Ир)+
Конструкция соприкасающегося эллипсоида применяется в данной работе для аппроксимации множеств достижимости X{to, t,xo) и управляемости Z(t, ti,x\) линейной динамической системы с гладкой областью управления Ы: x{t) = Ax(t) + u{t), x{t) Є Ж1, u(t) є U Є r(Ru).
Эти множества, как показано в [4], являются гладкими выпуклыми компактами, их опорные функции имеют следующий вид: c{X{t0, t, х0), ф) = ф*еА^-^х0 + Ґ c{U, еА'^ф)(1з, c(Z(t,tuxi), -ф) = -ф'е^-^хг + J ' c(W,eA*(t-eV)^, где x(t0) = Xq и x{tx) = хг.
Рассматриваются задача быстродействия в начало координат ' x(t) = Ax(t) + u(t), < х{0) = х0, х{Т) = 0, (1) T->min и задача с терминальным функционалом типа "норма разности" ( x(t) = Ax(t) + u(t),s(0) = x0, (2) \x(T)-yf-+mm, u(-) целевая точка у и момент времени Т предполагаются здесь зафиксированными.
На основании уравнений принципа максимума Л.С.Понтрягина, оптимальное управление в задачах (1) и (2) записывается в форме
М*)= с'ф(и,е-А'%), где р, Є К", р* Ф 0 - оптимальное начальное значение сопряженной переменной, единственное с точностью до положительнбго множителя, которое для задачи (1) определяется условием c{Z(Q,L,x{),-p+) = (х0,-р*), (3) здесь <* - время быстродействия - есть момент первого захвата точки х0 семейством множеств Z(0,t,xi), х\ = О Є К". В задаче (2) оптимальное начальное значение сопряженной переменной имеет вид р, = еА'тр, где р = у- п(Х (О, Т, х0),у), (4) где 7г(А,х) = argmin|a — х\ - оператор проектирования точки х на выпуклый компакт
Л. Таким образом, поставленные выше задачи оптимального управления формулируются в терминах множеств достижимости и управляемости, что позволяет редуцировать их к задаче проектирования точки на множество, заданное опорной функцией (4) и задаче захвата точки семейством множеств (3).
Квадратичный порядок локальной аппроксимации границы множества позволяет использовать соприкасающиеся эллипсоиды в качестве основы для построения алгоритмов с ньютоновской скоростью сходимости. Результатом, натолкнувшим па это предположение можно считать теорему о квадратичной скорости сходимости метода проектирования начального состояния на изохрону, изложенную в [4]. Вместе с тем, приведенный в работе результат получен другим путем и для несколько иного класса задач. Изначально в работе рассматривается постановка задачи, не ставящая во главу угла ее дифферепциальную специфику. Вместо этого используются геометрические соображения для рассматриваемых множеств и аналитические свойства их опорных функций, а уже потом полученные результаты применяются для решения задач оптимального управления. Такой взгляд на проблему можно признать родственным подходу, примененному С.П.Самсоновым в [15] и [16]. При доказательстве квадратичной скорости сходимости методов решения задачи быстродействия оказалась удобной параметризация начального значения сопряженной переменной, с небольшой особенностью отражающая суть подхода, предложенного в [9]. Использование идеи "одномерной оптимизации" привело к построению квадратично сходящегося метода, для которого не возникает проблемы выбора "достаточно" хорошего начального приближения. В качестве вспомогательного метода, а также в целях сравнительного анализа используется потенциал W(q), введенный в [17].
Основным результатом работы является доказательство квадратичной скорости сходимости методов проектирования на соприкасающиеся эллипсоиды для решения задачи с терминальным функционалом и задачи быстродействия (в геометрической трактовке), а также доказательство аналогичного результата и свойства гарантированной сходимости для построенных модифицированных итерационных процессов.
Сначала проводится исследование метода проектирования точки на множество в статическом случае; главным конструктивным элементом алгоритма решения этой задачи является соприкасающийся эллипсоид. Доказано, что при определенных предположениях можно гарантировать квадратичную скорость сходимости метода, [44]. Также проведено изучение вопроса о сходимости метода, теоретические и практические исследования для его модификаций, сравнение с имеющимися аналогами. Метод использован для решения задачи оптимального управления с терминальным функционалом. Построена его модификация, обладающая гарантированной сходимостью. Далее рассматривается задача быстродействия в геометрической интерпретации и алгоритм ее решения на основе проектирования точки на множество. Для этого метода сформулированы требования, гарантирующие сходимость, и получены условия, достаточные для ньютоновской скорости сходимости, [45], [46]. Следующая часть представляет собой конструктивный синтез результатов, полученных в работе ранее, - использование конструкции соприкасающегося эллипсоида для решения задачи быстродействия, [47]. Рассмотренный метод применяется для решения задачи оптимального управления, в качестве основы используется идея проектирования начального состояния на изохрону, подробно изложенная в [4], при этом дается ответ на вопрос о способе проектирования, который был оставлен открытым; дифференциальная интерпретация процесса проектирования (метод проектирования в непрерывной форме, изложенный, например, в [5]) при этом не используется. В заключительной части построена модификация метода, обладающая гарантированной сходимостью.
Полученные результаты сравниваются с другими известными алгоритмами. Отдельные части работы завершаются примерами численных расчетов, на практике иллюстрирующих рассмотренные проблемы. Теоретические результаты, освещенные в настоящей работе, нашли практическую реализацию в программном продукте ЕШ.
Модификация метода (промежуточная одномерная оптимизация)
Как показывает практика, при использовании рассматриваемого метода проектирования (1.5) могут возникать ситуации, когда вычислительный процесс зацикливается (см. раздел 1.5.2, стр. 25). Чтобы избежать этого неприятного явления, целесообразно использовать рассмотренный в этом разделе модифицированный численный алгоритм. Сначала введем новую итерирующую функцию, которая потребуется нам для описания вычислительного процесса. Положим Основываясь на (1.5), введем дополнительный корректирующий шаг, уточняющий текущее приближение pfe с использованием вектора Рк-х - результата, полученного на предыдущей итерации. Суть этого промежуточного шага состоит в решении одномерной задачи минимизации Эта задача, вообще говоря, не является выпуклой (соответствующий пример приведен в разделе 1.5.3, стр. 25) и поэтому может иметь не единственное решение. Пусть А& -произвольный локальный минимум функции д{\,Рк)- Модифицированный метод проектирования описывается следующим рекуррентным соотношеним: Теорема 1.4 (О сходимости модифицированного метода (1.45)) Пусть выполнены следующие условия: 1. МЄ Г(КП); 2. выполнено условие (1.7); 3. имеет место сходимость метода (1.45) к некоторому предельному вектору р, то есть рк — р при к — оо; 4. соответствующая последовательность {Хк} не имеет число 1 своим пределом. Тогда выполняется равенство р = р+, то есть вектор р является решением исходной задачи (1.3). Доказательство. Не вводя для краткости дополнительных индексов, будем рассматривать подпоследовательность последовательности {Ajt} такую, что все ее элементы лежат вне некоторой малой окрестности единицы. На этом основании существуют достаточно малое число 8 0 и номер N такие, что справедлива оценка Согласно определению итерационного процесса (1.45), выполнено равенство Так как имеет место сходимость рк — р при к — оо, то справедливо представление Pk+i —Рк + Єк, где вектор є к удовлетворяет требованию - 0 при к —» оо. С учетом этого замечания, из (1.47) следует равенство силу условия (1.46) эквивалентно равенству В силу определения вектора и числа 5, справедивы соотношения Теперь, на основании предельного перехода при к — со в равенстве (1.48) с учетом непрерывности функции S(-), обоснованной в теореме 1.2, справедливо равенство P = S{p), которое в силу теоремы 1.2 влечет выполнение соотношения р — р . Теорема 1.4 доказана. Замечание 1.11 Теорема 1.4 представляет собой аналог теоремы 1.2 для модифицированного метода (1.45). Замечание 1.12
Содержание условия 4 в теореме 1.4 иллюстрируется примером в разделе 1.5.3. Теорема 1.5 (О скорости сходимости модифицированного метода (1.45)) Пусть выполнены следующие условия: 1. Me Г(Шп); 2. выполнено условие (1.7); 3. функция сг(-), определенная равенством о (р) = с(ЛІ,р), имеет непрерывные частные производные до четвертого порядка включительно всюду в Rn \ {0}; 4- в методе (1.45) имеет место сходимость последовательности {р } к вектору р , то есть pk - р при к — оо. Тогда справедливо предельное соотношение А — 0 при к — оо, и существуют константа С 0 и номер К такие, что для всех номеров к К выполняется оценка (1.11). Доказательство. Обозначим /(А,р) = 7д(А,р), функция д( , ) определена равенством (1.43). Рассмотрим вопрос о существовании и непрерывности функции А = Х(р) в окрестности точки р». Эта функция определяется неявно уравнением Воспользуемся теоремой о неявной функции (см. [40]). 1. Из (1.49), условия (1.7) и равенства р = S(p.) следует, что при А = 0 выполняется равенство /(А , р.) = 0, причем А = 0 является единственным решением уравнения f(X,p,) = 0 и единственной точкой (локального и глобального) минимума при фиксированном значении второго аргумента р = р функции д( , ), определенной в (1.43). 2. Поскольку справедливо равенство р = 5(р„) и Л» = 0, то выполняется условие 3. Обозначим в пространстве R" базисные векторы е,-, г = 1,..., п. Частные производные содержат непрерывные (по условию теоремы) смешанные производные функции ст(-) не выше третьего порядка (см. выражение (1.49) для функции Z(-, ) и доказательство теоремы 1.3 относительно производных функции ()). Поэтому частные производные (1.51) непрерывны в окрестности точки (А«,р ). Таким образом, условия теоремы о неявной функции выполнены. Следовательно, в некоторой е-окрестности точки р» существует единственная функция А = А(р) - решение экстремальной задачи (1.44), причем эта функция в указанной окрестности является непрерывно дифференцируемой. Более того, аналогично сделанному при доказательстве теоремы 2 замечанию, функция А(-) имеет непрерывные производные, по крайней мере, до второго порядка включительно. Справедливость последнего утверждения следует из следующих выражений: Частные производные функции /(,) второго порядка будут содержать производные функций сг( ) и () до четвертого и второго порядка соответственно. Производные функции сг(-) - непрерывны по условию, непрерывность производных функции () в условиях настоящей теоремы обоснована при доказательстве теоремы 1.3. Таким образом, производные А" () непрерывны в рассматриваемой окрестности Ве(р«). В силу сходимости pk - р при к -+ со, существует такой номер N, что для любых номеров к N, выполнено включение Pk Є В(р,). В этой окрестности выполняется равенство Ajb = A(pjt), где А(-) - функция, определяемая неявным уравнением (1.49). В силу только что обоснованной непрерывности этой функции, справедливо соотношение Ajk = A(pfc) -+ А(р ) = 0 при к -+ оо. Теперь покажем выполнение оценки (1.11). Процесс (1.45) представляет собой метод простой итерации. Воспользуемся теоремой 1.1. Из равенств р„ = 5(р»), А» — 0 и S p.(p ) — 0 (последнее выполнено согласно теореме 1.3) следует выполнение следующих условий: 1. (А(р ),р») = (1 -А(р ))р» +А(р»)р =р«; Непрерывность производных функции А(«) соответствующих порядков в окрестности Вг(р«) следует из выражений (1.49), (1.50), (1.51) и (1.52). Ранее в теореме 1.3 обоснована непрерывность смешанных производных функции S( ) до второго порядка включитель J2 но. Таким образом, функции 7у( )} определяемые равенствами 7»j(p) = j J 5(А(р),р) при i,j = 1,...,п, являются непрерывными в окрестности Ве(р») и условия теоремы 1.1 выполнены. Теорема 1.5 доказана.
Применение метода для решения задачи оптимального управления с терминальным функционалом
Рассматривается задача оптимального управления с терминальным функционалом следующего вида: Будем полагать, что для всех допустимых управлений и(-) для конечных точек траектории выполнено неравенство х(Т,и(-)) ф у. Для решения этой задачи (см. [21]) необходимо найти проекцию точки у на множество достижимости Х(Т) в момент времени Т, опорная функция которого имеет вид: Вектор ф = у — -к(Х(Т),у), является оптимальным значением сопряженной переменной ф(ї) = е А 1ф0 в момент времени Т. Зная сопряженную переменную, получаем оптимальное управление Uop(-) в явном виде: Uop(t) = sign Ь ф{і), t Є [0,7і]. Таким образом, здесь необходимо решать задачу проектирования. Ниже приведен результат применения метода проектирования на основе соприкасающихся эллипсоидов для решения задачи (1.59). Рассматривается модель "тележка", матрица А имеет вид вектор b = (0,1) . Используется сглаживание области управления, опорная функция этого множества имеет вид: с([/е, ф) = \]ф\е + ф\. Параметр сглаживания є = Ю-4. Начальное положение системы XQ = (2,2) , целевая точка у = (0,0) , время управления Т = 5.5. Начальное приближение ро = (0, —1) . На рис. 17 приведено множество дости элементов итерационной последовательности для векторов pi и правые концы ХІ соответствующих им траекторий, а также расстояния до целевой точки \ц — у \ = \ХІ . Расчеты выполнены в системе Maple V с числом значащих цифр, равным 10. Рассматривается задача проектирования точки на гладкий выпуклый компакт, поставленная в части 1. За основу принимается алгоритм на соприкасающихся эллипсоидах (1.5). Его главный недостаток состоит в том, что для сходимости итерационного процесса необходимо "достаточно" хорошее начальное приближение. При изложении метода (1.5) не конкретизировался способ выбора такого начального приближения, при рассмотрении метода (1.45) был предложен промежуточный шаг, который, однако, оказался неспособным снять проблему по-существу и, кроме того, оставил открытым вопрос о способе решения задачи минимизации (1.44). Рассматриваемый в данной части работы метод проектирования на соприкасающиеся эллипосиды с доворотом в полной мере дает ответы на все перечисленные вопросы, сохраняя при этом квадратичную скорость сходимости.
Будем считать фиксированными множество М Є Г( ) с опорной функцией а(ф) = с(М,ф) и точку у Є R", удовлетворяющую условию у ф. Л4. Основой рассматриваемого метода служат итерирующая функция (), введенная в (1.6), и определенная ниже функция R(-, ) : 9Я -» S, называемая "доворотом": Замечание 2.1 В наших предположениях, согласно замечанию 2.6 к лемме 2.8 (при доказательстве которой установлена связь функции Я(-, ) с операцией проектирования на выпуклый компакт), функция #() имеет единственный минимум на любом множес-meeYi(p,q), определенном для всех векторов р uq, удовлетворяющихусловиям:д(р) О, р ф —Ад, А О, р ф О и q ф О, поэтому функция R(-, ) определена корректно на множестве WI. Рекуррентное соотношение в методе проектирования на соприкасающиеся эллипсоиды с доворотом имеет вид выбор начального приближения определяется условием Геометрический смысл множества С заключается в следующем: это множество состоит из единичных векторов, параметризующих часть границы множества ЛІ, освещенпую жимости Х[Т), а на рис. 18 и рис. 19 - графики найденного приближения для опимального управления u t) и оптимальной траектории Xop{t) соответственно. Ниже следуют первые десять элементов итерационной последовательности для векторов pi и правые концы ХІ соответствующих им траекторий, а также расстояния до целевой точки \ц — у \ = \ХІ . Расчеты выполнены в системе Maple V с числом значащих цифр, равным 10. Рассматривается задача проектирования точки на гладкий выпуклый компакт, поставленная в части 1. За основу принимается алгоритм на соприкасающихся эллипсоидах (1.5). Его главный недостаток состоит в том, что для сходимости итерационного процесса необходимо "достаточно" хорошее начальное приближение. При изложении метода (1.5) не конкретизировался способ выбора такого начального приближения, при рассмотрении метода (1.45) был предложен промежуточный шаг, который, однако, оказался неспособным снять проблему по-существу и, кроме того, оставил открытым вопрос о способе решения задачи минимизации (1.44). Рассматриваемый в данной части работы метод проектирования на соприкасающиеся эллипосиды с доворотом в полной мере дает ответы на все перечисленные вопросы, сохраняя при этом квадратичную скорость сходимости. Будем считать фиксированными множество М Є Г( ) с опорной функцией а(ф) = с(М,ф) и точку у Є R", удовлетворяющую условию у ф. Л4. Основой рассматриваемого метода служат итерирующая функция (), введенная в (1.6), и определенная ниже функция R(-, ) : 9Я -» S, называемая "доворотом": Замечание 2.1 В наших предположениях, согласно замечанию 2.6 к лемме 2.8 (при доказательстве которой установлена связь функции Я(-, ) с операцией проектирования на выпуклый компакт), функция #() имеет единственный минимум на любом множес-meeYi(p,q), определенном для всех векторов р uq, удовлетворяющихусловиям:д(р) О, р ф —Ад, А О, р ф О и q ф О, поэтому функция R(-, ) определена корректно на множестве WI. Рекуррентное соотношение в методе проектирования на соприкасающиеся эллипсоиды с доворотом имеет вид выбор начального приближения определяется условием Геометрический смысл множества С заключается в следующем: это множество состоит из единичных векторов, параметризующих часть границы множества ЛІ, освещенпую из точки у, см. рис. 23. Способ поиска начального приближения будет конкретизирован далее (см. замечание 2.7) с целью получения готовой алгоритмической процедуры.
Скорость сходимости метода
Теорема 2.4 Пусть зафиксированы множество М. Є Г(К"), точка у . М., вектор Ро Є С, а функция сг(-), определяемая согласно равенству о (р) = с(ЛІ,р), имеет непрерывные частные производные до четвертого порядка включительно всюду на множестве Rn \ {0}. Тогда метод (2.3) сходится к вектору р - решению задачи проектирования (1.3), определенному согласно (1.4) с квадратичной скоростью, то есть существуют константа С и номер К такие, что для любых номеров к К справедлива оценка Доказательство. Введем множество С(а) — {ф Є С R" : д{ф) = а}, множество Q{a) = {ф S С К" : д(ф) а}, число ак = д(рк) и число fik = д ({рк)}. Справедливы следующие соотношения: 2. Второе неравенство выполнено, поскольку справедливо соотношение a/t+i Рк и поэтому справедливо включение Q(afc+i) С Q(Pk). 3. Равенство выполняется согласно лемме 2.11 для достаточно малого числа є О при условии, что имеет место включение Рк Є [a«,a» + є]. Последнее требование будет заведомо выполнено для достаточно малого числа 5і 0 для всех векторов Рк В (р ) П (так как имеет место предельное соотношение а = д(р) — a + О при р -» р»). 4. Третье неравенство справедливо для всех векторов р Є S П Щ3(р ) (при любых достаточно малых числах 52 0) в силу леммы 2.9, поскольку выполнено предельное соотношение а = д(р) — a + 0 при р—їр . 5. Выполнение четвертого неравенства следует из включения В(рк) Є С(Рк), выполненного по определению последовательности {Рк} 6. Выполнение пятого неравенства следует из доказательства теоремы 1.3. Согласно этому доказательству, существуют константа С 0 и малое число 5з 0 такие, что для любых векторов р Є Bj3 (р ), справедлива оценка Поскольку на основании теоремы 2.1 имеет место сходимость итераквадратичной скоростью, то есть существуют константа С и номер К такие, что для любых номеров к К справедлива оценка Доказательство. Введем множество С(а) — {ф Є С R" : д{ф) = а}, множество Q{a) = {ф S С К" : д(ф) а}, число ак = д(рк) и число fik = д ({рк)}. Справедливы следующие соотношения: 2. Второе неравенство выполнено, поскольку справедливо соотношение a/t+i Рк и поэтому справедливо включение Q(afc+i) С Q(Pk). 3. Равенство выполняется согласно лемме 2.11 для достаточно малого числа є О при условии, что имеет место включение Рк Є [a«,a» + є]. Последнее требование будет заведомо выполнено для достаточно малого числа 5і 0 для всех векторов Рк В (р ) П (так как имеет место предельное соотношение а = д(р) — a + О при р -» р»). 4. Третье неравенство справедливо для всех векторов р Є S П Щ3(р ) (при любых достаточно малых числах 52 0) в силу леммы 2.9, поскольку выполнено предельное соотношение а = д(р) — a + 0 при р—їр . 5. Выполнение четвертого неравенства следует из включения В(рк) Є С(Рк), выполненного по определению последовательности {Рк} 6.
Выполнение пятого неравенства следует из доказательства теоремы 1.3. Согласно этому доказательству, существуют константа С 0 и малое число 5з 0 такие, что для любых векторов р Є Bj3 (р ), справедлива оценка Поскольку на основании теоремы 2.1 имеет место сходимость итерационного процесса (2.3) к вектору р», то существует достаточно большой номер К такой, что для всех номеров к К выполнено включение рк Є Вд(р ), где число 6 = mm{Si, 62,83}, а стало быть выполняется цепочка неравенств (2.19). Положим константу С = СС. Теорема доказана. Замечание 2.9 Из доказательства теоремы 2.4 следует, что выполнение "неточного" доворота не ухудшает скорость сходимости метода. Рассмотрим итерационный процесс на основе (2.3) с тем отличием, что очередной вектор p/t+i итерационной последовательности, определяемый условием подменяется "не ухудшающим" функцию ;() вектором pk+i, который удовлетворяет требованию Если при такой подмене метод (2.3) сходится, то скорость его сходимости по-прежнему останется квадратичной. Это утверждение справедливо, поскольку в этом случае остается верной цепочка оценок (2.19) в теореме 2.4. Лемма 2.9 Пусть зафиксировано множество .М Є Г(1КП) и точка у . ЛЛ. На единичной сфере S С К" рассматриваются множества уровня С(а) — {ф Є S С К" : д(ф) = а} функции д( ), определяемой равенством д(ф) = а(ф) — у ф. Обозначим вектор р = argmin д(ф) и число а» = д(р ) = т т д(ф). Тогда существуют положительные константы є и С такие, что сразу при всех значениях скалярного параметра а, удов Доказательство. Для произвольного вектора р Є (а), где скалярный параметр а = а + є, выполняется равенство Из доказанного выше утверждения (2.6) следует справедливость предельного соотношения h(C(a), {р }) —» 0 при а — а» +0. На этом основанииционного процесса (2.3) к вектору р», то существует достаточно большой номер К такой, что для всех номеров к К выполнено включение рк Є Вд(р ), где число 6 = mm{Si, 62,83}, а стало быть выполняется цепочка неравенств (2.19). Положим константу С = СС. Теорема доказана. Замечание 2.9 Из доказательства теоремы 2.4 следует, что выполнение "неточного" доворота не ухудшает скорость сходимости метода. Рассмотрим итерационный процесс на основе (2.3) с тем отличием, что очередной вектор p/t+i итерационной последовательности, определяемый условием подменяется "не ухудшающим" функцию ;() вектором pk+i, который удовлетворяет требованию Если при такой подмене метод (2.3) сходится, то скорость его сходимости по-прежнему останется квадратичной. Это утверждение справедливо, поскольку в этом случае остается верной цепочка оценок (2.19) в теореме 2.4. Лемма 2.9 Пусть зафиксировано множество .М Є Г(1КП) и точка у . ЛЛ. На единичной сфере S С К" рассматриваются множества уровня С(а) — {ф Є S С К" : д(ф) = а} функции д( ), определяемой равенством д(ф) = а(ф) — у ф. Обозначим вектор р = argmin д(ф) и число а» = д(р ) = т т д(ф). Тогда существуют положительные константы є и С такие, что сразу при всех значениях скалярного параметра а, удов Доказательство. Для произвольного вектора р Є (а), где скалярный параметр а = а + є, выполняется равенство Из доказанного выше утверждения (2.6) следует справедливость предельного соотношения h(C(a), {р }) —» 0 при а — а» +0. На этом основании, для любых векторов ра С{а) справедливо предельное соотношение ра — Р - 0 при а - а, + 0. Поэтому в силу гладкости функции ?() выполняется равенство Поскольку имеет место равенство д (р ) = (р ) У= \ {р ) — УІР и» согласно лемме 2.10, справедливо соотношение VP "—г 2 — _ 1 то выполняется равенство
Сходимость численного метода
Теорема 3.1 Пусть зафиксирована точка у Є Rn, для семейства множеств Л/"(-) имеет место включение Л/"() Є conv(Rn) для всех моментов времени t, удовлетворяющих условию t Є [Т0,Ті], и выполнены следующие требования: 1. если i,t Є [То,Ті] и і t, то справедливо включение М(І) С //(Ї) (монотонная зависимость множеств от времени); 2. для любого момента времени і Є [Т0, Ті] и для любого числа є О найдется число 8 = 8(і, є) 0 такое, что будет выполнена оценка h(N(i),ftf(t)) є для всех моментов времени Ї таких, что \і — t\ 8 ut Є [Т0, Ті] (непрерывная зависимость множеств от времени в метрике Хаусдорфа). Тогда итерационный процесс (3.2) сходится, и выполнены предельные соотношения \pk\ -I 0 и tk t t при к — со, где момент времени является решением рассматриваемой задачи и определяется в (3.1). Замечание 3.4 Теорема 3.1 допускает следующую эквивалентную формулировку в терминах опорных функций. Теорема 3.2 Пусть зафиксирована точка у Є Rn, для семейства множеств Л/"( ) имеет место включение M(t) Є conv(Rn) для всех моментов времени t, удовлетворяющих условию t Є [Т0,Ті], и выполнены следующие требования: 1. уфЩТо) иуеЫЩТг); 2. mm \c(J\f(t)}ip) — c(Af (і), ф)\ О, если t і и i,t Є [Т0,Ті] (монотонная зависимость множеств от времени); для всех моментов времени t, удовлетворяющих условию \i — t\ 5 и t Є [Т0,ТІ] (непрерывная зависимость множеств от времени в метрике Хаусдорфа). Тогда итерационный процесс (3.2) сходится, и выполнены предельные соотношения Pk \г О и tk 1" і при к — оо, где момент времени t является решением рассматриваемой задачи и определяется в (3.1). Эквивалентность двух формулировок вытекает из свойств опорных функций выпуклых компактных множеств (см. например, [21]). Доказательство. В том случае, если на к-оы шаге итерационного процесса (3.2) выполняется равенство pk = 0, то справедливы соотношения у — v(tk) = 7r(A/ (ffe),y) Є N{tk). Поскольку имеет место равенство $( ,Р -і) = (у Р -і)і то выполнено включение у Є dN(tk) и решение, определенное согласно (3.1), найдено: tk = t . Рассмотрим случай, когда процесс не завершается за конечное число шагов. В силу определения вектора Рк = У — v(tk) — У — ( / (tfc), г/)т справедливо неравенство это следует из доказательства Леммы об отделимости (см., например, [21] или [35]). Для момента времени t = Ті в силу условия 1 теоремы выполнено соотношение Введем функцию дРк( ) : Ж1 - R1, определенную равенством gPk(t) = c(ftf(t),pk) — (y,Pk)-Согласно (3.3) и (3.4) выполнены неравенства gPk(tk) 0 и дРк{Ті) 0. Функция дРк( ) непрерьгена на отрезке [ТЬ,Ті], справедливость этого утверждения напрямую следует из условия 3 доказываемой теоремы, сформулированном в терминах опорных функций. На этом основании, существует такой момент времени что выполняется равенство gPlt(tk+i) = 0. То есть в соответствии с рекуррентным соот Таким образом, из (3.3) и (3.6) следует неравенство основании условия 2 теоремы влечет выполнение неравенства Из (3.5) вытекает, что монотонная последовательность {tk} ограничена сверху числом 7\ и, следовательно, имеет место сходимость к некоторому пределу: tk t при к — оо. Последовательность {р } является невозрастающей в силу равенства р = р(у, Af(tk)) и включения J\f(tk) Q Af(tk+i), которое справедливо, поскольку последовательность {tk} не убывает и выполнено условие 2 теоремы.
Точка v(tk) = n(J\f(tk), у) является опорной точкой (см. лемму 3.1) ко множеству M(tk) на векторе рк, поэтому с учетом (3.2) справедливы равенства Перейдем в этих равенствах к пределу при к —у со. Тогда, в силу установленной сходимости, справедливо предельное соотношение tk t і, а в силу непрерывности функции и(-) (следует из доказательство леммы 1.4), выполняется условие рк — р = у—v[t). Поскольку опорная функция непрерывна по обоим аргументам, то имеют место равенства Вычитая первое равенство из второго, получим Следовательно, справедливо соотношение р = 0, то есть выполнены равенства у—v(i) = О и t = t . Теорема доказана. Замечание 3.5 Из доказательства теоремы 3.1 вытекает следующее важное утверждение: при выполнении только одного ее условия 3 (непрерывная зависимость множеств от времени), если последовательность {tk} в итерационном процессе (3.2) сходится, то справедливы предельные соотношения tk — t», pk — 0 при к — со. Справедливость замечания 3.5 следует из возможности предельного перехода в равенствах (3.7) при выполнении условия 3 теоремы 3.1. Лемма 3.1 Пусть зафиксированы множество Л Є conv(Rn) и точка у Є Rn, у $. Л. Пусть точка х = тг(А, у) - проекция точки у на множество Л. Тогда х является опорной точкой множества Л на векторе у — х, то есть выполнено равенство Настоящая лемма переформулирует в терминах опорных функций утверждение леммы 2.1. Замечание 3.6 В случае у G дЛ лемма 3.1 также справедлива, поскольку имеет место равенство у — х = 0. Лемма 3.2 Пусть зафиксированы множество АЛ Є Г(КП) с опорной функцией а( ) и точка у Є R", причем выполнено условие у ф. Л4. Пусть точка х = 7г(.М,у) - проекция точки у на множество АІ, а вектор р определен равенством р = і _—г. Тогда справедливы равенства Доказательство. Из леммы 3.1 и положительной однородности измерения один опорной функции следует равенство ст(р) = (х,р), которое на основании теоремы о градиенте опорной функции (см., например, [4]) равносильно равенству х = сг (р). Первое утверждение леммы - равенство (3.8) - доказано. Справедливы следующие соотношения: Это утверждение справедливо, поскольку в противном случае существует некоторый вектор фо Є Б такой, что фо ф р и точка /( »о) Є дМ. также является проекцией, то есть выполнено равенство (в силу единственности проекции на выпуклый компакт) а (фо) = х. Тогда выполнено равенство сг(фо) = (х,Фо), то есть вектор ф0 является опорным ко множеству М. в точке х, что противоречит однозначности определения такого вектора с точностью до скалярного положительного множителя для гладких выпуклых компактов (см., например, [4]). Равенство (3.9) обосновано. Лемма полностью доказана. Замечание 3.7 Если в предположениях леммы 3.2 выполнены условия у Є дЛі, р Є S « у = о (р) (последнее равенство в данных предположениях эквивалентно условию с{р) = у р), то, поскольку вектор р является опорным ко множеству Лі Є Г(К") в точке у и поэтому определен однозначно (см., например, [4]), и в этом случае справедливо равенство (3.9).
Похожие диссертации на Методы решения некоторых классов задач оптимального управления на основе соприкасающихся эллипсоидов
