Все выпуски

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

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

Mechanical properties of eukaryotic cells play an important role in life cycle conditions and in the development of pathological processes. In this paper we discuss the problem of parameters identification and verification of viscoelastic constitutive models based on force spectroscopy data of living cells. It is proposed to use one-dimensional continuous wavelet transform to calculate the relaxation function. Analytical calculations and the results of numerical simulation are given, which allow to obtain relaxation functions similar to each other on the basis of experimentally determined force curves and theoretical stress-strain relationships using wavelet differentiation algorithms. Test examples demonstrating correctness of software implementation of the proposed algorithms are analyzed. The cell models are considered, on the example of which the application of the proposed procedure of identification and verification of their parameters is demonstrated. Among them are a structural-mechanical model with parallel connected fractional elements, which is currently the most adequate in terms of compliance with atomic force microscopy data of a wide class of cells, and a new statistical-thermodynamic model, which is not inferior in descriptive capabilities to models with fractional derivatives, but has a clearer physical meaning. For the statistical-thermodynamic model, the procedure of its construction is described in detail, which includes the following. Introduction of a structural variable, the order parameter, to describe the orientation properties of the cell cytoskeleton. Setting and solving the statistical problem for the ensemble of actin filaments of a representative cell volume with respect to this variable. Establishment of the type of free energy depending on the order parameter, temperature and external load. It is also proposed to use an oriented-viscous-elastic body as a model of a representative element of the cell. Following the theory of linear thermodynamics, evolutionary equations describing the mechanical behavior of the representative volume of the cell are obtained, which satisfy the basic thermodynamic laws. The problem of optimizing the parameters of the statisticalthermodynamic model of the cell, which can be compared both with experimental data and with the results of simulations based on other mathematical models, is also posed and solved. The viscoelastic characteristics of cells are determined on the basis of comparison with literature data.

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

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

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

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

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

In the first part of the paper we present convergence analysis of AGMsDR method on a new class of functions — in general non-convex with $M$-Lipschitz-continuous gradients that satisfy Polyak – Lojasiewicz condition. Method does not need the value of $\mu^{PL}>0$ in the condition and converges linearly with a scale factor $\left(1 - \frac{\mu^{PL}}{M}\right)$. It was previously proved that method converges as $O\left(\frac1{k^2}\right)$ if a function is convex and has $M$-Lipschitz-continuous gradient and converges linearly with a~scale factor $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$ if the value of strong convexity parameter $\mu^{SC}>0$ is known. The novelty is that one can save linear convergence if $\frac{\mu^{PL}}{\mu^{SC}}$ is not known, but without square root in the scale factor.

The second part presents modification of AGMsDR method for solving problems that allow alternating minimization (Alternating AGMsDR). The similar results are proved.

As the result, we present adaptive accelerated methods that converge as $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ on a class of convex functions with $M$-Lipschitz-continuous gradient that satisfy Polyak – Lojasiewicz condition. Algorithms do not need values of $M$ and $\mu^{PL}$. If Polyak – Lojasiewicz condition does not hold, the convergence is $O\left(\frac1{k^2}\right)$, but no tuning needed.

We also consider the adaptive catalyst envelope of non-accelerated gradient methods. The envelope allows acceleration up to $O\left(\frac1{k^2}\right)$. We present numerical comparison of non-accelerated adaptive gradient descent which is accelerated using adaptive catalyst envelope with AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) and Sinkhorn's algorithm on the problem dual to the optimal transport problem.

Conducted experiments show faster convergence of alternating AGMsDR in comparison with described catalyst approach and AGMsDR, despite the same asymptotic rate $O\left(\frac1{k^2}\right)$. Such behavior can be explained by linear convergence of AGMsDR method and was tested on quadratic functions. Alternating AGMsDR demonstrated better performance in comparison with AGMsDR.

Ламинарно-турбулентный переход является предметом активных исследований, связанных с повышением экономической эффективности авиатранспорта, так как в турбулентном пограничном слое увеличивается сопротивление, что ведет к росту расхода топлива. Одним из направлений таких исследований является поиск эффективных методов нахождения положения перехода в пространстве. Используя эту информацию при проектировании летательного аппарата, инженеры могут прогнозировать его технические характеристики и рентабельность уже на начальных этапах проекта. Традиционным для индустрии подходом к решению задачи поиска координат ламинарно-турбулентного перехода является $e^N$-метод. Однако, несмотря на повсеместное применение, он обладает рядом существенных недостатков, так как основан на предположении о параллельности моделируемого потока, что ограничивает сценарии его применения, а также требует проводить вычислительно затратные расчеты в широком диапазоне частот и волновых чисел. Альтернативой $e^N$-методу может служить применение метода Dynamic Mode Decomposition, который позволяет провести анализ возмущений потока, напрямую используя данные о нем. Это избавляет от необходимости в проведении затратных вычислений, а также расширяет область применения метода ввиду отсутствия в его построении предположений о параллельности потока.

В представленном исследовании предлагается подход к нахождению положения ламинарно-турбулентного перехода с применением метода Dynamic Mode Decomposition, заключающийся в разбиении региона пограничного слоя на множества подобластей, по каждому из которых независимо вычисляется точка перехода, после чего результаты усредняются. Подход валидируется на случаях дозвукового и сверхзвукового обтекания двумерной пластины с нулевым градиентом давления. Результаты демонстрируют принципиальную применимость и высокую точность описываемого метода в широком диапазоне условий. Проводится сравнение с $e^N$-методом, доказывающее преимущества предлагаемого подхода, выражающиеся в более быстром получении результата при сопоставимой с $e^N$-методом точности получаемого решения, что говорит о перспективности использования описываемого подхода в прикладных задачах.

Laminar-turbulent transition is the subject of an active research related to improvement of economic efficiency of air vehicles, because in the turbulent boundary layer drag increases, which leads to higher fuel consumption. One of the directions of such research is the search for efficient methods, that can be used to find the position of the transition in space. Using this information about laminar-turbulent transition location when designing an aircraft, engineers can predict its performance and profitability at the initial stages of the project. Traditionally, $e^N$ method is applied to find the coordinates of a laminar-turbulent transition. It is a well known approach in industry. However, despite its widespread use, this method has a number of significant drawbacks, since it relies on parallel flow assumption, which limits the scenarios for its application, and also requires computationally expensive calculations in a wide range of frequencies and wave numbers. Alternatively, flow analysis can be done by using Dynamic Mode Decomposition, which allows one to analyze flow disturbances using flow data directly. Since Dynamic Mode Decomposition is a dimensionality reduction method, the number of computations can be dramatically reduced. Furthermore, usage of Dynamic Mode Decomposition expands the applicability of the whole method, due to the absence of assumptions about the parallel flow in its derivation.

The presented study proposes an approach to finding the location of a laminar-turbulent transition using the Dynamic Mode Decomposition method. The essence of this approach is to divide the boundary layer region into sets of subregions, for each of which the transition point is independently calculated, using Dynamic Mode Decomposition for flow analysis, after which the results are averaged to produce the final result. This approach is validated by laminar-turbulent transition predictions of subsonic and supersonic flows over a 2D flat plate with zero pressure gradient. The results demonstrate the fundamental applicability and high accuracy of the described method in a wide range of conditions. The study focuses on comparison with the $e^N$ method and proves the advantages of the proposed approach. It is shown that usage of Dynamic Mode Decomposition leads to significantly faster execution due to less intensive computations, while the accuracy is comparable to the such of the solution obtained with the $e^N$ method. This indicates the prospects for using the described approach in a real world applications.

В данной статье рассматривается проблема централизованного планирования маршрутов передачи данных в сетях, устойчивых к задержкам и разрывам. Исходная проблема расширяется дополнительными требованиями к хранению узлов и процессу связи. Во-первых, предполагается, что связь между узлами графа устанавливается с помощью антенн. Во-вторых, предполагается, что каждый узел имеет хранилище конечной емкости. Существующие работы не рассматривают и не решают задачу с этими ограничениями. Предполагается, что заранее известны информация о сообщениях, подлежащих обработке, информация о конфигурации сети в указанные моменты времени, взятые с определенными периодами, информация о временных задержках для ориентации антенн для передачи данных и ограничения на объем хранения данных на каждом спутнике группировки. Два хорошо известных алгоритма — CGR и Earliest Delivery with All Queues — модифицированы для удовлетворения расширенных требований. Полученные алгоритмы решают задачу поиска оптимального маршрута в сети, устойчивой к разрывам, отдельно для каждого сообщения. Также рассматривается проблема валидации алгоритмов в условиях отсутствия тестовых данных. Предложены и апробированы возможные подходы к валидации, основанные на качественных предположениях, описаны результаты экспериментов. Проведен сравнительный анализ производительности двух алгоритмов решения задачи маршрутизации. Два алгоритма, названные RDTNAS-CG и RDTNAS-AQ, были разработаны на основе алгоритмов CGR и Earliest Delivery with All Queues соответственно. Оригинальные алгоритмы были значительно расширены и была разработана дополненная реализация. Валидационные эксперименты были проведены для проверки минимальных требований «качества» к правильности алгоритмов. Сравнительный анализ производительности двух алгоритмов показал, что алгоритм RDTNAS-AQ на несколько порядков быстрее, чем RDTNAS-CG.

The problem of centralized planning for data transmission routes in delay tolerant networks is considered. The original problem is extended with additional requirements to nodes storage and communication process. First, it is assumed that the connection between the nodes of the graph is established using antennas. Second, it is assumed that each node has a storage of finite capacity. The existing works do not consider these requirements. It is assumed that we have in advance information about messages to be processed, information about the network configuration at specified time points taken with a certain time periods, information on time delays for the orientation of the antennas for data transmission and restrictions on the amount of data storage on each satellite of the grouping. Two wellknown algorithms — CGR and Earliest Delivery with All Queues are improved to satisfy the extended requirements. The obtained algorithms solve the optimal message routing problem separately for each message. The problem of validation of the algorithms under conditions of lack of test data is considered as well. Possible approaches to the validation based on qualitative conjectures are proposed and tested, and experiment results are described. A performance comparison of the two implementations of the problem solving algorithms is made. Two algorithms named RDTNAS-CG and RDTNAS-AQ have been developed based on the CGR and Earliest Delivery with All Queues algorithms, respectively. The original algorithms have been significantly expanded and an augmented implementation has been developed. Validation experiments were carried to check the minimum «quality» requirements for the correctness of the algorithms. Comparative analysis of the performance of the two algorithms showed that the RDTNAS-AQ algorithm is several orders of magnitude faster than RDTNAS-CG.

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

The decomposition algorithms provide approaches to deal with NP-hardness in solving discrete optimization problems (DOPs). In this article one of the promising ways to exploit sparse matrices — local elimination algorithm in parallel interpretation (LEAP) are demonstrated. That is a graph-based structural decomposition algorithm, which allows to compute a solution in stages such that each of them uses results from previous stages. At the same time LEAP heavily depends on elimination ordering which actually provides solving stages. Also paper considers tree- and block-parallel for LEAP and required realization process of it comparison of a several heuristics for obtaining a better elimination order and shows how is related graph structure, elimination ordering and solving time.

В работе рассматриваются возможности реализации крупноблочных схем метода ветвей и границ для решения частично целочисленных задач линейного программирования. В качестве основы берется пакет оптимизации с открытым исходным кодом CBC. Анализируется возможность использования пакета для реализации крупноблочной схемы метода ветвей и границ. Система реализуется с использованием языка Erlang. Проводятся численные эксперименты на основе задачи о коммивояжере, показывающие заметное ускорение распределенной схемы решения задачи по сравнению с единичным однопоточным экземпляром пакета.

The paper presents an implementation of branch and bound algorithm employing coarse grained parallelism. The system is based on CBC (COIN-OR branch and cut) open-source MIP solver and inter-process communication capabilities of Erlang. Numerical results show noticeable speedup in comparison to single-threaded CBC instance.

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

In this paper, we introduce the concept of non-uniform cellular genetic algorithm, in which a number of parameters that affect the operation of genetic operators is dependent on the location of the cells of a given cellular space. The results of numerical comparison of non-uniform cellular genetic algorithms with the standard genetic algorithms, showing the advantages of the proposed approach while minimizing multimodal functions with a large number of local extrema, are presented. The coarse-grained parallel implementation of the non-uniform algorithms using the technology of MPI is considered.