Все выпуски

Rugose spiraling whitefly (RSW) is one of the major pests which affects the coconut trees. It feeds on the tree by sucking up the water content as well as the essential nutrients from leaves. It also forms sooty mold in leaves due to which the process of photosynthesis is inhibited. Biocontrol of pest is harmless for trees and crops. The experimental results in literature reveal that Pseudomallada astur is a potential predator for this pest. We investigate the dynamics of predator, Pseudomallada astur’s interaction with rugose spiralling whitefly, Aleurodicus rugioperculatus in coconut trees using a mathematical model. In this system of ordinary differential equation, the pest-predator interaction is modeled using Holling type III functional response. The parametric values are calculated from the experimental results and are tabulated. An approximate analytical solution for the system has been derived. The homotopy analysis method proves to be a suitable method for creating solutions that are valid even for moderate to large parameter values, hence we employ the same to solve this nonlinear model. The $\hbar$-curves, which give the admissible region of $\hbar$, are provided to validate the region of convergence. We have derived the approximate solution at fifth order and stopped at this order since we obtain a more approximate solution in this iteration. Numerical simulation is obtained through MATLAB. The analytical results are compared with numerical simulation and are found to be in good agreement. The biological interpretation of figures implies that the use of a predator reduces the whitefly’s growth to a greater extent.

Rugose spiraling whitefly (RSW) is one of the major pests which affects the coconut trees. It feeds on the tree by sucking up the water content as well as the essential nutrients from leaves. It also forms sooty mold in leaves due to which the process of photosynthesis is inhibited. Biocontrol of pest is harmless for trees and crops. The experimental results in literature reveal that Pseudomallada astur is a potential predator for this pest. We investigate the dynamics of predator, Pseudomallada astur’s interaction with rugose spiralling whitefly, Aleurodicus rugioperculatus in coconut trees using a mathematical model. In this system of ordinary differential equation, the pest-predator interaction is modeled using Holling type III functional response. The parametric values are calculated from the experimental results and are tabulated. An approximate analytical solution for the system has been derived. The homotopy analysis method proves to be a suitable method for creating solutions that are valid even for moderate to large parameter values, hence we employ the same to solve this nonlinear model. The $\hbar$-curves, which give the admissible region of $\hbar$, are provided to validate the region of convergence. We have derived the approximate solution at fifth order and stopped at this order since we obtain a more approximate solution in this iteration. Numerical simulation is obtained through MATLAB. The analytical results are compared with numerical simulation and are found to be in good agreement. The biological interpretation of figures implies that the use of a predator reduces the whitefly’s growth to a greater extent.

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

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.

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

The article covered results of three-dimensional modeling of ecologic situation of shallow water on the example of the Azov Sea with using schemes of increased order of accuracy on multiprocessor computer system of Southern Federal University. Discrete analogs of convective and diffusive transfer operators of the fourth order of accuracy in the case of partial occupancy of cells were constructed and studied. The developed scheme of the high (fourth) order of accuracy were used for solving problems of aquatic ecology and modeling spatial distribution of polluting nutrients, which caused growth of phytoplankton, many species of which are toxic and harmful. The use of schemes of the high order of accuracy are improved the quality of input data and decreased the error in solutions of model tasks of aquatic ecology. Numerical experiments were conducted for the problem of transportation of substances on the basis of the schemes of the second and fourth orders of accuracy. They’re showed that the accuracy was increased in 48.7 times for diffusion-convection problem. The mathematical algorithm was proposed and numerically implemented, which designed to restore the bottom topography of shallow water on the basis of hydrographic data (water depth at individual points or contour level). The map of bottom relief of the Azov Sea was generated with using this algorithm. It’s used to build fields of currents calculated on the basis of hydrodynamic model. The fields of water flow currents were used as input data of the aquatic ecology models. The library of double-layered iterative methods was developed for solving of nine-diagonal difference equations. It occurs in discretization of model tasks of challenges of pollutants concentration, plankton and fish on multiprocessor computer system. It improved the precision of the calculated data and gave the possibility to obtain operational forecasts of changes in ecologic situation of shallow water in short time intervals.

В работе рассматривается задача оценивания параметров временных рядов, описываемых регрессионными моделями с марковскими переключениями двух режимов в случайные моменты времени и независимыми гауссовскими шумами. Для решения предлагается вариант EM-алгоритма, основанный на итерационной процедуре, в ходе которой происходит чередование оценивания параметров регрессии при заданной последовательности переключений режимов и оценивания последовательности переключений при заданных параметрах моделей регрессии. В отличие от известных методов оценивания параметров регрессий с марковскими переключениями режимов, которые основаны на вычислении апостериорных вероятностей дискретных состояний последовательности переключений, в работе находятся оптимальные по критерию максимума апостериорной вероятности оценки процесса переключений. В результате предлагаемый алгоритм оказывается более простым и требует меньшее количество расчетов. Компьютерное моделирование позволяет выявить факторы, влияющие на точность оценивания. К таким факторам относятся число наблюдений, количество неизвестных параметров регрессии, степень их различия в разных режимах работы, а также величина отношения сигнала к шуму, которую в моделях регрессии можно связать с величиной коэффициента детерминации. Предложенный алгоритм применяется для задачи оценивания параметров в моделях регрессии для доходности индекса РТС в зависимости от доходностей индекса S&P 500 и акций «Газпрома» за период с 2013 года по 2018 год. Проводится сравнение оценок параметров, найденных с помощью предлагаемого алгоритма, с оценками, которые формируются с использованием эконометрического пакета EViews, и с оценками обычного метода наименьших квадратов без учета переключений режимов. Учет переключений позволяет получить более точное представление о структуре статистической зависимости исследуемых переменных. В моделях с переключениями рост отношения сигнала к шуму приводит к тому, что уменьшаются различия в оценках, вырабатываемых предлагаемым алгоритмом и с помощью программы EViews.

The paper considers the problem of estimating the parameters of time series described by regression models with Markov switching of two regimes at random instants of time with independent Gaussian noise. For the solution, we propose a variant of the EM algorithm based on the iterative procedure, during which an estimation of the regression parameters is performed for a given sequence of regime switching and an evaluation of the switching sequence for the given parameters of the regression models. In contrast to the well-known methods of estimating regression parameters in the models with Markov switching, which are based on the calculation of a posteriori probabilities of discrete states of the switching sequence, in the paper the estimates are calculated of the switching sequence, which are optimal by the criterion of the maximum of a posteriori probability. As a result, the proposed algorithm turns out to be simpler and requires less calculations. Computer modeling allows to reveal the factors influencing accuracy of estimation. Such factors include the number of observations, the number of unknown regression parameters, the degree of their difference in different modes of operation, and the signal-to-noise ratio which is associated with the coefficient of determination in regression models. The proposed algorithm is applied to the problem of estimating parameters in regression models for the rate of daily return of the RTS index, depending on the returns of the S&P 500 index and Gazprom shares for the period from 2013 to 2018. Comparison of the estimates of the parameters found using the proposed algorithm is carried out with the estimates that are formed using the EViews econometric package and with estimates of the ordinary least squares method without taking into account regimes switching. The account of regimes switching allows to receive more exact representation about structure of a statistical dependence of investigated variables. In switching models, the increase in the signal-to-noise ratio leads to the fact that the differences in the estimates produced by the proposed algorithm and using the EViews program are reduced.

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

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

Стоит отметить, что в качестве метода для решения внутренней подзадачи при отсутствии ограничений мы используем супербыстрый тензорный метод. При решении внутренней подзадачи на компакте используется ускоренный проксимальный тензорный метод для задачи с композитом.

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

In this article we consider min-min type of problems or minimization by two groups of variables. In some way it is similar to classic min-max saddle point problem. Although, saddle point problems are usually more difficult in some way. Min-min problems may occur in case if some groups of variables in convex optimization have different dimensions or if these groups have different domains. Such problem structure gives us an ability to split the main task to subproblems, and allows to tackle it with mixed oracles. However existing articles on this topic cover only zeroth and first order oracles, in our work we consider high-order tensor methods to solve inner problem and fast gradient method to solve outer problem.

We assume, that outer problem is constrained to some convex compact set, and for the inner problem we consider both unconstrained case and being constrained to some convex compact set. By definition, tensor methods use high-order derivatives, so the time per single iteration of the method depends a lot on the dimensionality of the problem it solves. Therefore, we suggest, that the dimension of the inner problem variable is not greater than 1000. Additionally, we need some specific assumptions to be able to use mixed oracles. Firstly, we assume, that the objective is convex in both groups of variables and its gradient by both variables is Lipschitz continuous. Secondly, we assume the inner problem is strongly convex and its gradient is Lipschitz continuous. Also, since we are going to use tensor methods for inner problem, we need it to be p-th order Lipschitz continuous ($p > 1$). Finally, we assume strong convexity of the outer problem to be able to use fast gradient method for strongly convex functions.

We need to emphasize, that we use superfast tensor method to tackle inner subproblem in unconstrained case. And when we solve inner problem on compact set, we use accelerated high-order composite proximal method.

Additionally, in the end of the article we compare the theoretical complexity of obtained methods with regular gradient method, which solves the mentioned problem as regular convex optimization problem and doesn’t take into account its structure (Remarks 1 and 2).

Работа посвящена исследованию субградиентных методов с различными вариациями шага Б.Т. Поляка на классах задач минимизации слабо выпуклых и относительно слабо выпуклых функций, обладающих соответствующим аналогом острого минимума. Оказывается, что при некоторых предположениях о начальной точке такой подход может давать возможность обосновать сходимость сyбградиентного метода со скоростью геометрической прогрессии. Для субградиентного метода с шагом Б.Т. Поляка доказана уточненная оценка скорости сходимости для задач минимизации слабо выпуклых функций с острым минимумом. Особенность этой оценки — дополнительный учет сокращения расстояния от текущей точки метода до множества решений по мере роста количества итераций. Представлены результаты численных экспериментов для задачи восстановления фазы (которая слабо выпyкла и имеет острый минимyм), демонстрирующие эффективность предложенного подхода к оценке скорости сходимости по сравнению с известным ранее результатом. Далее, предложена вариация субградиентного метода с переключениями по продуктивным и непродуктивным шагам для слабо выпуклых задач с ограничениями-неравенствами и получен некоторый аналог результата о сходимости со скоростью геометрической прогрессии. Для субградиентного метода с соответствующей вариацией шага Б.Т. Поляка на классе относительно липшицевых и относительно слабо выпуклых функций с относительным аналогом острого минимума получены условия, которые гарантируют сходимость такого субградиентного метода со скоростью геометрической прогрессии. Наконец, получен теоретический результат, описывающий влияние погрешности доступной сyбградиентномy методу информации о (сyб)градиенте и целевой функции на оценку качества выдаваемого приближенного решения. Доказано, что при достаточно малой погрешности $\delta > 0$ можно гарантировать достижение точности решения, сопоставимой c $\delta$.

The work is devoted to the study of subgradient methods with different variations of the Polyak stepsize for minimization functions from the class of weakly convex and relatively weakly convex functions that have the corresponding analogue of a sharp minimum. It turns out that, under certain assumptions about the starting point, such an approach can make it possible to justify the convergence of the subgradient method with the speed of a geometric progression. For the subgradient method with the Polyak stepsize, a refined estimate for the rate of convergence is proved for minimization problems for weakly convex functions with a sharp minimum. The feature of this estimate is an additional consideration of the decrease of the distance from the current point of the method to the set of solutions with the increase in the number of iterations. The results of numerical experiments for the phase reconstruction problem (which is weakly convex and has a sharp minimum) are presented, demonstrating the effectiveness of the proposed approach to estimating the rate of convergence compared to the known one. Next, we propose a variation of the subgradient method with switching over productive and non-productive steps for weakly convex problems with inequality constraints and obtain the corresponding analog of the result on convergence with the rate of geometric progression. For the subgradient method with the corresponding variation of the Polyak stepsize on the class of relatively Lipschitz and relatively weakly convex functions with a relative analogue of a sharp minimum, it was obtained conditions that guarantee the convergence of such a subgradient method at the rate of a geometric progression. Finally, a theoretical result is obtained that describes the influence of the error of the information about the (sub)gradient available by the subgradient method and the objective function on the estimation of the quality of the obtained approximate solution. It is proved that for a sufficiently small error $\delta > 0$, one can guarantee that the accuracy of the solution is comparable to $\delta$.

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

This paper is devoted to some variants of improving the convergence rate guarantees of the gradient-type algorithms for relatively smooth and relatively Lipschitz-continuous problems in the case of additional information about some analogues of the strong convexity of the objective function. We consider two classes of problems, namely, convex problems with a relative functional growth condition, and problems (generally, non-convex) with an analogue of the Polyak – Lojasiewicz gradient dominance condition with respect to Bregman divergence. For the first type of problems, we propose two restart schemes for the gradient type methods and justify theoretical estimates of the convergence of two algorithms with adaptively chosen parameters corresponding to the relative smoothness or Lipschitz property of the objective function. The first of these algorithms is simpler in terms of the stopping criterion from the iteration, but for this algorithm, the near-optimal computational guarantees are justified only on the class of relatively Lipschitz-continuous problems. The restart procedure of another algorithm, in its turn, allowed us to obtain more universal theoretical results. We proved a near-optimal estimate of the complexity on the class of convex relatively Lipschitz continuous problems with a functional growth condition. We also obtained linear convergence rate guarantees on the class of relatively smooth problems with a functional growth condition. For a class of problems with an analogue of the gradient dominance condition with respect to the Bregman divergence, estimates of the quality of the output solution were obtained using adaptively selected parameters. We also present the results of some computational experiments illustrating the performance of the methods for the second approach at the conclusion of the paper. As examples, we considered a linear inverse Poisson problem (minimizing the Kullback – Leibler divergence), its regularized version which allows guaranteeing a relative strong convexity of the objective function, as well as an example of a relatively smooth and relatively strongly convex problem. In particular, calculations show that a relatively strongly convex function may not satisfy the relative variant of the gradient dominance condition.

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

Non-smooth optimization often arises in many applied problems. The issues of developing efficient computational procedures for such problems in high-dimensional spaces are very topical. First-order methods (subgradient methods) are well applicable here, but in fairly general situations they lead to low speed guarantees for large-scale problems. One of the approaches to this type of problem can be to identify a subclass of non-smooth problems that allow relatively optimistic results on the rate of convergence. For example, one of the options for additional assumptions can be the condition of a sharp minimum, proposed in the late 1960s by B. T. Polyak. In the case of the availability of information about the minimal value of the function for Lipschitz-continuous problems with a sharp minimum, it turned out to be possible to propose a subgradient method with a Polyak step-size, which guarantees a linear rate of convergence in the argument. This approach made it possible to cover a number of important applied problems (for example, the problem of projecting onto a convex compact set). However, both the condition of the availability of the minimal value of the function and the condition of a sharp minimum itself look rather restrictive. In this regard, in this paper, we propose a generalized condition for a sharp minimum, somewhat similar to the inexact oracle proposed recently by Devolder – Glineur – Nesterov. The proposed approach makes it possible to extend the class of applicability of subgradient methods with the Polyak step-size, to the situation of inexact information about the value of the minimum, as well as the unknown Lipschitz constant of the objective function. Moreover, the use of local analogs of the global characteristics of the objective function makes it possible to apply the results of this type to wider classes of problems. We show the possibility of applying the proposed approach to strongly convex nonsmooth problems, also, we make an experimental comparison with the known optimal subgradient method for such a class of problems. Moreover, there were obtained some results connected to the applicability of the proposed technique to some types of problems with convexity relaxations: the recently proposed notion of weak $\beta$-quasi-convexity and ordinary quasiconvexity. Also in the paper, we study a generalization of the described technique to the situation with the assumption that the $\delta$-subgradient of the objective function is available instead of the usual subgradient. For one of the considered methods, conditions are found under which, in practice, it is possible to escape the projection of the considered iterative sequence onto the feasible set of the problem.

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

The probabilistic topic model of a text document collection finds two matrices: a matrix of conditional probabilities of topics in documents and a matrix of conditional probabilities of words in topics. Each document is represented by a multiset of words also called the “bag of words”, thus assuming that the order of words is not important for revealing the latent topics of the document. Under this assumption, the problem is reduced to a low-rank non-negative matrix factorization governed by likelihood maximization. In general, this problem is ill-posed having an infinite set of solutions. In order to regularize the solution, a weighted sum of optimization criteria is added to the log-likelihood. When modeling large text collections, storing the first matrix seems to be impractical, since its size is proportional to the number of documents in the collection. At the same time, the topical vector representation (embedding) of documents is necessary for solving many text analysis tasks, such as information retrieval, clustering, classification, and summarization of texts. In practice, the topical embedding is calculated for a document “on-the-fly”, which may require dozens of iterations over all the words of the document. In this paper, we propose a way to calculate a topical embedding quickly, by one pass over document words. For this, an additional constraint is introduced into the model in the form of an equation, which calculates the first matrix from the second one in linear time. Although formally this constraint is not an optimization criterion, in fact it plays the role of a regularizer and can be used in combination with other regularizers within the additive regularization framework ARTM. Experiments on three text collections have shown that the proposed method improves the model in terms of sparseness, difference, logLift and coherence measures of topic quality. The open source libraries BigARTM and TopicNet were used for the experiments.