Строительные исследования
страница - 0
Опыт декомпозиции метода конечных элементов с использованием теории структурированных оптимизационных задач
А. С. Величко (vandre@dvo.ru), Е. А. Нурминский (nurmi@dvo.ru)
Институт Автоматики и Процессов Управления ДВО РАН
Аннотация
Большие и особенно сверхбольшие системы уравнений, порождаемые сложными задачами моделирования, как правило, имеют структурные особенности, предоставляющие определенные возможности для "крупнозернистой" декомпозиции задачи на относительно слабо связанные блоки. В данной работе подобные задачи рассматриваются как специальный класс структурированных задач линейного программирования, для решения которых применяется общий метод декомпозиции, модифицированный на случай неразрешимости подзадач. В качестве примера рассмотрено решение структурированной системы линейных уравнений метода конечных элементов, описывающей стационарное распределение температур в области сложной формы.
Введение
Большие и особенно сверхбольшие системы уравнений, порождаемые сложными задачами моделирования, как правило, имеют структурные особенности, предоставляющие определенные возможности для "крупнозернистой" декомпозиции задачи на относительно слабо связанные блоки. Такие структурные особенности могут быть связаны как с пространственными спецификациями задачи (области сложной формы с относительно узкими сечениями в определенных местах), так и с динамикой (зависимость будущего поведения системы только от текущего состояния или небольшой предыстории, разделением по физическим процессам и т.д.).
Рассматривая эти задачи как специальный класс экстремальных задач с возможно тривиальным оптимизируемым функционалом, мы приобретаем возможность использовать методы декомпозиции экстремальных задач при решении задач математического моделирования [8]. При этом возникает, однако, ряд теоретических и практических вычислительных проблем, связанных с неизбежной вырожденностью подзадач, формулируемых в ходе процесса декомпозиции. Исследование этих проблем, модификация алгоритма декомпозиции с учетом этого обстоятельства, программная реализация и вычислительные эксперименты представляют собой предмет настоящей работы.
Оценивая состояние теории и практики методов декомпозиции можно отметить, что особенно полно развита теория декомпозиции задач линейного программирования, где ее применение может существенно уменьшить вычислительные затраты [6], [7]. В алгоритмах типа симплекс-метода для решения задач линейного программирования с п переменными и т ограничениями пессемистические оценки обьема вычислений имеют экспоненциальный порядок вида 0(ап+т) стандартных операций, где а > 1. В последние годы большое внимание уделялось развитию несимплексных алгоритмов с полиномиальной сложностью, для которых такие оценки имеют вид 0(пк), где показатель степени обычно порядка 5. Однако, эта оценка предсказывает для практических задач, где п ~ 104, также весьма значительный объем вычислений. Кроме этого в этих алгоритмах существенным являются и требования к памяти ЭВМ (порядка иг).
Все вышеперечисленное оправдывает дальнейшую разработку алгоритмов решения задачи задач линейного программирования большого обьема, в частности, для задач с ограничениями специального вида, для которых удается предложить более экономные алгоритмы решения.
В реальных прикладных задачах матрица может иметь нескольких тысяч строк-столбцов. Как правило, они имеют специальную структуру со сравнительно небольшим количеством связывающих переменных или ограничений. В этом случае перспективным направлением развития алгоритмов решения таких задач являются схемы декомпозиции, одному из вариантов которых и посвящена настоящая работа.
1 Постановка задачи
В качестве основной модели структурированной оптимизационной задачи рассмотрим двублочную проблему следующего вида:
min cAzA + cBzB(1)
AAzA+ BAx < dA(2)
-hs--is + BBx < dB(3)
zA>0, zB>0, x> 0,(4)
где zA, zB - векторы переменных задачи размерностей NA и NB соответственно, х -вектор связывающих переменных задачи размерности Nx, сА, св - векторы длины NA и NB соответственно, АА, Ав, ВА, Вв - матрицы соответствующих размерностей, dA -вектор длины КА, dB - вектор длины Кв.
При фиксированном х эта задача распадается на два независимых блока, что и будет в основном использовано для развития специальных алгоритмов.
Без выделения блоков задача (1)-( 1) запишется как min г; при Az < d, z > 0, где
z = (zA,zB,x), с = (cA,cB,0), d = {dA, dB),
A=( Aa ° Ba ) \ 0 AB BB )
что демонстрирует специфику задачи. Неформальным требованием является небольшое число связывающих переменных, такие задачи хорошо приспособлены для применения принципов декомпозиции.
Одним из источников задач большой размерности являются проблемы вычислительной математической физики. Использование экстремальных принципов в таких задачах имеет давнюю историю и составляет основу как многих теоретических результатов, так и вычислительных подходов. В классическом варианте применение вариационных принципов ведет к формулировке необходимых условий экстремума, что переходит в вычислительную форму задачи, каковой является система уравнений большой размерности. Такая система зачастую имеет ряд особенностей типа ленточной структуры и решается специальными методами [1].
Вместе с тем, такую систему уравнений можно рассматривать как ограничения экстремальной задачи с тривиальной целевой функцией и применить для ее решения развиваемые в математическом программировании подходы. Мы продемонстрируем этот подход на примере метода конечных элементов [3].
Система уравнений метода конечных элементов с точки зрения теории оптимизации является вырожденной экстремальной задачей с тривиальным функционалом, где основная и единственная проблема заключается в удовлетворении ограничений. Тем не менее мы пока рассмотрим общий случай структурированной двублочной задачи с возможно ненулевым функционалом.
Введя функции
fA(x) = miiir л; л.
AAzA <dA- BAx zA > 0, x > 0
получим эквивалентную (1)-( 1) задачу:
mm{fA{x) + fB{x)}.(6)
Как известно, fA(x) и fB(х) - выпуклые и кусочно-линейные функции [4]. Введем для них сопряженные функции hA(p) и hB(p):
Ьа(р) = fA{x) = тах{рх - fA(x)}, hB(p) = f*B{x) = тах{рх - fB(x)}.
fB(x)= min cBzB,
-1.1-7; < dB - BBx ~is > 0. x >0
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6]