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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

имени М. В. Ломоносова ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

ГГ;> ОД „

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

СТАНЮКОВА Ирина Витальевна

УДК 519.85

ИССЛЕДОВАНИЕ ИТЕРАТИВНОЙ СХЕМЫ МЕТОДА КОНЕЧНЫХ ЭЛЕМЕНТОВ, ШТРАФОВ И ГРАДИЕНТНОГО СПУСКА ДЛЯ РЕШЕНИЯ ОДНОГО КЛАССА ВАРИАЦИОННЫХ ЗАДАЧ

Специальность 01.01.09 — математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 1998

Работа иыиолиопа па кафедре исследоиапия операций факультета им числительной математики и кибернетики Москонского государственного университета им. М. Б. Ломоносова

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

академик РАН П.С. Краснощекой

Официальные оппоненты:

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

Ведущая организация:

Институт проблем управления РАН

Защита диссертации состоится ^ддд Г- в ц час< 00 мин.

на заседании диссертационного Совета Д.053.05.38 при Московском

государственном университете по адресу:

119899, Москва, Воробьевы горы, МГУ, факультет ВМиК, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

МГУ.

Автореферат разослан г.

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

Н. П. Трифонов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Многие задачи математической физики и исследования операций могут быть спедены к задачам иыпуклой условной оптимизации в функциональных пространствах. При этом целевой функционал задается в виде интеграла по пространственным переменным, а выпуклое замкнутое множество ограничений — с помощью неравенств, содержащих операторы. Нелинейность ограничений не позволяет свести указанные экстремальные задачи к решению системы линейных уравнений даже в случае квадратичных функционалов. Поэтому их численное решение, как правило, основывается на последовательной аппроксимации конечномерными задачами выпуклой оптимизации. Аппроксимация проводится с помощью классических методов численного анализа (Ритца, конечных элементов, конечных разностей и т. д.). Данная диссертационная работа ориентирована на использование аппроксимации по методу конечных элементов (МКЭ), который на сегодняшний день является одним из наиболее распространенных методов численного решения различного рода сложных вариационных задач.

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

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

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

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

Научная новизна. Схема итеративной аппроксимации, комбинированной с методом штрафов и градиентной оптимизацией, была изучена ранее для случая аппроксимации по методу Ритца. Полученные при этом условия существенно использовали ортогональность базисных функций. Рассматриваемая в данной диссертационной работе схема аппроксимации по МКЭ заставляет отказаться от этого условия, что потребовало разработки новой техники исследования сходимости.

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

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

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

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

Практическая ценность работы обусловлена возможностью применения предложенных алгоритмов для численного решения широкого класса задач бесконечномерной оптимизации с операторными ограничениями. Ряд результатов диссертации включен в научный отчет кафедры исследования операций факультета ВМиК по теме НИР "Математические вопросы моделирования и принятия решений в сложных системах управления" (номер государственной регистрации 01960003307).

Публикации. По материалам диссертации опубликовано 3 печатные работы.

Апробация работы. Основные результаты диссертации докладывались на научно-исследовательских семинарах факультета ВМиК, ВЦ и ИПУ РАН.

Структура и объем работы. Диссертация состоит из введения, трех глав (в 1-й — 5, во 2-й — б, в 3-й — 3 параграфа) и списка литературы, включающего 75 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

ив К = {V Е Н\ д{ь,х) < О п. в. в П, тг(и,у) < О п.в. на Г}.

Предполагается, что функционал 3 — сильно выпуклый в гильбертовом пространстве Я с константой ц, дифференцируемый по Гато; производная Гато ¿'{V) удовлетворяет условию Липшица с константой Ь]>\ П — многогранная область в К" с границей Г; К— выпуклое замкнутое множество из Я; V х € П (у Е Г) функционал д(-, х) (тг(-, у)) — непрерывный и выпуклый по V. Граничные условия задачи понимаются в смысле следа V функции V € Н на границе Г.

Решение и задачи (1) существует и единственно вследствие сильной выпуклости и непрерывности целевого функционала .7, замкнутости и выпуклости множества ограничений К.

В главе 1 рассматривается задача минимизации, соответствующая случаю, когда при определенных значениях входных данных ограничения в задаче (1) оказываются несущественными и она сводится к задаче безусловной оптимизации: найти

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

Так как целевой функционал задач (1), (2) — интегральный, проводится его аппроксимация с помощью метода конечных элементов (МКЭ), наиболее ценным свойством которого является замена интегральных функционалов суммой интегралов по подобластям (элементам) множества О. Последние интегралы легко могут быть вычислены приближенно за счет удачного выбора базиса и триангуляции.

(1)

п

В п.1.2 обсуждаются теоретические аспекты МКЭ. Рассматривается плоская область П. Пространство Н является соотпотстиующим пространством Соболева. Далее используются обозначения: Т/,— триангуляция области П; Т— треугольные элементы; к— параметр триангуляции £/, = {х{, г = 1,2... /V} — множество се иершип (узлов), N = N(¡1). Координаты точки 1£Ив пространстве К2 обозначаются верхними индексами: х = (я1, я2). Граница Г многоугольной области

П аппроксимируется точно: (] = и Г. Через г = обозна-

ТеЪ

чаются кусочно-линейные базисные функции МКЭ, Бирр <,?; = у Т.

ГЭх(

Линейная оболочка системы функций представляет собой конечномерное подпространство пространства Н:

Уи = = а; € Я11, о,- = (3)

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

Аппроксимированная задача в пространстве В/7 формулируется следующим образом: найти

тт/(а), Г(о)= [ (2)

где функции 1,Вг соответствуют функционалу / и сужению оператора Ф на элемент Г, содержащий точку х, т.е. оператору Фт("> х) = Ф(-,а;)Тт(а;), 1т(а:) — индикаторная функция элемента Т Эх. Обозначим через щ кусочно-линейное восполнение решения задачи (2).

Сходимость (в норме пространства Н) семейства решений и/,, Л | О, является следствием предельной плотности конечноэлементных аппроксимаций пространства Я. Имеющиеся оценки точности аппроксимации по МКЭ — асимптотические. Поэтому при практическом счете приходится проводить увеличение порядка аппроксимации, что соответствует дроблению параметра триангуляции. Теоретические вопросы итеративной аппроксимации по МКЭ обсуждаются в параграфе 1.3, который составляет методологическую основу работы.

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

Введем в рассмотрение последовательность шагов дискретизации {/»,}, убывающую по правилу

где — задано. Ей соответствует возрастающая последовательность размерностей аппроксимирующих пространств {-/V,} и последовательность сеток {£4}, = = 1,/^}. Узлы сетки Е, служат вершинами триангуляции Определим сетку £г+1 = ¡С, где

= +1] = ¡Ыа]} Г4[,]} с т е г„ гф а} .

Узел £;[$] в триангуляции^! будет иметь номер 2,7(5+1], где г' = {(г, а). Элементы пространства V, *= Уд, будем обозначать через V,.

На сетке с номером 5, я = 1,2,..., ставится задача конечномерной оптимизации: найти

тш Ца), Ца) = V [ ¿V(а,х)<Ь. (2.)

Точность решения возникающих конечномерных задач существенно зависит от погрешности, вносимой при аппроксимации, и от точности конкретных методов конечномерной оптимизации. Стремлением вычислителя минимизировать общую погрешность объясняется необходимость согласования указанных величин. Таким образом, порядок аппроксимации по МКЭ формирует оценку (по порядку) достаточного для каждой триангуляции числа итераций оптимизационного метода в зависимости от оценок скорости сходимости последнего.

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

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

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

О <тв<Рв, 17 = 17(0), р = р(п), г}>0,

что

Л"тл|а|2<|К|||<Рв^|а|2. (5)

утверждение 1.1. Пусть в каждой точке V банахова пространства В у функционала 7: В —» В. существует производная Гато J'(v) 6 В*, где В* — пространство, двойственное к В, производная J'(v) непрерывна в метрике пространства В* и удовлетворяет условию Липшица с кон-

N

стантой Тогда в каждой точке а 6 для которой 3 ун = а1,(Л'>

¡=1

функция 1(а) непрерывно дифференцируема и ее градиент I' Липшицев с константой

Ьг < (6)

V = Т(Рв,<3), где <2 = тах<5,-, ф,- = Саг(1(ЕШ1.) — число узлов триангуляции принадлежащих носителю и>{ базисной функции

Здесь и далее константы обозначаются буквой V без индексов.

УТВЕРЖДЕНИЕ 1.2. Если В = Н — гильбертово пространство, и функционал 3 — сильно выпуклый в Н с константой ц, то функция I сильно выпукла в ВЛ с константой

¡11 > тиф4. (7)

Будем называть отношение V = и(К) = ^ числом обусловленности аппроксимированной задачи.

Вопросы счгласчтаиил точности конечномерной оптимизации с ите-ратнниым дроблением области Ü исследованы к и.1.5. Здесь проводится обосновании итеративного метода конечных элементом и скорейшего спуска (МИКЭГ) для решения задач безусловной оптимизации в гиль-бертопом прострапетпе. Выводятся оценки его скорости сходимости.

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

N.

T€TS кусочно-линейной функции и*' = ^ а1{'<р¡, s = 1,2,... находят-

«=1

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

- шагов дискретизации {Л,}, определяемых по правилу (4);

- интервалов между дроблениями сетки {А,}, удовлетворяющих

О < lim q^ =р < 1, ?, = 1--, (Si)

»—too Vt

где 0 < qs < 1, i/s — число обусловленности задачи (2,), s = 1,2,...;

- номеров итераций, после которых производится дробление сетки, {&,}'•

кх = А 1, Vs = 2,3,... = + + (82)

- шаговых множителей {7ь,*}> определяемых в ходе метода из условия скорейшего спуска

lk,s = argmin/,(al — 7/^(0*)), Vs = l,2,..., V* = l,2,...,

7>0

и построим ai+1 = ak — 7*^(0*) для к = -f1,..., к, — 1. Значения at.+i определим как коэффициенты разложения и'* по базису, соответствующему новой триангуляции, s = 1,2,....

Теорема 1.1. При выполнениии согласований (4), (8) последователь-N.

ность {v*' = J2 a, Vi}> генерируемая МИКЭГ, сходится в метрике про-¡=1

странства Н к решению и задачи (2). Если точность конечноэлементной аппроксимации задачи (2) есть е(Л) = 0(hs), 6 > 0, то при выполнении

услопия (81) с /; < | МИКЭГ сходится по « не медленнее геометрической прогрессии. При иыборс параметра ¡> <

Утверждение 1.3. В условиях теоремы 1.1 при р > 0 для сходимости МИКЭГ достаточно проводить дробление шага дискретизации через

А® =

итераций. (Здесь и далее символом [У| обозначается наименьшее целое число, превосходящее х.) Тогда скорость сходимости метода по к равна:

при р <'225+1 ||«1-«||<0

где постоянные т] и /9, характеризующие порядок констант щ, и Ьц, определены формулами (6), (7),

ПРИ ¿Г ^ < \ И"* " О ((2р')Щ ,

Значение параметра р определяет точность решения задачи конечномерной оптимизации на в-й сетке. Получить решение с "хорошей" точностью можно лишь при значениях р, близких к нулю. Задавшись последовательностью {р,}: р, | 0, э —» оо, р, < 1 — и делая на я-й сетке Д» = ("—1/41пр,] итераций, можно гарантировать, что точность решения конечномерных задач будет увеличиваться по мере приближения к минимуму. Для решения задачи (2) с точностью порядка точности аппроксимации следует выбирать р, = Ь\.

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

\

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

В параграфе 2.2. обосновано применение к указанным задачам интегрального штрафа типа сглаженной "срезки". Освобождение от ограничений задачи (1) с помощью интегрального штрафа представляется удобным, поскольку искомый функционал 3 — также интегральный, а число ограничений <?(и, х) < 0 бесконечно. Сформулированы достаточные условия регулярности операторных ограничений и получены оценки скорости сходимости метода интегральных штрафов в исходном гильбертовом пространстве.

На основании метода штрафов задача (1) сводится к последовательности задач минимизации на простом множестве £>г(0): найти

тш /с(и), Зс(ь) = ./(и) + СП(У), С Т оо, (1с)

vesr(o)

где 5Г(0) = {г;| V £ В, < г}, пространство В С Н — область определения функционала со штрафом Зс,

= I И«,*)]' = [та^О;^,*))]1, t > 1,

п

— функционал штрафа. Множество К можно считать ограниченным по норме пространства В.

Предположим, что минимум в задачах (1), (1с) достигается на выпуклом ограниченном множестве У пространства У С В: ||и||у, ||ис||у < Я УС. Обозначим Уц = У ПК, Уц, очевидно, непусто. Пространство У может совпадать с В, и тогда в качестве У достаточно взять £>г(0), В. —г, Ук = К. Кроме того, пусть

1) на множестве У ограничения д(у, •) удовлетворяют в П условию Гёльдера с показателем а 6 (0,1] равномерно по V, т. е.

6 С°'а(П) = {<?(«,-) € С°(П)|3 А > О, VI',х" в Г2 |5(г/,х') - зК*")! < А\х' - х"\а} VI/ € У,

2) для функционала Q(v) = шлк(/(у,х) пи множестве У имполияется

(2

условие Слейтсра: 3 v £ У : (/(Г) < 0.

ЛЕММА 2.1. В предположениях 1), 2) система ограничений задачи (1) р°-регулярна, т. е. W € Y\YK H(v') > Pf>°{v',YK), где 9 = t + 2 n = dim fi, a — показатель гёльдеропости функции t](v, •), /?(•, •) — расстояние в пространстве Н, постоянная ¡1 = О \ ^ „ ) , /3 = —-

Л° I (Нат/Г

теорема 2.1. (о сходимости метода штрафов в гильбертовом пространстве). Пусть система ограничений задачи (1) //-регулярна, а целевой функционал 7 — сильно выпуклый в Н с константой ц и гёльдеров с показателем у 6 (ОД] и константой М на ограниченном множестве пространства Н (т. е. локально). Тогда при С | оо метод штрафов сходится к решению и задачи (1) со скоростью

1/2 , _ АуМП*

в/3

Комбинированию метода штрафов и конечных элементов посвящен п. 2.3. Наряду с конечноэлементной аппроксимацией метода штрафов в гильбертовом пространстве изучена возможность штрафования аппроксимированных по МКЭ задач с ограничениями. Для таких задач обобщены известные условия регулярности ограничений и оценки скорости сходимости метода штрафов в конечномерных пространствах. При этом обобщенные условия регулярности в пространстве кусочно-линейных функций оказываются слабее предположений п.2.2.

Следуя терминологиии и описанию из главы 1, для численного решения задачи (1с) будем использовать кусочно-линейные аппроксимации V/, пространства Б. Результатом конечноэлементной аппроксимации задачи (1е) является последовательность приближенных задач: найти

тш1с{а), /Да) = 1(а) + СС?(а), (1с)

Да) = ^ / Ж«».*) °(а) = 1С /И^.2)]' ¿х, С] оо, И [ 0,

теъ у. т^Т/, гр

где функции 1,С, Рт, <тт вещественного аргумента соответствуют функционалам и сужению операторов Ф, д на Т Э х\ — шар в

пространстве RA', соопкпстиующий множеству 5Г(0) П V/,. Кусочно-линейное восполнение решения задачи (1с) обозначим через uch.

При условии пснустоты множества К/, = К П V/, П 5Г(0) к последовательности задач (1с) приводит также метод штрафов типа "срезки", примененный к аппроксимированной задаче с ограничениями. Оценки скорости сходимости метода штрафов в этом случае могут быть выражены через параметры штрафа и дискретизации следующим образом.

Утверждение 2.1. Пусть функционал J локально Липшицев с константой Lj = Lj(r,П), а функционал штрафа H(v) удовлетворяет на классе кусочно-линейных функций условию регулярности

W(«a) > Kh)hl VvheVh\ Кн- с 0 > 1, (> 0.

Тогда в случае 6 > 1 метод штрафов сходится со скоростью

<9>

к решению щ аппроксимированной задачи, а при © = 1 щ = uch уже для конечных значений параметра штрафа.

В п.2.4 предложен и подробно исследован итеративный метод штрафов и конечных элементов (МИКЭШ). В его основе лежит совмещение измельчения шага дискретизации с увеличением штрафных множителей в одной вычислительной процедуре. При этом отпадает необходимость для каждого значения ks —> 0, s —> оэ, стремить С, к бесконечности.

Выбирается возрастающая последовательность штрафных констант Cs Т оо и убывающая последовательность параметров аппроксимации hs J. 0 так, чтобы

Vt»6Ä" С,ЩЪ.)-+ 0 при s —► оо, (10)

где vs — кусочно-линейный интерполянт функции v.

В пространстве KN',s = 1,2,..., рассматривается задача безусловной оптимизации: найти

min Ic,s{a)> /с,,(а) = Ца) + C,G,{a), (ie,f)

/«(«) = Е /С.„.(«) = £ /

7'ег.:/. /ет,:/.

— аппроксимация в пространстве Л/^ оштрафованного целевого функционала задачи (1). Пусть V 5 = 1,2,... кусочно-линейная функция соответствует решению на множестве задачи конечномерной оптимизации (1С,»).

Требуемое в (10) согласование С, и /г5 всегда возможно в силу непрерывности Л и предполагает достаточно медленный рост С3. В п.2.4 получено его явное выражение на основании порядка обобщенной гладкости решения, локальной липшицевости производной Гато функционала штрафа и формул интерполяции в пространствах Соболева. А именно, пусть для некоторых целых чисел т > 0, к > 0 и некоторых чисел р, д £ [1, оо] таких, что

к + 1 — т +

„ (!-!)> о, (п)

решение задачи (1) есть элемент пространства ИЛ*+1,Р(А)| пространство В = ТУт'7(П) и выполняются непрерывные вложения

где С°(й) — пространство непрерывных в й функций, РР'^Л), I > 0, ] > 1, — пространство Соболева (состоящее из всех измеримых на П функций, суммируемых со степенью ] на П вместе со всеми обобщенными производными до порядка I включительно).

Тогда для функции и £ Илс41,р(П) и ее кусочно-линейного интерпо-лянта щ имеет место оценка

11« - «л11^(П) < -РПя^т (12)

обеспечивающая в силу локальной липшицевости согласование (10) при выборе С, из условия

Теорема 2.2. В предположениях (10), (11), (12) последовательность реализующая метод итеративного штрафования и итеративной

аппроксимации но МКЭ, сходится и сильной метрике пространства Я к решению и задами (1).

Предложенный вариант МИКЭШ предполагает штрафование исходных ограничений и аппроксимацию задачи безусловной оптимизации, что позволяет строить минимизирующую последовательность (получать приближение к решению) даже в тех случаях, когда аппроксимированное множество ограничений оказывается пустым, т. е. обычный метод аппроксимации может "не сработать". Использование итеративного по порядку аппроксимации штрафа в такой ситуации, безусловно, оправдано. В тех же случаях, когда для всех значений 5 гарантирована непустота множеств К, — Л"П 1/'4П5г(0), в схеме (1с,5) можно отказаться от условия (10) медленного роста штрафа.

Теорема 2..3. Пусть аппроксимированное множество ограничений К6 = К П V, П 5Г(0) непусто V г и имеет место сходимость последовательности конечноэлементных аппроксимаций:

||и - щ^Ия -+0, г —> оо, где = argmш

ъ.ек.

Тогда МИКЭШ сходится при произвольном темпе роста последовательности штрафных констант.

Замечание 2.6. Если граничные условия задачи (1) не могут быть учтены путем выбора базиса, для сходимости МИКЭШ достаточно, чтобы V V 6 К выполнялись условия (11), (12) и

СшЩь.) + А5Р(Ъ5) — 0 при 5 —► оо, (10')

где

р&) = АЛ оо.

г

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

Утверждение 2.3. Пусть выполнены условия утверждения 2.1 и последовательность конечноэлементных аппроксимаций {и/,}, Л — Н3,

гходтч-я со скоростью к решению //. исходной задачи. Тогда при

иыГюре штрафного параметра С — ("„ согласоиаимо с h следующим образом:

С=0' '

- метод интегральных штрафов и конечных элементов также сходится со скоростью 0(hl).

Полученные в п. 2.4 оценки являются базовыми для предложенного в параграфе 2.5 метода итеративного штрафования, итеративной конечноэлементной аппроксимации и скорейшего спуска (МЙКЭШГ). Обоснование сходимости данного метода и получение соответствующих условий согласования его управляющих последовательностей представляет собой ключевой результат настоящей работы. Сходимость метода исследована в предположении локальной липшицевости производной Гато оштрафованного целевого функционала.

Алгоритм МИКЭШГ.

Шаг 0. Выберем числовые последовательности

- {Л,} — шагов дискретизации, задаваемых по правилу (4);

- {С.} — штрафных констант, удовлетворяющих условию

Hm = 1; (13!)

i-KO Gj_l

- {А,} — интервалов между дроблениями сетки, определяемых из условия

0 < lim gf' =р < 1, qs = 1 - (132)

s—»OO

где vs = — число обусловленности задачи (2.1с>4), 0 < q, < 1;

- {к,} — итераций, после которых производится дробление сетки:

fei = Ab Vs = 2,3,... fcj = ks-\ 4- А, + 1. (133)

Шаг 1. Возьмем произвольное начальное приближение а1 6 RWl и триангуляцию Т\. Построим следующие к\ — 1 приближений по правилу:

Последовательность шаговых множителей {7t,«} определяется в ходе алгоритма из услоиия скорейшего спуска:

7i,g = argmiriIc,s{ak - уГсs{ak)), Vs = 1,2,..., VА = 1,2,.... 7>0

Шагя + l Ve = 1,2,... .

1) Vк = ks + 1, •.., ks+1 положим h = hs+i; С = Ct+1;

2) для к = ks определим Vi = 1, Ns+l

если узел я,- 6 Ei+i в триангуляции Т„ имел номер j, т.е. аф + 1] = i = f(j,s);

af+1 = если узел х,- € Sj+i не принадлежал

с}+а£, триангуляции но является серединой 2 ' стороны [xj,xm] треугольника Т € т.е.

®j[i + 1] = |(х,-[в] + Zm[s]), {Xj,xm} СТе Ts\

3) Vk = kt + l,...,ks+i-l, Vi = l71vs+1

„fc+i__i „ Obsi+Lt^

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

Правило останова. Эвристическим критерием окончания счета может служить, например, одновременное выполнение условий

(WO

£ 14-аМ2] <62, i' = f(i,S-l), (142)

V^eE,.! /

которые имеют место вблизи точки минимума. Здесь i = 1,2 — заданная точность. Отметим, что выполнение только первого из условий (14) (даже с достаточно высокой точностью 6{) свидетельствует лишь о

близости точки ак к л-му оптимуму п' 4, к.усочпо-лииейноо восполнение которого — — может окамитьсн д<толыи> грубым приближением решения и на начальных итерациях по я. Усилить это условие призвано неравенство (14г), которое гопорит о стабилизации процесса дробления: решение а* на 5-й сетке мало отличается от приближения, полученного на — 1)-й триангуляции.

ТЕОРЕМА 2.4. В предположениях теорем 2.2 или 2.3 при выполнении

N.

согласований (4),(13) последовательность {г/*' = Са-'у«}, генерируе-

{=1

мая методом, сходится в сильной метрике пространства Я к решению и задачи (1).

Подчеркнем, что согласование (10), обеспечивающее сходимость МИКЭШ, заведомо выполнено при темпе роста штрафа, заданном условием (1З1).

Основным следствием результатов п.2.5 служит оценка достаточного для каждой триангуляции числа итераций скорейшего спуска, которая при р ф 0 может быть выражена через значения Л, и С, с учетом локальной липшицевости градиента функции /с>, и полученных в п. 1.4 оценок для А именно:

ГД6 = (15)

(Л,)— локальная константа Липшица производной Гато функционала штрафа И.

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

Влияние условий согласования продемонстрировано в главе 3, где проведено тестирование метода на примере задачи кручения упруго-пластического стержня. Оптимизационная постановка этой задачи имеет вид (1) со следующими данными: гг = 2, Я = Я0!(П) — пространство

Соболева 1-го порядка с нулевым следом па границе Г;

J (и) = 1а(и,и) -i(u),

fi "-1 ft — симметричная билинейная форма, определенная и непрерывная на

Я0'(П); i(и) = / J v(x) dx, где / = const на fi; n

I< = {«| г; 6 Я0'(П), |Vv(x)| < 1 п.в. в П}.

В ходе практического исследования сходимости МИКЭШГ подтвердились теоретические выводы главы 2 и были отмечены следующие свойства метода. Рост размерности пространства, в котором осуществляется минимизация, т. е. увеличение числа узлов МКЭ, вместе с ростом штрафа усиливают эффекты, связанные с овражностью задачи. Медленное итеративное штрафование по возможности ослабляет ухудшение обусловленности и обеспечивает наилучшую практическую сходимость в задачах большой размерности. Параллельно с ростом штрафа происходит уменьшение (по порядку) длины шага в методе скорейшего спуска. Таким образом, в начале счета и, вообще говоря, вдали от решения делаются сравнительно большие шаги при небольшом штрафе за выход из ограничений, что способствует ускорению практической сходимости. Уменьшение порядка длины шаговых множителей происходит быстрее, чем растет штраф, что является дополнительным стабилизирующим фактором вблизи решения.

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

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

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

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

РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

2. Найдены гарантированные оценки констант сильной выпуклости и Липшица градиента для аппроксимированных по МКЭ задач в зависимости от размерности аппроксимирующего пространства и соответствующих констант бесконечномерной задачи. Для рассматриваемого класса вариационных задач разработана и обоснована схема итеративного комбинирования МКЭ, метода штрафов и градиентного спуска (МИКЭШГ). Получены условия согласования управляющих последовательностей, обеспечивающие сильную сходимость МИКЭШГ.

3. Проведено теоретическое исследование сходимости МИКЭШГ без предположения о глобальной липшицевости градиента оштрафованного целевого функционала.

4. На примере задачи кручения упруго-пластического стержня исследована практическая сходимость схемы МИКЭШГ для различных вариантов выбора управляющих параметров.

По результатам диссертации опубликованы работы:

1. Станюкова И. В. О согласовании точности метода конечных элементов с градиентной оптимизацией // Вестник Моск. ун-та. Сер. 15. Вычисл. матем. и киберн., 1992. № 2. С. 61-67.

2. Станюкова И. В. О сходимости метода штрафов для одного класса задач выпуклой оптимизации в гильбертовом пространстве // Вестник Моск. ун-та. Сер. 15. Вычисл. матем. и киберн., 1993. № 3. С. 51-57.

3. Станюкова И. В. Комбинированный метод штрафов и конечных элементов для одного класса задач выпуклой оптимизации // Вестник Моск. ун-та. Сер. 15. Вычисл. матем. и киберн., 1998. № 1. С. 18-23.