Все выпуски

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

$$ \text{Argmin}_{x\in X}{\langle p,\,x \rangle} $$

для заданного вектора $p \in \mathbb{R}^n$. Существует целый ряд методов условного градиента, имеющих линейную скорость сходимости в сильно выпуклом случае. Однако во всех этих методах в оценку скорости сходимости входит размерность задачи, которая в современных приложениях может быть очень большой. В данной работе доказывается, что в сильно выпуклом случае скорость сходимости методов условного градиента в лучшем случае зависит от размерности задачи $n$ как $\widetilde{\Omega}\left(\!\sqrt{n}\right)$. Таким образом, методы условного градиента могут оказаться неэффективными для решения сильно выпуклых оптимизационных задач больших размерностей.

Отдельно рассматривается приложение методов условного градиента к задачам минимизации квадратичной формы. Уже была доказана эффективность метода Франк – Вульфа для решения задачи квадратичной оптимизации в выпуклом случае на симплексе (PageRank). Данная работа показывает, что использование методов условного градиента для минимизации квадратичной формы в сильно выпуклом случае малоэффективно из-за наличия размерности в оценке скорости сходимости этих методов. Поэтому рассматривается метод рестартов условного градиента (Shrinking Conditional Gradient). Его отличие от методов условного градиента заключается в том, что в нем используется модифицированный линейный минимизационный оракул, который для заданного вектора $p \in \mathbb{R}^n$ вычисляет решение задачи $$ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. $$ В оценку скорости сходимости такого алгоритма размерность уже не входит. С помощью рестартов метода условного градиента получена сложность (число арифметических операций) минимизации квадратичной формы на $\infty$-шаре. Полученная оценка работы метода сравнима со сложностью градиентного метода.

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

В статье приводятся результаты верификационных расчетов в программном комплексе вычислительной аэро-, гидродинамики FlowVision характеристик сверхзвуковых турбулентных струй. Численное моделирование в статье охватывает несколько известных экспериментов по исследованию сверхзвуковых струй, находящихся в свободном доступе. Представленные тестовые случаи включают в себя тесты Сейнера с числом Маха на срезе $M = 2$ при расчетном $(n = 1)$ и нерасчетном $(n = 1.47)$ истечении из сопла в широком диапазоне температур газа. В работе также проведен численный эксперимент по распространению сверхзвуковой струи в спутном сверхзвуковом потоке $M = 2.2$. Для данного теста заданы параметры, определенные в эксперименте Putnam: степень понижения давления в сопле $\mathrm{NPR} = 8.12$ и полная температура $T = 317 \, \mathrm{K}$.

Показано сравнение расчетов FlowVision с экспериментальными и полученными в других расчетных кодах данными. Наилучшее совпадение с экспериментом Сейнера среди рассмотренных моделей турбулентности получено при использовании стандартной $k–\varepsilon$ модели турбулентности с установленной поправкой на сжимаемость по модели Wilcox. Достигнуто согласование с экспериментальными данными на дальнем следе до 7 % по скорости потока на оси сопла. Для струи в спутном потоке расчетная характеристика (число Маха) отличается на 3 % от экспериментальной.

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

Влияние применяемых моделей турбулентности показано на примере расчета теста Сейнера. SST-модель турбулентности, применяемая в FlowVision, существенно занижает скорость на оси сопла, для расчета струй данная модель не рекомендуется даже для предварительных оценок. Стандартная $k–\varepsilon$ модель без учета сжимаемости также несколько занижает скорость газа. Модель турбулентности KEFV, разработанная для FlowVision, показывает хорошее согласование и несколько завышает «дальнобойность» струи. И наилучшее совпадение с экспериментом по исследуемым характеристикам турбулентных струй получено при расчетах на стандартной $k–\varepsilon$ модели с учетом сжимаемости, соответствующей модели Wilcox. Представленная методика может быть взята за основу при моделировании истечения из сверхзвуковых сопел более сложной геометрии.

Статья носит методический характер и посвящена решению трех классических уравнений математической физики (Лапласа, диффузии и волнового) простейшими численными схемами в формулировке клеточных автоматов (КА). Особое внимание уделяется законам сохранения вещества и неприятному эффекту избыточной гексагональной симметрии (ИГС).

Делается вывод о том, что по сравнению с классическими конечно-разностными методами, хотя локальная функция перехода (ЛФП) КА терминологически эквивалентна шаблону вычислительной двухслоевой явной схемы, различие состоит в замене матричных (direct) методов (например, метода прогонки для трехдиагональной матрицы) итерационными. Из этого следуют более жесткие требования к дискретизации условий для граничных КА-ячеек.

Для гексагональной сетки и консервативных граничных условий записана корректная ЛФП для граничных ячеек, справедливая, по крайней мере, для границ прямоугольной и круговой формы. Предложена идея разделения ЛФП на internal, boundary и postfix. На примере этой задачи заново осмыслено значение числа Куранта–Леви как соотношения скорости сходимости КА к решению задачи, данному на фиксированный момент времени, и скорости изменения самого решения в динамике.

В настоящей работе приводятся результаты численного моделирования свободного сдвигового течения с помощью схемы «КАБАРЕ», реализованной в приближении слабой сжимаемости. Анализ схемы проводится на основе изучения свойств неустойчивости Кельвина–Гельмгольца и порождаемой ею двумерной турбулентности, с использованием интегральных кривых кинетической энергии и энстрофии, картин временной эволюции завихренности, спектров энстрофии и энергии, а также дисперсионного соотношения для инкремента неустойчивости. Расчеты проводились для числа Рейнольдса $\text{Re} = 4 \times 10^5$, на квадратных последовательно сгущаемых сетках в диапазоне $128^2-2048^2$ ячеек. Внимание уделено проблеме «недоразрешенности слоев», проявляющейся в возникновении лишнего вихря при свертывании двух вихревых листов (слоев вихревой пелены). Данное явление существует только на грубых сетках $(128^2)$, однако, полностью симметричная картина эволюции завихренности начинает наблюдаться только при переходе к сетке $1024^2$ ячеек. Размерные оценки отношения вихрей на границах инерционного интервала показывают, что наиболее подробная сетка $2048^2$ ячеек оказывается достаточной для качественного отображения мелкомасштабных сгустков завихренности. Тем не менее можно говорить о достижении хорошей сходимости при отображении крупномасштабных структур. Эволюция турбулентности, в полном соответствии с теоретическими представлениями, приводит к появлению крупных вихрей, в которых сосредотачивается вся кинетическая энергия движения, и уединенных мелкомасштабных образований. Последние обладают свойствами когерентных структур, выживая в процессе нитеобразования (филаментации), и практически не взаимодействуют с вихрями других масштабов. Обсуждение диссипативных характеристик схемы ведется на основе анализа графиков скорости диссипации кинетической энергии, вычисляемой непосредственно, а также на основе теоретических соотношений для моделей несжимаемой жидкости (по кривым энстрофии) и сжимаемого газа (по влиянию тензора скоростей деформации и эффектов дилатации). Асимптотическое поведение каскадов кинетической энергии и энстрофии подчиняется реализующимся в двумерной турбулентности соотношениям $E(k) \propto k^{−3}$, $\omega^2(k) \propto k^{−1}$. Исследование зависимости инкремента неустойчивости от безразмерного волнового числа показывает хорошее согласие с данными других исследователей, вместе с тем часто используемый способ расчета инкремента неустойчивости не всегда оказывается достаточно точным, вследствие чего была предложена его модификация.

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

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

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

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

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

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

Расчет переноса излучения в ударном слое космического аппарата вызывает значительные трудности из-за сложной многорезонансной зависимости макросечения поглощения излучения от энергий фотонов. В работе исследована сходимость двух приближенных методов осреднения спектров излучения к точному поточечному (line-by-line) расчету. Первым из приближенных методов является широко используемое многогрупповое приближение, вторым — метод лебеговского осреднения, относящийся к методам сокращения числа расчетных точек спектра за счет объединения точек с равновеликим поглощением. Показано, что с увеличением числа групп метод лебеговского осреднения сходится к точному решению значительно быстрее многогруппового приближения. Оказалось, что 100–150 лебеговых групп достаточно для достижения точности line-by-line-расчета даже в ударном слое в высоких слоях атмосферы, где линии поглощения узки. При этом объем вычислений сокращается более чем на четыре порядка. Выполнена серия расчетов функции распределения излучения в двумерном ударном слое, возникающем при обтекании сферы и затупленного конуса, с использованием приближения локально плоского слоя и метода лебеговского осреднения энергий фотонов. Показано, что излучение ударной волны становится все более сильным при увеличении размера космического аппарата, как в значениях падающего потока энергии на поверхности тела, так и в скорости обмена энергией с газодинамическим потоком, причем не только в точке торможения.

В данной работе приводятся нижние оценки скорости сходимости для класса численных методов выпуклой оптимизации первого порядка и выше, т. е. использующих градиент и старшие производные. Обсуждаются вопросы достижимости данных оценок. Приведенные в статье оценки замыкают известные на данный момент результаты в этой области. Отметим, что замыкание осуществляется без должного обоснования, поэтому в той общности, в которой данные оценки приведены в статье, их стоит понимать как гипотезу. Опишембо лее точно основной результат работы. Пожалуй, наиболее известнымм етодом второго порядка является метод Ньютона, использующий информацию о градиенте и матрице Гессе оптимизируемой функции. Однако даже для сильно выпуклых функций метод Ньютона сходится лишь локально. Глобальная сходимость метода Ньютона обеспечивается с помощью кубической регуляризации оптимизируемой на каждом шаге квадратичной модели функции [Nesterov, Polyak, 2006]. Сложность решения такой вспомогательной задачи сопоставима со сложностью итерации обычного метода Ньютона, т. е. эквивалентна по порядку сложности обращения матрицы Гессе оптимизируемой функции. В 2008 году Ю. Е. Нестеровымбыл предложен ускоренный вариант метода Ньютона с кубической регуляризацией [Nesterov, 2008]. В 2013 г. Monteiro – Svaiter сумели улучшить оценку глобальной сходимости ускоренного метода с кубической регуляризацией [Monteiro, Svaiter, 2013]. В 2017 году Arjevani – Shamir – Shiff показали, что оценка Monteiro – Svaiter оптимальна (не может быть улучшена более чем на логарифми- ческий множитель на классе методов 2-го порядка) [Arjevani et al., 2017]. Также удалось получить вид нижних оценок для методов порядка $p ≥ 2$ для задач выпуклой оптимизации. Отметим, что при этом для сильно выпуклых функций нижние оценки были получены только для методов первого и второго порядка. В 2018 году Ю. Е. Нестеров для выпуклых задач оптимизации предложил методы 3-го порядка, которые имеют сложность итерации сопоставимую со сложностью итерации метода Ньютона и сходятся почти по установленным нижним оценкам [Nesterov, 2018]. Таким образом, было показано, что методы высокого порядка вполне могут быть практичными. В данной работе приводятся нижние оценки для методов высокого порядка $p ≥ 3$ для сильно выпуклых задач безусловной оптимизации. Работа также может рассматриваться как небольшой обзор современного состояния развития численных методов выпуклой оптимизации высокого порядка.

Математические модели многих естественных процессов описываются дифференциальными уравнениями с особенностями решения. Классические численные методы для нахождения приближенного решения таких задач оказываются неэффективными. В настоящей работе рассмотрена краевая задача для векторного волнового уравнения в двумерной L-образной области. Наличие входящего угла величиной  $3\pi/2$ на границе расчетной области обусловливает сильную сингулярность задачи, то есть ее решение не принадлежит пространству Соболева $H^1$, в результате чего классические и специализированные численные методы имеют скорость сходимости ниже чем $O(h)$. Поэтому в работе введено специальное весовое множество вектор-функций. В этом множестве решение рассматриваемой краевой задачи определено как $R_ν$-обобщенное.

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

Представлены результаты численного эксперимента для серии модельных задач различных типов: для задач, решение которых содержит только сингулярную составляющую, и для задач, решение которых содержит как сингулярную, так и регулярную составляющие. Результаты численного анализа показали, что при измельчении конечноэлементной сетки скорость сходимости построенного весового векторного метода конечных элементов составляет $O(h)$, что по порядку степени в полтора раза выше, чем в разработанных к настоящему времени специализированных методах решения рассматриваемой задачи: методе сингулярных дополнений и методе регуляризации. Другие особенности построенного метода — его алгоритмическая простота и естественность определения решения, что является преимуществом при проведении численных расчетов.