Все выпуски

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

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

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

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

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

Рассмотрены особенности формирования поля температуры уходящих газов на выходе из малоэмиссионных камер сгорания (МЭКС) газотурбинных двигателей (ГТД). Показаны основные проблемы, связанные с их доводкой. Представлены результаты численных исследований влияния степени выгорания топлива по длине МЭКС на температурную неравномерность уходящих газов. Проведена оптимизация конструкции смесителя ввода воздуха на разбавление по количеству, форме и местоположению отверстий. Представлена методика разработки смесителя для камер сгорания подобного типа.

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

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

Эффективность производственного процесса непосредственно зависит от качества управления технологией, которая, в свою очередь, опирается на точность и оперативность обработки контрольно- измерительной информации. Разработка математических методов исследования системных связей и закономерностей функционирования и построение математических моделей с учетом структурных особенностей объекта исследований, а также написание программных продуктов для реализации данных методов являются актуальными задачами. Практика показала, что список параметров, имеющих место при исследовании сложного объекта современного производства, варьируется от нескольких десятков до нескольких сот наименований, причем степень воздействия каждого из факторов в начальный момент не ясна. Приступать к работе по непосредственному определению модели в этих условиях нельзя — объем требуемой информации может оказаться слишком велик, причем бóльшая часть работы по сбору этой информации будет проделана впустую из-за того, что степень влияния на параметры оптимизации большинства факторов из первоначального списка окажется пренебрежимо малой. Поэтому необходимым этапом при определении модели сложного объекта является работа по сокращению размерности факторного пространства. Большинство промышленных производств являются групповыми иерархическими процессами массового и крупносерийного производства, характеризующимися сотнями факторов. (Для примера реализации математических методов и апробации построенных моделей в основу были взяты данные Молдавского металлургического завода.) С целью исследования системных связей и закономерностей функционирования таких сложных объектов обычно выбираются несколько информативных параметров и осуществляется их выборочный контроль. В данной статье описывается последовательность приведения исходных показателей технологического процесса выплавки стали к виду, пригодному для построения математической модели с целью прогнозирования, внедрения новых видов стали и создание основы для разработки системы автоматизированного управления качеством продукции. В процессе преобразования выделяются следующие этапы: сбор и анализ исходных данных, построение таблицы слабокоррелированных параметров, сокращение факторного пространства с помощью корреляционных плеяд и метода весовых коэффициентов. Полученные результаты позволяют оптимизировать процесс построения модели многофакторного процесса.

Случайный поиск в настоящее время стал распространенным и эффективным средством решения сложных задач оптимизации и адаптации. В работе рассматривается задача о средней длительности случайного поиска одним объектом другого в зависимости от различных факторов на квадратной решетке. Решение поставленной задачи было реализовано при помощи проведения полного эксперимента с 4 факторами и ортогональным планом в 54 строки. В рамках каждой строки моделировались случайные блуждания двух точек с заданными начальными условиями и правила перехода, затем замерялась продолжительность поиска одного объекта другим. В результате построена регрессионная модель, отражающая среднюю длительность случайного поиска объекта в зависимости от четырех рассматриваемых факторов, задающих начальные положения двух объектов, условия их передвижения и обнаружения. Среди рассмотренных факторов, влияющих на среднее время поиска, определены наиболее значимые. По построенной модели проведена интерпретация в задаче случайного поиска объекта. Важным результатом работы стало то, что с помощью модели выявлено качественное и количественное влияние первоначальных позиций объектов, размера решетки и правил перемещения на среднее время продолжительности поиска. Показано, что начальное соседство объектов на решетке не гарантирует быстрый поиск, если каждый из них передвигается. Помимо этого, количественно оценено, во сколько раз может затянуться или сократиться среднее время поиска объекта при увеличении скорости ищущего объекта на 1 ед., а также при увеличении размера поля на 1 ед., при различных начальных положениях двух объектов. Выявлен экспоненциальный характер роста числа шагов поиска объекта при увеличении размера решетки при остальных фиксированных факторах. Найдены условия наиболее большого увеличения средней продолжительности поиска: максимальная удаленность объектов в сочетании с неподвижностью одного из них при изменении размеров поля на 1 ед. (т. е., к примеру, с $4 \times 4$ на $5 \times 5$) может увеличить в среднем продолжительность поиска в $e^{1.69} \approx 5.42$. Поставленная в работе задача может быть актуальна с точки зрения применения как в погранометрике для обеспечения безопасности государства, так и, к примеру, в теории массового обслуживания.

В данной работе приводятся нижние оценки скорости сходимости для класса численных методов выпуклой оптимизации первого порядка и выше, т. е. использующих градиент и старшие производные. Обсуждаются вопросы достижимости данных оценок. Приведенные в статье оценки замыкают известные на данный момент результаты в этой области. Отметим, что замыкание осуществляется без должного обоснования, поэтому в той общности, в которой данные оценки приведены в статье, их стоит понимать как гипотезу. Опишембо лее точно основной результат работы. Пожалуй, наиболее известнымм етодом второго порядка является метод Ньютона, использующий информацию о градиенте и матрице Гессе оптимизируемой функции. Однако даже для сильно выпуклых функций метод Ньютона сходится лишь локально. Глобальная сходимость метода Ньютона обеспечивается с помощью кубической регуляризации оптимизируемой на каждом шаге квадратичной модели функции [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$ для сильно выпуклых задач безусловной оптимизации. Работа также может рассматриваться как небольшой обзор современного состояния развития численных методов выпуклой оптимизации высокого порядка.

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

В данной работе рассматривается задача восстановления матрицы корреспонденций для наблюдений реальных корреспонденций в г. Москве. Следуя общепринятому подходу [Гасников и др., 2013], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа — районы, из которых выезжают / в которые въезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчете всех корреспонденций израйона $i$ в район $j$.

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийная модель. В работе, в соответствии с работой [Вильсон, 1978], приводится описание эволюционного обоснования энтропийной модели, описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчете матрицы корреспонденций. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В работе описывается несколько численных методов оптимизации для решения данной задачи: алгоритм Синхорна и ускоренный алгоритм Синхорна. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя некоторую комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Мы предполагаем, что шум в восстановленной матрице корреспонденций является гауссовским, в результате в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу невыпуклой оптимизации. В статье приводится обзор безградиенных методов оптимизации для решения невыпуклых задач. Так как число параметров функции затрат небольшое, для определения оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Далее по минимальному значению невязки для каждой функции затрат определяется, для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденции.