Численные методы решения задач оптимального управления эллиптическим уравнением с ограничениями на состояние и управление тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

На правах рукописи

Хасанов Марат Гумярович

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

управление

Специальность 01.01.07 — вычислительная математика

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

31 ИЮЛ 2014

005550926

Работа выполнена на кафедре вычислительной математики ФГАОУ ВПО «Казанский (Приволжский) федеральный университет».

Научный руководитель:

доктор физико-математических наук, профессор Лапин Александр Васильевич

Официальные оппоненты: доктор технических наук,

профессор Хайруллин Мухамед Хильмиевич кандидат физико-математических наук, доцент Попов Анатолий Вадимович

Ведущая организация: Институт механики Уральского отделения РАН

Защита состоится 18 сентября 2014 г. в 1630 часов на заседании диссертационного совета Д 212.081.21 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при ФГАОУ ВПО «Казанский (Приволжский) федеральный университет» (420008, г. Казань, ул. Кремлёвская, 18, корпус 2, ауд. 218).

С диссертацией можно ознакомиться в научной библиотеке им. Н.И. Лобачевского ФГАОУ ВПО «Казанский (Приволжский) федеральный университет».

Автореферат разослан 20 июля 2014 года.

Ученый секретарь диссертационного совета

д.ф.-м.н., профессор 3аДвоРнов А-

Общая характеристика работы

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

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

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

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

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

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

В работах Deckelnick К., Hinze М., Hintermuller М., Arada N., Casas Е., Troltzsch F. [8], [13], [1] исследованы сеточные схемы для эллиптических задач оптимального управления с ограничениями на состояние. Используя результат работы Deckelnick К. и Hinze М. [8], можно установить сходимость сеточных решений к решениям дифференциальных задач для всех рассмотренных в диссертации задач оптимального управления. Мы не приводим соответствующие результаты, так как основной целью диссертационной работы является построение и исследование итерационных методов для сеточных задач, аппроксимирующих задачи оптимального управления в правой части линейного эллиптического уравнения или граничного условия.

Сеточные задачи оптимального управления в правой части линейного эллиптического уравнения или граничного условия при наличии простых ограничений лишь на вектор управления могут быть эффективно решены градиентным методом с проекцией. При наличии ограничений на вектор состояния этот метод непосредственно уже применить нельзя. В этом случае можно использовать различные методы регуляризации, в том числе и перечисленные выше. Другой подход к построению итерационных методов для сеточных задач оптимального управления основан на методе множителей Лагранжа. Он сводит исходную задачу к так называемой седловой задаче с ограничениями. Решение этих задач можно осуществлять обобщенными (предобусловленными) методами Узавы без предварительной регуляризации индикаторных функций множеств ограничений. Такой подход к построению итерационных методов является основным в диссертации. Он позволяет избежать проблемы выбора параметра регуляризации (штрафа). Кроме того, при решении задачи обобщенным методом Узавы мы с высокой точностью определяем "свободную границу"задачи (множества активных и пассивных ограничений на вектор узловых значений сеточной функции состояния).

Метод решения задач оптимального управления с ограничениями на управление с применением стратегии активного множества прямых и двойственных переменных был рассмотрен в работе М. Bergounioux, К. Kunish, К. Ito [6]. Итерационные методы для решения седловых задач большой размер-

4

ности с ограничениями предложены в работе С. Gracer, R. Kornhuber [18], в которой приведены численные результаты для задачи оптимального управления с ограничениями только на управление.

Также можно отметить подходы, связанные с использованием методов типа Ньютона для решения задачи оптимального управления с ограничениями на состояние и управление, только в этом случае необходимо на каждой итерации метода решать систему линейных уравнений с седловой матрицей. В работе Herzog R., Sachs Е. [12] для этой цели был предложен вариант предобусловленного метода сопряженных градиентов. Седло вые задачи возникают и при применении метода Ньютона и использовании регуляризации Моро-Иосиды для задачи оптимального управления с ограничениями на состояние. Выбор предобусловливателя для итерационного метода решения был рассмотрен в работе Stoll М., Pearson J., Wathen А [22]. Сравнение методов регуляризации Моро-Иосиды и Лаврентьева с методами решения сеточных аппроксимаций задач оптимального управления, например, методами внутренней точки и активных множеств, приведено в работе Hintermuller М., Kunisch К. [15]. Численные эксперименты, приведенные в этой работе показали, что методы Ньютона, примененные для задач регуляризации Моро-Иосиды, оказались менее эффективными, чем методы активных множеств. Что касается метода внутренней точки, то по количеству итераций наблюдалось его эквивалентность указанному методу регуляризации.

В работе M.Bergounioux, К. Kunish [7] использован метод расширенного лагранжиана для регуляризованой задачи оптимального управления с ограничениями как на состояние, так и на управление.

Для решения линейных уравнений эффективным инструментом являются многосеточные методы. Эти методы были обобщены и для задач оптимального управления с ограничениями на состояние. Существуют два варианта многосеточных методов для решения задач оптимального управления: MGOPT и CSMG [23]. Первый вариант подразумевает применение многосеточной техники решения задач оптимального управления непосредственно для решения системы оптимальности.Необходимо упомянуть, что эти два подхода многосеточной техники основаны на регуляризации Лаврентьева основной задачи. В работах Nash S. [20], Lewis R.M. [19] рассмотрено применение многосеточных методов для решения задач оптимизации без ограничений.

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

5

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

Суть метода активных множеств заключается в поиске области, где ограничения на переменные активны. На каждой итерации данного метода происходит решение задачи квадратичного программирования с ограничениями-равенств. Как отмечено в работе Wong Е. [24], данный метод эффективен при известном начальном приближении к решению. Поэтому его часто используют при решении задач нелинейного программирования методом последовательного квадратичного программирования, на каждом шаге которого необходимо решить задачу квадратичного программирования. В качестве начального приближения берется решение из предыдущего шага.

Метод внутренней точки реализован в пакетах Matlab, OOQP, Finmath. Основная сложность данного метода - это необходимость решения большой разреженной системы линейных алгебраических уравнений. Способ использования наименьшего объема памяти для этой цели был предложен в работе Gondzio J. [10]. Анализ сходимости методов внутренней точки для задач оптимального управления был проведен в работе Prüfer U., Trolzchy F. и Weiserz М. [21].

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

Научная новизна исследования заключается в том, что

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

• получены оценки близости решений исходной дискретной задачи оптимального управления и ее регуляризованного варианта;

• для построенных седловых задач предложены и исследованы различные варианты предобусловленного метода Узавы;

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

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

Апробация работы. Основные положения диссертации обсуждались на Всероссийских школах-конференциах "Лобачевские чтения", г. Казань, 2009г. и 2011г., Всероссийской конференции 'Туполевские чтения", г. Казань, 2011г., Всероссийской конференции "КВМ - 2011", г. Новосибирск, академгородок, 2011г., Межвузовской конференции "Математика и физика в системе инженерного образовани", 2011г., г. Нижнекамск, Всероссийской конференции "Сеточные методы для краевых задач и приложения", 2012г., г. Казань.

Практическая значимость Построенные и исследованные предобу-словленньге методы Узавы могут быть применены для решения задач оптимального управления.

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

Личный вклад. Автор принимал непосредственное участие в разработке второго и третьего вариантов метода Узавы, а так же доказательств их сходимости. Все программы для проведения вычислительного эксперимента и сами численные эксперименты были проведены автором.

Содержание работы

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

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

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

—Ау = / + и в П, у = 0 на сЮ. 7

Пусть, для определенности, Uad = {и 6 Ьг(^) : ^

1 при почти всех х 6 ÍI} и Ya¿ = {у 6 #¿(0) ' У(х) ^ ^ ПРИ почти всех х € Í2} - непустые, выпуклые и замкнутые множества ограничений на функции управления и и состояния у, соответственно. Зададим целевой функционал

J(V, u) = \j y2dx + \j u2dx■ (2)

í) fi

Задачу оптимального управления определим следующим образом:

min J(y,u), Мек " (3)

К = {(у, и) G Yod х Uad '■ выполнено уравнение состояния (1)}

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

'-Ay = f в fi,

у = 0 на Гд (4)

ду

— = и на Гдг коп

Пусть

J(y,u) = ±j(^-qdydr + r-ju2dx, (5)

Гоь Tn

где qd & ¿г(Г) - заданная функция, Г/v и Г0(, строго отделены друг от друга, т.е. р{FN, Гоь) > 0.

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

Теорема 1 Пусть Ya<¡, Uad ~ выпуклые замкнутые множества, тогда задача оптимального управления с наблюдением в подобласти

min J(y,u),

(у,и)€К (g)

К = {(у, и) : у € Yad,u £ Uad и выполнено (1) или (4)}, имеет единственное решение, если К ф 0.

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

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

ьтт+/ (\\\МуУГ + ^\\Мии\\2 + %) + *,(«)). (7)

Здесь у и и - векторы узловых параметров сеточных функций состояния и управления, Ь - матрица сеточного оператора Лапласа, функции О и р - это индикаторные функции множеств ограничений на у и и, Ь - положительно определенная матрица, N - прямоугольная в общем случае матрица, Ми и М - диагональные положительно определенные матрицы, Му - диагональная положительно полуопределенная матрица. Отметим, что ограничения на векторы у и и имеют вид у,- > О V! и \щ\ ^ 1 Уг, поэтому функции в и <р> -сепарабельные. Определим функцию Лагранжа для задачи (7):

С(у, и, А) = \\\Муу\\2 + ±||и||2 + %) + ф) + (Л, Ьу-Ни- /). Ее седловая точка является решением системы

(му 0 L \ (у\ (Щу)\

0 мп г + ду(и) э 0

к L -N 0) W \ ° ) V f

где дв и dip - субдифференциалы функций 0 и (р, соответственно. 80 и dtp являются максимально монотонными (многозначными) операторами. Важно отметить, что они имеют диагональную форму в силу сепарабельности функций в и (р.

В четвертом параграфе доказана теорема о существовании решения задачи включения с седловой матрицей.

Теорема 2 Пусть выполнены следующие условия:

■ф : R" —» R — собственная, выпуклая и полунепрерывная снизу функция,

матрица В € Msxn, s ^ п, имеет полный ранг: rank В = s,

D П int dom -ф ф 0, D = {х € R" : Вх = д}, 9

матрица А положительно полуопределена на всем пространстве К" и положительно определена на ядре матрицы В:

САх,х) ^ О Ухе Мп, (Ах,х) ^ т||х||2 Ух € КетВ, тп > О.

Тогда задача

О

(10)

А -Вт к-в О )

имеет решение (х*,Л*), и его первая компонентах* определяется од позначно.

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

/у\ (дО(у)\

+ I д<р(и) I э

У и

О О

\-MfJ

(11)

где дв(у), д(р(и) - субдифференциалы индикаторных функций множеств ограничений на состояние и управление, соответственно.

Если матрица Му вырождена, то вектор у нельзя выразить через Л из первого включения в (11), поэтому нельзя применить для решения (11) метод Узавы. С другой стороны, из первого включения в (11) нельзя выразить и А, так как оно содержит многозначный оператор дв. В связи с этим ниже рассматриваются два вида преобразования седловой задачи (11). Первый из них — эквивалентное, позволяющее получить седловую задачу, к которой можно применить метод Узавы. Второе состоит в замене недиференцируемой функции в регуляризованной дифференцируемой функцией. Фактически — это метод штрафа. Получена оценка близости решений исходной и регуляризованной задач.

Проведем эквиваленирные преобразования (11). Первое эквивалентное преобразование получим, прибавив к первой строке третью, умноженную на -аМЬ'\

(Му + аМ -аМЬ~1 О

-Ь

(Щу)\

+ I Э

Второе эквивалентное преобразование получим прибавив к первой строке третью, умноженную на —а. Получим эквивалентную (11) задачу

(My + aL -aN

\

О

-L

у\ (Щу)\

и + dtp(u) Э

N V 0 )

(13)

Наконец, третье эквивалентное преобразование получим также прибавив к первой строке третью, умноженную на —аЬ. Получим эквивалентную (11) задачу

Л

'My + aL2 -aLN -L

О

+

(Щу)\

ду{и) Э 0 )

/—aLM О

V -м/

(14)

В конце первой главы приводится результат об оценке погрешности решения системы с регуляризацией Моро-Иосида. Применение метода регуляризации Моро-Иосиды к задаче (3) означает, по существу, применение метода штрафа. Именно, ограничения на функцию состояния включаются в целевой функционал в виде штрафного слагаемого:

МУ, = У2(1х + \! и2(1х + Те ! (у~}2<1х-п п п

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

min JE(y, и), {у,и)ек„

(15)

К0 = {{у, и) G Щ(П) х Uaj : выполнено уравнение состояния (1)}.

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

min J£(y,u) (у,и)ек0

где Му,и) = Je(y,u) + 1-J((u- 1 )+)2dx + ^J((U+ l)~fdx,

Я f!

Ко = {(у,и) 6 Hq(Q.) х ¿2(П) : выполнено уравнение состояния (1)}.

(16)

Метод регуляризация Лаврентьева можно применить к задаче (3) в частном случае, когда отсутствуют ограничения на функцию управления (существенным является, также, тот факт, что управление и - распределенное в области Г2). Ограничения на состояние у(х) ¡2 0 Vx € П заменяется "смешанным ограничением" у(х) +еи(х) > 0 Vre € П с малым параметром е > 0.

11

Введем вспомогательную функцию ги = у + ей, тогда задача состояния примет вид

Регуляризованная по методу Лаврентьева задача - это задача с ограничением только на новую функцию управления го:

К\ = {(y,w) € Hq(Q) х Yod : выполнено уравнение состояния (17)}.

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

При е —» 0 решения регуляризованных задач стремятся к решению исходной задачи оптимального управления. В ряде случаев получены оценки скорости сходимости в зависимости от £. В том числе, в диссертации получены оценки близости решений сеточных исходной и регуляризованной задач. Из этих оценок можно сделать вывод, что при отсутствии регулярности у множителей Лагранжа для исходной задачи приходится выбирать очень малые е > 0, чтобы решение регуляризованной задачи было близко к решению исходной задачи. В свою очередь, при малых £ задача становится "плохо обусловленной", что приводит к медленной сходимости итерационных методов.

Пусть для определенности Yac¡ = Ya¿ = {у € : у{х) ^ 0 Vx € ÍÍ}

и индикаторная функция д(у) = Iyad{y) множества Yat¡ аппроксимирована дифференцируемой функцией

(17)

(18)

где у — вектор с координатами у1 .

Таким образом из задачи (11) мы получим систему:

Ч70е(уе)\ ( g дч>Ы Э О | . (20)

0 ) \-Mfj

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

Лемма 1 Пусть (у,и,Х) — решение (11) и {уе,Щ, К) ~~ решение (20), I = {i : y€i < 0 и 7y¿ < 0}. Тогда справедлива оценка

(Му(Уе -у),уе-у) + (Ми(и£ -и),и£-и)< (21)

Вторая глава содержит описания итерационных методов решения задач оптимального управления: методы Эрроу-Гурвица, Дугласа-Рэкфорда, последовательной верхней релаксации (SOR), предобусловленный метод Уза-вы, метод штрафа (регуляризации), двусеточный метод, двухступенчатый метод решения включения относительно у с предобусловливателем L и неполным обращением оператора — L + дв, где дО - субдифференциал индикатор-

т

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

Обратимся снова к модельной задаче (3) для более детального описания упомянутых выше методов.

При отсутствии ограничений на состояния (дв = 0) седловая задача (8) принимает вид

( ° ^

3 0 ,

\Mf)

Ее можно разрешить относительно и, получив включение

Мии + NTL-lMyL~lNu + ду(и) Э -NTЬ~1МУЬ~1М/.

Рассмотрим частный случай Ми = Е, тогда матрица Ми + NTL^MyL^N спектрально эквивалентна единичной матрице Е: Е ^ Ми + L~2 < сЕ, с = 1 + Aminí-Í')-2 ^ cj, с постоянной Ci, не зависящей от размерности пространства (иными словами, от параметра сетки К). Благодаря этому метод простой итерации fc+l к

--— + Muuk + NTL-1MyL-1Nuk + d<p(uk+l) Э —NTL~lMyL~lMf (22)

т 13

сходится со скоростью, не зависящей от К. Реализация одного шага метода (22) сводится к двукратному обращению Ь и простой операции покоординатного проектирования на множество ограничений для и. Отметим, что метод (22) совпадает с методом градиентного спуска с проекцией для задачи минимизации (7).

Пусть теперь присутствуют ограничения на вектор состояния: у,; ^ О \/г. Аппроксимируем индикаторную функцию этого множества в дифференцируемой функцией в£ = — Соответствующая седловая задача примет вид '

<Е О Ь \ (у\ (Чве(у)\ О Е -Е и + д<р(и) КЬ -Е О )\Х) \ 0 )

Разрешив эту систему относительно и, получим включение

Мии + ЫТЬ~1 о (Е + У0£) о ХГ^ЛГи + М/) + д(р(и) Э 0.

Метод простой итерации для этой задачи принимает вид: к+1 к

и ~и +Миик + ^Ь~1о(Е + \'вЕ)оЬ-1(Мик + М/)+д<р(ик+1)эО. (23)

Трудоемкость его реализации такова же, что и в случае отсутствия ограничений на у. Оператор Р(и) = и + Ь-1 о (Е + Ч9е) о Ь~1{и + М/) - строго монотонный: (Р(и) — Р(у),и — ь) ^ ||м — «||2 и липшиц-непрерывный. Однако константа его липшиц-непрерывности существенно зависит от е:

\\Р(и)-Р(у)\\^-£\\и-ь\\,

поэтому метод (23) при оптимальном итерационном параметре г сходится со скоростью, линейно зависящей от е.

Вернемся к исходной седловой задаче (13). Разрешим ее относительно вектора А:

-Ь о (Му + дв)~1 о (-£)(А) + Ы{Ми + ду)-\\) э -М/

и применим предобусловленный метод простой итерации для решения полученного включения: _ \к

ь2----Ьо(Му + де)-1о(-Ь)(\к) + М{Ми + ду)-1{\к) Э -М/. (24)

Метод (24) - это обобщенный метод Узавы решения задачи (13). Его сходимость следует из общих результатов диссертации. Трудоемкость реализации

14

(24) такова же, что и градиентных методов (22) и (23): на каждой итерации требуется два обращения матрицы L и "дешевые" операции покоординатного проектирования на множества ограничений для у и и. В данной главе также доказывается сходимость данного метода при параметре т не зависящем от шага сетки.

Отметим, также, что в случае отсутствия ограничений на у (в = 0) этот метод сходится со скоростью, не зависящей от Л, а в случае регуляризации функции в его скорость сходимости асимптотически по е такая же, что и у градиентного метода (23).

Применение обобщенного метода Узавы возможно лишь в случае, когда соответствующая сеточная седловая задача может быть разрешена относительно вектора А. При решении задач с наблюдением в подобласти области Í1 эта задача имеет вид

(му о ь\( у\ (дв{у)\ ( о\

О Ми -NT и + д<р{и) Э 0 , (25)

\L -N 0 ) \Х) V 0 / W/

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

Рассмотрим еще частный случай задачи, когда нет ограничений на вектор управления и и N = Е. В этом случае седловая задача может быть преобразована к включению

МуУ + LMuLy + дв{у) Э LMuMf. (26)

По существу, эта задача соответствует сеточной аппроксимации вариационного неравенства с дифференциальным оператором 4-ого порядка, для решения которой можно применить известные методы, например, методы расщепления, SOR-метод и др. Заметим, однако, что матрица Му + L2 имеет обусловленность порядка /г-4, поэтому скорость сходимости этих методов будет невысокой. В настояящей диссертационной работе для решения данных задач были предложены 2 метода: двуступенчатый метод с предобусловливателем L и двусеточный метод.

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

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

~Огьмиь+му + и?ШиЬ+ум + 7*+1 = ^ - ОгШиЬ+МуУк-—итьмиь+муУк + ЬМ/ + д,7к+1 € 8в{ук+х).

Методы расщепления (Дугласа-Рэкфорда) состоит из двух шагов: 1. Решаем систему из включений и линейных алгебраических уравне-

+ МуУк + ЬтХк + ^ = д, ^ е дв(у^),

икЦ~ик + гМиик + = е

,т

--Ьук + Ыик + М/ = 0.

2. Решаем систему линейных алгебраических уравнений:

,.к+1 _ ..к \

/ ук+1 _ ук+\ \ / Му 0 Ьт \ ( у

ик+1 _ ик+1 I + т \ А*+1 -

0 гМи -1ЧТ ик+1-ик N 0 ) \ А*+1 - \к

0.

В двухступенчатом методе на каждой итерации с предобусловливате-лем Ь осуществляется точное, либо приближенное решение включения к+1 _ к

Ьу т У + дв(ук+1) Э ЬМиМ/ + МуУл - ЬМиЬук - Муук.

Оказалось, для его сходимости можно не полностью обращать нелинейный

оператор —Ь 4- 89, вследсвтии чего наблюдалась его эффективность по от-т

ношению других "классических"методов, например, метод верхней релаксации, Дугласа-Рэкфорда и др. В численных экспериментах для частичного решения указанного выше вариационного неравенства на каждой итерации применялся метод последовательной верхней ралаксации(БОК метод).

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

16

и, наконец, последний этап есть "конечная сглаживающая"итерация Гаусса-Зейделя на исходной мелкой сетке.

Численный эксперимент показал эффективность двуступенчатового и двусеточного методов по сравнению с классическими методами, например, SOR, Дуглас-Рэкфорда и градиентного метода для решения регуляризиро-ванной системы.

Третья глава содержит численные результаты решения задач оптимального управления методами, описанными во второй главе, среди которых содержаться новые методы, предложенные в данной диссертационной работе. Как уже упоминалось выше, численный эксперимент показал, что двусту-пенчатый метод с предобусловливателем L и двусеточный метод оказались эффективнее "классических"методов, например, Дугласа-Рэкорда, последовательной верхней релаксации, регуляризации для сетки с количеством узлов равным 100 по одному направлению.

Для сравнения эффективности предложенных в данной диссертационной работе методов, например, вариантов предобусловленного метода Узавы с другими методами, допустим, методами внутренней точки, использовались пакеты Matlab, finmath, OOQP, Laspack. Метод внутренней точки дал искомый результат за меньшее количество времени, чем варианты метода Узавы. Но необходимо заметить, что эффективность итерационного метода, который содержит подзадачи, зависит от эффективности разрешений этих задач. Например, в предлагаемом методе Узавы, который основан на преобразовании седловой задачи с ограничениями, необходимо решать задачу квадратичного программирования с положительно опеределенной матрицей с простыми ограничениями, а в методе внутренней точки систему Каруша-Куна-Таккера, что есть система линейных алгебраических уравнений с большой разреженной матрицей. В случае, если получится ускорить решение задачи квадратичного программирования с простыми ограничениями, то возможно, что предлагаемый вариант метода Узавы для решения задачи оптимального управления будет затрачивать сравнимое или меньшее время, чем метод внутренней точки. Для достижения необходимой точности метод Узавы затратил 40 итераций, что является вполне приемлемым количеством итераций. В качестве метода решения задачи квадратичного программирования с матрицей L2+My и простыми ограничениями использовался метод внутренней точки.

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

бусловленный метод Узавы, его первый и второй вариант имеют одинаковую алгоритмическую сложность, которая состоит в решение системы алгебраических уравнений и вариационного неравенства с матрицей обусловленностью 0(h~2), поэтому трудоемкость этих методов равна 0(h~2). Предложенный новый вариант предобусловленного метода Узавы содержит решение вариационного неравенства с матрицей обусловленностью 0(Л-4), поэтому имеет такую же алгоритмическую сложность. Несмотря на то, что последний вариант метода Узавы имеет столь большую трудоемкость, он оказался эффективнее остальных вариантов метода Узавы и градиентного метода для решения ре-гуляризированной системы. Вариационное неравенство, которое необходимо решать на каждой итерации третьего варианта метода Узавы, явяется частным случаем задачи квадратичного программирования с простыми ограничениями, для которого метод внутренней точки является эффективным. В силу большой размерности задач для реализации методов использовались пакеты Laspack при работе с разряженными матрицами и решения систем линейных алгебраических уравнений, метод внутренней точки был использован с помощью пакета OOQP на интерфейсе языка С и С++.

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

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

2. Варианты предобусловленного метода Узавы для решения задачи оптимального управления с ограничением на состояние и управление

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

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

Публикации автора по теме диссертации

В рецензируемых изданиях из списка ВАК

1. Лапин A.B., Хасанов М.Г. Решение задачи оптимального управления правой частью эллиптического уравнения при наличии ограничений на состояние // Ученые записки Казанского университета, серия физ.-мат.

наук,- 2010. - т. 152, книга 4. - С. 40-56.

2. Хасанов М.Г. Сравнительный анализ методов решения одной задачи оптимального управления // Ученые записки Казанского университета, серия физ.-мат. наук - 2011. - т. 153, книга 4. - С. 49-58.

В других изданиях

1. Хасанов М. Г. Численное решение задач оптимального управления с наблюдением не во всей области. // Тезисы X молодежной школы-конференции "Лобачевские чтения-2011" — Казань: КФУ, 2011.

2. Хасанов М. Г. Численное тестирование сеточных схем для решения задач оптимального управления при наличие ограничений на состояние. // Тезисы VIII молодежной школы-конференции "Лобачевские чтения-2009"

- Казань: КФУ, 2009. - С.381.

3. Хасанов М. Г. Численное решение задачи оптимального управления при наличие ограничений на состояние. // Материалы межвузовской конференции посвященной 45 летию г. Нижнекамска — Нижнекамск: НХТИ, 2011. - С.51.

Список литературы

[1] Arada N., Casas Е., Troltzsch F. Error estimates for the numerical approximation of a semilinear elliptic control problem. // Comput. Optim. Appl.- 2002,- V. 23, №2- P. 201 - 229.

[2] Benedix 0. Adaptive Numerical Solution of State Constrained Optimal Control Problems // PhD, Munchen, 2011.

[3] Bergounioux M. Augmented Lagrangian method for distributed optimal control problems with state constraints// Optimization Theory Appl. - 1993.

- V. 78. №3.- P.493-521.

[4] Bergounioux M., Haddou V., Hintermuller M., Kunisch K. A comparison of a Moreau-Yosida-based active set strategy and interior point methods for constrained optimal control problems // SIAM J. Optim. - V. 11,- №2. -2000 - P. 495-521.

[5] Bergounioux M., Kunisch K. Primal-dual active set strategy for state-constrained optimal control problems // Comput. Optim. Appl. - 2002. -V. 22,- №.2. - P. 193-224.

[6] Dergouniuox M., Ito K., Kunisch K. Primal-dual strategy for constrained optimal control problems.// SIAM J. Control Optim. V. - 1999. - V. 37-№. 4. - P. 1176-1194.

[7] Bergouniuox M., Kunisch K. Augmented lagrangian techniques for elliptic state constrained optimal control problems.// SIAM J. Control Optim. -1997. - V. 35.- №. 5. - P. 1524-1543.

[8] Deckelnick K., Hinze M. Numerical analysis of a control and state constrained elliptic control problem with piecewise constant control approximations//Proceedings of ENUMATH 2007, the 7th European Conference on Numerical Mathematics and Advanced Applications, Graz, Austria, September 2007. - P. 597-604.

[9] Ekeland I., Temam R. Convex analysis and variational problems, North Holland, Amsterdam, 1976.

[10] Gondzio J. Matrix-Free Interior Point Method//Comput. Optim. Appl. -2012. - V. 51. -№. 2. - P. 457-480.

[11] Gugat M. Lavrentiev-prox-regularization for optimal control of PDEs with state constraints//Comput. Appl. Math - 2009 - V.28.-№.2.

[12] Herzog R., Sachs E. Preconditioned congugate gradient method for optimal control problems with control and state constraints//SIAM Journal on Matrix Analysis and Applications- 2009 - V. 31. - №2. - P. 2291-2317.

[13] Hintermuller M., Hinze M. Moreau-Yosida regularization in state constrained elliptic control problems: error estimates and parameter adjustment.// SIAM J. Numer. Anal - 2009.- V. 47.-№3. - P. 1666-1683.

[14] Hintermuller M. Yousept I. A sensitivity-based extrapolation technique for the numerical solution of state-constrained optimal control problems.// ESAIM,Control Optim. CalC.- 2010. - V. 16.-№3. - P. 503-522.

[15] Hintermuller M., Kunisch K. Stationary optimal control problems with pointwise state constraints//Lecture Notes in Computational Science and Engineering, 2009.

[16] Hinze M., Schiela A. Discretization of interior point methods for state constrained elliptic optimal control problems: Optimal error estimates and parameter adjustment// Comput. Optim. Appl. - 2011. - V. 48 - №3. -P. 581-600.

[17] Ito K., Kunisch K. Semi-smooth Newton methods for state-constrained optimal control problems // Syst. Control Lett. - 2003. - V. 50 - №3. -P. 221-228.

[18] C. Gracer, R. Kornhuber Nonsmooth Newton methods for set-valued saddle point problems.// SIAM J. numer. anal. - 2009. - V. 47. - №2. - P.1251-1273.

[19] Lewis R.M., Nasch S. Model problems for the multigrid optimization of systems governed by differential equations// SIAM J. Sc. Comp. -2005-№26.- P. 1811 - 1837.

[20] Nash S. A multigrid approach to discretized optimization problems, Optimization Methods and Software.- 2000. №14. - P. 99 - 116.

[21] Prüfer U., Trolzchy F., Weiserz M. The convergence of an interior point method for an elliptic control problem with mixed control state constraints//Comp. Opt. and Appl-2008. -V. 39. -№2. -P. 183-218.

[22] Stoll M. , Pearson J., Wathen A. Preconditioners for state constrained optimal control problems with Moreau-Yosida penalty function//Numerical Linear Algebra with Applications. - 2014. - V. 21. - P. 81-97.

[23] Vallejos M. Multigrid Methods for Elliptic Optimal Control Problems with Pointwise State Constraints//Numer. Math. Theor. Meth. Appl - 2012 - V. 5,- №1. - P. 99-109.

[24] Wong E.Active-Set Methods for Quadratic Programming//PhD Mathematics, 2011, University of California, San Diego.

Подписано в печать 20.06.2014. Бумага офсетная. Печать цифровая. Формат 60x84 1/16. Гарнитура «Times New Roman». Тираж 90 экз. Заказ 117/6.

Отпечатано с готового оригинал-макета в типографии Издательства Казанского университета

420008, г. Казань, ул. Профессора Нужина, 1/37 тел. (843) 233-73-59, 233-73-28