All issues

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

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

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

Mathematical models of many natural processes are described by partial differential equations with singular solutions. Classical numerical methods for determination of approximate solution to such problems are inefficient. In the present paper a boundary value problem for vector wave equation in L-shaped domain is considered. The presence of reentrant corner of size $3\pi/2$ on the boundary of computational domain leads to the strong singularity of the solution, i.e. it does not belong to the Sobolev space $H^1$ so classical and special numerical methods have a convergence rate less than $O(h)$. Therefore in the present paper a special weighted set of vector-functions is introduced. In this set the solution of considered boundary value problem is defined as $R_ν$-generalized one.

For numerical determination of the $R_ν$-generalized solution a weighted vector finite element method is constructed. The basic difference of this method is that the basis functions contain as a factor a special weight function in a degree depending on the properties of the solution of initial problem. This allows to significantly raise a convergence speed of approximate solution to the exact one when the mesh is refined. Moreover, introduced basis functions are solenoidal, therefore the solenoidal condition for the solution is taken into account precisely, so the spurious numerical solutions are prevented.

Results of numerical experiments are presented for series of different type model problems: some of them have a solution containing only singular component and some of them have a solution containing a singular and regular components. Results of numerical experiment showed that when a finite element mesh is refined a convergence rate of the constructed weighted vector finite element method is $O(h)$, that is more than one and a half times better in comparison with special methods developed for described problem, namely singular complement method and regularization method. Another features of constructed method are algorithmic simplicity and naturalness of the solution determination that is beneficial for numerical computations.

В статье проводится систематическое исследование возможностей метода решеточных уравнений Больцмана (lattice Boltzmann method, LBM или РУБ) для описания распространения акустических волн. Рассмотрена задача о распространении возмущений от точечного гармонического источника акустических возмущений в неограниченном пространстве как в неподвижной среде (число Маха $M=0$), так и при наличии набегающего потока (число Маха $M=0{,}2$). Обе рассмотренные задачи имеют аналитическое решение в приближении линейной акустики, что позволяет количественно оценить точность численного метода.

Численная реализация осуществлена с использованием двумерной модели скоростей D2Q9 и оператора столкновений Бхатнагара – Гросса – Крука (BGK). Источник колебаний задавался согласно схеме Gou, а возникающий от источника паразитный шум в моментах старших порядков убирался за счет использования процедуры регуляризации функций распределения. Для минимизации отражений от границ расчетной области использовался гибридный подход, основанный на совместном использовании характеристических граничных условий на основе инвариантов Римана и поглощающих PML-слоев (perfectly matched layer) с параболическим профилем затухания.

В ходе работы проведен детальный анализ влияния вычислительных параметров метода на точность расчета. Исследована зависимость погрешности от толщины PML-слоя ($L_{\text{PML}}^{}$) и максимального коэффициента демпфирования ($\sigma_{\max}^{}$), безразмерной амплитуды источника ($Q'_0$) и шага расчетной сетки. Показано, что метод РУБ применим для моделирования распространения акустических волн и обладает вторым порядком точности. Установлено, что для достижения высокой точности расчета (относительная погрешность давления — не более $1\,\%$) достаточно пространственного разрешения в $20$ точек на длину волны ($\lambda$). Определены минимальные эффективные параметры PML-слоя: $\sigma_{\max}^{}\geqslant 0{,}02$ и $L_{\text{PML}}^{} \geqslant 2\lambda$, обеспечивающие отсутствие отражения от границ расчетной области. Также продемонстрировано, что при амплитудах источника $Q_0' \geqslant 0{,}1$ влияние нелинейных эффектов становится существенным по сравнению с другими источниками погрешности.

The article presents a systematic investigation of the capabilities of the lattice Boltzmann method (LBM) for modeling the propagation of acoustic waves. The study considers the problem of wave propagation from a point harmonic source in an unbounded domain, both in a quiescent medium (Mach number $M=0$) and in the presence of a uniform mean flow ($M=0.2$). Both scenarios admit analytical solutions within the framework of linear acoustics, allowing for a quantitative assessment of the accuracy of the numerical method.

The numerical implementation employs the two-dimensional D2Q9 velocity model and the Bhatnagar – Gross – Krook (BGK) collision operator. The oscillatory source is modeled using Gou’s scheme, while spurious high-order moment noise generated by the source is suppressed via a regularization procedure applied to the distribution functions. To minimize wave reflections from the boundaries of the computational domain, a hybrid approach is used, combining characteristic boundary conditions based on Riemann invariants with perfectly matched layers (PML) featuring a parabolic damping profile.

A detailed analysis is conducted to assess the influence of computational parameters on the accuracy of the method. The dependence of the error on the PML thickness ($L_{\text{PML}}^{}$) and the maximum damping coefficient ($\sigma_{\max}^{}$), the dimensionless source amplitude ($Q'_0$), and the grid resolution is thoroughly examined. The results demonstrate that the LBM is suitable for simulating acoustic wave propagation and exhibits second-order accuracy. It is shown that achieving high accuracy (relative pressure error below $1\,\%$) requires a spatial resolution of at least $20$ grid points per wavelength ($\lambda$). The minimal effective PML parameters ensuring negligible boundary reflections are identified as $\sigma_{\max}^{}\geqslant 0.02$ and $L_{\text{PML}}^{} \geqslant 2\lambda$. Additionally, it is shown that for source amplitudes $Q_0' \geqslant 0.1$, nonlinear effects become significant compared to other sources of error.

В работе предлагается подход, позволяющий организовать оперативный контроль за интенсивностью действия источника выбросов в атмосферу. Восстановление неизвестной интенсивности источника загрязнения атмосферы производится по измерениям концентрации примеси в отдельных стационарных точках. Для решения обратной задачи использовались методы шаговой регуляризации и последовательной функциональной аппроксимации. Решение представлено в форме цифрового фильтра в смысле Хэмминга. Описан алгоритм выбора регуляризирующего параметра r для метода функциональной аппроксимации. Работа продолжает исследования, представленные в [1,2].

The approach given in this work helps to organize the operative control over action intensity of pollution emissions in atmosphere. The approach allows to sequential estimate of unknown intensity of atmospheric pollution source on the base of concentration measurements of impurity in several stationary control points is offered in the work. The inverse problem was solved by means of the step-by-step regularization and the sequential function specification method. The solution is presented in the form of the digital filter in terms of Hamming. The fitting algorithm of regularization parameter r for function specification method is described.

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

In this paper, we introduce a new version of Gauss–Newton method for solving a system of nonlinear equations based on ideas of the residual upper bound for a system of nonlinear equations and a quadratic regularization term. The introduced Gauss–Newton method in practice virtually forms the whole parameterized family of the methods solving systems of nonlinear equations and regression problems. The developed family of Gauss–Newton methods completely consists of iterative methods with generalization for cases of non-euclidean normed spaces, including special forms of Levenberg–Marquardt algorithms. The developed methods use the local model based on a parameterized proximal mapping allowing us to use an inexact oracle of «black–box» form with restrictions for the computational precision and computational complexity. We perform an efficiency analysis including global and local convergence for the developed family of methods with an arbitrary oracle in terms of iteration complexity, precision and complexity of both local model and oracle, problem dimensionality. We present global sublinear convergence rates for methods of the proposed family for solving a system of nonlinear equations, consisting of Lipschitz smooth functions. We prove local superlinear convergence under extra natural non-degeneracy assumptions for system of nonlinear functions. We prove both local and global linear convergence for a system of nonlinear equations under Polyak–Lojasiewicz condition for proposed Gauss– Newton methods. Besides theoretical justifications of methods we also consider practical implementation issues. In particular, for conducted experiments we present effective computational schemes for the exact oracle regarding to the dimensionality of a problem. The proposed family of methods unites several existing and frequent in practice Gauss–Newton method modifications, allowing us to construct a flexible and convenient method implementable using standard convex optimization and computational linear algebra techniques.

Статья посвящена выпукло-вогнутым седловым задачам, в которых целевая функция является суммой большого числа слагаемых. Такие задачи привлекают значительное внимание математического сообщества в связи с множеством приложений в машинном обучении, включая adversarial learning, adversarial attacks и robust reinforcement learning, и это лишь некоторые из них. Отдельные функции в сумме обычно представляют собой ошибку, связанную с объектом из выборки. Кроме того, формулировка допускает (возможно, негладкий) композитный член. Такие слагаемые часто отражают регуляризацию в задачах машинного обучения. Предполагается, что размерность одной из групп переменных относительно мала (около сотни или меньше), а другой — велика. Такой случай возникает, например, при рассмотрении двойственной формулировки задачи минимизации с умеренным числом ограничений. Предлагаемый подход основан на использовании метода секущей плоскости Вайды для минимизации относительно внешнего блока переменных. Этот алгоритм оптимизации особенно эффективен, когда размерность задачи не очень велика. Неточный оракул для метода Вайды вычисляется через приближенное решение внутренней задачи максимизации, которая решается ускоренным алгоритмом с редукцией дисперсии Katyusha. Таким образом, мы используем структуру задачи для достижения быстрой сходимости. В исследовании получены отдельные оценки сложности для градиентов различных компонент относительно различных переменных. Предложенный подход накладывает слабые предположения о целевой функции. В частности, не требуется ни сильной выпуклости, ни гладкости относительно низкоразмерной группы переменных. Количество шагов предложенного алгоритма, а также арифметическая сложность каждого шага явно зависят от размерности внешней переменной, отсюда предположение, что она относительно мала.

The paper is devoted to convex-concave saddle point problems where the objective is a sum of a large number of functions. Such problems attract considerable attention of the mathematical community due to the variety of applications in machine learning, including adversarial learning, adversarial attacks and robust reinforcement learning, to name a few. The individual functions in the sum usually represent losses related to examples from a data set. Additionally, the formulation admits a possibly nonsmooth composite term. Such terms often reflect regularization in machine learning problems. We assume that the dimension of one of the variable groups is relatively small (about a hundred or less), and the other one is large. This case arises, for example, when one considers the dual formulation for a minimization problem with a moderate number of constraints. The proposed approach is based on using Vaidya’s cutting plane method to minimize with respect to the outer block of variables. This optimization algorithm is especially effective when the dimension of the problem is not very large. An inexact oracle for Vaidya’s method is calculated via an approximate solution of the inner maximization problem, which is solved by the accelerated variance reduced algorithm Katyusha. Thus, we leverage the structure of the problem to achieve fast convergence. Separate complexity bounds for gradients of different components with respect to different variables are obtained in the study. The proposed approach is imposing very mild assumptions about the objective. In particular, neither strong convexity nor smoothness is required with respect to the low-dimensional variable group. The number of steps of the proposed algorithm as well as the arithmetic complexity of each step explicitly depend on the dimensionality of the outer variable, hence the assumption that it is relatively small.

В данной работе решается задача поиска конструкции магнитной системы для создания магнитного поля с требуемыми характеристиками в заданной области. На основе анализа математической модели магнитной системы предлагается достаточно общий подход к решению нелинейной обратной задачи, которая описывается уравнением Фредгольма H(z) = ∫_SIJ(s)G(z, s)ds, z ∈ S _H, s ∈ S _I . Необходимо определить распределение плотности тока J(s), а также расстановку источников тока для создания поля H(z). В работе предлагается метод решения этих задачс помощью регуляризованных итерационных процессов. На примере конкретной магнитной системы проводится численное исследование влияния различных факторов на характер создаваемого магнитного поля.

In this paper the problem of searching for the design of the magnetic system for creation a magnetic field with the required characteristics in the given area is solved. On the basis of analysis of the mathematical model of the magnetic system rather a general approach is proposed to the solving of the inverse problem, which is written by the Fredgolm equation H(z) = ∫_SIJ(s)G(z, s)ds, z ∈ S _H, s ∈ S _I . It was necessary to define the current density distribution function J(s) and the existing winding geometry for creation of a required magnetic field H(z). In the paper a method of solving those by means of regularized iterative processes is proposed. On the base of the concrete magnetic system we perform the numerical study of influence of different factors on the character of the magnetic field being designed.

Решение задачи лазерной спектрометрии позволяет определять размеры частиц в растворе по спектру интенсивности рассеянного света. В результате эксперимента методом динамического рассеяния света получается кривая интенсивности рассеяния, по которой необходимо определить, частицы каких размеров представлены в растворе. Экспериментально полученный спектр интенсивности сравнивается с теоретически ожидаемым спектром, который является кривой Лоренца. Основная задача сводится к тому, чтобы на основании этих данных найти относительные концентрации частиц каждого сорта, представленных в растворе. В статье представлен способ построения и использования нейронной сети, обученной на синтетических данных, для определения размера частиц в растворе в диапазоне 1–500 нм. Нейронная сеть имеет полносвязный слой из 60 нейронов с функцией активации RELU на выходе, слой из 45 нейронов и с аналогичной функцией активации, слой dropout и 2 слоя с количеством нейронов 15 и 1 (выход сети). В статье описано, как сеть обучалась и тестировалась на синтетических и экспериментальных данных. На синтетических данных метрика «среднеквадратичное отклонение» (rmse) дала значение 1.3157 нм. Экспериментальные данные были получены для размеров частиц 200 нм, 400 нм и раствора с представителями обоих размеров. Сравниваются результаты работы нейронной сети и классических линейных методов, основанных на применении различных регуляризаций за счет введения дополнительных параметров и применяемых для определения размера частиц. К недостаткам классических методов можно отнести трудность автоматического определения степени регуляризации: слишком сильная регуляризация приводит к тому, что кривые распределения частиц по размерам сильно сглаживаются, а слабая регуляризация дает осциллирующие кривые и низкую надежность результатов. В работе показано, что нейронная сеть дает хорошее предсказание для частиц с большим размером. Для малых размеров предсказание хуже, но ошибка быстро уменьшается с увеличением размера.

Solution of Dynamic Light Scattering problem makes it possible to determine particle size distribution (PSD) from the spectrum of the intensity of scattered light. As a result of experiment, an intensity curve is obtained. The experimentally obtained spectrum of intensity is compared with the theoretically expected spectrum, which is the Lorentzian line. The main task is to determine on the basis of these data the relative concentrations of particles of each class presented in the solution. The article presents a method for constructing and using a neural network trained on synthetic data to determine PSD in a solution in the range of 1–500 nm. The neural network has a fully connected layer of 60 neurons with the RELU activation function at the output, a layer of 45 neurons and the same activation function, a dropout layer and 2 layers with 15 and 1 neurons (network output). The article describes how the network has been trained and tested on synthetic and experimental data. On the synthetic data, the standard deviation metric (rmse) gave a value of 1.3157 nm. Experimental data were obtained for particle sizes of 200 nm, 400 nm and a solution with representatives of both sizes. The results of the neural network and the classical linear methods are compared. The disadvantages of the classical methods are that it is difficult to determine the degree of regularization: too much regularization leads to the particle size distribution curves are much smoothed out, and weak regularization gives oscillating curves and low reliability of the results. The paper shows that the neural network gives a good prediction for particles with a large size. For small sizes, the prediction is worse, but the error quickly decreases as the particle size increases.

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

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

Численные решения сопоставлены с результатами других авторов, полученных по схемам повышенного порядка аппроксимации: КАБАРЕ, HLLC (Harten Lax van Leer Contact), CFLFh (CFLF hybrid scheme), JT (centered scheme with limiter by Jiang and Tadmor), PPM (Piecewise Parabolic Method), WENO5 (weighted essentially non-oscillatory scheme), RKGD (Runge–Kutta Discontinuous Galerkin), с гибридной взвешенной нелинейной интерполяцией CCSSR-HW4 и CCSSR-HW6. К достоинствам гибридного метода крупных частиц относятся расширенные возможности решения задач гиперболического и смешанного типов, хорошее соотношение диссипативных и дисперсионных свойств, сочетание алгоритмической простоты и высокой разрешающей способности в задачах со сложной ударно-волновой структурой, развитием неустойчивости и вихреобразованием на контактных границах.

We study the computational properties of a parametric class of finite-volume schemes with customizable dissipative properties with splitting by physical processes into Lagrangian, Eulerian, and the final stages (the hybrid large-particle method). The method has a second-order approximation in space and time on smooth solutions. The regularization of a numerical solution at the Lagrangian stage is performed by nonlinear correction of artificial viscosity. Regardless of the grid resolution, the artificial viscosity value tends to zero outside the zone of discontinuities and extremes in the solution. At Eulerian and final stages, primitive variables (density, velocity, and total energy) are first reconstructed by an additive combination of upwind and central approximations weighted by a flux limiter. Then numerical divergent fluxes are formed from them. In this case, discrete analogs of conservation laws are performed.

The analysis of dissipative properties of the method using known viscosity and flow limiters, as well as their linear combination, is performed. The resolution of the scheme and the quality of numerical solutions are demonstrated by examples of two-dimensional benchmarks: a gas flow around the step with Mach numbers 3, 10 and 20, the double Mach reflection of a strong shock wave, and the implosion problem. The influence of the scheme viscosity of the method on the numerical reproduction of a gases interface instability is studied. It is found that a decrease of the dissipation level in the implosion problem leads to the symmetric solution destruction and formation of a chaotic instability on the contact surface.

Numerical solutions are compared with the results of other authors obtained using higher-order approximation schemes: CABARET, HLLC (Harten Lax van Leer Contact), CFLFh (CFLF hybrid scheme), JT (centered scheme with limiter by Jiang and Tadmor), PPM (Piecewise Parabolic Method), WENO5 (weighted essentially non-oscillatory scheme), RKGD (Runge –Kutta Discontinuous Galerkin), hybrid weighted nonlinear schemes CCSSR-HW4 and CCSSR-HW6. The advantages of the hybrid large-particle method include extended possibilities for solving hyperbolic and mixed types of problems, a good ratio of dissipative and dispersive properties, a combination of algorithmic simplicity and high resolution in problems with complex shock-wave structure, both instability and vortex formation at interfaces.

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

We consider one of the problems of transport modelling — searching the equilibrium distribution of traffic flows in the network. We use the classic Beckman’s model to describe time costs and flow distribution in the network represented by directed graph. Meanwhile agents’ behavior is not completely rational, what is described by the introduction of Markov logit dynamics: any driver selects a route randomly according to the Gibbs’ distribution taking into account current time costs on the edges of the graph. Thus, the problem is reduced to searching of the stationary distribution for this dynamics which is a stochastic Nash – Wardrope equilibrium in the corresponding population congestion game in the transport network. Since the game is potential, this problem is equivalent to the problem of minimization of some functional over flows distribution. The stochasticity is reflected in the appearance of the entropy regularization, in contrast to non-stochastic case. The dual problem is constructed to obtain a solution of the optimization problem. The universal primal-dual gradient method is applied. A major specificity of this method lies in an adaptive adjustment to the local smoothness of the problem, what is most important in case of the complex structure of the objective function and an inability to obtain a prior smoothness bound with acceptable accuracy. Such a situation occurs in the considered problem since the properties of the function strongly depend on the transport graph, on which we do not impose strong restrictions. The article describes the algorithm including the numerical differentiation for calculation of the objective function value and gradient. In addition, the paper represents a theoretical estimate of time complexity of the algorithm and the results of numerical experiments conducted on a small American town.

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

В данной работе рассмотрены как выпуклые задачи оптимизации, так и седловые. Для сильно выпуклых задач были обобщены уже имеющиеся результаты об одинаковых размерах выборки в обоих подходах (онлайн и офлайн) на произвольные нормы. Более того, было показано, что условие сильной выпуклости может быть ослаблено: полученные результаты справедливы для функций, удовлетворяющих условию квадратичного роста. В случае когда данное условие не выполняется, предлагается использовать регуляризацию исходной задачи в произвольной норме. В отличие от выпуклых задач седловые задачи являются намного менее изученными. Для седловых задач размер выборки был получен при условии $\gamma$-роста седловой функции по разным группам переменных. Это условие при $\gamma = 1$ есть не что иное, как аналог условия острого минимума в выпуклых задач. В данной статье было показано, что размер выборки в случае острого минимума (седла) почти не зависит от желаемой точности решения исходной задачи.

In this paper, we consider convex stochastic optimization problems arising in machine learning applications (e. g., risk minimization) and mathematical statistics (e. g., maximum likelihood estimation). There are two main approaches to solve such kinds of problems, namely the Stochastic Approximation approach (online approach) and the Sample Average Approximation approach, also known as the Monte Carlo approach, (offline approach). In the offline approach, the problem is replaced by its empirical counterpart (the empirical risk minimization problem). The natural question is how to define the problem sample size, i. e., how many realizations should be sampled so that the quite accurate solution of the empirical problem be the solution of the original problem with the desired precision. This issue is one of the main issues in modern machine learning and optimization. In the last decade, a lot of significant advances were made in these areas to solve convex stochastic optimization problems on the Euclidean balls (or the whole space). In this work, we are based on these advances and study the case of arbitrary balls in the $p$-norms. We also explore the question of how the parameter $p$ affects the estimates of the required number of terms as a function of empirical risk.

In this paper, both convex and saddle point optimization problems are considered. For strongly convex problems, the existing results on the same sample sizes in both approaches (online and offline) were generalized to arbitrary norms. Moreover, it was shown that the strong convexity condition can be weakened: the obtained results are valid for functions satisfying the quadratic growth condition. In the case when this condition is not met, it is proposed to use the regularization of the original problem in an arbitrary norm. In contradistinction to convex problems, saddle point problems are much less studied. For saddle point problems, the sample size was obtained under the condition of $\gamma$-growth of the objective function. When $\gamma = 1$, this condition is the condition of sharp minimum in convex problems. In this article, it was shown that the sample size in the case of a sharp minimum is almost independent of the desired accuracy of the solution of the original problem.