Оптимизационный подход к решению вариационных неравенств тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I. О РЕШЕНИИ ЭЛЛИПТИЧЕСКИХ ВАШАЩСЗННЫХ

НЕРАВЕНСТВ В УСЛОВИЯХ СЛАБОЙ КОЭРЩШВНОСТИ

§ I. Характеристика минимизирующих последовательностей в задаче Синьорини.

§ 2. Построение минимизирующей последовательности

§ 3. Устойчивость вспомогательных задач.

ГЛАВА 2. О ЧИСЛЕННОМ РЕШЕНИИ ЭЛЛИПТИЧЕСКИХ

ВАШАЩОННЫХ НЕРАВЕНСТВ.

§ I. Необходимые сведения о внешних аппроксимациях

§ 2. Метод поточечной релаксации.

§ 3. О скорости сходимости метода поточечной релаксации в задаче упругопластического кручения цилиндрического стержня.

ГЛАВА 3. МОДШЩРОВАННЫЙ МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

§ I. Некоторые сведения о методе возможных направлений

§ 2. Метод возможных направлений с отбрасыванием ограничений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЩОННОЙ РАБОТЫ.

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

Пусть - открытая область с кусочно-гладкой гранигильбертово пространство, билинейная форма непрерывна на

УхУ . Требуется найти минимум квадратичного функционала

SL на некотором замкнутом выпуклом множестве }C<Z?\fРешение вариационной задачи существует, если функционал ^ выпуклый и удовлетворяет условию нестрогой (слабой) коэрцитивности

2J: p(U)-нос при Ilully-UeX ,

Методы решения таких задач в последнее время интенсивно развиваются, причем особый вклад внесен математиками школы ЖгЛ.Лион-са. Решение LL экстремальной задачи р(и)-пгщ ! иеХ. характеризуется условием

•4-<t>(U*+*(U-U*l) >0 для любого иеТС Я* oL-0 т.е. задача (0.1) эквивалентна решению вариационного неравенства

0.1) для любого UeJC где Uu)=ifUzfSL. ) л

В предположении, что квадратичная форма CC(U,U) строго коэрцитивна, т.е. при некотором jf > О для всех U€~\T справедливо неравенство , вариационная задача (0.1) имеет единственное решение и любая минимизирующая последовательность {ИП} сходится в норме пространства V к этому решению fz] . При более слабых предположениях эти вопросы требуют дополнительных исследований.

В первой главе диссертации рассматривается задача об установившемся движении жидкости в области, ограниченной полупроницаемой мембраной: JW=k\m\x-ljU.)t(lL-min! (0.2)

SL ueK={ir<i\Ni(SL): rr>f п.б. на Г}

Здесь - ограниченная область с достаточно регулярной границей Г ^ f€Lz(SL) » LZ(D - заданные функции, f U. - след функции Щ € на Г

При естественном предположении, что Jfi^SL < 0 решение

SL задачи (0.2) существует и единственно, причем

Т(и)-> + при ll^ll -»и tJC.

Однако функционал в (0.2) не является строго коэрцитивным на множестве . По этой причине утверждение о сильной сходимости в V\£L(Sl) минимизирующей последовательности (lC"J к решению Ц* требует обоснования. Известные результаты

Ш . /29] сводятся к установлению слабой сходимости [UH] % к искомому решению U и легко проверяемого соотношения im l!iru"-vu*lll .

L2(SL)

В § I, б предположении, что на области SI Для функций иещй) справедливо неравенство Пуанкаре

Л SL л А>0 и В>0 - постоянные, не зависящие от U. ), доказывается два утверждения.

ТЕОРЕМА I.I. Для любой минимизирующей последовательности имеет место

Ьт IIU"-U*IL=0 . схо Щ (SI)

Приведенная характеристика минимизирующих последовательностей установлена совместно с научным руководителем А.А.Капланом.

ТЕОРЕМА 1.2. Для последовательности [2И] > определяемой условиями а^щтм (КФф-г"-^ } (^>о-соМ{) г

IIК -л«бое); Z £ * ~ справедливо

•йт II2*-и*II =0 .

Щ(SL)

Как нетрудно заметить, регуляризирующая добавка оL \{Ur^h Mit(SL) обеспечивает строгую коэрцитивность в Wi^Q) функционалов в экстремальных задачах, рассматриваемых в теореме 1.2. Далее предполагается, что Sl^K .

Для построения последовательности {г**} предлагается использовать метод конечных элементов на последовательности нерегулярных сеток с условием iim^-O ( - шаг сетки)

Обозначим

- фиксированное разбиение области Q на треугольники Т (с использованием криволинейных элементов у границы области), . удовлетворяющие стандартным условиям триангуляций ( [ю] , стр, 115);

Ni - шожество узлов ^ /;

Vj> - линейная оболочка соответствующих кусочно-аффинных базисных функций; Ре/%}

Последовательность fU^ } (т.е. ) определяется из условий tft =г агапгт {Т(иЫЦи-й£ Цг ]

-к iic -i£\\ <L где ^ - произвольный элемент из К. , £uz0 , t(m Ёи — О . Можно проверить, что в предлагаемом методе обеспечивается хорошая обусловленность гессианов минимизируемых функционалов в соответствующих конечномерных экстремальных задачах. В § 2 показано, что если (2 - многоугольник, - выпукла на каждой из сторон L и последовательность триангуляций [^j удовлетворяет условиям ъО

UT-fl, М тс <х=> при всех h. , то

Щ Vt > lm\\L-u.*\\ =<9 .

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

В § 3 исследована устойчивость этих задач по отношению к малым возмущениям J- и У . Пусть / и такие, что f/Ш, IIKII,^, nun, lf-т п.в. на Г.

Доказано, что решение iC(fi) возмущенной задачи

Мг-2^и*ф-Г1П ИI-torn на Г} при -0 сходится в (теорема 1.4). иск. 1

При конечноэлементной или разностной аппроксимации некоторых вариационных неравенств возникают экстремальные задачи специальной структуры. В § I главы 2 на примере задачи об упругопластическом кручении цилиндрического стержня [z] , [8] = л Л

-.} (ГСг/)

- расстояние от точки 2 ДО границы области J2. »

1 С R ) рассматривается конечномерная аппроксимация, приводящая к задаче квадратичного программирования следующего вида:

Г(х)=т<Ах>+<р>*>-! хеК

А/ ^ где , /Ы , </U,X>>0 для ХФО,

А Л/

ТС=ПК. /=1,Л/ могут быть неограниченными).

Заметим, что аппроксимация и некоторых других вариационных неравенств (например, задача о препятствии) приводит к (0.3). Это объясняется тем, что конструкция множества в ряде важных вариационных неравенств является относительно несложной.

Минимизируемые функционалы в (0.3) подобны соответствующим функционалам, получаемым при аппроксимации линейных краевых задач математической физики. Зто обстоятельство делает привлекательным использование для решения задачи (0.3) итерационных методов, учитывающих специальную структуру матрицы /\ . В главе 2 изучается метод поточечной релаксации для решения задачи квадратичного программирования (0.3).

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

И =

1) задаемся начальным вектором X \

2) определяем X; как решение неравенства

ТАЛ* Vй ^М ✓ TV Mtt л*"- л

3) полагаем Р ((1-Ш)Х*+со х"*'Л) , где Р (•)

Jv| "Ту- ■^•J

- оператор проектирования на Д. , а СО - параметр релаксации.

Известно /"2J , что при 0<tO ^Z алгоритм сходится к элементу X*€jV > минимизирующему функционал X на А

Х^ • В § 2 устанавливаются оценки скорости сходимости в предположении, что /4 - симметрическая, положительно определенная матрица общего вида.

Пусть Е ~ множество индексов, соответствующих нулевым компонентам вектора и Хр вектора, полученные в результате исключения из X компонент, индексы которых принадлежат соответственно множествам Р и Е . Имеет место[27]

ЛЕММА 2.1. Пусть Q< СО < Z . Тогда существует номер ХА , начиная с которого в методе поточечной релаксации V1 * < • - — Хр .

Из леммы 2.1, в частности, следует, что в задаче об упругопластическом кручении стержня за конечное число шагов будут найдены компоненты решения, соответствующие области пластичности.

Для матрицы {\ через обозначим подматрицу Д соответствующую множеству

Е , т.е. Ae~(4ij), Ue£ .

Очевидно, что R , где $) - диагональная матрица, L - левая треугольная, L . Аналогично + Re . При естественном предположении о том, что /7JC • » нетрудно установить, что, начиная с

Е ieE lr Т • г некоторого номера / ^ / , для всех I € Ь выполняются соотношения хър^а-ш^+юхгь^а-^хг+шх*-* .

Полагая в дальнейшем Ц Iz , рассмотрим функционал

Алгоритм поточечной релаксации при /I Zможно рассматривать как обычный метод релаксации (см. /~19] ) для решения системы Ае • Матрица перехода в методе релаксации имеет вид

TfaHQ+vLif [(*■-*)(o<cv<z).

A.M.Островским для случая СО—1 была получена оценка спектрального радиуса М (TW) матрицы ~J~(l) (см. [3l/) i F 171 £ - наименьшее собственное число матрицы /\ , # При СО < Z аналогичным путем уста /6 jb. навливается

7, "tTf £

I ll(i-&)wt

В § 2 доказано, что в действительности имеет место строгое неравенство

1 (ти < ^ из которого, используя свойства спектрального радиуса, следует соотношение ( /14J , стр. 15)

Однако на указанном пути не удается получить эффективную оценку постоянной С . Вместе с тем, анализ релаксационного процесса, проведенный в § 2, позволяет установить оценку

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

Пусть О < СО < 4- • Тогда, используя специфику задачи, легко доказать следующее утверждение: для того, чтобы процесс

0 4 Z. релаксации был неубывающим, т.е. Х^Х , достаточно, о i. чтобы X йХ . Утверждение справедливо, например, если х°~о.

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

ТЕОРЕМА 2.1. Имеет место где • • • > c-ff®. r-it ц, . Cm

1((1-&Ш1Г

X^aiftnLn J(X) ? M - наименьшее собственное число матрицы /\

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

-f(x) -шк ! xeSL=£:фт > со.4) где f- ^ ~ выпуклые дифференцируемые на функции.

В процессе реализации различных схем метода возможных направлений на каждом шаге в соответствующей точке допустимой области определяется направление убывания минимизируемой функции, по которому возможен сдвиг, не выводящий из допустимой области.На выбранном направлении находится новая допустимая точка с меньшим значением целевой функции, являющаяся исходной для следующего шага. Из многочисленных работ, посвященных методу возможных направлений, следует особо выделить исследования Г.Зойтендейка [i\] , который рассмотрел указанный метод в достаточно общем виде и предложил различные подходы его реализации, а также [ъ] , /хзJ , [l5] .

Такое направление назовем возможным.

В § I приведены необходимые сведения о методе возможных направлений. В § 2 рассматривается модификация указанного метода, связанная с уменьшением числа ограничений во вспомогательной задаче поиска подходящего направления сдвига. Предполагается, что множество решений задачи (0.4) ограничено и выполнено условие Слейтера: существует точка X » такая, что ^(х

Пусть к началу итерационного процесса имеется некоторая точка Х°€ „(2 и число JO> J • Алгоритм состоит в следующем. Полагая известными последовательности чисел ft € JO, 1J , где litfif^O и Д.- > 0 с iftV^tfij—O на ( K+l )-OM шаге решаем следующую задачу

J-*oo

Vf(X%S>£-6 t,-ivax!

Здесь s*- означает скалярное произведение векторов;

T(x")=(j ■?(х*)=0] ■ шиит) ■ $ - аффинная функция } ;

Т,ФШ)\Шит :<v/(xl WxfrXl-u,)|lv/Mltllv?WII хотя бы для одного (€

Принцип выбора И^ следующий: в начале процесса полагаем (о =<9. Далее к если 7^=0 или или fflct/x. llVf'wil

K+l J +1 в противном случае;

1С

Определяем x'ttfeQ. если ; ' если

Для рассмотренной модификации метода возможных направлений доказана теорема 3.1, в условиях которой гарантирована сходимость метода, т.е. iim, f(xK)-=wn f(x)=fM(Vl . к->с>о хба

Множество » соответствующее отбрасываемым ограничениям, можно конструировать и другими способами, что отражено в § 2. Если вместо описанной выше процедуры построения положить "Л — ф К- t.Z, - -• , данный алгоритм превращается в

С ) один из основных вариантов метода возможных направлений (естественно, что при такой замене нет нужды в использовании управляющих последовательностей {fi}7 J )•

Приведенный метод наиболее целесообразно использовать в тех задачах выпуклого программирования, в которых число ограничений существенно превосходит размерность пространства переменных. Важный класс таких задач составляют задачи выпуклой полубесконечной оптимизации5^ [2з] , [29] j-(x)-min ! = [2ОС ОUM где ограничение £ зависит от непрерывного параметра t , принадлежащего некоторому компактному множеству (замечание 1.4). х) Точнее их дискретизированные аналоги.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

1. Аннин Б.Д., Черепанов Г.П. Упругопластическая задача.-Новосибирск: Наука, 1983.- 240 с.

2. Гловински Р., Лионе Ж.-Л., Тремольер Р. Численное исследование вариационных неравенств/ перев. с франц.- М.: Мир, 1979.574 с.

3. Дюво Г., Лионе Ж.-Л. Неравенства в механике и физике/ перев. с франц.- М.: Наука, 1980.- 384 с.

4. Зойтендейк Г. Методы возможных направлений/ перев. с англ.-М.: ИЛ, 1963.- 176 с.

5. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование.- М.: Наука, 1964.- 348 с.

6. Каплан А.А. К вопросу о реализации метода возможных направлений.- Оптимизация, 1972, вып. 5, с. 41-46.

7. Каплан А.А. Алгоритмы выпуклого программирования, использующие сглаживание точных функций штрафа.- Сиб. мат. журн., 1982, т. 23, № 4, с. 1322-1350.

8. Лионе l.-Л. Некоторые методы решения нелинейных краевых задач/ перев. с франц.- М.: Мир, 1972.- 587 с.

9. Мазья В.Г. 0 задаче Неймана в областях с нерегулярными границами.- Сиб. мат. журн., 1968, т. 9, № 6, с. 1322-1350.

10. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы.- М.: Наука, 1981.- 416 е.

11. Михлин С.Г. Линейные уравнения в частных производных.-М.: Высш. школа, 1977.- 431 с.

12. Оганесян Л.А., Руховец Л.А. Вариационно-разностные методы решения эллиптических уравнений.- Ереван: Изд-во АН Армянской ССР, 1979.- 334 с.

13. Полак Э. Численные методы оптимизации. Единый подход/ перев. с англ.- М.: Мир, 1974.- 376 с.

14. Приближенное решение операторных уравнений/ Красносельский М.А., Вайникко Г.М., Забрейко П.П., Рутицкий Я.Б., Сте-ценко В.Я.- М.: Наука, 1969.- 455 с.

15. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.- М.: Наука, 1975.- 319 с.

16. Рокафеллар Р. Выпуклый анализ/ перев. с англ.- М.: Мир, 1973.- 471 с.

17. Стренг Г., Фикс Дж. Теория метода конечных элементов/ перев. с англ.- М.: Мир, 1977.- 349 с.

18. Сьярле §. Метод конечных элементов для эллиптических систем/ перев. с англ.- М.: Мир, 1980.- 512 с.

19. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры.- М.: Физматгиз, I960.- 656 с.

20. Каплан А.А., Намм Р.В. К характеристике минимизирующих последовательностей для задачи Синьорини.- Докл. АН СССР, 1983, т. 273, № 4, с.797-800.

21. Намм Р.В. Метод возможных направлений с отбрасыванием ограничений.- Оптимизация, 1978, вып. 22, с. 94-97.

22. Намм Р.В. Метод поточечной релаксации в задаче упругоплас-тического кручения цилиндрического стрежня.- Оптимизация, 1983, вып. 32, с. 140-152.

23. Borweih Т. /1 Direct theorems \п semi-infiniie convex t>ro3rzmmin<jf.—p\${h, Proyrtm., m±} V.2i, AA°3, PAot-zn .

24. В regis H. ProUemes цтЫегаих. -J Je ftaih . Pares ei Afrfifuees, mz, V. ЗГ1, №1,2, Р.1-Ш •

25. Cditereli I, A, Friedman A. The free houndiry ±or tUstic-phsh'c torsion problems. ~Trdft. Awer. ML Soc., f№, V.2S2, A tS-9? .

26. СШггеО I. A., Friedman A., Pozzi Q. Reflection methods ш He eUstiC-pkstic torsion problem-Indim tilth. X, mo, V.23J P.zos-zz$ .

27. Cryer C.W. The Solution of a fuadrdlc /эгоугамм/и? problem using systematic over-relaxdtio/i. Si AM T OH Control, 1SH, Л 34S-Z32 .

28. Glowhski R., Lions J.-LTremolteres R. bfumtricd шlysis of vtriztionrf /ле futilities.-kmsierdim d. 0. : North-Holland, mi, Нбр.

29. Н(шМ I. Convergence of dud finite element approximations for и ft it den I boundary value problems.-Apliket Mdkmiiky, 'Щ

30. Kirvey &F A duality theorem for se/ni-Ufinite Convex programs tnd their iinite subprograms.-ML Projrtmmi) v.Zf, A ?s-gL .

31. Tinj T.W. FUstiC-pUstiL torsion Of Simply connected cylindrical krs-Itldim V/iiv. MtU. Т.,1. Ш, Hiu9 p.mt-wc.

32. Xoiuntj J). M. Ikrd-fivc solution of (гг?е (ine&r5Vskms.-Mew York} London: Aazte/m'C Press, im3 5tfp.