Методом условного градиента как найти вспомогательное приближение
Перейти к содержимому

Методом условного градиента как найти вспомогательное приближение

  • автор:

33. Алгоритм метода условного градиента

если то строим отрезок (5) и соединяем точки и . На отрезке (5)рассматриваем функцию и решаем задачу одномерной минимизации . Обозначим через –решение последней зад. минимизации т.е , тогда следующее приближение .

Замечание:

  1. Метод условного градиента является эффективным в том случае, когда вспомогательная зад. допускает простое решение;
  2. На каждом шаге метода условного градиента решается зад. одномерной минимизации . Для некоторых классов задач, решение этой задачи удается найти в явном виде, например, в случае квадратичной целевой функции. Для некоторых классов задач для решения задачи применяют численные методы одномерной минимизации. На практике часто пользуются следующим алгоритмом:
  • Задают некоторое значение и проверяют условие (6)
  • В случае выполнения (6), ; иначе дробят
  1. В качестве критериев окончания счета используют выполнение неравенств или , где и согласованные числа, характеризующие точность вычисления.

Теорема3

Если функция f(x) в зад.(1) непрерывно дифференцируема , удовлетворяет векторному условию Липшица, множество Х — выпукло, замкнуто и ограничено, то при любом начальном приближении процесс метода условного градиента является релаксационным и сходится к непустому множеству стационарных точек. Если дополнительно f(x) выпукло, то построенная последовательность является минимизирующей и сходится к непустому множеству решений задачи.

34. Алгоритм метода покоординатного спуска.

Рассмотрим задачу . Пусть выбрано некоторое начальное приближение. И мтодом покоординатного спуска было получено приближение . Ч/з , , обозначим координатные вектора (1 на j-ом месте). Положим и для , где определяется из условия . И следующее приближение , если для некоторого k , то процесс вычисления заканчивают, А т считают приближением к точке минимума.

Данный метод хорошо подходит для задач с параллепипедными ограничениями,

, . В этом случае при решении вспомагательной задачи минимизации , .

Численные методы расчета оптимального по быстродействию управления Текст научной статьи по специальности «Математика»

МЕТОД ВЫПУКЛЫХ ОБОЛОЧЕК / CONVEX HULL METHOD / МНОЖЕСТВО ДОСТИЖИМОСТИ / ЗАДАЧА БЫСТРОДЕЙСТВИЯ / МИНИМАКСНЫЙ АЛГОРИТМ / MINIMAX ALGORITHM / ЛИНЕЙНАЯ УПРАВЛЯЕМАЯ СИСТЕМА / LINEAR CONTROLLED SYSTEM / ATTAINABILITY SET / TIME-OPTIMAL PROBLEM

Аннотация научной статьи по математике, автор научной работы — Тятюшкин Александр Иванович

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Тятюшкин Александр Иванович

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

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

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

Numerical Methods for Calculation of Time-Optimal Control

The article is devoted to algorithms for calculation of time-optimal control in the linear systems. Proposed set of algorithms make possible apply multi-method technique to solving time-optimal control problems with different singularity. Corresponding to this technology the solution is found by a multimethods algorithm consisting of a sequence of steps of different methods applied to the optimization process in order to accelerate it. Such a technology allows to consider some particularities of the problem of interest at all stages of its solution and to improve the efficiency of optimal control search.

Текст научной работы на тему «Численные методы расчета оптимального по быстродействию управления»

2014. Т. 8. С. 164—177

Онлайн-доступ к журналу: http://isu.ru/izvestia

Численные методы расчета оптимального по быстродействию управления *

Институт динамики систем и теории управления СО РАН

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

Ключевые слова: метод выпуклых оболочек, множество достижимости, задача быстродействия, минимаксный алгоритм, линейная управляемая система.

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

* Работа выполнена при частичной финансовой поддержке Совета по грантам Президента Российской Федерации для государственной поддержки ведущих научных школ (НШ-5007.2014.9).

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

Для численного решения задачи быстродействия при наличии ограничений только на управляющие функции здесь описывается алгоритмическое обеспечение, основанное на математических методах [1; 2; 5; 6; 10] и позволяющее реализовать многометодную технологию [7; 12] поиска оптимального по быстродействию управления. Задачи с ограничениями на фазовые координаты обычно решаются посредством дискретизации системы с формированием задачи линейного программирования, для решения которой затем используются специальные методы, учитывающие структуру матрицы основных ограничений [4].

1. Минимизация выпуклой функции конечного состояния

Будем рассматривать задачи оптимального управления в линейных системах

х = л(г)х + в(г)и(г) + /(г), х(г°) = х°, (1.1)

где х(г) е Еп, и(г) е Ет , Л(г), в (г), / (г) — п х п, п х г, п х 1-матрицы с кусочно-непрерывными элементами.

В теории линейных управляемых систем значительную роль играет переходная матрица [1] Ф(г,т), называемая также матрицей Грина. Она удовлетворяет следующему матричному дифференциальному уравнению:

С помощью этой матрицы решение (1.1) записывается по формуле Ко-ши

х(г) = Ф(Мо)х0 + У Ф(г,т) [в(т)и(т) + /(т)] йт.

Введя обозначение с = Ф(г1,г°)х° + / Ф(г1,т)/(т) йт, вектор состоя-

ния в момент г = ¿1 представим в виде

х(Ь) = с + ! Ф(и,т)в(т)и(т) йт. (1.3)

Из (1.3) следует, что вектор с является состоянием системы (1.1) в момент г = г1, в которое она переводится с помощью нулевого управления (и(г) = 0).

Множество конечных состояний x(t\), соответствующее заданному классу допустимых управлений, называется множеством достижимости системы (1.1).

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

Пусть на правых концах траекторий системы (1.1) определена непрерывно дифференцируемая выпуклая скалярная функция p(x(t1)) и поставлена задача

Наиболее распространенный подход к решению задачи (1.1), (1.4) состоит в применении градиентных методов

uk+1(t) = uk(t) + akB'(г)фк(t), к = 0,1.

где ф(t) — решение задачи Коши

ak находится, например, из условия наискорейшего спуска.

Опишем вычислительную технологию решения задачи (1.1), (1.4) с ограничениями на управление

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

Решением линейной вспомогательной задачи Vp (xk(ti)) x — min, определяемой на каждом шаге метода, будет управление

r,km — / если ftiC0VfcСО < о, п 7]

j Xßj(t), если b,-(i)Vfc(i) > о, j = l,r, 1 j

где фк(t) — решение задачи Коши (1.5) при ф(t1) = -Vp(xk(t1)). Итерация метода условного градиента описывается формулами

Для получения точек xk(t\) и xk(t\) необходимо интегрировать систему (1.1) при управлениях uk (t) и uk (t). Используя покоординатное представление точки x(ti):

можно исключить операцию интегрирования системы (1.1), заменив ее интегрированием более простой системы. Для этого необходимо предварительно найти решения (1.5) фl(t), при начальных условиях — единичных векторах ортонормированного базиса: ipl(ti) = ег, г = 1,п; с помощью этих решений посчитать и запомнить в узлах интегрирования строки nxr-матрицы M(i), равные ф1^)1 B(t), г = 1, п. Проинтегрировав систему (1.1) при u(t) = 0, вычислить вектор с.

Пусть теперь задано допустимое управление uk (t). Тогда итерация (1.8) состоит из следующих операций:

1) решается задача Коши Xk = M(t)uk(t), xk(t0) = с, в результате чего найдется вектор xk (t1);

2) решается задача Коши (1.5), и по формулам (1.7) вычисляется управление uk (t);

3) решается задача Коши xk = M(t) uk(t), xk(t0) = с, после чего будем иметь xk (t1);

4) решается задача одномерного поиска

ю (xk (t1) + а \xk(t1) — xk (t1 )Л ^ min ;

5) по формуле (1.8) строится новое приближение.

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

— J B'(t^k (t) \uk (t) — uk (t)

где фк ф — решение задачи Коши (1.5). Значение левой части второго неравенства удобно находить при выполнении операции 2). Значения е и

е\ определяют точность решения задачи (1.1), (1.5), (1.6) и должны задаваться с учетом погрешностей счета величин, стоящих в левых частях неравенств. Поскольку на практике задать «достижимое» значение £\ не всегда удается, во избежание зацикливания обычно применяется первое неравенство, выполнение которого свидетельствует о прекращении сходимости релаксационного процесса.

Недостаток данного алгоритма состоит в том, что его реализация требует получения и хранения базисного набора решений сопряженной системы, составляющего фундаментальную матрицу. Однако если размерность задачи такова, что имеющийся объем памяти позволяет реализовать описанный алгоритм, то такой подход будет вполне оправданным, поскольку задачи Коши, решаемые в п. 1) и 3), значительно проще, чем задачи Коши (1.1), а число итераций, выполняемых методом условного градиента для получения решения с заданной точностью, обычно бывает достаточно большим. Если необходимый объем памяти гиИ + ии > V, где V — допустимый объем, V > 2, то можно реализовать традиционный вариант метода условного градиента, в котором вместо операций 1) и 3) будет интегрироваться система (1.1) при управлениях пкф и йк(£) соответственно. Тогда потребуется всего гИ + vи слов памяти. Трудоемкость итерации эквивалентна интегрированию 2и скалярных уравнений.

1.1. МИНИМИЗАЦИЯ нормы УКЛОНЕНИЯ от ЗАДАННОГО состояния

Рассмотрим задачу, в которой вместо (1.4) будет минимизироваться функция, измеряющая уклонение конечного состояния системы от заданного состояния xT:

\\x(t1) — xT || — min, (1.9)

где x(t1) — решение системы (1.1) при t = t1, соответствующее управлению из класса допустимых (1.6). Решение этой задачи, очевидно, можно получить, применяя в приведенном выше алгоритме вместо операции одномерного поиска 4) следующую формулу:

Известно, что метод условного градиента обладает медленной сходимостью, поэтому в его развитие предложены алгоритмы квадратичного программирования [9, 11], которые позволяют получить решение задачи (1.9) за существенно меньшее число итераций.

1.2. Метод выпуклых оболочек

Основная идея рассматриваемого алгоритма состоит в том, что для уменьшения целевой функции (1.9) максимально используются результаты наиболее трудоемкой операции — решения задачи Коши, полученные на нескольких итерациях. Вместо выпуклой оболочки двух точек хк и Хк, на которой отыскивается новое приближение в методе условного градиента, здесь применяется выпуклая оболочка в, 2 < в < п + 1, точек множества достижимости. Для поиска минимума функции (1.9) на выпуклой оболочке в точек решается простейшая задача квадратичного программирования. Приближение, полученное в результате решения этой задачи, значительно лучше приближения, полученного на отрезке методом условного градиента.

Алгоритм начинает работу с допустимого управления и1, и на его первой итерации, как и в методе условного градиента, новое приближение строится в виде выпуклой комбинации и1 и управления (1.7), вычисленного на решении системы (1.5) при

Ш) = 91 = (х1^) — хт) / \\x\ti) — хт 1

Параметр вычисляется по формуле (1.10).

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

Опишем и-ю итерацию алгоритма. Пусть на его итерациях получены управления и1, и2. ик, к < п + 1, и им соответствующие точки хг, г = 1,к, с помощью которых представляется приближение

иг и хУ = 2^ вгхг

где > 0, г = 1 ,к, Рг = 1- Тогда шаг алгоритма состоит из следую-

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

решение которой удовлетворяет линейной системе алгебраических уравнений 1

2J aj(xг — xy(xJ — х+ (хг — хк)\хк -х2)=0, i = l,k-l. (1.11) j=i

С помощью решения данной системы и ак = 1 — ^ аг легко строится

искомая точка на плоскости: y = ^ aixi;

2) если среди щ, г = 1, к, имеются отрицательные и, следовательно, точка у не принадлежит выпуклой оболочке точек хг, г = 1 ,к, то на отрезке, содержащем точки y и xv, отыскивается точка пересечения отрезка с гранью выпуклой оболочки: z = y + a(xv — y), где

а = max = ai0 / (ai0 — ßi0)), или z = ^ jixi, Yi =

ai + a(ßi — ai). Очевидно, jiQ = 0, поэтому точка xi0 и управление ui0 исключаются из дальнейшего рассмотрения;

u(t) = J2 ai ui(t), t e [to,ti]] (1.12)

5) оставшиеся точки хг, г = l,s, дополняются новой точкой xs+l = x(ti), соответствующей управлению (1.7), посчитанному на решении задачи Коши (1.5) при tl) = (y — xT) / ||y — xT||, и повторяются операции 1)—5) при k = s + 1. Процесс прекращается при выполнении неравенства

||y — xT||2 — (gs+l)’ (x(ti) — xT) < e,

которое следует проверять после окончания операции 5) (e — заданная точность решения задачи (1.9)). Найденная при этом точка y является проекцией xT на множество достижимости: y = arg min Hx — xTУ.

Управление (1.12), приводящее систему (1.1) в точку у, будет оптимальным для задачи (1.9).

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

Требования алгоритма к памяти определяются в основном числом управлений иг, г = 1,5, и их размерностью г. Учитывая релейную структуру управлений (1.7), для хранения их в памяти достаточно запомнить лишь точки переключения каждой управляющей функции и ее начальных значений: -и*(¿о), .] = 1, г*, г = 1,«, что требует (п + 2) слов памяти. Кроме того, необходим объем памяти для хранения управления (1.12), точек хг, г = 1, в, в < п+1, а также векторов, с помощью которых реализуются решения линейной системы алгебраических уравнений и численное интегрирование. Таким образом, необходимый объем памяти составляет тМ + /п + (п + 1)п + (п + 2)г, / >5, слов.

1.3. Алгоритм, основанный на теореме о минимаксе

Для решения задачи (1.9) с ограничениями на управление (1.6) построим алгоритм, основанный на теоремах об отделимости и о минимаксе [3]. Если множество достижимости X(I) строго выпукло и содержит точку хт, то данный алгоритм позволяет получить управление, которое с минимальной интенсивностью I* < I переводит систему (1.1) в точку хт, и следовательно, на этом управлении функционал (1.9) достигает абсолютного минимума. В случае, когда хт / X(I), данный алгоритм найдет управление, которое переводит систему (1.1) из х° в точку множества X(I), ближайшую к точке хт.

Пусть при и(^ = 0 решена задача Коши (1.1), найден вектор с = х^1) и задано первое приближение

д1 = (х(^) — хт) / \\х(^) — хт\\ .

Тогда Л(0,д1) = д1 (х^ <)—хт) >0 и итерация алгоритма будет состоять из следующих операций:

1) при заданном I вычисляется значение функции

Л(1,д1 )= д1′ (х(д1) — хт);

3) Выполнив операцию максимизации, найдем вектор дк+ = д(ак) такой, что Л(1к,дк+1) > 0;

4) находится новое значение

_ дк'(с-хт) 1к+1~ 9к'(с-хТ)-\(1к,дк) 1к’

для которого Л(1к+1,дк+1) = 0;

6) если ¡к+1 > I и, следовательно, Л(1,дк) > 0, то процесс расширения множества достижимости X(¡) прекращается и в дальнейшем при заданном ¡ повторяются итерации основного алгоритма до выполнения неравенства

Управление, с которым на последней итерации найдена точка х(дк), будет оптимальным.

Сходимость данного алгоритма имеет место лишь в случае строго выпуклого множества X(¡). Поэтому в общем случае возможно зацикливание итерационного процесса. Чтобы избежать зацикливания, следует ввести дополнительное условие прекращения процесса

где ед — оценка погрешностей вычисления функции Л(1,д). Если это условие выполняется при нарушении неравенства (1.13), то данный алгоритм не может обеспечить решение задачи (1.9) и для дальнейшего поиска оптимального управления необходимо использовать изложенные выше алгоритмы.

2. Алгоритмы решения задачи быстродействия

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

2.1. Минимаксный алгоритм

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

интенсивности управления [2; 6]. Вместо наименьшего значения параметра l = l* алгоритмы быстродействия отыскивают минимальный отрезок времени t* — to, за который переводима система (1.1) из x° в xT при заданных ограничениях на управление. Предполагая управляемость системы (1.1), построим алгоритм, который генерирует сходящуюся возрастающую последовательность моментов времени ti,t2. с двумя основными свойствами:

1) вдоль последовательности множество достижимости

расширяется (X(tk) С X(tk+i)),

2) в момент t* = lim tk происходит первое касание точки xT.

Для определения значений tk, к = 1, 2. будем применять следующее условие:

Ф(tkУ (x(tk) — xT) = 0,

проверка которого требует одновременного интегрирования систем (1.1) и (1.5) в прямом времени.

При каждом фиксированном значении tk корректировка вектора g — нормали опорной плоскости — осуществляется посредством решения задачи X(g,tk) ^ max. Иными словами, полагается

gk+1 = arg max X(g,tk). g g \\g\\

Пусть g0 е G+. Тогда k-й шаг минимаксного алгоритма состоит из следующих операций:

1) при управлении (1.7) в прямом времени интегрируется система

x = A(t)x + bj (t)uj (t) + f (t), x(tk) = x(tk) = x(gk ,tk), j=i

ф = —А(Ь)’ф, ф(tk)= gk, t > tk, (2.1)

до первого корня tk+l функции ф(t)'(x(t) — xT):

ф(tk+i)'(x(tk+i) — xT ) = 0;

2) при фиксированном tk+i, начиная с g = ф(Ьк+1) выполняется несколько шагов градиентного метода. В результате находится gk+i £ G++1.

Операции 1), 2) повторяются, пока градиентный метод обеспечивает выполнение неравенства X(gk+i ,tk+i) > 0, а интегрирование системы (2.1) позволяет получить tk+i > tk. Для управляемой системы данный итерационный процесс сходится к (g*,t*):

X(g*,t*) = min \\x(t*) — xT II = 0, X(g* ,t*) = max X(g,t*). x(t*)ex(t*) geG+

При этом управление (1.7), посчитанное на решении системы (1.5) при Ф(.ti) = g, будет оптимальным по быстродействию.

Недостатками минимаксного алгоритма являются, с одной стороны, необходимость интегрирования сопряженной системы в прямом времени и, с другой — гарантированная вычислительная устойчивость только для строго выпуклых множеств достижимости.

Трудоемкость итерации алгоритма оценивается трудоемкостью интегрирования 2n(v + 1) скалярных уравнений на отрезке [t0,tk], где v — число пересчетов X(g,tk), при вычислении параметра ak. Требуемый объем памяти — jn слов, y < 5.

2.2. Алгоритм выпуклых оболочек

Рассмотрим алгоритм, в котором вместо градиентных процедур для попадания в область G+ применяется итерационная процедура из раздела 1. Тогда в качестве вектора g берется приближенное решение задачи (1.9):

gk = (xk(tk) — xT) /\xk(tk) — xTI . (2.2)

Поскольку max X(g,tk) = min \\x — xT\\, при xk(tk) = xT найдется \\g\\

такой номер k, для которого gk вида (2.2) будет принадлежать G+. В

противном случае xT £ X (tk) и при gk £ G^ вычисляется оптимальное

Пусть g° = (x0 — xT) / \\x0 — xT \\, k = 0. Тогда итерация алгоритма состоит из следующих операций:

1) начиная с x(tk) = x(tk), ф(tk) = gk интегрируется 2п-мерная система (2.1) от tk до ближайшего к нему корня tk+i уравнения

2) задается входная информация для алгоритма выпуклых оболочек из разд. 1.2: xl = x(tk), ui = u(t) — управление (1.7), приводящее (1.1) в x(tk).

Затем при ф(Ьк) = (х1 — хт) / ||х1 — хт || интегрируется система (1.5) и по формуле (1.7) считается управление и2 = и(Ь). Решение системы, соответствующее и2(Ь), при Ь = 11 берется в качестве х2;

3) начиная с к = 2 реализуются итерации алгоритма выпуклых оболочек из разд. 1.2, пока не выполнится неравенство

(У+1)’ №) — хт) = \(дк+ ,1к) > 0,

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

где дк+1 = (уи — хт) / ||у^ — хт||, уи — полученное приближение для задачи (1.9). Затем к меняется на к + 1 и повторяются операции 1)—3).

Сходимость этого процесса следует из сходимости метода условного градиента и имеет место для произвольного выпуклого множества.

Итерационный процесс прекращается при выполнении неравенства ||у^(£к) — хт|| < е. Тогда оптимальное управление считается по формуле (1.12).

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

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

1. Андреев Ю. Н. Управление конечномерными линейными объектами / Ю. Н. Андреев. — М. : Наука, 1976. — 424 с.

2. Васильев О.В. К численному решению задач линейного быстродействия / О. В. Васильев, А. И. Тятюшкин // Дифференц. и интегр. уравнения. — Иркутск : Изд-во Иркут. ун-та, 1973. — Вып. 2. — С. 57-69.

3. Габасов Р. Качественная теория оптимальных процессов / Р. Габасов, Ф. М. Кириллова. — М. : Наука, 1971. — 508 с.

4. Габасов Р. Конструктивные методы оптимизации. Ч. 1. Линейные задачи / Р. Габасов, Ф. М. Кириллова, А. И. Тятюшкин. — Минск : Университетское, 1984. — 214 с.

5. Калман Р. Очерки по математической теории систем / Р. Калман, П. Фалб, М. Арбиб. — М.: Мир, 1971. — 400 с.

6. Красовский Н. Н. Теория управления движением / Н. Н. Красовский. — М. : Наука, 1968. — 476 с.

7. Тятюшкин А. И. Многометодная технология оптимизации управляемых систем / А. И. Тятюшкин. — Новосибирск : Наука, 2006. — 343 с.

8. Тятюшкин А. И. Численное исследование свойств оптимального управления в одной задаче преследования / А. И. Тятюшкин, Б. Е. Федунов // Изв. РАН, ТиСУ. — 2005. — № 3. — С. 104-113.

9. Barr R. O. An efficient computational procedure for a generalized quadratic programming problem //J. SIAM Control. — 1969. — Vol. 7, N 3. — P. 415-429.

10. Eaton J. H. An iterative solution to time-optimal control //J. Math. Anal. and Appl. — 1962. — Vol. 5, N 2. — P. 329-344.

11. Gibert E. G. An iterative procedure for computing the minimum of a quadratic from on a convex set // J. SIAM Control. — 1966. — Vol. 4, N 1. — P. 61-80.

12. Tyatyushkin A. I. A multimethod technique for solving optimal control problem // Optimization Letters. — 2012. — N 7. — P. 1335-1347.

A. I. Tyatyushkin

Numerical Methods for Calculation of Time-Optimal Control

Abstract. The article is devoted to algorithms for calculation of time-optimal control in the linear systems. Proposed set of algorithms make possible apply multi-method technique to solving time-optimal control problems with different singularity. Corresponding to this technology the solution is found by a multimethods’ algorithm consisting of a sequence of steps of different methods applied to the optimization process in order to accelerate it. Such a technology allows to consider some particularities of the problem of interest at all stages of its solution and to improve the efficiency of optimal control search.

Keywords: convex hull method, attainability set, time-optimal problem, minimax algorithm, linear controlled system.

1. Andreev N. Manage finite linear objects (in Russian). Moscow, Nauka 1976, 424 p.

2. Vasil’ev O.V., Tyatyushkin A.I. On the numerical solution of linear time-optimal control (in Russian). Differential and Integral Equations. Irkutsk, University Press, 1973, issue 2, pp. 57-69.

3. Gabasov R., Kirillova F.M. Qualitative theory of optimal processes (in Russian). Moscow, Nauka, 1971, 508 p.

4. Gabasov R., Kirillova F.M., Tyatyushkin A.I. Constructive Optimization Methods. Part 1: Linear problems (in Russian). Minsk, 1984, 214 p.

5. Kalman R., Falb P., Arbib M. Essays on mathematical systems theory. New York, Wiley, 1971 . 400 p.

6. Krasovskii N.N. Theory of motion control (in Russian). Moscow, Nauka, 1968, 476 p.

7. Tyatyushkin A.I., Fedunov B.E. Numerical study of the properties of optimal control in a pursuit problem (in Russian). Math. RAS, Tisza. 2005, no. 3, pp. 104-113.

8. Tyatyushkin A.I. Multimethod optimization technology controlled systems (in Russian). Novosibirsk, Nauka, 2006, 343 p.

9. Barr R.O. An efficient computational procedure for a generalized quadratic programming problem. J.SIAM Control, 1969, vol. 7, no. 3, pp. 415-429.

10. Eaton J.H. An iterative solution to time-optimal control. J. Math. Anal. and Appl., 1962, vol. 5, no. 2, p. 329-344.

11. Gibert E.G. An iterative procedure for computing the minimum of a quadratic from on a convex set. J. SIAM Control, 1966, vol. 4, no. 1, pp. 61-80.

12. Tyatyushkin A.I. A multimethod technique for solving optimal control problem. Optimization Letters, 2012, vol. 7, pp. 1335-1347.

Tyatyushkin Alexander Ivanovich, Doctor of Sciences (Physics and Mathematics), Professor, Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences (ISDCT SB RAS), 134, Lermontov st., Irkutsk, 664033, (e-mail: tjat@icc.ru)

Задача условной оптимизации. Метод приведенного градиента.

Методику решение задач выпуклого программирования с линейными ограничениями методом приведенного градиента впервые предложил Вульф в 1963 году. Данный метод получил название метод Франка–Вульфа или метод приведенного градиента. В дальнейшем данный метод распространили на решение задач нелинейного программирования с заданными нелинейными ограничениями.

Метод приведенного градиента (в англ. литературе «reduced gradient method») ˗ это итерационный численный метод решения оптимизационных задач, который позволяет определить «условный» экстремум целевой функции (минимальное или максимальное значение)

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

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

Метод приведенного градиента основан на сокращении размерности задачи с помощью представления всех переменных через множество зависимых (Y) и независимых (X) переменных. Количество зависимых (Y) переменных должно соответствовать размерности системы ограничений (1…m). В результате задача поиска экстремума функции переписывается следующим образом:

Система уравнений с ограничениями:

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

В зависимости от условия поиска (поиск максимального или минимального значения целевой функции) используется либо знак «+», либо знак «-».

Направление движение определяется градиентом функции через производные целевой функции по независимым (X) переменным. Следует отметить, что зависимые (Y) переменные целевой функции является неявной функцией от независимых (X) переменных в системе уравнений, которые определяют ограничения задачи. Запишем производную целевой функции по независимым (X) переменным с учетом неявной зависимости:

где производные в скобках определяются с учетом явной зависимости целевой функции от зависимых (Y) и независимых (X) переменных.

Производную определяем аналогично, используя систему уравнений с ограничениями

где производные в скобках определяются с учетом явной зависимости системы уравнений с ограничениями от зависимых (Y) и независимых (X) переменных.

В результате получили выражение для определения приведенного градиента функции:

В рассматриваемой задачи используется понятие приведённого градиента целевой функции , который определяется проекцией градиента целевой функции на плоскость проведенной к нелинейной поверхности, описываемой уравнениями с ограничениями задачи . Следует отметить, что градиент и антиградиент ортогонален поверхности проведенной к целевой функции f(x) в точке x. Идея градиентных методов основана на том, что антиградиент функции указывает направление наиболее быстрого ее убывания в окрестности точки , в которой он вычислен. Поэтому, если из некоторой текущей точки перемещаться в направлении антиградиента функции , то функция f(x) будет убывать.

Рис.1. График линий равного уровня функции f(x) с пояснением метода приведенного градиента

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

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

В дальнейшем на каждом шаге расчета определяются независимые (X) переменные, которые используются для определения зависимых (Y) переменных используя систему уравнений с ограничениями.

Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев):

— траектория поиска остается в малой окрестности текущей точки поиска:

— приращение целевой функции не меняется:

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

Методика расчета

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

Система уравнений с ограничениями:

2 шаг: Определение аналитических соотношений (в символьном виде) для вычисления приведенного градиента функции:

› Определение производной целевой функции по независимым переменным с учетом явной зависимости функции от независимых (X) и зависимых (Y) переменных

;

› Определение производной системы уравнений, записанной для ограничений, по независимым переменным с учетом явной зависимости функции от независимых (X) и зависимых (Y) переменных

;

3 шаг: Задаем начальное приближение для вектор-столбца независимых (X) переменных

Далее выполняется итерационный процесс.

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

5 шаг: Определяем значение приведенный градиент для текущего шага расчета.

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

7 шаг: определяем вектор-столбец независимых (X) переменных на следующем шаге расчета:

8 шаг: проверяем критерии останова итерационного процесса:

— траектория поиска остается в малой окрестности текущей точки поиска;

— приращение целевой функции не меняется;

— градиент целевой функции в точке локального минимума обращается в нуль.

В противном случае возвращаемся к «шагу 4» и продолжаем итерационный расчет.

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

Градиентные методы решения задач Стокса Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Голичев Иосиф Иосифович, Шарипов Тимур Рафаилевич, Лучникова Наталья Иосифовна

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Голичев Иосиф Иосифович, Шарипов Тимур Рафаилевич, Лучникова Наталья Иосифовна

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

Итерационный метод решения задачи Стокса

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

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

Периодические решения уравнений типа свертки с монотонной нелинейностью
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Gradient methods for solving Stokes problem

In the present paper we consider gradient type iterative methods for solving the Stokes problems in bounded regions. where the pressure serves as the control; they are obtained by reducing the problem to that of a variational type. In the differential form the proposed methods are very close to the algorithms in the Uzawa family. We construct consistent finite-difference algorithms and we present their approbation on the sequence of meshes for solving two-dimensional problem with a known analytic solution.

Текст научной работы на тему «Градиентные методы решения задач Стокса»

ISSN 2074-1871 Уфимский математический журнал. Том 8. № 2 (2016). С. 22-38.

ГРАДИЕНТНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ СТОКСА

И.И. ГОЛИЧЕВ, Т.Р. ШАРИПОВ, Н.И. ЛУЧНИКОВА

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

Ключевые слова: задача Стокса, оптимальное управление, градиентный метод, конечно-разностная схема.

Mathematics Subjects Classifications: 49M20, 35Q30, 93C05

1. Введение. В ограниченной области П С Rn (п =2, 3) с гладкой границей S G С2 (т.е. дважды непрерывно дифференцируемой) рассматривается задача Стокса

— vAv = f -Vp, v\s = 0, (1)

Согласно [1, гл. III, §5, теорема 2], в данных условиях задача (1)-(3) имеет единственное сильное решение v G H2(П) = (Н2(П))п, Vp G Х2(П). Здесь и далее используются стандартные обозначения для пространств Соболева Нг(П) = W2 (П), I = 1, 2 .

Будем рассматривать задачу (1) — (3) как обратную задачу к задаче (1), (3), в которой неизвестен градиент давления Vp, но задано дополнительное условие (2). Такую задачу можно сформулировать как эквивалентную исходной задачи оптимального управления:

J(u) = 1 lldivv(u)|||2(Q) ^ inf, u G G(fi),

где G(Q) = — градиентная составляющая в ортогональном разложении L2(H), а v(u) — решение системы

— vAv(u) = f- u, v(u)|s = 0. (4)

Тот факт, что решение многих задач математической физики можно свести к решению экстремальных задач, хорошо известен и широко используется. Из известных методов решения стационарной задачи Стокса в естественных переменных, имеющих в своей основе вариационные методыб отметим, прежде всего, методы Эрроу-Гурвица и Удзавы [2], дифференциальная форма которых, основанная на вариационной формулировке исходной задачи и теории двойственности [3], позволяет отделить процесс нахождения неизвестных, решая тем самым проблему отсутствия уравнения на давление. Рассматриваемый далее подход идейно близок методам из [4], [5].

I.I. Golichev, T.R. Sharipov, N.I. Luchnikova, Gradient methods for solving Stokes problem. © ГоличЕв И.И., Шарипов Т.Р., ЛучниковА Н.И. 2016.

Поступила 9 декабря 2015 г.

Наряду с задачей минимизации функционала J(u) в пространстве L2(H) также будем рассматривать задачи минимизации J(Vu) в пространствах Н^П) и ¿2(П), в которых за управление и берется само давление р. Поскольку градиенты функционала в этих случаях имеют различный вид, нам удобно их обозначить в соответствии с рассматриваемыми в работе задачами:

Задача I. Найти минимум функционала J0(u) = ||divv(u)|||2(q)/2 на множестве U0 = G(H), где v(u) — решение задачи (4).

Задача II. Найти минимум функционала J1(u) = ||divv(w)|||2(п)/2 на множестве U1 = , где v(u) — решение задачи

— и Av(u) = f -Vu, v(u)|s = 0. (5)

Задача III. Найти минимум функционала J2(u) = ||divv(w)|||2(П)/2 на множестве U2 = [и Е L2(Q) : (и, 1)l2(q) = 0>, где v(u) — обобщенное решение задачи (5).

Решение задач I-III будем искать методом проекции градиента [6], [7]:

uk+i = Pui (ик — акJ'(uk)), I = 0, 1, 2, (6)

где Риг — оператор проектирования на множество Ui, а J/ (ик) — градиент функционала Ji (ик) в точке ик 1.

В дальнейшем изложении будет показано, что

J2 (u) = — div w(u), (9)

где w(-) — сопряженное состояние системы (4), определяемое для всех задач как решение задачи

а p(w) определяется из ортогонального разложения вектора w(u) = Vp(w) + (р на градиентную и соленоидальную составляющие.

Для всех рассматриваемых задач найдем операторы проектирования и покажем, что задачи I и II эквивалентны.

Отметим, что в [4] рассмотрен аналог задачи II для обобщенной задачи Стокса, а для построения итерационного процесса использована общая теория сопряженных операторных уравнений. Тестовый расчет из этой работы используется нами для верификации расчета по формуле (6). К близким по структуре дифференциальных итерационных процессов настоящей работы приводит также метод неполного и полного расщепления граничных условий [5], где применяется теория граничных операторов Пуанкаре-Стеклова.

Далее везде через v(u) обозначается решение задачи (4) при f = 0, а через v(и) — решение задачи (5) при f =0.

2. Дифференцируемость функционала J0 (u). Обозначим через L оператор на множестве Н»^(П) = jz Е Н2(П) : z|s = 0> равенством L(z) = -vAz. Заметим, что область значений оператора L совпадает со всем пространством L2(П). Действительно, пусть f — произвольный элемент из L2(H); тогда задача

имеет, согласно [8, гл. II §7, теорема 7.1], единственное решение из Н2(П).

Используя второе энергетическое неравенство [8, гл. II, §6, формула (6.29)]2

1В целях обобщенной записи мы не выделяем жирными шрифтом вектор и для задачи I.

2Если область И выпуклая, то константа С1 равна единице.

с учетом очевидного для задачи (11) равенства ||Az||^2(п) = V ЧШНх^п), получаем используемую далее оценку

Пусть и и Ь — произвольные элементы из Щ. Учитывая определение оператора Ь, нетрудно видеть, что у(и + Ь) — у(и) = V(Ь), где V(Ь) = Ь-1 (—Ь). Тем самым,

Л (и + Ь) — Л (и) = 2 ||&У У(и + Ь)У|2(П) — 2 ||&у у(и) || ¿2 (п) =

= (ё1уу(и), а1у V(Ь))Ь2(П) + 1 ||ё1у V(Ь)||2(П). (14)

Преобразуем первое слагаемое в правой части последнего равенства с использованием интегрирования по частям, условия V(Ь)|^ = 0 и самосопряженности оператора Ь:

Таким образом, с учетом обозначения ‘(и) = L-1Vdiv v(u) тождество (14) принимает вид

Ми + Ь) — 7о(и) = (‘(и), Ь)£2(п) + 2Иу V(Ь)||2(п). (15)

Умножая левую и правую части (11) на z и интегрируя по частям, получаем соотноше-

откуда, и из неравенства Фридрихса

Из (17) и легко проверяемого неравенства

поэтому главная линейная часть приращения функционала

Покажем, что градиент ^(и) удовлетворяет условию Липшица. Пусть и(1), и(2) е ио, а ‘(1), ‘(2) — соответствующие им решения задачи (10). Заметим, что

Д'(1) — ‘(2)) = Vdiv v(u(1)) — Vdiv v(u(2)) = Vdiv V (и(1) — и(2)), поэтому из неравенств (16), (17) получаем

Учитывая то, что V(и(1) — и(2)) является решением уравнения (11) с правой частью Ш = —(и(1) — и(2)), для которого справедлива оценка (13), из (20) получаем:

Таким образом, доказана

Теорема 1. Пусть f е ^(П), где П — ограниченная область с границей Б е С2; тогда функционал (и) дифференцируем по Фреше на и0, его градиент определяется по формуле (7) и удовлетворяет условию Липшица с константой Ь0 = у/пс° С1 и-2, где со и с1 — константы из неравенств (16), (12).

3. Дифференцируемость функционала ,]1 (и) На множестве и1 введем метрику, эквивалентную метрике пространства Н ^П), по скалярному произведению (М)я01(п) = (Va, УЬ)£2(П).

Пусть и и к — произвольные элементы из 171. Аналогично (15) легко видеть, что

Зг(и + к) — Ш = (ы(и), Ук)^(п) + 1 Иу V(к)||2(п), V(к) = £-1(-Ук), (22)

причем, с учетом разложения вектора ы(и) = Рс(п)ы(и) + ф на градиентную и соленои-дальную (diy ф =0) составляющие,

Далее известно [9], что Vd € £2(П) = Ур, где р есть решение задачи Неймана

Из (22), (23), (24) следует:

31(и + к) — = (рЫ,к)Я0(п) + 1 ||diy ^ (к)||2(П)

где р(ы) — решение задачи

Аналогично (19) имеем оценку

откуда следует, что главная линейная часть приращения функционала 3\_ (и) определяется выражением (р(ы), к)Я0(п).

Покажем, что градиент (и) удовлетворяет условию Липшица. Пусть м(1) и м(2) принадлежат [Д, а ы(1) и ы(2) — соответствующие им решения задачи (10); тогда

Учитывая первое из неравенств (21), а также то, что V(м(1) — м(2)) является решением уравнения (11) с правой частью f = -У(и(1) — и(2)) и принимая во внимание оценку (13), получим

= Vп с0с1 и-2Ци(1 -и(2)ЦН0(п).

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Теорема 2. Пусть выполнены условия теоремы 1; тогда функционал /1(м) дифференцируем по Фреше на и1, его градиент определяется по формуле (8) и удовлетворяет, условию Липшица с константой Ь0.

Если в задачах I и II начальные приближения в итерационных процессах (6) при I = 0 и 1 = 1 связаны равенством и0 = Уи0, то щ = Уик при всех к = 1, 2.

Доказательство. Действительно, если щ = Уик, то с очевидностью v(ufc) = v(uk) и ) = ы(ик), поэтому

ик+1 = Р0(п) (ик — ак30(ик)) = ик — акРС(п)ы(ик) = = ик — акУрк(ик) = У(ик — акрк(ик)) = Уик+1. Таким образом, задачи I и II можно считать эквивалентными. □

4. Дифференцируемость функционала (и). Пусть и и к — произвольные элементы из и2. Для доказательства формулы (9) воспользоваться непосредственно, как в предыдущих разделах, интегрированием по частям здесь невозможно, поскольку не гарантирована принадлежность функций v(u) и ‘(и) пространству Н2(П). Воспользуемся предельным переходом; выберем последовательности , , содержащиеся в и1 так, что ип ^ и, кп ^ к в Ь2(П) при п ^ го.

На последовательностях , справедливо равенство (22):

■Ыип + кп) — Мип) = (‘(ип), Vкп)i2(п) + 1 ||divV(ЮЦ^п). (26)

Покажем, что div'(ип) ^ div'(и), divV(кп) ^ divV(к) при п ^ го в метрике Ь2(П).

Умножая уравнение (5) на V и интегрируя по частям, получим тождество

V Н^Ьф) = № ^2(П) + (Щ div

применение неравенств (18) и (16), к которому дает неравенство

Разность v(м(1)) — v(м(2)) = V(м(1) — м(2)) является решением задачи (5) при Ш =0 и и = м(1) — м(2). Тогда по неравенству (27)

Аналогичным образом, учитывая оценки (18), (28), получаем неравенство

Из двух последних оценок и неравенства (17) следует, что в соотношениях (26) можно перейти к пределу при п ^ го. В результате получаем, что

,]2(и + к) — Ми) = (w(u), ^^(п) + 1 Иу ^^(к)|^2(п) =

(— div ‘(и),к)Ь2(п) + 2 ИУ ^^ (к)||L2(П),

причем, с учетом оценок (18), (28)

Условие Липшица для 32 (и) устанавливается с применением неравенства (29):

Таким образом, справедлива следующая

Теорема 3. Пусть выполнены условия теоремы 2; тогда функционал 32(и) дифференцируем по Фреше на и2, его градиент определяется по формуле (9), удовлетворяет условию Липшица с константой Ь2 = и-2 п2.

5. Модифицированный градиентный метод наискорейшего спуска. Существуют различные способы выбора величины а^ (см. [6], [7]). Наиболее быструю сходимость дает метод наискорейшего спуска, в котором а^ определяется из условия

(ак)= тгп ¡к(а), Д (а) = Зг [Рщ(ик — а/г (ик))) , I = 0,1, 2. а>о \ /

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

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

Если ик € и1, то Рц1 (ик) = ик, поэтому, с учетом обозначения с1к = Ри1 (3 (щ)), имеем Д (а) = 3 (ик -a.dk) = Н^у v(ufc) — а ^^ (4 )|Ц2(П)/2 =

= v(uк)||2(п)/2 — аv(ик), v((1к))ь2(п) + а2|а1уv((1к)||2(п)/2, откуда точкой минимума является

а (6) принимает вид

ик+1 = ик — акАк. (32)

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

где 7 — параметр метода, а ак определяется как в методе наискорейшего спуска по формуле (31).

Поскольку предлагаемый метод может быть использован и в других задачах оптимизации, сформулируем утверждение в виде теоремы в абстрактном гильбертовом пространстве Н. Введем обозначения: J* = inf J (и), U С Н, U* = , С1,1 (U) —

множество дифференцируемых функционалов, градиент которых удовлетворяет условию Липшица.

Теорема 4. 1 Пусть U — выпуклое, замкнутое множество из гильбертового пространства Н с нормой |1 ■ ||, J (и) Е С1,1 (U) — выпуклый функционал (J* > —ю), множество U* непусто и ограничено, последовательность

El I J’ ) 11 2 ^ Ь1, (34)

тогда последовательность ^0 минимизирует функцию J (и) на U и слабо в Н сходится к множеству U*.

Доказательство. Обозначим p(u,,U*) = min ||и — v||; тогда по определению оператора

р2 (uk+1, U*) = ||ий+1 — Ри* (и^)||2 ^ Цик+1 — Ри* (ик)||2

1 Данная теорема с доказательством приведена в работе [10]. Однако утверждение о том, что в случае, если область и является подпространством или всем пространством, то условие (34) можно отбросить, доказано для конкретного функционала. В данной работе это установлено для любого выпуклого функционала 7(и) € С 1’1(и).

2При отсутствии в обозначении функционала J(и) нижнего индекса, аналогичное предполагается и в формуле (6).

= \\Pu (Uk — акJ’ (ик)) — Ри (Ри* (uk))\\2 ^ \\uk — акJ’ (ик) — Ри* (ик)\\2 =

= р2 (uk, U*) + ак \\J’ (uk)\\2 — 2ак (J’ (uk) ,Uk — Pu* (uk)). (36)

Воспользовавшись необходимым и достаточным условием выпуклости дифференцируемого функционала на выпуклом множестве U [6] J (u) — J (v) > (J’ (v) ,и — v) У и, v G U, полагая в нем v = Uk, и = Pjt (щ), получаем

(J’ (ик), Uk — Pu* (uk)) > J (uk) — J (Pu* (uk)) = J (uk) — J* > 0, (37)

откуда неравенство (36) принимает вид

p2 (uk+i, U*) — p2 (uk, U*) ^ a2k \\J’ (uk )\\2 .

Суммируя последнее неравенство от 0 до т — 1 (т > 0), и учитывая условие (34), получаем

Р2 (Um, и*) ^ ^ а2к \\J’ (Uk )\\2 + р2 (щ,и*) ^ 62 bi + Р2 (щ,и*). к=0

Таким образом, последовательность |мк>^=0 ограничена в Н, а из условия (34) следует, что lim, \\J’ (ик)\\ = 0; тогда из неравенства (37) следует, что последовательность (ик>^=0

минимизирует функционал J (и). Таким образом, последовательность (и к>те=0 — ограниченная и минимизирующая J (и) на U.

Обозначим через W множество выпуклых комбинаций последовательности (ик>^=0, то есть множество точек и, представимых в виде:

и = Y1 акUk, ак > 0, ак = 1. к=0 к=0

Используя [7, гл. 4, §1, теорема 5], легко показать, что W С U и поскольку U — замкнутое множество, замыкание W множества W также принадлежит U.

Последовательность (ик>те=0 минимизирует функцию J (и) на U и, следовательно, минимизирует J (и) на W. Из доказанного следует, что J*

W* = G U*. Из ограниченности последовательности (uk>^=0 следует ограниченность множества W. Согласно [6, гл. 1, §3, теорема 6] выпуклый, полуограниченный снизу функционал J (и) на ограниченном, выпуклом, замкнутом множестве U из рефлексивного банахового пространства имеет непустое множество точек минимума U*, и любая минимизирующая последовательность (ик>те=0 слабо сходится к U*. Из слабой сходимости последовательности (ик>^=0 к W* следует ее слабая сходимость к U*, теорема доказана. □

Замечание 1. Если множество W компактно, то имеет место сильная сходимость. Здесь можно воспользоваться [6, гл. 1 §3, теорема 1].

Замечание 2. Если U — подпространство гильбертового пространства Н, Pjj — оператор ортогонального проектирования на это подпространство, то Uk+i = Uk — Pu J’ (uk). В этом случае соотношение (36) можно записать в виде:

р2 (uk+i, U*) = р2 (ик, U*) + с?к \\PuJ’ (ик)\\2 — 2а,к (PuJ’ (щ) ,Uk — Pu* Ю).

Учитывая, что (PuJ’ (ик) ,ик — Ри* (ик)) = (J’ (ик) ,ик — Ри* (ик)), легко видеть, что утверждения теоремы справедливы, если вместо условия (34) выполняется условие

Теорема 5. Пусть и — подпространство или все гильбертово пространство Н, 3(и) € С 1,1 (и) — выпуклый функционал, множество и* непусто и ограничено, последовательность [ик>£=0 определена по формулам (33), (6), тогда последовательность [ик> минимизирует функционал 3(и) на и и слабо в Н сходится к множеству и*.

Доказательство. Покажем, что если 3(и) € С1,1 (и), где и либо подпространство, либо все пространство Н и параметр ак определяется по формулам (33), (30), то выполнено условие (38) и, следовательно, утверждения теоремы верны без условия (34). Для этого воспользуемся известным неравенством, справедливым для функций из С1,1 (и) (см. [7, гл. 2, §3, лемма 1]):

| 3 (и) — 3 (г;) — (3′ (г;) ,и — г;)| ^ Ь \\и -V||2 /2 Уи,у € и,

где Ь — константа Липшица для градиента 3 (и) функционала 3 (и). Полагая в нем V = ик, и = и^+1 = ик — аРи3′ (ик), получим

> а (/ (ик), Ри3′ (ик)) — а2Ь |Р^3′ (ик)||2 /2.

Учитывая, что оператор Ри — оператор ортогонального проектирования на подпространство, получаем, что (3 (ик), Ри3 (ик)) = \\Ри3′ (ик)\\, а из неравенства (39) следует:

3 (ик) — 3 ( <+1) >а (1 — аЬ/2) \\Ри3′ (ик)\\2 . (40)

Полагая а = 1/Ь, получаем

3 (ик) -3 «+0 > \\Ри3′ (ик)\\2 /(2Ь).

Предположим, что ак ^7, тогда ак = ак и поэтому при а = 1/Ь справедливы неравенства

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

3 (ик) — 3 (ик+1) > 3 (ик) — 3 «+1) > Ри3 (ик) /(2Ь). (41)

Таким образом, учитывая неравенства (40), (41), в любом случае получаем оценку

3 (ик) — 3 (ик+1) > с Ри3 (ик) ,

где с = тгп [7/2, 1/(2Ь)].

Из последней оценки следует, что последовательность [ 3 (ик )>^0 монотонно убывает, ^ / 2

ряд £ | | Ри3 (ик)|| сходится и имеет место искомая оценка

| Ри3 (ик) ^ с-1 (3 (ик) -3*).

Таким образом, выполнено условие (38), и теорема доказана. □

6. Итерационные процессы. Теорема сходимости. С учетом теоремы 2 далее будем говорить только о задачах I = 1, 2. Покажем, что функционалы 3\(и) удовлетворяют всем условиям теоремы 5.

Нетрудно убедиться, что функционалы 3 I выпуклы. Действительно при У а Е [0,1] и

3[(аи + (1 — а)ь) = ||а + (1 — а) у(^) |||2(П)

= а2||&уУ(И)||2(П) + (1 — а?ИГу^^(П) + М1 — а) (аГуv(u), аГу^^(П) = а^гуу(и)^^(П) + (1 — аОИ^^^(П) — а(1 — аОИ^у(и) — ^^(П) ^

Выполнение условия принадлежности функционалов 3\ классу С1,1 (и) следует из результатов разделов 2, 3, 3%* = т/ 3%(и) = 0 > — го, множества и^* =

состоят из одной точки и* = р, где р есть искомое давление.

Из теоремы 5, таким образом, следует, что последовательности £=0, определенные соотношениями (6), (31), (33) при I = 1, 2 слабо сходятся в соответствующих пространствах Н^П) и Ь2(П) при любом начальном приближении.

Теорема 6. Пусть f Е Х2(П), 5 Е С2; тогда последовательность ^=0, определенная формулами (6), (33), где I = 1, 2, при любом начальном приближении и0 Е сходится к и* = р слабо в Н1 (П) и при I = 1 — сильно в Ь2(П). Последовательности ^0 при I = 1, 2 сильно в Н(П) сходятся к V, где р и V — решение задачи (1)-(3).

Доказательство. Как было показано, первое утверждение сразу следует из теоремы 5. Справедливость второго утверждения вытекает из следующих соображений. Известно (см., например, [1, гл. 1, §1, лемма 8]), что если область П ограничена и ее граница кусочно-гладкая, то Н 1(П) вкладывается компактно в Ь2(П) (т.е. ограниченное в Н 1(П) множество компактно в Ь2(П)). Из компактности и слабой сходимости в Н (П) последовательности д= следует ее сильная сходимость в Х2(П).

Заметим далее, что разность — V, где = ч(ик), а V — решение задачи (1)-(3), является решением задачи

—и А (V к — V) = —V (ик — р) , (V к — V) ^ = 0.

Умножая последнее уравнение на V к — V и интегрируя по частям, получаем

№(Ук — у)||£2(п) = — р-1^(ик — р), V к — у)£2(п) = «-1(ик — Р, Ук)ь2(П). (42)

поэтому из соотношений (42) следует справедливость последнего утверждения теоремы.

Установленная теорема сходимости позволяет сформулировать итерационные процессы в дифференциальной форме для решения задачи (1)-(3). Алгоритм для 31(и)

1. Выбрать начальное и0 Е и1, например, и0 = 0.

2. Найти скорость Ук (ик) как решение векторной задачи Дирихле (5).

3. Найти сопряженное состояние Wк(ик) из решения векторной задачи Дирихле (10).

4. Определить Зк = Ри1 (р(‘к)), где р(‘к) — решение скалярной задачи Неймана (25).

5. Определить Vк(Зк) из решения векторной задачи Дирихле (5) при < = 0.

6. Вычислить ак по формулам (31), (33) для найденных Ук(ик), Ук(Зк).

7. Пересчитать управление ик+1 по формуле (32) для найденных ак, Зк и перейти к шагу 2.

Алгоритм для 32(и) идентичен алгоритму 31(и) за исключением шага 4:

Операторы проектирования для обоих алгоритмов вычисляются по формуле

Рщ (и)=и — (щ 1)мп) Уи € Щ, / = 1, 2.

7. Комбинированный градиентный метод. Состоит в том, что попеременно делается несколько шагов первого градиентного метода (т.е. 3′(и) = 31 (и)), а затем несколько шагов второго (т.е. 3′(и) = 32(и)). Расчеты ниже показывают, что комбинирование методов обеспечивает ускорение сходимости. Этот факт имеет простое объяснение. Функционалы 31 (и), 32(и) достигают минимума через обращение в нуль в точке и* = р тогда и только тогда, когда сопряженное состояние ш(и*) = 0. Действительно, если ш(ик) = 0, то в разложении ш(ик) на градиентную и соленоидальную составляющие, по крайней мере, хотя бы одна часть не равна нулю. Пусть, например, не равна нулю градиентная часть ш(ик), тогда спуск по градиенту 31(ик) обеспечит уменьшение функционала. Комбинированный метод состоит в последовательном переходе от использования одного градиента на использование другого, как только величина \\3/(ик)\\ ( 1 = 1, 2) станет меньше заданной величины.

Заметим, что области определений функционалов и (1 = 1, 2) различные, поэтому требуется убедиться, что по окончании использования одного метода градиентного спуска мы получаем управление ик, принадлежащее области определения другого функционала. Это условие будет выполнено, если начальное приближение и0 € и1. Чтобы в этом убедиться, достаточно показать, что если и0 € Н 1(П), то 3’2(и0) € Н 1(П). Действительно, если и0 € Н 1(П), то при условии гладкости границы Б € С2 в уравнении (5) правая часть f — Уи0 € Х2(П), поэтому его решение у(и0) € Н (П). Откуда следует, что правая часть уравнения (10) принадлежит Х2(П), поэтому его решение ш(и0) € Н2(П) и, следовательно, 32(и0) = — ^у ш(и0) € Н (П). Таким образом, все члены последовательности ик, полученные комбинированным методом, содержатся в и2.

Если применение градиента 32 (и) заканчивается, начиная с некоторого номера итерационного процесса, то, в соответствии с теоремой 6, итерационный процесс сходится слабо в Н 1(П) и сильно в Ь2 (П). В противном случае можно доказать слабую сходимость итерационного процесса в £2(П). Последовательности векторов скорости [\(ик)>£=0 в силу теоремы 6 сильно сходятся в пространстве Н^(П).

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

Условие на гладкость границы области Б € С2 используется лишь для применения второго энергетического неравенства (12). Однако, как отмечается в [8], условие на границу можно значительно ослабить, и этим ослабленным условиям удовлетворяют, например, любой многогранник или произвольная выпуклая область.

Для решения задачи Стокса с неоднородными граничными условиями

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

управлению и. Если управлению и дается приращение к, то приращение вектора скорости v(Vh) = v(V(u + к)) — v(Vи) определяется решением однородной краевой задачи как и в ранее рассмотренных случаях. Теперь нетрудно видеть, что выкладки, приведенные при доказательстве теорем 1, 2, 3, остаются без изменений.

Таким образом, функционалы 31 (I = 1, 2), рассматриваемые в пространствах Н 1(П) и Ь2(П) и в случае неоднородных краевых условий, дифференцируемы и удовлетворяют условию Липшица, кроме того, сохраняется формула (31) для определения параметров ®к.

Для обоснования сходимости последовательности ^=0, построенных указанными выше методами, необходимо показать, что множество точек минимума функционалов 3\ непусто и ограничено. Для этого достаточно убедиться, что решение задачи (44)-(46) существует.

9. Конечно-разностная аппроксимация. Для построения сеточных аналогов дифференциальных итерационных процессов из раздела 5 недостаточно воспользоваться произвольными аппроксимациями операторов ^у и V и гарантировать при этом сходимость, с чем и столкнулись авторы при численном моделировании. Однако, если сначала аппроксимировать исходную задачу (1)-(3) в конечномерных пространствах Соболева и построить для этой задачи градиентный метод аналогично рассмотренному выше дифференциальному случаю, удается получить сходящийся сеточный итерационный процесс, для которого справедлива теорема 6.

Как и в работе [11] будем рассматривать двумерную прямоугольную область Пн = (0, /1) х (0,12) и узловую равномерную неразнесенную сетку = с границей Бн (состоит из множества граничных узлов, за исключением угловых точек). Здесь ка = Iа/(Ыа + 1) — равномерный шаг, а К — число внутренних узлов сетки по направлению а = 1, 2. В дальнейшем ограничимся случаем равномерной сетки N = К2 = N в квадрате /1 = 12 = I (к1 = к2 = к).

Определим скалярное произведение в конечномерном пространстве Ь2(Пн):

(у, ^ Ь2Ш = к2 Е у™ + Т Е У™ = к2 Е Е Уч

Уí,N+1 +1 + Е У0,з20,] + Е УN+1,jzN+1, з I

í=1 í=1 3 = 1 3 = 1 )

где у^ = у(х^э), г^у = г(х^3).

Под согласованной аппроксимацией операторов ^Ун и Vh понимается сохранение дифференциального свойства интегрирования по частям:

(VhP, ^(Пн) = -(Р, (Пн) Vv € Н01(Пн). (47)

Соотношению (47) удовлетворяют направленные разности первого порядка [11]:

diУhVгз = ^ , í-lJ + íJ , íJ-1, г = 1 . К + 1, = 1 . К + 1, к к

VhPг,з = (^+1″к- 1КЗ , ^ ) , . = 0 . К, 3=0 . К.

Очевидно, что в этом случае оператор -Дн = — divhVh есть стандартный пятиточечный разностный шаблон для задачи Дирихле [12].

Таким образом, сеточным аналогом задачи (1)-(3) является задача

для которой выпишем итерационные процессы из раздела 5 в удобном при программной реализации виде. При этом вместо 31(и) будем теперь рассматривать 30(и). Алгоритм для /0(м)

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *