Все выпуски

Статья посвящена специальному подходу к субградиентным методам для задач сильно выпуклого программирования с несколькими функциональными ограничениями. Точнее говоря, рассматривается задача сильно выпуклой минимизации с несколькими сильно выпуклыми ограничениями-неравенствами и предлагаются оптимизационные методы первого порядка для такого класса задач. Особенность предложенных методов — возможность использования в теоретических оценках качества выдаваемого методом решения параметров сильной выпуклости именно тех функционалов ограничений, для которых нарушается условие продyктивности итерации. Основная задача — предложить для такой постановки субградиентный метод с адаптивными правилами подбора шагов и остановки метода. Ключевая идея предложенной в данной статье методики заключается в объединении двух подходов: схемы с переключениями по продуктивным и непродуктивным шагам и недавно предложенных модификаций зеркального спуска для задач выпуклого программирования, позволяющих игнорировать часть функциональных ограничений на непродуктивных шагах алгоритма. В статье описан субградиентний метод с переключением по продyктивным и непродyктивным шагам для задач сильно выпуклого программирования в случае, когда целевая функция и функциональные ограничения удовлетворяют условию Липшица. Также рассмотрен аналог этой схемы типа зеркального спуска для задач с относительно липшицевыми и относительно сильно выпуклыми целевой функцией и ограничениями. Для предлагаемых методов получены теоретические оценки качества выдаваемого решения, указывающие на оптимальность этих методов с точки зрения нижних оракульных оценок. Кроме того, поскольку во многих задачах операция нахождения точного вектора субградиента достаточно затратна, то для рассматриваемого класса задач исследованы аналоги указанных выше методов с заменой обычного субградиента на $\delta$-субградиент целевого функционала или функциональных ограничений-неравенств. Отмеченный подход может позволить сэкономить вычислительные затраты метода за счет отказа от требования доступности точного значения субградиента в текущей точке. Показано, что оценки качества решения при этом изменяются на величину $O(\delta)$. Также приводятся результаты численных экспериментов, иллюстрирующие преимущество предлагаемых в статье методов в сравнении с некоторыми ранее известными.

В работе рассматривается метод исследования панельных данных, основанный на использовании агломеративной иерархической кластеризации — группировки объектов на основании сходства и разли- чия их признаков в иерархию вложенных друг в друга кластеров. Применялись 2 альтернативных способа вычисления евклидовых расстояний между объектами — расстояния между усредненными по интервалу наблюдений значениями и расстояния с использованием данных за все рассматриваемые годы. Сравнивались 3 альтернативных метода вычисления расстояний между кластерами. В первом случае таким расстоянием считается расстояние между ближайшими элементами из двух кластеров, во втором — среднее по парам элементов, в третьем — расстояние между наиболее удаленными элементами. Исследована эффективность использования двух индексов качества кластеризации — индекса Данна и Силуэта для выбора оптимального числа кластеров и оценки статистической значимости полученных решений. Способ оценивания статистической достоверности кластерной структуры заключался в сравнении качества кластеризации, на реальной выборке с качеством кластеризаций на искусственно сгенерированных выборках панельных данных с теми же самыми числом объектов, признаков и длиной рядов. Генерация производилась из фиксированного вероятностного распределения. Использовались способы симуляции, имитирующие гауссов белый шум и случайное блуждание. Расчеты с индексом Силуэт показали, что случайное блуждание характеризуется не только ложной регрессией, но и ложной кластеризацией. Кластеризация принималась достоверной для данного числа выделенных кластеров, если значение индекса на реальной выборке оказывалось больше значения 95%-ного квантиля для искусственных данных. В качестве выборки реальных данных использован набор временных рядов показателей, характеризующих производство в российских регионах. Для этих данных только Силуэт показывает достоверную кластеризацию на уровне $p < 0.05$. Расчеты также показали, что значения индексов для реальных данных в целом ближе к значениям для случайных блужданий, чем для белого шума, но имеют значимые отличия и от тех, и от других. Визуально можно выделить скопления близко расположенных друг от друга в трехмерном признаковом пространстве точек, выделяемые также в качестве кластеров применяемым алгоритмом иерархической кластеризации.

В статье исследуется влияние нерыночных действий участников олигополистических рынков на рыночную структуру. Анализируются следующие действия одного из участников рынка, направленные на повышение его рыночной доли: 1) манипуляция ценами; 2) блокировка инвестиций более сильных олигополистов; 3) уничтожение производственной продукции и мощностей конкурентов. Для моделирования стратегий олигополистов используются линейные динамические игры с квадратичным критерием. Целесообразность их использования обусловлена возможностью как адекватного описания эволюции рынков, так и реализации двух взаимно дополняющих подходов к определению стратегий олигополистов: 1) подхода, основанного на представлении моделей в пространстве состояний и решении обобщенных уравнений Риккати; 2) подхода, основанного на применении методов операционного исчисления (в частотной области) и обладающего необходимой для экономического анализа наглядностью.

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

На основе расчетов по игровой модели построены зависимости, характеризующие связь относи- тельного увеличения объемов производства за 25-летний период слабого $dy_2$ и сильного $dy_1$ дуополистов при манипуляции ценами. Показано, что увеличение цены при принятой линейной функции спроса приводит к весьма незначительному росту производства сильного дуополиста, но вместе с тем — к существенному росту этого показателя у слабого.

В то же время блокировка инвестиций, а также уничтожение продукции сильного дуополиста приводят к росту объемов производства товарной продукции у слабого дуополиста за счет снижения этого показателя у сильного, причем эластичность $\frac{y_2}{dy_1}$ превышает по модулю 1.

Задачи негладкой оптимизации нередко возникают во многих приложениях. Вопросы разработки эффективных вычислительных процедур для негладких задач в пространствах больших размерностей весьма актуальны. В таких случаях разумно применятьмет оды первого порядка (субградиентные методы), однако в достаточно общих ситуациях они приводят к невысоким скоростным гарантиям. Одним из подходов к этой проблеме может являться выделение подкласса негладких задач, допускающих относительно оптимистичные результаты о скорости сходимости в пространствах больших размерностей. К примеру, одним из вариантов дополнительных предположений может послужитьуслови е острого минимума, предложенное в конце 1960-х годов Б. Т. Поляком. В случае доступности информации о минимальном значении функции для липшицевых задач с острым минимумом известен субградиентный метод с шагом Б. Т. Поляка, который гарантирует линейную скорость сходимости по аргументу. Такой подход позволил покрыть ряд важных прикладных задач (например, задача проектирования точки на выпуклый компакт или задача отыскания общей точки системы выпуклых множеств). Однако как условие доступности минимального значения функции, так и само условие острого минимума выглядят довольно ограничительными. В этой связи в настоящей работе предлагается обобщенное условие острого минимума, аналогичное известному понятию неточного оракула. Предложенный подход позволяет расширить класс применимости субградиентных методов с шагом Б. Т. Поляка на ситуации неточной информации о значении минимума, а также неизвестной константы Липшица целевой функции. Более того, использование в теоретической оценке качества выдаваемого методом решения локальных аналогов глобальных характеристик целевой функции позволяет применять результаты такого типа и к более широким классам задач. Показана возможностьпр именения предложенного подхода к сильно выпуклым негладким задачам и выполнено экспериментальное сравнение с известным оптимальным субградиентным методом на таком классе задач. Более того, получены результаты о применимости предложенной методики для некоторых типов задач с релаксациями выпуклости: недавно предложенное понятие слабой $\beta$-квазивыпуклости и обычной квазивыпуклости. Исследовано обобщение описанной методики на ситуацию с предположением о доступности на итерациях $\delta$-субградиента целевой функции вместо обычного субградиента. Для одного из рассмотренных методов найдены условия, при которых на практике можно отказаться от проектирования итеративной последовательности на допустимое множество поставленной задачи.

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

В настоящей работе схемы расщепления 3-го и 4-го порядка были применены непосредственно к решению двумерной гиперболической системы уравнений в частных производных линейной теории упругости. Это позволило повысить итоговый порядок сходимости расчетного алгоритма. В работе эмпирически оценена сходимость по нормам $L_1$ и $L_\infty$ с использованиемана литических решений определяющей системы достаточной степени гладкости. Для получения объективных результатов рассмотрены случаи продольных и поперечных плоских волн, распространяющихся как вдоль диагонали расчетной ячейки, так и не вдоль нее. Проведенные численные эксперименты подтверждают повышение точности метода и демонстрируют теоретически ожидаемый порядок сходимости. При этом увеличивается в 3 и в 4 раза время моделирования (для схем 3-го и 4-го порядка соответственно), но не возрастает потребление оперативной памяти. Предложенное усовершенствование вычислительного алгоритма сохраняет простоту его параллельной реализации на основе пространственной декомпозиции расчетной сетки.

В работе методом математического моделирования проведено исследование механизмов влияния света на скорость роста и макромолекулярный состав накопительной культуры микроводорослей. Показано, что даже при единственном лимитирующем факторе рост микроводорослей сопряжен со значительным изменением биохимического состава биомассы. Отмечено, что существующие математические модели, основанные на принципах ферментативной кинетики, не учитывают возможную смену лимитирующего фактора в процессе увеличения биомассы и не позволяют описать динамику относительного содержания ее биохимических компонентов. В качестве альтернативного подхода предложена двухкомпонентная модель, в основе которой положено предположение о двухстадийности фотоавтотрофного роста. Биомассу микроводорослей можно рассматривать в виде суммы двух макромолекулярных составляющих — структурной и резервной. Предполагается пропорциональность всех структурных компонентов биомассы, что значительно упрощает математические выкладки и верификацию модели. Предлагаемая модель представлена системой двух дифференциальных уравнений: скорость синтеза резервных составляющих биомассы определяется интенсивностью света, а структурных компонентов — потоком резервов на ключевой мультиферментный комплекс. Модель учитывает, что часть резервных компонентов расходуется на пополнение пула макроэргов. Скорости синтеза структурных и резервных форм биомассы заданы линейными сплайнами, которые позволяют учесть смену лимитирующего фактора с ростом плотности накопительной культуры. Показано, что в условиях светового лимитирования накопительную кривую необходимо разделять на несколько областей: неограниченного роста, малой концентрации клеток и оптически плотной культуры. Для каждого участка получены аналитические решения предлагаемой модели, которые выражены в элементарных функциях и позволяют оценить видоспецифические коэффициенты. Проведена верификация модели на экспериментальных данных роста биомассы и динамики относительного содержания хлорофилла $a$ накопительной культуры красной морской микроводоросли Pоrphуridium purpurеum.

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

В развитие ранее полученного результата по моделированию динамики растительного покрова, вследствие изменчивости температурного фона, представлена новая схема интервального анализа динамики флористических образов формаций в случае, когда параметр скорости реагирования модели динамики каждого учетного вида растения задан интервалом разброса своих возможных значений. Желаемая в фундаментальных исследованиях детализация описания функциональных параметров макромоделей биоразнообразия, учитывающая сущностные причины наблюдаемых эволюционных процессов, может оказаться проблемной задачей. Использование более надежных интервальных оценок вариабельности функциональных параметров «обходит» проблему неопределенности в вопросах первичного оценивания эволюции фиторесурсного потенциала осваиваемых подконтрольных территорий. Полученные решения сохраняют не только качественную картину динамики видового разнообразия, но и дают строгую, в рамках исходных предположений, количественную оценку меры присутствия каждого вида растения. Практическая значимость схем двустороннего оценивания на основе конструирования уравнений для верхних и нижних границ траекторий разброса решений зависит от условий и меры пропорционального соответствия интервалов разбросов исходных параметров с интервалами разбросов решений. Для динамических систем желаемая пропорциональность далеко не всегда обеспечивается. Приведенные примеры демонстрирует приемлемую точность интервального оценивания эволюционных процессов. Важно заметить, что конструкции оценочных уравнений порождают исчезающие интервалы разбросов решений для квазипостоянных температурных возмущений системы. Иными словами, траектории стационарных температурных состояний растительного покрова предложенной схемой интервального оценивания не огрубляется. Строгость результата интервального оценивания видового состава растительного покрова формаций может стать определяющим фактором при выборе метода в задачах анализа динамики видового разнообразия и растительного потенциала территориальных систем ресурсно-экологического мониторинга. Возможности предложенного подхода иллюстрируются геоинформационными образами вычислительного анализа динамики растительного покрова полуострова Ямал и графиками ретроспективного анализа флористической изменчивости формаций ландшафтно-литологической группы «Верховые» по данным вариации летнего температурного фона метеостанции г. Салехарда от 2010 до 1935 года. Разработанные показатели флористической изменчивости и приведенные графики характеризуют динамику видового разнообразия, как в среднем, так и индивидуально, в виде интервалов возможных состояний по каждому учетному виду растения.

Задача вероятностного тематического моделирования заключается в том, чтобы по заданной коллекции текстовых документов найти две матрицы: матрицу условных вероятностей тем в документах и матрицу условных вероятностей слов в темах. Каждый документ представляется в виде мультимножества слов, то есть предполагается, что для выявления тематики документа не важен порядок слов в нем, а важна только их частота. При таком предположении задача сводится к вычислению низкорангового неотрицательного матричного разложения, наилучшего по критерию максимума правдоподобия. Данная задача имеет в общем случае бесконечное множество решений, то есть является некорректно поставленной. Для регуляризации ее решения к логарифму правдоподобия добавляется взвешенная сумма оптимизационных критериев, с помощью которых формализуются дополнительные требования к модели. При моделировании больших текстовых коллекций хранение первой матрицы представляется нецелесообразным, поскольку ее размер пропорционален числу документов в коллекции. В то же время тематические векторные представления документов необходимы для решения многих задач текстовой аналитики — информационного поиска, кластеризации, классификации, суммаризации текстов. На практике тематический вектор вычисляется для каждого документа по необходимости, что может потребовать десятков итераций по всем словам документа. В данной работе предлагается способ быстрого вычисления тематического вектора для произвольного текста, требующий лишь одной итерации, то есть однократного прохода по всем словам документа. Для этого в модель вводится дополнительное ограничение в виде уравнения, позволяющего вычислять первую матрицу через вторую за линейное время. Хотя формально данное ограничение не является оптимизационным критерием, фактически оно выполняет роль регуляризатора и может применяться в сочетании с другими критериями в рамках теории аддитивной регуляризации тематических моделей ARTM. Эксперименты на трех свободно доступных текстовых коллекциях показали, что предложенный метод улучшает качество модели по пяти оценкам качества, характеризующим разреженность, различность, информативность и когерентность тем. Для проведения экспериментов использовались библиотеки с открытымк одомB igARTM и TopicNet.

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка AGMsDR на классе задач минимизации, вообще говоря, невыпуклых функций с $M$-липшицевым градиентом и удовлетворяющих условию Поляка – Лоясиевича. При реализации метода не требуется знать параметр $\mu^{PL}>0$ из условия Поляка – Лоясиевича, при этом метод демонстрирует линейную скорость сходимости (сходимость со скоростью геометрической прогрессии со знаменателем $\left.\left(1 - \frac{\mu^{PL}}{M}\right)\right)$. Ранее для метода была доказана сходимость со скоростью $O\left(\frac1{k^2}\right)$ на классе выпуклых задач с $M$-липшицевым градиентом. А также сходимость со скоростью геометрической прогрессии, знаменатель которой $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$, но только если алгоритму известно значение параметра сильной выпуклости $\mu^{SC}>0$. Новизна результата заключается в том, что удается отказаться от использования методом значения параметра $\mu^{SC}>0$ и при этом сохранить линейную скорость сходимости, но уже без корня в знаменателе прогрессии.

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

Таким образом, представлены адаптивные ускоренные методы с оценкой сходимости $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ на классе выпуклых функций с $M$-липшицевым градиентом, которые удовлетворяют условию Поляка – Лоясиевича. При этом для работы метода не требуются значения параметров $M$ и $\mu^{PL}$. Если же условие Поляка – Лоясиевича не выполняется, то можно утверждать, что скорость сходимости равна $O\left(\frac1{k^2}\right)$, но при этом методы не требуют никаких изменений.

Также рассматривается адаптивная каталист-оболочка неускоренного градиентного метода, которая позволяет доказать оценку скорости сходимости $O\left(\frac1{k^2}\right)$. Проведено экспериментальное сравнение неускоренного градиентного метода с адаптивным выбором шага, ускоренного с помощью адаптивной каталист-оболочки с методами AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) и алгоритмом Синхорна для задачи, двойственной к задаче оптимального транспорта.

Проведенные вычислительные эксперименты показали более быструю работу метода Alternating AGMsDR по сравнению как с неускоренным градиентным методом, ускоренным с помощью адаптивной каталист-оболочки, так и с методом AGMsDR, несмотря на асимптотически одинаковые гарантии скорости сходимости $O\left(\frac1{k^2}\right)$. Это может быть объяснено результатом о линейной скорости сходимости метода Alternating AGMsDR на классе задач, удовлетворяющих условию Поляка – Лоясиевича. Гипотеза была проверена на квадратичных задачах. Метод Alternating AGMsDR показал более быструю сходимость по сравнению с методом AGMsDR.