All issues
- 2024 Vol. 16
- 2023 Vol. 15
- 2022 Vol. 14
- 2021 Vol. 13
- 2020 Vol. 12
- 2019 Vol. 11
- 2018 Vol. 10
- 2017 Vol. 9
- 2016 Vol. 8
- 2015 Vol. 7
- 2014 Vol. 6
- 2013 Vol. 5
- 2012 Vol. 4
- 2011 Vol. 3
- 2010 Vol. 2
- 2009 Vol. 1
-
О построении линейно неявных схем, LN-эквивалентных неявным методам Рунге–Кутты
Компьютерные исследования и моделирование, 2012, т. 4, № 3, с. 483-496В работе предложен новый класс безитерационных схем (явно-неявных), который позволяет получать методы, повторяющие на линейных неавтономных задачах свойства лучших неявных жестко-точных методов Рунге–Кутты [Хайрер, Ваннер,1999] – RadauIIA и LobattoIIIC. Для этого используется понятие LN-эквивалентности методов [Ширков, 2012]. С использованием среды аналитических вычислений получены уравнения порядка и затухания таких методов и найдены коэффициенты некоторых схем до 3-го порядка включительно. Проводится численное исследование новых методов на классических тестах, применяемых для проверки схем, разрабатываемых для жестких систем.
Ключевые слова: жесткие системы обыкновенных дифференциальных уравнений, жестко- точные методы Рунге–Кутты и схемы Розенброка, устойчивость и L-эквивалентность.
Constructing of linearly implicit schemes which are LN-equivalent to implicit Runge–Kutta methods
Computer Research and Modeling, 2012, v. 4, no. 3, pp. 483-496Views (last year): 2. Citations: 2 (RSCI).New family of linearly implicit schemes are presented. This family allows to obtain methods which are equivalent to stiffly accurate implicit Runge–Kutta schemes (such as RadauIIA and LobattoIIIC) on nonautonomous linear problems. Notion of LN-equivalence of schemes is introduced. Order conditions and stability conditions of such methods are obtained with the use of media for computer symbolic calculations. Some examples of new schemes have been constructed. Numerical studying of new method have been done with the use of classical tests for stiff problems.
-
Метод построения неструктурированных шестигранных сеток из объемных данных
Компьютерные исследования и моделирование, 2013, т. 5, № 1, с. 11-24Разработан метод преобразования поверхностного представления расчетной области в формат воксельных данных. Предложен алгоритм генерации расчетной шестигранной сетки на основе объемного формата данных.
Ключевые слова: неструктурированная шестигранная сетка, объемные данные, воксель, знакоопределенные поля расстояний, двойственное контурирование.
The method of unstructured hexahedral mesh generation from volumetric data
Computer Research and Modeling, 2013, v. 5, no. 1, pp. 11-24Views (last year): 4. Citations: 11 (RSCI).The method of conversion of surface representation to the voxel data is developed. Voxel data based algorithm of hexahedral mesh generation is proposed.
-
О разложении матриц при помощи метода стохастического градиентного спуска в приложении к задаче направляемой классификации микрочипов
Компьютерные исследования и моделирование, 2013, т. 5, № 2, с. 131-140Многомерные данные, при использовании значительно большего количества признаков относительно меньшего числа наблюдений, порождают хорошо известную проблему переопределённой задачи. В связи с этим, представляется целесообразным описание данных в терминах меньшего числа мета-признаков, которые вычисляются при помощи так называемых матричных факторизаций. Такие факторизации способствуют уменьшению случайного шума при сохранении наиболее существенной информации. Три новых и взаимосвязанных метода предложены в этой статье: 1) факторизационный механизм градиентного спуска с двумя (согласно размерности микрочипа) гибкими и адаптируемыми параметрами обучения, включая явные формулы их автоматического пересчета, 2) непараметрический критерий для отбора количества факторов, и 3) неотрицательная модификация градиентной факторизации, которая не требует дополнительных вычислительных затрат в сравнении с базовой моделью. Мы иллюстрируем эффективность предложенных методов в приложении к задаче направляемой классификации данных в области биоинформатики.
Ключевые слова: матричная факторизация, ненаправляемое обучение, количество факторов, непараметрический критерий, неотрицательность, оставить одного извне, классификация.
On the stochastic gradient descent matrix factorization in application to the supervised classification of microarrays
Computer Research and Modeling, 2013, v. 5, no. 2, pp. 131-140Citations: 4 (RSCI).Microarray datasets are highly dimensional, with a small number of collected samples in comparison to thousands of features. This poses a significant challenge that affects the interpretation, applicability and validation of the analytical results. Matrix factorizations have proven to be a useful method for describing data in terms of a small number of meta-features, which reduces noise, while still capturing the essential features of the data. Three novel and mutually relevant methods are presented in this paper: 1) gradient-based matrix factorization with two adaptive learning rates (in accordance with the number of factor matrices) and their automatic updates; 2) nonparametric criterion for the selection of the number of factors; and 3) nonnegative version of the gradient-based matrix factorization which doesn't require any extra computational costs in difference to the existing methods. We demonstrate effectiveness of the proposed methods to the supervised classification of gene expression data.
-
Подход к разработке алгоритмов ньютоновских методов безусловной оптимизации, программная реализация и сравнение эффективности
Компьютерные исследования и моделирование, 2013, т. 5, № 3, с. 367-377Предложен подход к увеличению эффективности алгоритма Гилла и Мюррея к построению ньютоновских методов безусловной оптимизации с регулировкой шага, основанных на факторизации Холецкого. Доказано, что стратегия выбора направления спуска определяет и решение проблемы масштабирования шагов при спуске, и аппроксимацию не квадратичными функциями, и интеграцию с методом доверительной окрестности.
Approach to development of algorithms of Newtonian methods of unconstrained optimization, their software implementation and benchmarking
Computer Research and Modeling, 2013, v. 5, no. 3, pp. 367-377Views (last year): 2. Citations: 7 (RSCI).The approach to increase efficiency of Gill and Murray's algorithm of Newtonian methods of unconstrained optimization with step adjustment creation is offered, rests on Cholesky’s factorization. It is proved that the strategy of choice of the descent direction also determines the solution of the problem of scaling of steps at descent, and approximation by non-quadratic functions, and integration with a method of a confidential vicinity.
-
Идентификация онлайн-подписи с помощью оконного преобразования Фурье и радиального базиса
Компьютерные исследования и моделирование, 2014, т. 6, № 3, с. 357-364В данной работе описан метод идентификации онлайн-подписи с использованием оконного преобразования Фурье и вейвлет-преобразования с радиальным базисом специального вида. При идентификации используются динамические характеристики подписи. Приведены оценки достоверности предложенной процедуры.
Ключевые слова: онлайн-подпись, оконное преобразование Фурье, вейвлет-преобразование, радиальный базис.
On-line signature identification using a short-time Fourier transform and the radial basis
Computer Research and Modeling, 2014, v. 6, no. 3, pp. 357-364Views (last year): 4. Citations: 3 (RSCI).This paper describes a method of on-line signature identification using the short-time Fourier transform and wavelet transform with radial basis of a special kind. In carrying out the identification, we use dynamic properties signature. We adduce the assessment of the reliability of the proposed procedure.
-
Обоснование гипотезы об оптимальных оценках скорости сходимости численных методов выпуклой оптимизации высоких порядков
Компьютерные исследования и моделирование, 2018, т. 10, № 6, с. 737-753В данной работе рассматривается проксимальный быстрый градиентный метод Монтейро – Свайтера (2013 г.), в котором используется один шаг метода Ньютона для приближенного решения вспомогательной задачи на каждой итерации проксимального метода. Метод Монтейро – Свайтера является оптимальным (по числу вычислений градиента и гессиана оптимизируемой функции) для достаточно гладких задач выпуклой оптимизации в классе методов, использующих только градиент и гессиан оптимизируемой функции. За счет замены шага метода Ньютона на шаг недавно предложенного тензорного метода Ю. Е. Нестерова (2018 г.), а также за счет специального обобщения условия подбора шага в проксимальном внешнем быстром градиентном методе удалось предложить оптимальный тензорный метод, использующий старшие производные. В частности, такой тензорный метод, использующий производные до третьего порядка включительно, оказался достаточно практичным ввиду сложности итерации, сопоставимой со сложностью итерации метода Ньютона. Таким образом, получено конструктивное решение задачи, поставленной Ю. Е. Нестеровым в 2018 г., об устранении зазора в точных нижних и завышенных верхних оценках скорости сходимости для имеющихся на данный момент тензорных методов порядка $p \geqslant 3$.
Ключевые слова: метод Ньютона, матрица Гессе, нижние оценки, методы высокого порядка, тензорные методы, проксимальный быстрый градиентный метод.
The global rate of convergence for optimal tensor methods in smooth convex optimization
Computer Research and Modeling, 2018, v. 10, no. 6, pp. 737-753Views (last year): 75.In this work we consider Monteiro – Svaiter accelerated hybrid proximal extragradient (A-HPE) framework and accelerated Newton proximal extragradient (A-NPE) framework. The last framework contains an optimal method for rather smooth convex optimization problems with second-order oracle. We generalize A-NPE framework for higher order derivative oracle (schemes). We replace Newton’s type step in A-NPE that was used for auxiliary problem by Newton’s regularized (tensor) type step (Yu. Nesterov, 2018). Moreover we generalize large step A-HPE/A-NPE framework by replacing Monteiro – Svaiter’s large step condition so that this framework could work for high-order schemes. The main contribution of the paper is as follows: we propose optimal highorder methods for convex optimization problems. As far as we know for that moment there exist only zero, first and second order optimal methods that work according to the lower bounds. For higher order schemes there exists a gap between the lower bounds (Arjevani, Shamir, Shiff, 2017) and existing high-order (tensor) methods (Nesterov – Polyak, 2006; Yu.Nesterov, 2008; M. Baes, 2009; Yu.Nesterov, 2018). Asymptotically the ratio of the rates of convergences for the best existing methods and lower bounds is about 1.5. In this work we eliminate this gap and show that lower bounds are tight. We also consider rather smooth strongly convex optimization problems and show how to generalize the proposed methods to this case. The basic idea is to use restart technique until iteration sequence reach the region of quadratic convergence of Newton method and then use Newton method. One can show that the considered method converges with optimal rates up to a logarithmic factor. Note, that proposed in this work technique can be generalized in the case when we can’t solve auxiliary problem exactly, moreover we can’t even calculate the derivatives of the functional exactly. Moreover, the proposed technique can be generalized to the composite optimization problems and in particular to the constraint convex optimization problems. We also formulate a list of open questions that arise around the main result of this paper (optimal universal method of high order e.t.c.).
Indexed in Scopus
Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU
The journal is included in the Russian Science Citation Index
The journal is included in the RSCI
International Interdisciplinary Conference "Mathematics. Computing. Education"