Все выпуски

Задачи потери устойчивости тонких упругих оболочек снова стали актуальными, так как в последние годы обнаружено несоответствие между стандартами многих стран по определению нагрузок, вызывающих потерю несущей способности пологих оболочек, и результатами экспериментов по испытаниям тонкостенных авиационных конструкций, изготовленных из высокопрочных сплавов. Основное противоречие состоит в том, что предельные внутренние напряжения, при которых наблюдается потеря устойчивости (хлопок) оболочек, оказываются меньше тех, которые предсказывает принятая теория расчета, отраженная в стандартах США и Европы. Действующие нормативные акты основаны на статической теории пологих оболочек, предложенной в 1930-е годы: в рамках нелинейной теории упругости для тонкостенных структур выделяются устойчивые решения, значительно отличающиеся от форм равновесия, присущих небольшим начальным нагрузкам. Минимальная величина нагрузки, при которой существует альтернативная форма равновесия (низшая критическая нагрузка), принималась в качестве предельно допустимой. В 1970-е годы было установлено, что такой подход оказывается неприемлемым при сложных загружениях. Подобные случаи ранее не встречались на практике, сейчас они появились на более тонких изделиях, эксплуатируемых в сложных условиях. Поэтому необходим пересмотр исходных теоретических положений по оценке несущей способности. Основой теории могут служить недавние математические результаты, установившие асимптотическую близость расчетов по двум схемам: трехмерной динамической теории упругости и динамической теории пологих выпуклых оболочек. В предлагаемой работе вначале формулируется динамическая теория пологих оболочек, которая затем сводится к одному разрешающему интегро-дифференциальному уравнению (после построения специальной функции Грина). Показано, что полученное нелинейное уравнение допускает разделение переменных, имеет множество периодических по времени решений, которые удовлетворяют уравнению Дуффинга «с мягкой пружиной». Это уравнение хорошо изучено, его численный анализ позволяет находить амплитуду и период колебаний в зависимости от свойств функции Грина. Если вызвать колебания оболочки с помощью пробной гармонической по времени нагрузки, то можно измерить перемещения точек поверхности в момент максимальной амплитуды. Предлагается экспериментальная установка, в которой генерируются резонансные колебания пробной нагрузкой, направленной по нормали к поверхности. Экспериментальные измерения перемещений оболочки, а также амплитуды и периода колебаний дают возможность рассчитать коэффициент запаса несущей способности конструкции неразрушающим методом в условиях эксплуатации.

Buckling problems of thin elastic shells have become relevant again because of the discrepancies between the standards in many countries on how to estimate loads causing buckling of shallow shells and the results of the experiments on thinwalled aviation structures made of high-strength alloys. The main contradiction is as follows: the ultimate internal stresses at shell buckling (collapsing) turn out to be lower than the ones predicted by the adopted design theory used in the USA and European standards. The current regulations are based on the static theory of shallow shells that was put forward in the 1930s: within the nonlinear theory of elasticity for thin-walled structures there are stable solutions that significantly differ from the forms of equilibrium typical to small initial loads. The minimum load (the lowest critical load) when there is an alternative form of equilibrium was used as a maximum permissible one. In the 1970s it was recognized that this approach is unacceptable for complex loadings. Such cases were not practically relevant in the past while now they occur with thinner structures used under complex conditions. Therefore, the initial theory on bearing capacity assessments needs to be revised. The recent mathematical results that proved asymptotic proximity of the estimates based on two analyses (the three-dimensional dynamic theory of elasticity and the dynamic theory of shallow convex shells) could be used as a theory basis. This paper starts with the setting of the dynamic theory of shallow shells that comes down to one resolving integrodifferential equation (once the special Green function is constructed). It is shown that the obtained nonlinear equation allows for separation of variables and has numerous time-period solutions that meet the Duffing equation with “a soft spring”. This equation has been thoroughly studied; its numerical analysis enables finding an amplitude and an oscillation period depending on the properties of the Green function. If the shell is oscillated with the trial time-harmonic load, the movement of the surface points could be measured at the maximum amplitude. The study proposes an experimental set-up where resonance oscillations are generated with the trial load normal to the surface. The experimental measurements of the shell movements, the amplitude and the oscillation period make it possible to estimate the safety factor of the structure bearing capacity with non-destructive methods under operating conditions.

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

We build new tests which permit to increase the human capacity for the information processing by the parallel execution of the several logic operations of prescribed type. For checking of the causes of the capacity increasing we develop the check tests on the same logic operations class in which the parallel organization of the calculations is low-effectively. We use the apparatus of the universal algebra and automat theory. This article is the extension of the cycle of the work, which investigates the human capacity for the parallel calculations. The general publications on this theme content in the references. The tasks in the described tests may to define in the form of the calculation of the result in the sequence of the same type operations from some algebra. If this operation is associative then the parallel calculation is effectively by successful grouping of process. In Theory of operations that is the using the simultaneous work several processors. Each processor transforms in the time unit the certain known number of the elements of the input date or the intermediate results (the processor productivity). Now it is not known what kind elements of date are using by the brain for the logical or mathematical calculation, and how many elements are treating in the time units. Therefore the test contains the sequence of the presentations of the tasks with different numbers of logical operations in the fixed alphabet. That is the measure of the complexity for the task. The analysis of the depending of the time for the task solution from the complexity gives the possible to estimate the processor productivity and the form of the calculate organization. For the sequence calculations only one processor is working, and the time of solution is a line function of complexity. If the new processors begin to work in parallel when the complexities of the task increase than the depending of the solution time from complexity is represented by the curve which is convex at the bottom. For the detection of situation when the man increases the speed of the single processor under the condition of the increasing complexity we use the task series with similar operations but in the no associate algebra. In such tasks the parallel calculation is little affectivity in the sense of the increasing efficiency by the increasing the number of processors. That is the check set of the tests. In article we consider still one class of the tests, which are based on the calculation of the trajectory of the formal automat state if the input sequence is determined. We investigate the special class of automats (relay) for which the construction affect on the affectivity of the parallel calculations of the final automat state. For all tests we estimate the affectivity of the parallel calculation. This article do not contained the experiment results.

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

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.

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

In this paper, we develop a new first-order method for composite nonconvex minimization problems with simple constraints and inexact oracle. The objective function is given as a sum of «hard», possibly nonconvex part, and «simple» convex part. Informally speaking, oracle inexactness means that, for the «hard» part, at any point we can approximately calculate the value of the function and construct a quadratic function, which approximately bounds this function from above. We give several examples of such inexactness: smooth nonconvex functions with inexact H¨older-continuous gradient, functions given by the auxiliary uniformly concave maximization problem, which can be solved only approximately. For the introduced class of problems, we propose a gradient-type method, which allows one to use a different proximal setup to adapt to the geometry of the feasible set, adaptively chooses controlled oracle error, allows for inexact proximal mapping. We provide a convergence rate for our method in terms of the norm of generalized gradient mapping and show that, in the case of an inexact Hölder-continuous gradient, our method is universal with respect to Hölder parameters of the problem. Finally, in a particular case, we show that the small value of the norm of generalized gradient mapping at a point means that a necessary condition of local minimum approximately holds at that point.

В данной статье проведен обзор как исторических достижений, так и современных результатов в области марковских процессов принятия решений (Markov Decision Process, MDP) и выпуклой оптимизации. Данный обзор является первой попыткой освещения на русском языке области обучения с подкреплением в контексте выпуклой оптимизации. Рассматриваются фундаментальное уравнение Беллмана и построенные на его основе критерии оптимальности политики — стратегии, принимающие решение по известному состоянию среды на данный момент. Также рассмотрены основные итеративные алгоритмы оптимизации политики, построенные на решении уравнений Беллмана. Важным разделом данной статьи стало рассмотрение альтернативы к подходу $Q$-обучения — метода прямой максимизации средней награды агента для избранной стратегии от взаимодействия со средой. Таким образом, решение данной задачи выпуклой оптимизации представимо в виде задачи линейного программирования. В работе демонстрируется, как аппарат выпуклой оптимизации применяется для решения задачи обучения с подкреплением (Reinforcement Learning, RL). В частности, показано, как понятие сильной двойственности позволяет естественно модифицировать постановку задачи RL, показывая эквивалентность между максимизацией награды агента и поиском его оптимальной стратегии. В работе также рассматривается вопрос сложности оптимизации MDP относительно количества троек «состояние–действие–награда», получаемых в результате взаимодействия со средой. Представлены оптимальные границы сложности решения MDP в случае эргодического процесса с бесконечным горизонтом, а также в случае нестационарного процесса с конечным горизонтом, который можно перезапускать несколько раз подряд или сразу запускать параллельно в нескольких потоках. Также в обзоре рассмотрены последние результаты по уменьшению зазора нижней и верхней оценки сложности оптимизации MDP с усредненным вознаграждением (Averaged MDP, AMDP). В заключение рассматриваются вещественнозначная параметризация политики агента и класс градиентных методов оптимизации через максимизацию $Q$-функции ценности. В частности, представлен специальный класс MDP с ограничениями на ценность политики (Constrained Markov Decision Process, CMDP), для которых предложен общий прямодвойственный подход к оптимизации, обладающий сильной двойственностью.

This article reviews both historical achievements and modern results in the field of Markov Decision Process (MDP) and convex optimization. This review is the first attempt to cover the field of reinforcement learning in Russian in the context of convex optimization. The fundamental Bellman equation and the criteria of optimality of policy — strategies based on it, which make decisions based on the known state of the environment at the moment, are considered. The main iterative algorithms of policy optimization based on the solution of the Bellman equations are also considered. An important section of this article was the consideration of an alternative to the $Q$-learning approach — the method of direct maximization of the agent’s average reward for the chosen strategy from interaction with the environment. Thus, the solution of this convex optimization problem can be represented as a linear programming problem. The paper demonstrates how the convex optimization apparatus is used to solve the problem of Reinforcement Learning (RL). In particular, it is shown how the concept of strong duality allows us to naturally modify the formulation of the RL problem, showing the equivalence between maximizing the agent’s reward and finding his optimal strategy. The paper also discusses the complexity of MDP optimization with respect to the number of state–action–reward triples obtained as a result of interaction with the environment. The optimal limits of the MDP solution complexity are presented in the case of an ergodic process with an infinite horizon, as well as in the case of a non-stationary process with a finite horizon, which can be restarted several times in a row or immediately run in parallel in several threads. The review also reviews the latest results on reducing the gap between the lower and upper estimates of the complexity of MDP optimization with average remuneration (Averaged MDP, AMDP). In conclusion, the real-valued parametrization of agent policy and a class of gradient optimization methods through maximizing the $Q$-function of value are considered. In particular, a special class of MDPs with restrictions on the value of policy (Constrained Markov Decision Process, CMDP) is presented, for which a general direct-dual approach to optimization with strong duality is proposed.

С 50-х годов XX века транспортное моделирование крупных мегаполисов стало усиленно развиваться. Появились первые модели равновесного распределения потоков по путям. Наиболее популярной (и использующейся до сих пор) моделью была модель Бэкмана и др. 1955 г. В основу этой модели положены два принципа Вардропа. На современном теоретико-игровом языке можно кратко описать суть модели как поиск равновесия Нэша в популяционной игре загрузки, в которой потери игроков (водителей) рассчитываются исходя из выбранного пути и загрузках на этом пути, при фиксированных корреспонденциях. Загрузки (затраты) на пути рассчитываются как сумма затрат на различных участках дороги (ребрах графа транспортной сети). Затраты на ребре (время проезда по ребру) определяется величиной потока автомобилей на этом ребре. Поток на ребре, в свою очередь, определяется суммой потоков по всем путям, проходящим через заданное ребро. Таким образом, затраты на проезд по пути определяются не только выбором пути, но и тем, какие пути выбрали остальные водители. Таким образом, мы находимся в стандартной теоретико-игровой постановке. Специфика формирования функций затрат позволяет сводить поиск равновесия к решению задачи оптимизации (игра потенциальная). Эта задача оптимизации будет выпуклой, если функции затрат монотонно неубывающие. Собственно, различные предположения о функциях затрат формируют различные модели. Наиболее популярной моделью является модель с функцией затрат BPR. Такие функции используются при расчетах реальных городов повсеместно. Однако в начале XXI века Ю. Е. Нестеровым и А. де Пальмой было показано, что модели типа Бэкмана имеют серьезные недостатки. Эти недостатки можно исправить, используя модель, которую авторы назвали моделью стабильной динамики. Поиск равновесия в такой модели также сводится к задаче оптимизации. Точнее, даже задаче линейного программирования. В 2013 г. А. В. Гасниковым было обнаружено, что модель стабильной ди- намики может быть получена предельным переходом, связанным с поведением функции затрат, из модели Бэкмана. Однако обоснование упомянутого предельного перехода было сделано в нескольких важных (для практики), но все- таки частных случаях. В общем случае вопрос о возможности такого предельного перехода, насколько нам известно, остается открытым. Данная работа закрывает данный зазор. В статье в общем случае приводится обоснование возможности отмеченного предельного перехода (когда функция затрат на проезд по ребру как функция потока по ребру вырождается в функцию, равную постоянным затратам до достижения пропускной способности, и равна плюс бесконечности, при превышении пропускной способности).

Since 1950s the field of city transport modelling has progressed rapidly. The first equilibrium distribution models of traffic flow appeared. The most popular model (which is still being widely used) was the Beckmann model, based on the two Wardrop principles. The core of the model could be briefly described as the search for the Nash equilibrium in a population demand game, in which losses of agents (drivers) are calculated based on the chosen path and demands of this path with correspondences being fixed. The demands (costs) of a path are calculated as the sum of the demands of different path segments (graph edges), that are included in the path. The costs of an edge (edge travel time) are determined by the amount of traffic on this edge (more traffic means larger travel time). The flow on a graph edge is determined by the sum of flows over all paths passing through the given edge. Thus, the cost of traveling along a path is determined not only by the choice of the path, but also by the paths other drivers have chosen. Thus, it is a standard game theory task. The way cost functions are constructed allows us to narrow the search for equilibrium to solving an optimization problem (game is potential in this case). If the cost functions are monotone and non-decreasing, the optimization problem is convex. Actually, different assumptions about the cost functions form different models. The most popular model is based on the BPR cost function. Such functions are massively used in calculations of real cities. However, in the beginning of the XXI century, Yu. E. Nesterov and A. de Palma showed that Beckmann-type models have serious weak points. Those could be fixed using the stable dynamics model, as it was called by the authors. The search for equilibrium here could be also reduced to an optimization problem, moreover, the problem of linear programming. In 2013, A.V.Gasnikov discovered that the stable dynamics model can be obtained by a passage to the limit in the Beckmann model. However, it was made only for several practically important, but still special cases. Generally, the question if this passage to the limit is possible remains open. In this paper, we provide the justification of the possibility of the above-mentioned passage to the limit in the general case, when the cost function for traveling along the edge as a function of the flow along the edge degenerates into a function equal to fixed costs until the capacity is reached and it is equal to plus infinity when the capacity is exceeded.

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

In this paper, we consider two variants of the concept of sharp minimum for mathematical programming problems with quasiconvex objective function and inequality constraints. It investigated the problem of describing a variant of a simple subgradient method with switching along productive and non-productive steps, for which, on a class of problems with Lipschitz functions, it would be possible to guarantee convergence with the rate of geometric progression to the set of exact solutions or its vicinity. It is important that to implement the proposed method there is no need to know the sharp minimum parameter, which is usually difficult to estimate in practice. To overcome this problem, the authors propose to use a step adjustment procedure similar to that previously proposed by B. T. Polyak. However, in this case, in comparison with the class of problems without constraints, it arises the problem of knowing the exact minimal value of the objective function. The paper describes the conditions for the inexactness of this information, which make it possible to preserve convergence with the rate of geometric progression in the vicinity of the set of minimum points of the problem. Two analogs of the concept of a sharp minimum for problems with inequality constraints are considered. In the first one, the problem of approximation to the exact solution arises only to a pre-selected level of accuracy, for this, it is considered the case when the minimal value of the objective function is unknown; instead, it is given some approximation of this value. We describe conditions on the inexact minimal value of the objective function, under which convergence to the vicinity of the desired set of points with a rate of geometric progression is still preserved. The second considered variant of the sharp minimum does not depend on the desired accuracy of the problem. For this, we propose a slightly different way of checking whether the step is productive, which allows us to guarantee the convergence of the method to the exact solution with the rate of geometric progression in the case of exact information. Convergence estimates are proved under conditions of weak convexity of the constraints and some restrictions on the choice of the initial point, and a corollary is formulated for the convex case when the need for an additional assumption on the choice of the initial point disappears. For both approaches, it has been proven that the distance from the current point to the set of solutions decreases with increasing number of iterations. This, in particular, makes it possible to limit the requirements for the properties of the used functions (Lipschitz-continuous, sharp minimum) only for a bounded set. Some computational experiments are performed, including for the truss topology design problem.

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

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

In this paper we propose high-order (tensor) methods for two types of saddle point problems. Firstly, we consider the classic min-max saddle point problem. Secondly, we consider the search for a stationary point of the saddle point problem objective by its gradient norm minimization. Obviously, the stationary point does not always coincide with the optimal point. However, if we have a linear optimization problem with linear constraints, the algorithm for gradient norm minimization becomes useful. In this case we can reconstruct the solution of the optimization problem of a primal function from the solution of gradient norm minimization of dual function. In this paper we consider both types of problems with no constraints. Additionally, we assume that the objective function is $\mu$-strongly convex by the first argument, $\mu$-strongly concave by the second argument, and that the $p$-th derivative of the objective is Lipschitz-continous.

For min-max problems we propose two algorithms. Since we consider strongly convex a strongly concave problem, the first algorithm uses the existing tensor method for regular convex concave saddle point problems and accelerates it with the restarts technique. The complexity of such an algorithm is linear. If we additionally assume that our objective is first and second order Lipschitz, we can improve its performance even more. To do this, we can switch to another existing algorithm in its area of quadratic convergence. Thus, we get the second algorithm, which has a global linear convergence rate and a local quadratic convergence rate.

Finally, in convex optimization there exists a special methodology to solve gradient norm minimization problems by tensor methods. Its main idea is to use existing (near-)optimal algorithms inside a special framework. I want to emphasize that inside this framework we do not necessarily need the assumptions of strong convexity, because we can regularize the convex objective in a special way to make it strongly convex. In our article we transfer this framework on convex-concave objective functions and use it with our aforementioned algorithm with a global linear convergence and a local quadratic convergence rate.

Since the saddle point problem is a particular case of the monotone variation inequality problem, the proposed methods will also work in solving strongly monotone variational inequality problems.

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

Сравнение описанных методов проводится для двух типов стохастических задач — выпуклой оптимизации и седел. Для задач стохастической выпуклой оптимизации существующие решения позволяют довольно подробно сравнить онлайн- и офлайн-алгоритмы. В частности, для сильно выпуклых задач вычислительная сложность алгоритмов одинаковая, причем условие сильной выпуклости может быть ослаблено до условия $\gamma$-роста целевой функции. С этой точки зрения седловые задачи являются гораздо менее изученными. Тем не менее существующие решения позволяют наметить основные направления исследования. Так, значительные продвижения сделаны для билинейных седловых задач с помощью онлайн-алгоритмов. Оффлайн-алгоритмы представлены всего одним исследованием. В данной работе на этом примере демонстрируется аналогичная с выпуклой оптимизацией схожесть обоих алгоритмов. Также был проработан вопрос точности решения вспомогательной задачи для седел. С другой стороны, седловая задача стохастической оптимизации обобщает выпуклую, то есть является ее логичным продолжением. Это проявляется в том, что существующие результаты из выпуклой оптимизации можно перенести на седла. В данной работе такой перенос осуществляется для результатов онлайн-алгоритма в выпуклом случае, когда целевая функция удовлетворяет условию $\gamma$-роста.

Stochastic optimization is a current area of research due to significant advances in machine learning and their applications to everyday problems. In this paper, we consider two fundamentally different methods for solving the problem of stochastic optimization — online and offline algorithms. The corresponding algorithms have their qualitative advantages over each other. So, for offline algorithms, it is required to solve an auxiliary problem with high accuracy. However, this can be done in a distributed manner, and this opens up fundamental possibilities such as, for example, the construction of a dual problem. Despite this, both online and offline algorithms pursue a common goal — solving the stochastic optimization problem with a given accuracy. This is reflected in the comparison of the computational complexity of the described algorithms, which is demonstrated in this paper.

The comparison of the described methods is carried out for two types of stochastic problems — convex optimization and saddles. For problems of stochastic convex optimization, the existing solutions make it possible to compare online and offline algorithms in some detail. In particular, for strongly convex problems, the computational complexity of the algorithms is the same, and the condition of strong convexity can be weakened to the condition of $\gamma$-growth of the objective function. From this point of view, saddle point problems are much less studied. Nevertheless, existing solutions allow us to outline the main directions of research. Thus, significant progress has been made for bilinear saddle point problems using online algorithms. Offline algorithms are represented by just one study. In this paper, this example demonstrates the similarity of both algorithms with convex optimization. The issue of the accuracy of solving the auxiliary problem for saddles was also worked out. On the other hand, the saddle point problem of stochastic optimization generalizes the convex one, that is, it is its logical continuation. This is manifested in the fact that existing results from convex optimization can be transferred to saddles. In this paper, such a transfer is carried out for the results of the online algorithm in the convex case, when the objective function satisfies the $\gamma$-growth condition.