close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Том 154, кн. 3
УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОО УНИВЕСИТЕТА
Физико-математические науки
2012
УДК 519.63+517.977.58
ЧИСЛЕННОЕ ЕШЕНИЕ ОДНОЙ ЗАДАЧИ
ОПТИМАЛЬНОО УПАВЛЕНИЯ СИСТЕМОЙ,
ОПИСЫВАЕМОЙ ЛИНЕЙНЫМ ЭЛЛИПТИЧЕСКИМ
УАВНЕНИЕМ, ПИ НАЛИЧИИ НЕЛОКАЛЬНЫХ
ОАНИЧЕНИЙ НА СОСТОЯНИЕ СИСТЕМЫ
Д.. Залялов, А.В. Лапин
Аннотация
ассмотрена задача оптимального управления правой частью линейного эллиптического уравнения при наличии поточечных ограничений на ункцию управления и нелокального ограничения на ункцию состояния системы. Построены сеточная аппроксимация задачи, доказано существование единственного приближенного решения и сходимость
к точному при измельчении сетки. Изучена сходимость двух классов итерационных методов решения полученной сеточной задачи оптимизации. Проведено сравнение численных
результатов, полученных разными методами, проанализирована зависимость скорости
сходимости от шага сетки и параметра регуляризующего слагаемого в целевом ункционале.
Ключевые слова: линейное эллиптическое уравнение, оптимальное управление,
конечно-разностная аппроксимация, итерационные методы.
Введение
Задачи оптимального управления системами, описываемыми уравнениями в
частных производных при наличии ограничений на состояние системы, представляют собой весьма сложный объект численного анализа.
Известны два основных подхода при решении указанных задач оптимального
управления. В первом из них для диеренциальной задачи строится ункция
Лагранжа и затем находятся ее стационарные точки. Основная трудность в этом
случае связана с отсутствием какой-либо гладкости множителей Лагранжа, которые являются лишь мерами. В связи с этим используются методы регуляризации
диеренциальных задач (регуляризации типа Моро Иосиды или Лаврентьева),
затем регуляризованные задачи аппроксимируются конечномерными задачами и
решаются каким-либо из известных методов (см. статьи [17? и библиограию в
них). Второй подход к решению задач оптимального управления, в том числе с
ограничениями на состояние, состоит в первоначальной аппроксимации диеренциальной задачи с использованием, как правило, сеточных методов, и в дальнейшем решении дискретной задачи оптимизации с ограничениями-равенствами и
ограничениями-неравенствами. Несмотря на ѕклассическийї характер таких задач
(см. монограии [810?), проблемы построения эективных итерационных методов их решения продолжают оставаться актуальными [11?, поскольку в большинстве случаев эти задачи характеризуются очень высокой размерностью и плохой
обусловленностью.
Настоящая статья является продолжением исследований в области построения
и теоретического и численного анализа итерационных методов решения сеточных
130
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
задач оптимального управления с ограничениями на ункции управления и состояния (см. [1214?).
ассматривается следующая задача оптимального управления. В качестве задачи состояния выступает однородная задача Дирихле для уравнения Пуассона
в ограниченной области ? с липшицевой границей ?? :
??y = u,
x ? ?,
y(x) = 0,
(1)
x ? ??.
Здесь u ункция управления, решение y состояние системы. Множества ограничений на ункции управления и состояния задаются ормулами
(
)
Z
1
Uad = {u ? L2 (?) : |u(x)| 6 1 ?x ? ?}, Yad = y ? H0 (?) :
y(x) dx 6 1 ,
?
а целевой ункционал имеет вид
Z
Z
1
r
2
(y ? yd ) dx +
u2 dx,
J(y, u) =
2
2
?
r = const > 0,
yd ? L2 (?).
?
ассматриваемая задача оптимального управления аппроксимирована конечноразностной задачей на равномерной сетке в случае квадратной области ? . Изучена
однозначная разрешимость исходной и сеточной задач, сходимость приближенных
решений к точному. Наряду с исходной дискретной задачей оптимального управления рассмотрена регуляризованная задача. Получена оценка нормы разности
решений исходной и регуляризованной задач.
Для обеих конечномерных задач построены итерационные методы решения, доказана их сходимость. Проведены численные эксперименты, направленные на сравнение скорости сходимости предложенных итерационных методов, в том числе при
уменьшении шага сетки, и параметра r .
1.
Аппроксимация задачи оптимального управления
Обобщенная постановка задачи состояния (1) ормулируется в виде интегрального тождества
Z
Z
y ? H01 (?) :
?y · ?z dx =
uz dx ? z ? H01 (?).
(2)
?
?
Оно имеет единственное решение y ?
при любой правой части u ? L2 (?) ,
при этом справедливо неравенство устойчивости
H01 (?)
kykH01 (?) 6 kkukL2(?) ,
Лемма 1.
k = const.
(3)
Задача оптимального управления
найти
min J(y, u),
(y,u)?K
K = {(y, u) : y ? Yad , u ? Uad , выполнено (2)},
(4)
имеет единственное решение.
Доказательство. Множества Uad и Yad выпуклы и замкнуты, при этом Uad
ограничено. Отсюда, а также из линейности уравнения состояния (2) и неравенства устойчивости (3) следует выпуклость, замкнутость и ограниченность множества K . Функционал J непрерывный и строго выпуклый в H01 (?) Ч L2 (?) .
Из приведенных свойств K и J следует существование единственного решения
задачи (4).
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
131
Пусть ? = (0, 1) Ч (0, 1). Построим конечно-разностную аппроксимацию задачи
(4) на равномерной сетке ?h = {(xi , yj ) = (ih, jh), i, j = 0, 1, . . . , n+1; (n+1)h = 1} ,
считая, что ункции u и yd непрерывны. Будем обозначать через vij узловые
параметры сеточной ункции vh , то есть vij = vh (ih, jh) .
Конечно-разностные аппроксимации задачи состояния (2), множеств ограничений на сеточные ункции управления uh и состояния yh и целевого ункционала
имеют соответственно вид:
?
?yij?1 + 2yij ? yij+1
? ?yi?1j + 2yij ? yi+1j
+
= uij , 1 6 i, j 6 n,
2
(5)
h
h2
?y = y = y
=y
= 0.
0j
h
Uad
j0
jn+1
n+1j
= {uh : |uij | 6 1, i, j = 1, 2, . . . , n},
Jh (yh , uh ) =
h
Yad
= {yh : h
2
n
X
yij 6 1}.
i,j=1
n
n
h2 X
rh2 X 2
(yij ? yd,ij )2 +
u .
2 i,j=1
2 i,j=1 ij
В результате получаем конечномерную задачу оптимального управления
найти
Kh = {(yh , uh ) : yh ?
min
Jh (yh , uh ),
(yh ,uh )?Kh
h
h
Yad
, uh ? Uad
,
выполнено уравнение (5)}.
(6)
Аналогично лемме 1 легко доказать следующее утверждение.
Лемма 2.
Задача (6) имеет единственное решение.
Проведем исследование сходимости последовательности решений задачи (6) при
h ? 0 к решению задачи (4). С этой целью прежде всего запишем конечноразностную задачу (6) в виде задачи для сеточных ункций из конечномерного
подпространства пространства H01 (?) Ч L2 (?).
Пусть каждая ячейка [x1 , x1 +h]Ч[x2 , x2 +h] сетки ?h разбита на два треугольника диагональю, параллельной биссектрисе положительного квадранта. Множество полученных треугольников ei образует триангуляцию Th замыкания области ? . Обозначим через Vh = {yh ? C(??) ? H01 (?) : yh (x) линейна на каждом
ei ? Th } ? H01 (?) пространство конечных элементов.
Пусть далее ?(x) = [x1 ? h/2, x1 + h/2] Ч [x2 ? h/2, x2 + h/2] для x ? ?h и
Wh ? L2 (?) это пространство S
кусочно-постоянных ункций, постоянных на ?(x)
и продолженных нулем на ? \
?(x).
x??
Ясно, что ункции yh ? Vh и yeh ? Wh однозначно определяются своими узловыми значениями {yij } в узлах сетки ?h , поэтому между yh и yeh существует
взаимно-однозначное соответствие. Кроме того, справедливо неравенство:
(7)
kyh ? yeh kL2 6 chkyh kH 1 .
Используя введенные обозначения, сеточную задачу состояния перепишем в виде
Z
Z
?yh · ?zh dx =
u
eh zeh dx ? zh ? Vh ,
(8)
?
?
а сеточную задачу оптимального управления (6) в следующем виде:
Z
Z
1
r
2
найти
min {Jh (yh , uh ) =
(yh ? ydh ) dx +
u
e2h dx},
2
2
(yh ,e
uh )?Kh
Kh = {(yh , u
eh ) : yh ?
h
Yad
,u
eh
?
?
h
Uad
?
и выполнено уравнение (8)}.
(9)
132
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
Лемма 3. Пусть (yh , u
eh ) ? Kh и последовательность {(yh , u
eh )} слабо в
H01 (?) Ч L2 (?) сходится к (y, u) . Тогда (y, u) ? K .
Возьмем ункцию z ? C(??) ? H01 (?) и обозначим через
zh и zeh ее Vh - и Wh -интерполянты (сеточные ункции из соответствующих пространств, совпадающие с z(x) в узлах сетки ?h ). Тогда последовательность {zh }
сходится сильно в H 1 к z , а последовательность {e
zh } сходится к z сильно в L2 .
Переходя к пределу при h ? 0 в интегральном тождестве
Z
Z
?yh · ?zh dx =
u
eh zeh dx, ? zh ? Vh ,
Доказательство.
?
?
получим (2). Поскольку пространство C(??)?H01 (?) плотно в H01 (?) , то пара (y, u)
удовлетворяет уравнению состояния (2).
Множества Yad ? H01 (?) и Uad ? L2 (?) выпуклы и замкнуты, следовательно,
слабо замкнуты, поэтому y ? Yad , u ? Uad . В итоге (y, u) ? K .
Лемма 4. Для любой пары ункций (y, u) ? K найдется последовательность
{(yh , u
eh )} ункций из Kh , которая сильно в H01 (?) Ч L2 (?) сходится к (y, u) .
Z
Доказательство. Пусть (y, u) ? K , в частности
y(x) dx 6 1 . Поскольку
?
последовательность (y? , u? ) = ?(y, u) принадлежит K и сильно в H01 (?) Ч L2 (?)
сходится к (y, u) при ? ? 1Z ? 0, то можно доказывать утверждение леммы для
пары (y, u) ? K такой, что
y(x) dx 6 ? < 1.
?
Определим u
eh ? Wh равенством u
eh = h
?2
Z
u(t) dt на ячейке ?(x) и пусть
?(x)
h
yh решение уравнения состояния (8) с правой частью u
eh . Тогда u
eh ? Uad
, последовательность u
eh сильно в L2 (?) сходится к u и последовательность yh сильно в H 1 (?)Z сходится к y при h ? 0 . Из последнего утверждения вытекает, что
Z
h
.
y dx 6 ? < 1 , поэтому, начиная с некоторого h(?) , ункции yh ? Yad
yh dx ?
?
?
Таким образом, начиная с h 6 h(?) , последовательность (yh , u
eh ) принадлежит Kh
и сильно в H01 (?) Ч L2 (?) сходится к (y, u) .
Теорема 1. Последовательность решений {(yh , u
eh )} сеточных задач оптимального управления (9) сильно в H01 (?)ЧL2 (?) сходится к решению (y, u) задачи
оптимального управления (4).
Доказательство. Из (8) и ограниченности ke
uh kL2 следует ограниченность
kyh kH 1 . Отсюда и из неравенства (7) следует существование подпоследовательности (сохраним за ней обозначение (yh , u
eh ) ) и пары (y, u) ? H01 (?) Ч L2 (?) таких,
что
yh ? y слабо в H01 (?) и сильно в L2 (?) при h ? 0 ,
yeh ? y сильно в L2 (?) , u
eh ? u слабо в L2 (?) при h ? 0 .
В силу леммы 3 предельная пара (y, u) принадлежит K , а согласно лемме 4 для
любой пары ункций (z, v) ? K существует последовательность (zh , e
vh ) из Kh ,
сильно в H01 (?) Ч L2 (?) сходящаяся к (z, v) . Поэтому
J(y, u) 6 lim inf Jh (yh , u
eh ) 6 lim Jh (zh , veh ) = J(z, v).
h?0
h?0
(10)
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
133
Итак, пара (y, u) является решением задачи (4). В силу единственности решения
и вся последовательность {(yh , u
eh )} слабо в H01 (?) Ч L2 (?) сходится к (y, u) .
Докажем ее сильную сходимость. Для этого возьмем в цепочке неравенств (10)
последовательность (zh , veh ) из Kh , сильно в H01 (?) Ч L2 (?) сходящуюся к (y, u) ,
откуда получим, что последовательность Jh (yh , u
ehZ) стремится при h Z? 0 к J(y, u) .
Поскольку yh ? y, ydh ? yd сильно в L2 (?) , то
поэтому и
Z
?
u
e2h dx
?
Z
(yh ? ydh )2 dx ?
?
(y ? yd )2 dx,
?
u dx при h to0 . Вместе со слабой сходимостью в L2 (?) по2
?
следовательности {e
uh } к u это влечет ее сильную сходимость. Осталось доказать
сильную сходимость в H01 (?) последовательности решений {yh } уравнения состояния (8) к y . Пусть zh сильно в H01 (?) стремятся к y . Тогда, используя уравнения
состояния (8), получим
Z
Z
Z
?(yh ? zh ) · ?(yh ? zh ) dx =
u
eh (e
yh ? zeh ) dx ? ?zh · ?(yh ? zh ) dx.
?
?
?
Левая часть этого равенства стремится к нулю, поэтому kyh ? zh kH 1 ? 0 , откуда
следует сильная сходимость {yh } к y в H01 (?) .
2.
Конечномерные седловые задачи
Пусть множество внутренних узлов xij , 1 6 i, j 6 n, сетки ?h каким-либо
образом упорядочено. Поставим во взаимно-однозначное соответствие сеточным
ункциям векторы из RN , N = n2 , их узловых параметров с координатами, соответствующими выбранному упорядочению узлов. Далее k·k и (·, ·) это евклидова
норма и скалярное произведение в RN .
Система линейных уравнений (5) может быть записана в виде Ly = u с симметричной и положительно определенной матрицей L матрицей сеточного оператора
Лапласа при нулевых граничных условиях Дирихле. Отметим, что минимальное
8
?h
собственное число L равно µmin = 2 sin2
и ограничено снизу константой,
h
2
не зависящей от h .
Множества ограничений в сеточной задаче принимают вид:
Uad = {u ? RN : |ui | 6 1 ?i},
Yad = {y ? RN :
N
X
i=1
h2 yi 6 1 ?i},
1
r
ky ? yd k2 + kuk2. Пусть ?(u) =
2
2
= IUad (u) и ?(y) = IYad (y) индикаторные ункции множеств Uad и Yad . В итоге
сеточная задача оптимального управления (6) преобразуется к виду
1
r
min J(y, u) = ky ? yd k2 + kuk2 + ?(u) + ?(y) .
(11)
Ly=u
2
2
а целевая ункция после деления на h2 равна
Определим ункцию Лагранжа для задачи (11) равенством
L(y, u) =
1
r
ky ? yd k2 + kuk2 + ?(u) + ?(y) ? (Ly ? u, ?).
2
2
(12)
134
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
Седловая точка ункции Лагранжа является решением (см., например, [16?) следующей системы, дающей условия оптимальности первого порядка:
?
?? ? ?
? ? ?
E
0 ?L
y
??(y)
yd
? 0 rE E ? ?u? + ???(u)? ? ? 0 ? .
(13)
?L E
0
?
0
0
Лемма 5. Задача (13) имеет решение (y, u, ?) , при этом пара (y, u) определяется однозначно и совпадает с решением задачи (11).
Доказательство.
Введем следующие обозначения: x = (y, u), ?(x) =
= (?(y), ?(u)),
C = ?L E ,
E
A=
0
0
.
rE
(14)
Матрица A положительно определена, в то время как матрица C имеет полный
ранг. Кроме того, пара векторов (y, u) = (0, 0) является внутренней точкой множества Yad Ч Uad и удовлетворяет уравнению Ly = u . Перечисленные свойства
обеспечивают справедливость сормулированного результата (см. [13, гл. 5?).
Пусть теперь индикаторная ункция ?(y) = IYad (y) множества Yad аппроксимирована диеренцируемой ункцией
N
+
1 X 2
?? (y) =
h yi ? 1
2?
i=1
!2
.
ассмотрим наряду с седловой задачей (13) следующую регуляризованную задачу:
?
?? ? ?
? ? ?
E
0 ?L
y?
??? (y? )
yd
? 0 rE E ? ?u? ? + ? ??(u? ) ? ? ? 0 ? .
(15)
?L E
0
??
0
0
Здесь градиент ??? (y) ункции ?(y) вектор с постоянными координатами, равN
+
1 X 2
ными
h yi ? 1 .
? i=1
Аналогично лемме 5 нетрудно доказать, что задача (15) имеет решение
(y? , u? , ?? ) с единственными компонентами y? и u? . Более того, ?? также определяется однозначно из равенства ?? = L?1 (y? ? yd + ??? (y? )).
Оценку близости решений исходной и регуляризованной задач дает следующая
Лемма 6. Пусть (y? , u? , ?? ) решение регуляризованной задачи (15), (y, u, ?)
решение исходной седловой задачи (13), ?y ? ??(y) соответствующий этому
решению однозначно определяемый вектор из множества ??(y) , то есть ?y =
= yd ? y + L? . Тогда справедлива оценка
ky? ? yk + r ku? ? uk2 6
?
k?y k2 .
2
(16)
Доказательство. Будем использовать введенные ранее обозначения для векторов и матриц A и C (см. (14)) и пусть, кроме того, ?? (x) = (?? (y), ?(u)). Используя эти обозначения и вычитая (13) из (15), получим
A ?C T
x? ? x
??? (x? ) ? ??(x)
+
? 0.
?C
0
?? ? ?
0
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
135
Умножая теперь скалярно соотношения этой системы соответственно на x? ? x и
? ? ?? и складывая, приходим к равенству
ky? ? yk2 + r ku? ? uk2 + (??? (y? ) ? ??(y), y? ? y) + (??(u? ) ? ??(u), u? ? u) = 0.
Из монотонности оператора ?? следует (??(u? ) ? ??(u), u? ? u) > 0 . В силу выпуклости ?? справедливо неравенство (??? (y? ), y? ? y) > ?? (y? ) ? ?? (y) = ?? (y? ) .
В результате получим
ky? ? yk2 + r ku? ? uk2 + ?? (y? ) 6 (?y , y? ? y),
?y ? ??(y).
(17)
Множество ограничений Yad это полупространство, граница которого плоскость
N
P
S = {y :
h2 yi = 1} . Вектор ?y = 0, если y принадлежит внутренности Yad , он
i=1
ортогонален плоскости S и направлен в сторону возрастания
N
P
i=1
h2 yi , если y ? S .
Поэтому (?y , y? ? y) > 0 только в том случае, когда y? ?
/ Yad . Далее считаем, что
y? такой вектор. Обозначим через PS оператор ортогонального проектирования
на плоскость S , тогда
(?y , y? ? y) = (?y , y? ? y ? PS (y? ? y)) = (?y , y? ? PS (y? )) = k?y kky? ? PS (y? )k =
= k?y k
N
X
i=1
2
h yi ? 1
+
?
1
6 k?y k2 +
2
2?
N
X
i=1
h2 y i ? 1
+ 2
=
?
k?y k2 + ?? (y). (18)
2
Из (17) и (18) следует оценка (16).
Замечание 1. a) Если решение седловой задачи (y, u, ?) единственное,
то ?y ? ??(y) также единственный вектор, определенный равенством ?y = yd ?
? y + L? .
b) Для оценки близости точного и регуляризованного решений можно использовать в (16) вектор ?y = yd ? y + L? с вычисленными приближениями к y и ? .
) Величина k?y k в оценке (16) зависит от количества точек сетки, в которых ограничения на вектор состояния y активны, а также от того, насколько эти
ограничения ѕжесткиеї.
Пусть теперь индикаторная ункция ? множества ограничений Uad также заменена регуляризованной ункцией
?? (u) =
1
1
k(u + 1)? k2 +
k(u ? 1)+ k2
2?
2?
+
где v ? и v + векторы с координатами u?
i и vi соответственно. ассмотрим
полностью регуляризованный вариант задачи:
?
?? ? ?
? ? ?
E
0 ?L
y?
??? (y? )
yd
? 0 rE E ? ?u? ? + ???? (u? )? = ? 0 ? .
(19)
?L E
0
??
0
0
Она имеет единственное решение (y? , u? , ?? ) .
Лемма 7. Пусть (y? , u? , ?? ) решение регуляризованной задачи (19),
(y, u, ?) решение исходной седловой задачи (13). Пусть ?y ? ??(y) и ?u ?
? ??(u) соответствующие этому решению однозначно определяемые векторы
136
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
из множеств ??(y) и ??(u) , то есть ?y = yd ? y + L? , ?u = ?ru ? ? . Тогда
справедлива оценка
ky? ? yk + r ku? ? uk2 6
?
(k?y k2 + k?u k2 ).
2
(20)
Доказательство. Почти дословно повторяя доказательство леммы 6, получаем неравенство (аналог (17)):
ky? ? yk2 + r ku? ? uk2 + ?? (y? ) + ?? (u? ) 6 (?y , y? ? y) + (?u , u? ? u),
?
где ?y ? ??(y), ?u ? ??(u) . Оценка (?y , y? ? y) 6 k?y k2 + ?? (y) получена выше.
2
Далее,
X
X
(?u , u? ? u) 6
?ui (u?i + 1) +
?ui (u?i ? 1) = (?u? , (u? + 1)? ) + (?u+ , (u? ? 1)+ ),
i?I
i?J
где I = {i : u?i < ?1; и ?ui < 0} и J = {i : u?i > 1 и ?ui > 0}. Отсюда
(?u , u? ? u) 6 (?u? , (u? + 1)? ) + (?u+ , (u? ? 1)+ ) 6
?
1
(k(u? + 1)? k2 + k(u? ? 1)+ k2 ) + (k?u? k2 + k?u+ k2 ) =
6
2?
2
?
= ?? (u? ) + k?u k2 . (21)
2
Объединяя полученные оценки, приходим к (20).
3.
Итерационные методы решения седловых задач
3.1.
радиентный метод решения регуляризованной задачи (15). азрешив третье уравнение в системе (15) относительно y? и затем первое уравнение
относительно ?? , получим включение для вектора u? (в дальнейшем опускаем
индекс ? у вектора u? ):
ru + L?2 u + L?1 ??? (L?1 u) + ??(u) ? L?1 yd .
(22)
Применим для решения (22) одношаговый итерационный метод
uk+1 ? uk
+ P? uk + ??(uk+1 ) ? L?1 yd ,
?
(23)
где P? = rE + L?2 + L?1 ??? ? L?1 .
Алгоритм реализации метода (23) состоит из следующих шагов.
1. Для известного вектора управления uk находим решение уравнения состояния Ly k = uk ;
2. Находим сопряженное состояние ?k = L?1 (y k ? yd + ??? (y k )) .
3. Находим новое приближение к вектору управления, решив включение с диагональным максимально монотонным оператором E + ? ?? :
uk+1 + ? ??(uk+1 ) ? (1 + ? r)uk ? ? ?k .
При исследовании сходимости и скорости сходимости метода (23) будем использовать следующий результат.
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
137
Утверждение 1 [12, Теорема 4?. Пусть Q монотонный (в общем случае
многозначный) оператор, а оператор P удовлетворяет условиям
(P (u) ? P (v), u ? v) > ?ku ? vk2B ,
(P (u) ? P (v), w) 6 ? 1/2 (P (u) ? P (v), u ? v)1/2 kwkB ,
(24)
где B симметричная и положительно определенная матрица. Тогда итерации
стационарного одношагового метода
1
B(uk+1 ? uk ) + P (uk ) + Q(uk+1 ) ? 0
?
сходятся к решению включения P (u) + Q(u) ? 0 при ? ? (0, 2/?) и любом начальном приближении u0 . Для оптимального параметра ? = 1/? справедлива
оценка
kuk+1 ? ukB 6 ?1/2 kuk ? ukB , ? = 1 ? ?/?.
(25)
Теорема 2.
Итерационный метод (23) сходится при
0<? <
µ?2
min
2?
,
+ ?(r + µ?2
min )
где µmin минимальное собственное число сеточного оператора Лапласа. При
?=
µ?2
min
?
+ ?(r + µ?2
min )
скорость сходимости характеризуется неравенством
kuk+1 ? uk 6 ?1/2 kuk ? uk,
?=1?
µ?2
min
r?
.
+ ?(r + µ?2
min )
Доказательство. Используем утверждение 1 с единичной матрицей B . Достаточно получить оценки вида (27) для оператора P? = P1 + P2 ? , где
P1 = L?2 + rE,
P2 ? = L?1 ??? ? L?1 .
Для P1 справедливы оценки rE 6 P1 6 (r + µ?2
min )E. Далее, оператор P2 ? монотонный:
(P2 ? (u) ? P2 ? (v), u ? v) = (??? (L?1 u) ? ??? (L?1 v),
L?1 u ? L?1 v) > 0.
Для вывода второй оценки для P2 ? докажем одно вспомогательное неравенство
для вектора ??? (y) . Напомним, что ??? (y) это вектор с постоянными коордиN
X
1
натами, равными widee
y + , ye =
h2 yi ? 1 . Поэтому
?
i=1
(??? (y) ? ??? (z), y ? z) =
N
X
1 +
1
(e
y ? ze+ )
(yi ? zi ) = 2 (e
y + ? ze+ )(e
y ? ze) >
?
h
?
i=1
>
1
(e
y + ? ze+ )2
h2 ?
138
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
и как следствие
(??? (y) ? ??? (z), x) =
N
X
1 +
(e
y ? ze+ )
xi 6
?
i=1
N
X
1
|xi | 6
6 ? (??? (y) ? ??? (z), y ? z)1/2 h
?
i=1
1
6 ? (??? (y) ? ??? (z), y ? z)1/2 kxk. (26)
?
В силу неравенства (26) справедлива следующая оценка для P2 ? :
(P2 ? (u) ? P2 ? (v), w) 6
? (P2 ? (u) ? P2 ? (v), u ? v)1/2 w,
µmin ?
1
Объединяя оценки для P1 и P2 ? , получим
2
(P? (u) ? P? (v), u ? v) > ru ? v ,
(P? (u) ? P? (v), w) 6 ? 1/2 (P? (u) ? P? (v), u ? v)1/2 w,
(27)
?2 ?1
где ? = µ?2
. Для завершения доказательства достаточно воспольmin + r + µmin ?
зоваться утверждением 1.
3.2.
Предобусловленный метод Узавы для исходной задачи.
чив векторы y и u в системе (13), получим уравнение для ?
P (?) ? L(E + ??)?1 (L? + yd ) ? (rE + ??)?1 (??) = 0.
Исклю(28)
Применим для решения (28) итерационный метод
L2
?k+1 ? ?k
+ P (?k ) = 0,
?
(29)
являющийся предобусловленным методом Узавы для отыскания седловой точки
ункции Лагранжа (12). При реализации этого метода выполняются следующие
шаги.
1. Для известного вектора ?k находим y k и uk , решив включения с диагональными максимально монотонными операторами
(E + ??)y k ? L?k + yd и (r E + ??)uk ? ??k .
2. Вычисляем pk = L?1 uk .
3. ешаем уравнение
L
Теорема 3.
?k+1 ? ?k
= ?y k + pk .
?
Итерационный метод (29) сходится при условии
0<? <
Доказательство.
полнено неравенство
2r
.
r + µ?2
min
(30)
Согласно [13? итерационный метод (29) сходится, если выL2 >
?
CA?1 C T ,
2
(31)
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
139
где A и C матрицы, определенные в (14). Поскольку
2
CA?1 C T = L2 + r?1 E 6 (1 + r?1 µ?2
min )L ,
2r
.
r + µ?2
min
условие (31) выполнено при ? <
ассмотрим теперь метод Узавы для полностью регуляризованной задачи (19) и
получим оценку скорости сходимости и теоретически оптимальный итерационный
параметр ? .
Исключив векторы y и u в системе (19), для нахождения ? получим уравнение
P? (?) ? L(E + ??? )?1 (L? + yd ) ? (rE + ??? )?1 (??) = 0.
(32)
Применим для решения (32) итерационный метод
L2
Теорема 4.
?k+1 ? ?k
+ P? (?k ) = 0.
?
(33)
Итерационный метод (29) сходится при условии
0<? <
При
?=
2r
.
r + µ?2
min
(34)
r
r + µ?2
min
скорость сходимости характеризуется неравенством
kuk+1 ? uk 6 ?1/2 kuk ? uk,
?=1?
r?
.
(1 + ?)(r + µ?2
min )
Доказательство. В очередной раз используем утверждение 1, полагая B =
= L2 , P = P1? +P2? , P1? (?) = L(E +??? )?1 (L?+yd ) , P2? (?) = ?(rE +??? )?1 (??) .
Непосредственные вычисления дают равенство
(E + ??? )?1 (y)i = yi ?
из которого следует неравенство
1 +
ye
1+?
? i,
((E + ??? )?1 (y) ? (E + ??? )?1 (z), y ? z) =
1
?
= ky ? zk2 ?
(e
y + ? ze+ , y ? z) >
ky ? zk2 .
1+?
1+?
Это неравенство влечет равномерную монотонность оператора P1? :
(P1? (?) ? P1? (µ), ? ? µ) >
?
kL(? ? µ)k2
1+?
? ?, µ.
Оператор P2? также монотонный:
(P2? (?)?P2? (µ), ??µ) = (?(rE +??? )?1 (??)+(rE +??? )?1 (?µ), ??µ) > 0
? ?, µ.
Далее, из неравенств
k(E + ??? )?1 (y) ? (E + ??? )?1 (z)k 6 ((E + ??? )?1 (y) ? (E + ??? )?1 (z), y ? z)1/2 ,
140
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
1
((rE+??? )?1 (y)?(rE+??? )?1 (z), y?z)1/2
r
следуют оценки сверху для операторов P1? и P2? :
k(rE+??? )?1 (y)?(rE+??? )?1 (z)k 6
(P1? (?) ? P1? (µ), ?) > (P1? (?) ? P1? (µ), ? ? µ)1/2 kL?k ? ?, µ, ?.
(P2? (?) ? P2? (µ), ?) 6
1
r1/2
(P2? (?) ? P2? (µ), ? ? µ)1/2 k?k 6
6
1
r1/2 µmin
(P2? (?) ? P2? (µ), ? ? µ)1/2 kL?k ? ?, µ, ?.
Объединяя оценки для P1 ? и P2 ? , получим
? u ? v 2 ,
(P? (u) ? P? (v), u ? v) >
1+?
(P? (u) ? P? (v), w) 6 ? 1/2 (P? (u) ? P? (v), u ? v)1/2 w,
1
. Для завершения доказательства достаточно воспользоваться
r1/2 µmin
утверждением 1.
где ? = 1 +
Как видно из оценок теорем 2 и 4, градиентный метод и метод Узавы для регуляризованных задач сравнимы по скорости сходимости (асимптотически по ? они
имеют одинаковую скорость сходимости). При этом в методе Узавы допустимый
интервал для итерационного параметра не зависит от ? , более того, теоретически
оптимальный параметр
r
?=
r + µ?2
min
также не зависит от ? . Поэтому ормальный переход к пределу при ? ? 0 дает теоретически ѕоптимальныйї итерационный параметр в методе Узавы для исходной
(нерегуляризованной) задачи. Численные эксперименты показывают, что численно
оптимальный параметр ? близок к указанному значению.
3.3.
Контроль точности и критерии остановки. Для контроля точности
итераций мы используем оценку нормы вектора невязки, определение которого в
случае решения включения с многозначным оператором, дано ниже.
При решении системы
Ax ? C T ? + ??(x) ? f,
Cx = 0
каким-либо итерационным методом, мы находим не только приближение (xk , ?k )
к точному решению (x, ?) , но и единственный вектор ? k ? ??(xk ) . Определим
компоненты вектора невязки равенствами
rxk = f ? Axk ? ? k + C T ?k ,
r?k = Cxk .
(35)
Тогда вектор погрешности (x ? xk , ? ? ?k )T удовлетворяет системе включений
k
x ? xk
r
A ?C T
??(x) ? ? k
+
? xk .
C
0
0
? ? ?k
r?
Умножив скалярно эту систему на вектор (x ? xk , ? ? ?k )T и воспользовавшись
неравенством (??(x) ? ??(xk ), x ? xk ) > 0 , получим
(A(x ? xk ), x ? xk ) 6 (rxk , x ? xk ) + (r?k , ? ? ?k ).
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
141
Пусть (Ax, x) > m kxk2 , тогда
mkx ? xk k2 6 krxk kkx ? xk k + kr?k k k? ? ?k k,
или
kx ? xk k 6 c1 krxk k + c2 k? ? ?k k1/2 kr?k k1/2
?k
(36)
с постоянными c1 , c2 , не зависящими от номера итерации k . Так как k? ? ?k k ? 0
при k ? ? , то k? ? ?k k 6 const , и неравенство (36) дает инормацию о погрешности kx ? xk k через оценку норм компонент невязки krxk k и kr?k k .
Пусть тройка векторов (y k , uk , ?k ) это k -я итерация градиентного метода (23).
При реализации этого метода векторы uk и ?k решения сеточного уравнения состояния и сеточного сопряженного уравнения соответственно находятся точно
(или по крайней мере с очень высокой точностью). Поэтому контролем точности
итераций выступает норма вектора невязки во включении для определения приближения к вектору управления u : ?uk = ruk + ?k + ?uk , где ?uk ? ??(uk ) вектор,
определенный на предыдущем итерационном шаге:
uk ? uk?1
+ ruk?1 + ?k?1 + ?uk = 0,
?
?uk ? ??(uk ).
Несложные вычисления дают следующее выражение для невязки:
1 k
?uk = r ?
(u ? uk?1 ) + ?k ? ?k?1 .
?
В качестве нормы берем в дальнейшем сеточный аналог L2 -нормы:
k?uk kL2 =
N
X
i=1
k 2
h2 (?ui
)
1/2
.
Отметим, что малость нормы вектора невязки характеризует близость итерации
метода (23) к решению регуляризованной задачи (15), которое, в свою очередь,
может достаточно существенно отличаться от решения исходной задачи (13) (см.
оценку (16)).
Пусть теперь тройка векторов (y k , uk , ?k ) есть k -я итерация метода (29). При
реализации этого метода решения двух включений на первом шаге описанного
выше алгоритма находятся точно. Поэтому в качестве контроля точности итераций
берется L2 -норма вектора невязки ??k = Ly k ? uk .
4.
езультаты численных экспериментов
Численные эксперименты были проведены для задачи с ункцией наблюдения
yd = 10(sin ?x1 + sin ?x2 ) и для разных весовых параметров r в целевой ункции.
Критерием остановки итераций были условия k?uk k2L2 < 10?5 и k??k k2L2 < 10?5 для
методов (23) и (29) соответственно.
В качестве начальных приближений в обоих методах выбирались нулевые векторы. Кроме того, были реализованы варианты итерационных методов, названные
двухсеточными. Именно, вначале проводились вычисления на сетке, в два раза более крупной, чем исходная. Затем полученные результаты интерполировались на
мелкую сетку и принимались в качестве начальных приближений. Этот прием позволил ускорить вычисления. Как показали численные эксперименты, использование последовательности трех и более сгущающихся сеток не приводят к заметному
ускорению сходимости.
142
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
Табл. 1
радиентный метод для регуляризованной задачи, r = 0.005, ? = 0.02
n
60
100
200
ешение на одной сетке
число итераций, время
946, 00:00:31
950, 00:02:31
951, 00:22:28
Двухсеточный метод
число итераций, время
1902, 00:00:26
1890, 00:01:49
1858, 00:13:48
Табл. 2
Метод Узавы, r = 0.005
n
60
100
200
ешение на одной сетке
число итераций, время
540, 00:00:09
901, 00:00:34
1868, 00:04:42
Двухсеточный метод
число итераций, время
815, 00:00:07
1339, 00:00:31
2748, 00:03:56
Табл. 3
радиентный метод для регуляризованной задачи, r = 0.01, ? = 0.02
n
60
100
200
ешение на одной сетке
число итераций, время
901, 00:00:30
901, 00:02:27
904, 00:20:46
Двухсеточный метод
число итераций, время
1851, 00:00:27
1829, 00:01:49
1801, 00:13:15
Табл. 4
Метод Узавы, r = 0.01
n
60
100
200
ешение на одной сетке
число итераций, время
955, 00:00:12
1615, 00:00:59
3411, 00:08:14
Двухсеточный метод
число итераций, время
1415, 00:00:09
2369, 00:00:42
4973, 00:05:28
Табл. 5
радиентный метод для регуляризованной задачи, r = 0.015, ? = 0.02
n
60
100
200
ешение на одной сетке
число итераций, время
868, 00:00:32
867, 00:02:31
869, 00:20:18
Двухсеточный метод
число итераций, время
1811, 00:00:28
1789, 00:01:48
1761, 00:12:59
Табл. 6
Метод Узавы, r = 0.015
n
60
100
200
ешение на одной сетке
число итераций, время
1373, 00:00:17
2328, 00:01:25
4947, 00:11:31
Двухсеточный метод
число итераций, время
2009, 00:00:10
3395, 00:00:49
7187, 00:06:59
ЕШЕНИЕ ОДНОЙ ЗАДАЧИ ОПТИМАЛЬНОО УПАВЛЕНИЯ. . .
143
езультаты вычислений с использованием градиентного метода приведены для
регуляризованной задачи с параметром регуляризации ? = 0.02 . Выбор меньшего
параметра регуляризации приводил к существенному увеличению числа итераций
и времени вычислений для достижения заданной точности.
Во всех тестовых расчетах метод Узавы оказался более эективным, чем градиентный метод для регуляризованной задачи. езультаты расчетов приведены
в табл. 16, в которых указаны общее количество итераций и время вычислений
в ормате чч:мм:сс, n число точек сетки в одном направлении.
абота выполнена при инансовой поддержке ФФИ (проект ќ 10-01-00629).
Summary
D.G. Zalyalov, A.V. Lapin. Numerial Solution of an Optimal Control Problem Governed
by a Linear Ellipti Equation with Non-Loal State Constraints.
An ellipti optimal ontrol problem with distributed ontrol, pointwise ontrol onstraints
and non-loal state onstraints has been onsidered. A mesh approximation of the problem
has been onstruted. The existene and uniqueness of the approximate solution have been
established, and the onvergene of the approximate solution to the exat one has been
proved. The onvergene of the two lasses of iterative methods of solving the onstruted
mesh optimal ontrol problem has been studied. The results of the numerial experiments
have been ompared. The dependene of the onvergene rate upon the mesh size and the
regularization parameter in the objetive funtional has been analyzed.
Key words:
iterative method.
linear ellipti equation, optimal ontrol, nite dierene approximation,
Литература
1.
Bergounioux M., Haddou V., Hintermuller M., Kunish K.
A omparison of a MoreauYosida-based ative set strategy and interior point methods for onstrained optimal
ontrol problems // SIAM J. Optim. 2000. V. 11, No 2. P. 495521.
2.
Bergounioux M., Kunish K.
3.
Troltzsh F., Pufert U., Weiser M.
Primal-dual ative set strategy for state-onstrained optimal
ontrol problems // Comput. Optim. Appl. 2002. V. 22, No 2. P. 193224.
The onvergene of an interior point method for an
ellipti ontrol problem with mixed ontrol-state onstraints // Comput. Optim. Appl. 2008. V. 39, No 2. P. 183218.
4.
Troltzsh F., Yousept I. A regularization method for the numerial solution of ellipti
boundary ontrol problems with pointwise state onstraints // Comput. Optim. Appl. 2009. V. 42, No 1. P. 4366.
5.
Moreau-Yosida regularization in state onstrained ellipti
ontrol problems: error estimates and parameter adjustment // SIAM J. Numer. Anal. 2009. V. 47, No 3. P. 16661683.
6.
Graser C., Kornhuber R.
Nonsmooth Newton methods for set-valued saddle point
problems // SIAM J. Numer. Anal. 2009. V. 47, No 2. P. 12511273.
Hintermuller M., Hinze M.
7.
Hinze M., Shiela A.
8.
илл Ф., Мюррей У., айт М.
9.
Disretization of interior point methods for state onstrained ellipti
optimal ontrol problems: Optimal error estimates and parameter adjustment // Comput.
Optim. Appl. 2011. V. 48, No 3. P. 581600.
Практическая оптимизация. М.: Мир, 1985. 509 с.
Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. М.: адио
и связь, 1987. 400 с.
144
10.
Д.. ЗАЛЯЛОВ, А.В. ЛАПИН
Васильев Ф.П.
Численные методы решения экстремальных задач. М: Наука, 1988. 549 с.
11.
Biegler L.T., Ghattas O., Heinkenshloss M., van Bloemen Waanders B.
12.
Laitinen E., Lapin A., Lapin S.
13.
Lapin A.
14.
Лапин А.В., Хасанов М..
15.
(eds.) Largesale PDE-onstrained optimization. Berlin: Springer-Verlag, 2003. 350 p.
On the iterative solution of nite-dimensional inlusions
with appliations to optimal ontrol problems // Comp. Methods Appl. Math. 2010. V. 10, No 3. P. 283301.
Preonditioned Uzawa type methods for nite-dimensional onstrained saddle
point problems // Lobahevskii J. Math. 2010. V. 31, No 4. P. 309322.
ешение задачи оптимального управления правой частью эллиптического уравнения при наличии ограничений на состояние // Учен.
зап. Казан. ун-та. Сер. Физ.-матем. науки. 2010. Т. 152, кн. 4. С. 5667.
Михайлов В.П.
Диеренциальные уравнения в частных производных. М.: Наука,
1976. 391 с.
16.
Экланд И., Темам .
Выпуклый анализ и вариационные проблемы. М.: Мир, 1979. 399 с.
Поступила в редакцию
15.05.12
Залялов Динар умарович аспирант каедры математической статистики Казанского (Приволжского) едерального университета.
E-mail: dinar1988mail.ru
Лапин Александр Васильевич доктор изико-математических наук, проессор
каедры математической статистики Казанского (Приволжского) едерального университета.
E-mail: Alexandr.Lapinksu.ru
1/--страниц
Пожаловаться на содержимое документа