Содержание к диссертации
Введение
Глава 1. Аппроксимация задачи оптимального управления 26
1.1. Постановка задачи и аппроксимация задачи оптимального управления 26
1.2. Конечномерная седловая задача 31
Глава 2. Итерационные методы решения седловых задач 36
2.1. Градиентный метод решения регуляризованной задачи (52) 36
2.2. Предобусловленный метод Удзавы для исходной задачи 38
2.3. Контроль точности и критерии остановки 41
2.4. Результаты вычислительных экспериментов 44
Глава 3. Регуляризация седловых задач по двойственным переменным 53
3.1. Общая теорема 53
3.2. Оценки погрешности метода регуляризации для специального случая седловой задачи 56
3.3. Блочный метод Гаусса-Зейделя для седловой задачи (86) с симметричной матрицей 59
3.4. Решение эллиптической задачи оптимального управления с нелокальными ограничениями на состояние 63
3.5. Результаты вычислительных экспериментов 67
Глава 4. Задача с дополнительным поточечным ограничением на состояние 74
4.1. Формулировка и сеточная аппроксимация задачи 74
4.2. Исследование сходимости сеточной схемы 77
4.3. Сеточная седловая задача и итерационный метод решения 82
4.4. Результаты вычислительных экспериментов 88
Заключение
- Конечномерная седловая задача
- Предобусловленный метод Удзавы для исходной задачи
- Блочный метод Гаусса-Зейделя для седловой задачи (86) с симметричной матрицей
- Исследование сходимости сеточной схемы
Конечномерная седловая задача
Рассматривается следующая задача оптимального управления. В качестве задачи состояния выступает однородная задача Дирихле для уравнения Пуассона в ограниченной области Q с кусочно гладкой границей Q: — A = , Є Г2, () = 0, Є Vt. (37) Здесь - функция управления, решение - состояние системы. Множества ограничений на функции управления и состояния задаются равенствами
Рассматриваемая задача оптимального управления аппроксимирована конечно-разностной задачей на равномерной сетке в случае квадратной области Q. Изучена однозначная разрешимость исходной и сеточной задач, сходимость приближенных решений к точному. Наряду с исходной дискретной задачей оптимального управления рассмотрена регуляризованная задача. Получена оценка нормы разности решений исходной и регуляризованной задач. Для обеих конечномерных задач построены итерационные методы решения, доказана их сходимость. Проведены вычислительные эксперименты, направленные на сравнение скорости сходимости предложенных итерационных методов, в том числе, при уменьшении шага сетки и параметра . Обобщенная постановка задачи состояния (37) есть интегральное тождество у Є H0(Q) : / \7у \7zdx = / uzdx Vz Є H0(Q). (39) Оно имеет единственное решение у Є HQ(Q) при любой правой части и Є L2(f2), при этом справедливо неравенство устойчивости ІМІяЧп) MIIL2(O), к = const. (40) Лемма 1. Задача оптимального управления найти min J (у, и), Шек (41) К = {(у, и) : у Є Yad, и Є Uad, выполнено (39)} имеет единственное решение. Доказательство. Множества Uad и Yad выпуклы и замкнуты, при этом Uad ограничено. Отсюда, а также из линейности уравнения состояния (39) и нера венства устойчивости (40) следует выпуклость, замкнутость и ограничен ность множества К. Функционал J - непрерывный и строго выпуклый в HQ(Q) х L,2(P). Из приведенных свойств К и J следует существование един ственного решения задачи (41). Пусть Q = (0,1) х (0,1). Построим конечно-разностную аппроксимацию задачи (41) на равномерной сетке Mh = {{хі,Уз) = i h,jh), г, j, = 0,1,... ,n + 1; (n + l)/i = 1}, считая для простоты, что функции и и yd непрерывны. Будем обозначать через Vij узловые параметры сеточной функции Vh, т. е. Vij = Vh{ih,jh).
Конечно-разностные аппроксимации задачи состояния (39), множеств ограничений на сеточные функции управления Uh и состояния у и целевого функционала имеют, соответственно, вид:
В результате получаем конечномерную задачу оптимального управления найти min Jh(yh,Uh), К = {(yh,Uh) Ун adiuh Є ad? выполнено уравнение (42)}. Аналогично Лемме 1 легко доказать следующее утверждение: Лемма 2. Задача (43) имеет единственное решение. Проведем исследование сходимости последовательности решений задачи (43) при /І 4 0 к решению задачи (41). С этой целью прежде всего запишем конечно-разностную задачу (43) в виде задачи для сеточных функций из конечномерного подпространства пространства HQ(Q) Х L2 l).
Пусть каждая ячейка [жі,Жі + h] х [ 2, 2 + /г] сетки си разбита на два треугольника диагональю, параллельной биссектрисе положительного квадранта. Множество полученных треугольников ЄІ образует триангуляцию Th замкнутой области Q. Обозначим через Vh = {ун С(і) П HQ(Q) : yh(x) линейна на каждом Є{ Є Th} С HQ(Q) пространство конечных элементов.
Пусть далее 5(х) = [х\ — /г/2, х\ + /г/2] х [х2 — /г/2, Х2 + /г/2] для х Є си и Wh Є L2{Q) — это пространство кусочно-постоянных функций, постоянных на 5(х) и продолженных нулем на Q \ Uxeuj5(x).
Ясно, что функции yh Є Vh и yh Є Wh однозначно определяются своими узловыми значениями {yij} в узлах сетки о;, поэтому между ними существует взаимно-однозначное соответствие. Кроме того, справедливо неравенство: \\yii — Ук\\ь2 сЩунЦн1- (44) Используя введенные обозначения, сеточную задачу состояния перепишем в виде
Доказательство. Возьмем функцию z(x) Є C(Q) P\HQ(Q) И обозначим через Zh и Zh ее 14- и W/j-интерполянты (сеточные функции из соответствующих пространств, совпадающие с z(x) в узлах сетки си). Тогда последовательность {zh} сходится сильно в Н1 к z, а последовательность {zh} сходится к z сильно в L i. Переходя к пределу при /і Ов интегральном тождестве Vy/j Vzhdx = uhZhdx, получим (39). Поскольку пространство C(Q)P\HQ(Q) ПЛОТНО В HQ(Q), ТО пара (у, и) удовлетворяет уравнению состояния (39). Множества Yaj С HQ(Q) И Uad С (Г ) выпуклы и замкнуты, т. е. слабо замкнуты, поэтому у Є Yad, и Є Uag. В итоге (у, и) Є К. Лемма 4. Для любой пары функций (у, и) Є К найдется последовательность {(yh,uh)} функций из Kh, которая сильно в HQ(Q) Х L2(f2) сходится к (у,и).
Доказательство. Из (45) и ограниченности u/ji,2 следует ограниченность II У/і II я1- Отсюда и из неравенства (44) следует существование подпоследовательности (сохраним за ней обозначение (уь,йь)) и пары (у,и) Є HQ(Q) Х ІУ2(Г2) таких, что
Предобусловленный метод Удзавы для исходной задачи
Как видно из оценок теорем 2 и 4, градиентный метод и метод Удзавы для регуляризованных задач сравнимы по скорости сходимости (асимптотически по є они имеют одинаковую скорость сходимости). При этом в методе Удзавы допустимый интервал для итерационного параметра не зависит от є, более того, теоретически оптимальный параметр г г + /І ІП также не зависит от є. Поэтому формальный переход к пределу при є — 0 дает теоретически "оптимальный" итерационный параметр в методе Удзавы для исходной (нерегуляризованной) задачи. Вычислительные эксперименты показывают, что численно оптимальный параметр г близок к указанному значению.
Для контроля точности итераций мы используем оценку нормы вектора невязки, определение которого в случае решения включения с многозначным оператором, дано ниже. При решении системы Ах — С X + дф(х) Э /, Сх = 0 каким-либо итерационным методом, мы находим не только приближение (хк, Хк) к точному решению (ж, А), но и вектор 7 дф(хк) — селекцию многозначного оператора. Определим компоненты вектора невязки равенствами rx = f — Ах — 7 + С X , гл = Сх . (72) Тогда вектор погрешности (х — хк, Х — Хк)т удовлетворяет системе включений А —С \ (х — х \ ( дф(х) — 7 \ [тх С О J \А — Л J \ О J \гЛ Умножив скалярно эту систему на вектор (х—хк, Х—Хк)т и воспользовавшись неравенством (дф(х) — дф(хк),х — хк) 0, получим (А(х — х ),х — х ) (гх,х — х ) + (гЛ, Л — Л ). Пусть (Ах, х) m \\х\\2, тогда т\\х — х гжж — х \\ + \\i"\\\\\X — X , или \\х — х сігж + С2ІЛ — Л гл Vk (73) с постоянными Сі,С2, не зависящими от номера итерации к. о погрешности \\х — Хк\\ через оценку норм компонент невязки \\гк\\ и Г; При решении седловой задачи итерационным методом Удзавы включение Ах — ВТХ + дір(х) Э / решается точно на каждой итерации. Поэтому гк = 0 У к, и оценка (73) принимает вид
Пусть тройка векторов (ук, ик,Хк) - это &-ая итерация градиентного метода (60). При реализации этого метода векторы ик и Хк — решения, соответственно, сеточного уравнения состояния и сеточного сопряженного уравнения - находятся точно (или, по крайней мере, с очень высокой точностью). Поэтому контролем точности итераций выступает норма вектора невязки во включении для определения приближения к вектору управления и: 5к = гик+Хк+ к, где 7м д(р(ик) — единственная селекция из соответствующего множества, определенная на предыдущем итерационном шаге:
Отметим, что малость нормы вектора невязки характеризует близость итерации метода (60) к решению регуляризованной задачи (52), которое, в свою очередь, может достаточно существенно отличаться от решения исходной задачи (50) (см. оценку (53)).
Пусть теперь тройка векторов (ук,ик,Хк) есть к-ая итерация метода (66). При реализации этого метода решения двух включений на первом шаге описанного выше алгоритма находятся точно. Поэтому в качестве контроля точности итераций берется Ь2-норма вектора невязки 5к = Lyk — ик. 2.4. Результаты вычислительных экспериментов
В качестве начальных приближений в обоих методах выбирались нулевые векторы. Результаты вычислений с использованием градиентного метода приведены для регуляризованной задачи с параметром регуляризации = 0,02. Выбор меньшего параметра регуляризации приводил к существенному увеличению числа итераций и времени вычислений для достижения заданной точности.
Зависимость погрешности , - от в градиентном методе, где u -точное решение аппроксимированной задачи, полученное в методе Удзавы после большого числа итераций, сетка 10 10 Расчеты показали независимость этой погрешности от шага сетки. Во всех тестовых расчетах метод Удзавы оказался более эффективным, чем градиентный метод для регуляризованной задачи. Результаты расчетов приведены в нижеследующих таблицах, в которых указаны общее количество итераций и время вычислений в формате минуты:секунды:миллисекунды, — число точек сетки в одном направлении.
Также были реализованы варианты итерационных методов, названные двухсеточными и трехсеточными. Для этого, вначале проводились вычисления на сетке, в два раза более крупной, чем исходная. Затем полученные результаты интерполировались на мелкую сетку и принимались в качестве начальных приближений.
Блочный метод Гаусса-Зейделя для седловой задачи (86) с симметричной матрицей
Применим полученные результаты к исходной сеточной аппроксимации к исходной задаче оптимального управления (38). Приведем оценки погрешности метода регуляризации и скорости сходимости итераций метода (93) к решению регуляризованной задачи (103) (следствия оценок (89)-(91) и (102), соответственно). Кроме того, обсудим алго 64 ритмы численной реализации итерационного метода. Отметим, что с точностью до множителя h векторная норма г соответствует Ь2-норме сеточной функции Vh с узловыми параметрами -и, векторная норма fz, – И -норме сеточной функции Vh и векторная норма \\Lv\\ - W$-норме сеточной функции Vh. Таким образом, можно оценки вида (89)-(91) записать для норм сеточных функций yh — yjh и uh — Uh через соответствующие нормы множителя Лагранжа А . Будем использовать следующие обозначения: 1Мо = 112/11ь2, \\у\\\ = IMIvr1? 1Mb = IMIvr2 a) D = Е. Оценка близости регуляризованного и точного решений:
Решение включения для и сводится к проекции известного вектора на множество ограничений Uad, которая находится прямыми вычислениями благодаря структуре Uad. С другой стороны, включение для у эквивалентно вариационному неравенству с матрицей Е + —L , число обусловленности которой имеет порядок /г-4. В связи вычисление у внутренним итерационным методом требует значительных вычислительных затрат. При этом численные эксперименты показывают, что скорость сходимости внешнего итерационного метода () чувствительна к точности нахождения uk+l и yk+l.
Его скорость сходимости при оптимальном параметре г характеризуется множителем перехода порядка 1 — re. Другой вариант решения включения для и - это его преобразование к системе из включения с диагональным оператором и нелинейного уравнения с симметричной, положительно определенной матрицей L и монотонным, диа 1 1 гональным и липшиц-непрерывным оператором -{гЕ + др) :
Из приведенного анализа следует, что наиболее просто реализуемым является метод с = 2. С другой стороны, как следует из оценок точности (104) — (106), при его использовании для достижения хорошей точности метода штрафа может потребоваться существенно меньший параметр , чем при = и, тем более, при = .
Действительно, с точностью до множителя векторная норма соответствует 2-норме сеточной функции с узловыми параметрами , векторная норма – 21-норме сеточной функции и векторная норма – 22-норме сеточной функции . Таким образом, оценки (104) — (106) можно трактовать как погрешности метода штрафа – оценки норм сеточных функций - и - через 2-норму множителя Лагранжа 0 в случае D = Е, его И -норму при D = L и И -норму при D = L2. Ясно, что величина AJw2 может оказаться существенно больше, чем AJr„, если А9
В качестве начальных приближений в обоих методах выбирались нулевые векторы. Расчеты показали независимость этой погрешности от шага сетки. Результаты расчетов приведены в нижеследующих таблицах, в которых указаны общее количество итераций и время вычислений в формате мину-ты:секунды:миллисекунды, N — число точек сетки в одном направлении.
Также были реализованы варианты итерационных методов, названные двухсеточными и трехсеточными. (см. (75)) Этот прием позволил ускорить вычисления. Как показали вычислительные эксперименты, использование последовательности трех и более сгущающихся сеток не приводят к заметному ускорению сходимости.
Для начала приведем расчеты с блочным методом Гаусса-Зейделя для случая D = L. Слабая сходимость этого метода и линейное увеличение числа итераций от шага сетки показали крайнюю неэффективность данного выбора предобуславителя. Рисунок 5: Зависимость погрешности , \\у — у \\ от є в блочном методе
Гаусса-Зейделя, Случай D = L где y -точное решение, полученное в методе Удзавы после большого числа итераций, сетка 40 40 Таблица 10: Блочный метод Гаусса-Зейделя, Случай = . = 0.01, = 0. N решение на одной сетке число итераций, время Использование предобуславливателя = 2 дало более оптимистичные результаты, например малую зависимость от шага сетки. В дальнейшем в этой главе будут приведены расчеты только для этого случая.
Кроме того, была рассмотрена работа двухшагового метода, при котором сначала находилось решение задачи с использованием более крупного параметра ї, затем (при нахождении точного решения для данного параметра или спустя некоторое число итераций) этот параметр уменьшался в несколько раз (в расчетах на 5) и продолжалась работа метода.
Исследование сходимости сеточной схемы
Из выпуклости множеств Uad и Yad и линейности уравнения состояния (107) следует выпуклость множества К. В силу замкнутости Uad и Yad и неравенства устойчивости (110) множество К замкнуто. Наконец, оно не пусто, так как содержит нулевой элемент.
Функционал J - непрерывный, строго выпуклый и коэрцитивный в HQ(Q) х L,2(P). Из приведенных свойств К и J следует существование един ственного решения задачи (109) (см., например, [15]). Построим конечно-разностную аппроксимацию задачи (109). С целью дальнейшего исследования сходимости сформулируем конечно-разностную схему в виде задачи для сеточных функций из конечномерного подпространства пространства HQ(Q) Х L2(f2).
Пусть си = {{xi, Х2) = (ih,jh), і, j, = 0,1,..., n + 1; (n + 1)/г = 1} - равномерная сетка на Cl. Разобьем каждую ячейку А(х) = [хі, х\ + Щ х [х2, Х2 + /г] сетки си на два треугольника диагональю, параллельной биссектрисе положительного квадранта. Множество полученных треугольников ЄІ образует триангуляцию Th замкнутой области Сі. Обозначим через Vh = {ун С(0,) : Ун(х) линейна на каждом ЄІ Є Th} С Н1(С1) пространство кусочно-линейных функций и через Vh - его подпространство функций, равных нулю на границе области, Vh С HQ(Q). Пусть далее 8{х) = [х\ — /г/2, х\ + /г/2] х [х2 — /г/2, Х2 + /г/2] - ячейка с центром в точке х Є и и Qo = Q\\\ 5(х). Введем в рассмот рение пространство Wh кусочно-постоянных функций уh, которые постоянны на каждом 5{х) и продолжены нулем на CIQ. Функции % Є У/,0 и Є Wh однозначно определяются своими узловыми параметрами {vij}, i,j = l,2,...n, - значениями во внутренних узлах сетки о;, поэтому между ними существует взаимно однозначное соответствие. Обозначим через у-h, y+h 14-интерполянты непрерывных функций у_, у+, т.е. функции из Vh, совпадающие в узлах сетки си с интерполируемыми непрерывными функциями. Пусть 7T/j : Li(Q) — Wh, 7Thu(y) = h / u(t)dt в точках у Є 5(х), - оператор интегрального усреднения и д(х) jjdh = T hVdi "Udh = hUd-, U-h = TThU-i U+h = 7 hU-\- - И -интерполянты соответ ствующих функций. Используя введенные обозначения, определим сеточную задачу состояния, множества ограничений и сеточную целевую функцию следующими равенствами:
Для обоснования сходимости конечномерных аппроксимаций вариационных неравенств и задач минимизации следует доказать аппроксимацию множества К семейством множеств {Kh\h и функционала J - семейством функций {Jh}h (см. напр., [7], глава 1, п.4.3, 4.4). Следующие две леммы характеризуют аппроксимацию множества К множествами К .
Лемма 12. Пусть {yh-,Uh) Є Kh и последовательность {(yh uh)} слабо в HQ(Q) х L2 l) сходится к (у,и). Тогда (у,и) Є К.
Доказательство. Докажем сначала, что предельная пара (у, и) удовлетворяет уравнению состояния (107). Возьмем функцию z(x) Є С {Сі) П HQ(Q) и обозначим через Zh и Zh ее Vh- и И -интерполянты. Тогда последовательность {zh} сходится сильно в Hl(Q) к z, а последовательность {zh} сходится к z сильно в L2{1). Переходя к пределу при h — 0 в интегральном тождестве (111), получим (107). Поскольку пространство C(Q)P\HQ(Q) плотно в HQ(Q), то пара (у,и) удовлетворяет уравнению состояния (107).
Перейдем к доказательству включений и Є Uad и у Є Ya&. Возьмем произвольное є 0 и введем в рассмотрение множества Yaf = {у Є HQ(Q) : У-(х) — є у{х) У+{%) + є п.вс. в Q} и [/ = {it Є (Г ) : ІІ_(Ж) — є it (ж) и+(х) + є п.вс. в Q}. В силу предельных соотношений (116) при достаточно малых h h(є) справедливы включения Y j1 С Yaf и U d С L d. Поскольку выпуклые и замкнутые множества Yaj и (У слабо замкнуты, то у Є Yad и и Є UFad. Осталось заметить, что Yad = ( Yad и Uad = ґ U d, є 0 є 0 а у Є Уд/, м Є Uad для всех є 0, поэтому у Є Y и и Є [7 . Наконец, Y J1 С Y d и Y слабо замкнуто, поэтому у Є Y .
Таким образом, любая пара (у,и) Є К является пределом функций {уП)ип) Є К, обладающих дополнительной гладкостью, и таких, что (уп,ип) Є intY х intUad. Поэтому далее будем строить последовательность {{yh,Uh)} Kh, которая сильно в HQ(Q) Х Ь2ІР) сходится к паре (у, и) Є К, обладающей перечисленными свойствами, а именно: