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

11/09/2018

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

Использование множителя Лагранжа для глобального ограничения

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

E[u(x)] = \int_a^b u(x)\sqrt{1+u^{\prime}(x)^2}dx

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

\int_a^b \sqrt{1+u^{\prime}(x)^2}dx = l

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

\mathcal{L}[u(x),\lambda] = \int_a^b u(x)\sqrt{1+u^{\prime}(x)^2}dx + \lambda \left[\int_a^b \sqrt{1+u^{\prime}(x)^2}dx – l \right]

Вспомним, что для одного глобального ограничения добавляется один множитель Лагранжа, а не поле множителей, как в случае распределенных условий (в каждой точке). Давайте теперь обобщим задачу и введем обозначения F = u(x)\sqrt{1+u^{\prime}(x)^2}, \qquad g = \sqrt{1+u^{\prime}(x)^2}.

Выведем условия экстремума первого порядка, приравняв нулю первые вариационные производные \mathcal{L}[u(x),\lambda] по переменным u(x) и \lambda. Вариацонные производные более подробно описаны в первой части этой серии статей.

\int_a^b \left[\frac{\partial F}{\partial u}\hat{u} + \frac{\partial F}{\partial u'}\hat{u'}\right]dx + \lambda\int_a^b \left[\frac{\partial g}{\partial u}\hat{u} + \frac{\partial g}{\partial u'}\hat{u'}\right]dx=0, \quad \forall \hat{u},
\hat{\lambda}\left[\int_a^b g(x,u,u')dx – l \right]=0, \quad \forall \hat{\lambda}.

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

На концах кабеля также добавляются два граничных условия Дирихле в виде условий со своими собственными множителями Лагранжа. Во второй части мы показали, как это сделать. Теперь давайте сконцентрируемся на реализации глобального ограничения. Для фиксации концов мы будем использовать встроенный узел Dirichlet Boundary Condition (Граничное условие Дирихле).

Снимок экрана с настройками узла Weak Contributions (Слагаемые в слабой форме) в COMSOL Multiphysics.
Снимок экрана с настройками узла Global Equations (Глобальные уравнения) в COMSOL Multiphysics.

Реализация глобального ограничения.

Обратите внимание, что приведенная выше слабая форма не содержит члена \frac{\partial g}{\partial u}, поскольку g является функцией u^{\prime}, но не u.

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

Одним из распространенных способов преодоления этой трудности является использование решения задачи безусловной оптимизации в качестве начального приближения для решения задачи условной оптимизации. В программном пакете COMSOL Multiphysics® это можно сделать, добавив два шага в рамках одного исследования и убрав ограничения в первом исследовании. Решение, полученное на первом шаге, будет автоматически использовано в качестве исходных данных на втором шаге.

Снимок экрана с настройками узла Stationary Study (Стационарное исследование) в COMSOL Multiphysics.
Решение задачи безусловной оптимизации используется как начальное приближение в задаче условной оптимизации.

График для сравнения кабеля ограниченной длины с кабелем неограниченной длины.
Подвесной кабель ограниченной длины.

Вычислив intop1(g) в меню Results (Результаты) > Derived Values (Производные значения) > Global Evaluation (Глобальное вычисление), мы увидим, что длина равна точно 10,5 м. Значение множителя Лагранжа также можно вывести с помощью узла Global Evaluation (Глобальное вычисление). По физическому смыслу множитель Лагранжа связан с растягивающим усилием, которое необходимо приложить для сохранения требуемой длины.

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

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

Метод штрафов

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

E_{\mu}[u(x)] = \int_a^b F(x,u,u^{\prime})dx + \frac{\mu}{2} \left[\int_a^b g(x,u,u')dx – l \right]^2.

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

Здесь штрафной коэффициент мы выбираем сами, поэтому единственным неизвестным является u(x). Следовательно, условие экстремума первого порядка принимает вид

\int_a^b \left[\frac{\partial F}{\partial u}\hat{u}+\frac{\partial F}{\partial u'}\hat{u'}\right]dx + \mu \left[\int_a^b g(x,u,u')dx – l \right]\int_a^b \left[\frac{\partial g}{\partial u}\hat{u}+\frac{\partial g}{\partial u'}\hat{u'}\right]dx, \qquad \forall \hat{u}.

Этот подход можно рассматривать как аппроксимацию множителя Лагранжа в виде произведения константы пропорциональности и отклонения от ограничения.

\lambda \approx \mu \left[\int_a^b g(x,u,u')dx – l \right].

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

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

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

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

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

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

Вспомогательный параметрический анализ для штрафного параметра

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

Приблизительный множитель Лагранжа содержит произведение штрафного параметра и отклонения от заданного ограничения. При этом, если отклонение от условия мало, можно использовать большой штрафной параметр, и задача не станет плохо обусловленной. Таким образом, если начать с пробного решения, в котором ограничение выполняется даже приблизительно, можно использовать более высокие штрафные коэффициенты (по сравнению с пробным решением, которое значительно отклоняется от ограничения). Эту стратегию можно легко реализовать в COMSOL Multiphysics, добавив шаг исследования Auxiliary Sweep (Вспомогательный параметрический анализ) по параметру штрафа.

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

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

График в COMSOL Multiphysics для сравнения решений, полученных методом штрафов и методом множителей Лагранжа.
Сравнение решений, полученных методом штрафов и методом множителей Лагранжа.

Расширенный метод множителей Лагранжа

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

Рассмотрим задачу

\textrm{minimize } f(x), \quad \textrm{при условии } g(x)=0.

Метод множителя Лагранжа работает для задачи без ограничений

\mathcal{L}(x,\lambda) = f(x) + \lambda g(x),

в то время как для метода штрафов используется

E_{\mu}(x) = f(x) + \frac{\mu}{2}g^2(x).

В расширенном методе Лагранжа применяются слагаемые обоих типов.

E_{\mu,\lambda}(x) = f(x) + \lambda^* g(x) + \frac{\mu}{2}g^2(x).

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

Условие экстремума первого порядка для расширенного метода Лагранжа является

\frac{d}{dx} E_{\mu,\lambda} = \frac{df}{dx} + \lambda^* \frac{dg}{dx} +\mu g \frac{dg}{dx} = \frac{df}{dx} + (\lambda^* +\mu g )\frac{dg}{dx} = 0.

Если сравнить его с условием экстремума в методе множителя Лагранжа, можно увидеть, что уточненное приближение для множителя равно

\lambda = \lambda^* +\mu g .

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

\int_a^b \left[\frac{\partial F}{\partial u}\hat{u}+\frac{\partial F}{\partial u'}\hat{u'}\right]dx + \left(\lambda_k + \mu \left[\int_a^b g(x,u,u')dx – l \right]\right) \int_a^b \left[\frac{\partial g}{\partial u}\hat{u}+\frac{\partial g}{\partial u'}\hat{u'}\right]dx, \qquad \forall \hat{u}.
\lambda_{k+1}=\lambda_k + \mu \left[\int_a^b g(x,u,u')dx – l \right]

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

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

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

Намеренное нарушение ограничения

Иногда необходимо намеренно нарушить условия. Скажем, в показанном выше примере требуется установить условие на длину кабеля, равную 10,04 м. Это физически невозможно, поскольку наименьшее расстояние (по прямой) между опорами составляет 10,05 м.

Метод множителя Лагранжа требует точного выполнения условия, поэтому возникает ошибка сходимости. Однако иногда нас может устроить и неточное решение, пусть даже с нарушением ограничения. В таких случаях — с противоречивыми или избыточными условиями — метод множителя Лагранжа, естественно, не сходится. Однако можно использовать методы приближенного выполнения условий, например, метод штрафов и расширенный метод Лагранжа, чтобы ослабить ограничения и получить «близкое» решение. Например, в модуле Динамика многотельных систем реализован метод штрафов для соединений, благодаря которому модели менее чувствительны к избыточным ограничениям.

В следующих статьях

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

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

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

Свяжитесь с COMSOL, чтобы узнать подробности о моделировании на основе уравнений в COMSOL Multiphysics. Нажмите кнопку ниже.

Изучите другие статьи из серии о вариационных задачах и условиях


Комментарии (0)

Оставить комментарий
Войти | Регистрация
Загрузка...
РУБРИКАТОР БЛОГА COMSOL
РУБРИКИ
ТЕГИ