Квазиньютоновские (град) методы с нелинейными ограничениями

[ilghiz]

Добрый день,

вопрос возник после обсуждения topic139067.html

Дана функция $f(x_1,\dots,x_n) \in \R$, для которой можно быстро посчитать градиент в заданной точке (да хотя бы Бауэром-Штрассеном) и хочется найти минимум этой функции.

Но на минимум наложено одно или несколько ограничений, или в виде тихоновских регуляризаторов или в виде лагранжевых множителей, то есть имеется набор $g_i(x_1,\dots,x_n), ~~ i=1, \dots, I$, для которых тоже есть хорошо вычисляемые градиенты, что нам надо найти

$$\min_{x_1, \dots, x_n} f(x_1,\dots,x_n) + \sum_{i=1}^I \alpha_i g_i(x_1,\dots,x_n) \eqno (1)$$

где $\alpha_i$ либо лагранжевы множители, либо тихоновские регуляризаторы.

Одним из таких примеров можно рассмотреть параметры $x_1,\dots,x_n$, которые задают границу какой-либо области (например лопасть лопатки турбины) а функция - суть величина тяги, вычисленная из решения уравнений Навье-Стокса с такой турбиной, или еще чего похожего. В этом случае, набор $g_i$ - это какие-то технологические ограничения, например, на гладкость, какие-то углы, или еще чего.

Если есть свой решатель (того же Навье-Стокса) написать градиент не составляет большого труда (или прикрутить туда Бауера-Штрассена), а число варьируемых параметров $x_1,\dots,x_n$ достаточно высок, чтобы задумываться об использовании симплекс методов.

Если бы $g_i$ не было, то вроде тут гадать нечего, LM-BFGS более-менее самое то. Но вот применить BFGS вместе с ограничениями очень затруднительно.

Понятно можно минимизировать (1), выбирая вначале $\alpha_i$ маленькими, и постепенно их увеличивая. Будем исходить из того, что выразить какие-то переменные через другие, сократив размерность и убирая лагранжевые множители нельзя.

Как сейчас принято такое решать и как такое называется, чтобы статьи почитать и сходимость поизучать, поделитесь, пожалуйста, ссылками и соображениями?

Спасибо!

[feedinglight]

Вопрос в том как задать краевые условия в уравнениях Навье-Стокса? Ну пусть есть сопряжённая задача: Навье-Стокса для жидкости и механика для лопатки. Осталось понять, что и как передаётся через эту границу между двумя решателями. В крайнем случае можно просто решать по-очереди механику и Стокса, пока итерации не сойдутся(Из Стокса как-нибудь вычислить давления на лопатку, подставить в механику, откуда получить скорость лопатки, подставить её как краевое в Стокса и т.д.). В простейшем случае турбина задаёт скорости, они в качестве краевых подставляются в Стокса и решается задача, не?
В идеале может получиться ввести дополнительные переменные, которые определяют контактную границу и входят в механику и в Стокса(типа прям совсем двустороннее сопряжение), но из сабжа вообще ничего не понял, плюс это наверно не всегда просто/можно сделать(люди не просто так платят за ансисы), гуглите сопряжённые задачи. Ещё есть некие [квази]вариационные неравенства, о них совсем ничего не знаю.
Ну а по уравнению $(1)$ не понятно, где тут нелинейные ограничения и чем мешают $g_i$, если для них легко вычисляются градиенты.
(сообщение написано просто для поддержания темы)

[ilghiz]

Спасибо большое, за ответ!

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

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

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

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

Ну и на последок - да, можно описать поверхность этой лопатки мелкой-мелкой сеточкой, на пару миллионов конечных элементов, и иметь функцию $f$ как раз зависимую от пары миллионов параметров этой конечноэлементной дискретизации. А можно взять 5-10 точек и провести очень грубо по ним сетку. В случае с парой миллионов конечных элементов мы зависним на итерациях квазитньютона, который при этом числе неизвестных даже теоретически не сойдется за меньше сотни итераций (мы же еще помним, что каждая итерация - это полное решение Больцманом всей этой задачи). В случае с 5-10 точек скорей всего геометрия этой лопатки будет на столько отвратная, что и сходиться будем плохо, и результат на выброс будет.

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

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

[vpb]

ilghiz в сообщении #1442140 писал(а):

Бауэром-Штрассеном

Правильно Баур, без "э" или "е".

-- 03.03.2020, 17:01 --

ilghiz в сообщении #1442140 писал(а):

как такое называется,

Я бы назвал это "нелинейная оптимизация с ограничениями", "constrained nonlinear optimization". Есть еще такой термин "математическое программирование" (здесь "программирование" должно означать не создание программ для компьютера, а планирование в экономике. Отсюда и термин "линейное программирование", кстати). Насчет литературы счас прикину (сам не специалист, если чо, но кое о чем в курсе).

[vpb]

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

Сухарев, Тимохов, Федоров, Курс методов оптимизации.
Деннис, Шнабель, Численные методы безусловной оптимизации
и решения нелинейных уравнений.
Поляк, Введение в оптимизацию
Ортега, Рейнболдт, Итерационные методы решения систем уравнений
со многими неизвестными
Нестеров, Введение в выпуклую оптимизацию
Рокафеллар, Выпуклый анализ
Аоки, Введение в методы оптимизации
Васильев, Методы оптимизации
Карманов, Математическое программирование
Conn, Gould, Toint, Trust region methods
Floudas, Pardalos (eds), Encyclopedia of optimization
Nocedal, Wright, Numerical optimization
Солодовников, Системы линейных неравенств

И еще пара книг, которые я не смотрел, но которые могут быть Вам полезны
Фиакко, Маккормик, Методы последовательной безусловной минимизации
Kelley, Iterative methods for optimization

(и еще глава про оптимизацию в Бахвалове).

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

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