All issues

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

Recently, saddle point problems have received much attention due to their powerful modeling capability for a lot of problems from diverse domains. Applications of these problems occur in many applied areas, such as robust optimization, distributed optimization, game theory, and many applications in machine learning such as empirical risk minimization and generative adversarial networks training. Therefore, many researchers have actively worked on developing numerical methods for solving saddle point problems in many different settings. This paper is devoted to developing a numerical method for solving saddle point problems in the nonconvex uniformly-concave setting. We study a general class of saddle point problems with composite structure and H\"older-continuous higher-order derivatives. To solve the problem under consideration, we propose an approach in which we reduce the problem to a combination of two auxiliary optimization problems separately for each group of variables, the outer minimization problem w.r.t. primal variables, and the inner maximization problem w.r.t the dual variables. For solving the outer minimization problem, we use the Adaptive Gradient Method, which is applicable for nonconvex problems and also works with an inexact oracle that is generated by approximately solving the inner problem. For solving the inner maximization problem, we use the Restarted Unified Acceleration Framework, which is a framework that unifies the high-order acceleration methods for minimizing a convex function that has H\"older-continuous higher-order derivatives. Separate complexity bounds are provided for the number of calls to the first-order oracles for the outer minimization problem and higher-order oracles for the inner maximization problem. Moreover, the complexity of the whole proposed approach is then estimated.

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

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

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

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

A critical analysis of existing approaches, methods and models to solve the problem of financial resources operational management has been carried out in the article. A number of significant shortcomings of the presented models were identified, limiting the scope of their effective usage. There are a static nature of the models, probabilistic nature of financial flows are not taken into account, daily amounts of receivables and payables that significantly affect the solvency and liquidity of the company are not identified. This necessitates the development of a new model that reflects the essential properties of the planning financial flows system — stochasticity, dynamism, non-stationarity.

The model for the financial flows distribution has been developed. It bases on the principles of optimal dynamic control and provides financial resources planning ensuring an adequate level of liquidity and solvency of a company and concern initial data uncertainty. The algorithm for designing the objective cash balance, based on principles of a companies’ financial stability ensuring under changing financial constraints, is proposed.

Characteristic of the proposed model is the presentation of the cash distribution process in the form of a discrete dynamic process, for which a plan for financial resources allocation is determined, ensuring the extremum of an optimality criterion. Designing of such plan is based on the coordination of payments (cash expenses) with the cash receipts. This approach allows to synthesize different plans that differ in combinations of financial outflows, and then to select the best one according to a given criterion. The minimum total costs associated with the payment of fines for non-timely financing of expenses were taken as the optimality criterion. Restrictions in the model are the requirement to ensure the minimum allowable cash balances for the subperiods of the planning period, as well as the obligation to make payments during the planning period, taking into account the maturity of these payments. The suggested model with a high degree of efficiency allows to solve the problem of financial resources distribution under uncertainty over time and receipts, coordination of funds inflows and outflows. The practical significance of the research is in developed model application, allowing to improve the financial planning quality, to increase the management efficiency and operational efficiency of a company.

В данной статье осуществляется сравнение эффективности некоторых современных методов и практик стохастической оптимизации применительно к задаче цифрового предыскажения сигнала (DPD), которое является важной составляющей процесса обработки сигнала на базовых станциях, обеспечивающих беспроводную связь. В частности, рассматривается два круга вопросов о возможностях применения стохастических методов для обучения моделей класса Винера – Гаммерштейна в рамках подхода минимизации эмпирического риска: касательно улучшения глубины и скорости сходимости данного метода оптимизации и относительно близости самой постановки задачи (выбранной модели симуляции) к наблюдаемому в действительности поведению устройства. Так, в первой части этого исследования внимание будет сосредоточено на вопросе о нахождении наиболее эффективного метода оптимизации и дополнительных к нему модификаций. Во второй части предлагается новая квази-онлайн-постановка задачи и, соответственно, среда для тестирования эффективности методов, благодаря которым результаты численного моделирования удается привести в соответствие с поведением реального прототипа устройства DPD. В рамках этой новой постановки далее осуществляется повторное тестирование некоторых избранных практик, более подробно рассмотренных в первой части исследования, и также обнаруживаются и подчеркиваются преимущества нового лидирующего метода оптимизации, оказывающегося теперь также наиболее эффективным и в практических тестах. Для конкретной рассмотренной модели максимально достигнутое улучшение глубины сходимости составило 7% в стандартном режиме и 5% в онлайн-постановке (при том что метрика сама по себе имеет логарифмическую шкалу). Также благодаря дополнительным техникам оказывается возможным сократить время обучения модели DPD вдвое, сохранив улучшение глубины сходимости на 3% и 6% для стандартного и онлайн-режимов соответственно. Все сравнения производятся с методом оптимизации Adam, который был отмечен как лучший стохастический метод для задачи DPD из рассматриваемых в предшествующей работе [Pasechnyuk et al., 2021], и с методом оптимизации Adamax, который оказывается наиболее эффективным в предлагаемом онлайн-режиме.

In this paper, we test the performance of some modern stochastic optimization methods and practices with respect to the digital pre-distortion problem, which is a valuable part of processing signal on base stations providing wireless communication. In the first part of our study, we focus on the search for the best performing method and its proper modifications. In the second part, we propose the new, quasi-online, testing framework that allows us to fit our modeling results with the behavior of real-life DPD prototype, retest some selected of practices considered in the previous section and approve the advantages of the method appearing to be the best under real-life conditions. For the used model, the maximum achieved improvement in depth is 7% in the standard regime and 5% in the online regime (metric itself is of logarithmic scale). We also achieve a halving of the working time preserving 3% and 6% improvement in depth for the standard and online regime, respectively. All comparisons are made to the Adam method, which was highlighted as the best stochastic method for DPD problem in [Pasechnyuk et al., 2021], and to the Adamax method, which is the best in the proposed online regime.