All issues

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

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.

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

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

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

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

Small practical value of many numerical methods for solving single-ended systems of linear equations with ill-conditioned matrices due to the fact that these methods in the practice behave quite differently than in the case of precise calculations. Historically, sustainability is not enough attention was given, unlike in numerical algebra ‘medium-sized’, and emphasis is given to solving the problems of maximal order in data capabilities of the computer, including the expense of some loss of accuracy. Therefore, the main objects of study is the most appropriate storage of information contained in the sparse matrix; maintaining the highest degree of rarefaction at all stages of the computational process. Thus, the development of efficient numerical methods for solving unstable systems refers to the actual problems of computational mathematics.

In this paper, the approach to the construction of numerically stable direct multiplier methods for solving systems of linear equations, taking into account sparseness of matrices, presented in packaged form. The advantage of the approach consists in minimization of filling the main lines of the multipliers without compromising accuracy of the results and changes in the position of the next processed row of the matrix are made that allows you to use static data storage formats. The storage format of sparse matrices has been studied and the advantage of this format consists in possibility of parallel execution any matrix operations without unboxing, which significantly reduces the execution time and memory footprint.

Direct multiplier methods for solving systems of linear equations are best suited for solving problems of large size on a computer — sparse matrix systems allow you to get multipliers, the main row of which is also sparse, and the operation of multiplication of a vector-row of the multiplier according to the complexity proportional to the number of nonzero elements of this multiplier.

As a direct continuation of this work is proposed in the basis for constructing a direct multiplier algorithm of linear programming to put a modification of the direct multiplier algorithm for solving systems of linear equations based on integration of technique of linear programming for methods to select the host item. Direct multiplicative methods of linear programming are best suited for the construction of a direct multiplicative algorithm set the direction of descent Newton methods in unconstrained optimization by integrating one of the existing design techniques significantly positive definite matrix of the second derivatives.

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

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

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

Multiplicative methods for sparse matrices are best suited to reduce the complexity of operations solving systems of linear equations performed on each iteration of the simplex method. The matrix of constraints in these problems of sparsely populated nonzero elements, which allows to obtain the multipliers, the main columns which are also sparse, and the operation of multiplication of a vector by a multiplier according to the complexity proportional to the number of nonzero elements of this multiplier. In addition, the transition to the adjacent basis multiplier representation quite easily corrected. To improve the efficiency of such methods requires a decrease in occupancy multiplicative representation of the nonzero elements. However, at each iteration of the algorithm to the sequence of multipliers added another. As the complexity of multiplication grows and linearly depends on the length of the sequence. So you want to run from time to time the recalculation of inverse matrix, getting it from the unit. Overall, however, the problem is not solved. In addition, the set of multipliers is a sequence of structures, and the size of this sequence is inconvenient is large and not precisely known. Multiplicative methods do not take into account the factors of the high degree of sparseness of the original matrices and constraints of equality, require the determination of initial basic feasible solution of the problem and, consequently, do not allow to reduce the dimensionality of a linear programming problem and the regular procedure of compression — dimensionality reduction of multipliers and exceptions of the nonzero elements from all the main columns of multipliers obtained in previous iterations. Thus, the development of numerical methods for the solution of linear programming problems, which allows to overcome or substantially reduce the shortcomings of the schemes implementation of the simplex method, refers to the current problems of computational mathematics.

In this paper, the approach to the construction of numerically stable direct multiplier methods for solving problems in linear programming, taking into account sparseness of matrices, presented in packaged form. The advantage of the approach is to reduce dimensionality and minimize filling of the main rows of multipliers without compromising accuracy of the results and changes in the position of the next processed row of the matrix are made that allows you to use static data storage formats.

As a direct continuation of this work is the basis for constructing a direct multiplicative algorithm set the direction of descent in the Newton methods for unconstrained optimization is proposed to put a modification of the direct multiplier method, linear programming by integrating one of the existing design techniques significantly positive definite matrix of the second derivatives.

Дороги — ресурс, который может использоваться как водителями, так и автономными транспортными средствами. Ежегодно количество транспортных средств увеличивается, из-за чего каждое отдельно взятое транспортное средство тратит всё больше времени в пробках, тем самым увеличивая суммарные временные затраты. При планировании новой дороги ключевой задачей становится сокращение времени в пути. Оптимизация транспортных сетей в настоящее время часто происходит с помощью добавления новых связующих дорог между высоконагруженными частями трасс. Парадокс Браесса заключается в том, что построение нового ребра дорожной сети приводит к увеличению времени в пути для каждого транспортного средства в сети. Целью данной статьи является предложение различных разрешений парадокса Браесса при рассмотрении автономных транспортных средств в качестве участников дорожного движения. Один из вариантов топологического решения транспортной задачи — использование искусственных ограничителей трафика. Как пример таких ограничителей статья рассматривает введение выделенных полос, доступных только для определенных видов транспорта. Выделенные полосы занимают особое место в транспортной сети и могут обслуживать поток по-разному. В данной статье рассмотрены наиболее часто встречающиеся случаи распределения трафика на сети из двух дорог, приведены аналитический и численный методы оптимизации модели и представлена модель оптимального распределения трафика, которая рассматривает различные варианты выделения полос на изолированной транспортной сети. В результате проведенных исследований было обнаружено, что введение выделенных полос решает парадокс Браесса и приводит к уменьшению общего времени в пути. Решения приведены как для искусственно смоделированной сети, так и на реальных примерах. В статье представлен алгоритм моделирования трафика на браессовской сети и приведено обоснование его корректности на реальном примере.

Roads are a shared resource which can be used either by drivers and autonomous vehicles. Since the total number of vehicles increases annually, each considered vehicle spends more time in traffic jams, and thus the total travel time prolongs. The main purpose while planning the road system is to reduce the time spent on traveling. The optimization of transportation networks is a current goal, thus the formation of traffic flows by creating certain ligaments of the roads is of high importance. The Braess paradox states the existence of a network where the construction of a new edge leads to the increase of traveling time. The objective of this paper is to propose various solutions to the Braess paradox in the presence of autonomous vehicles. One of the methods of solving transportation topology problems is to introduce artificial restrictions on traffic. As an example of such restrictions, this article considers designated lanes which are available only for a certain type of vehicles. Designated lanes have their own location in the network and operating conditions. This article observes the most common two-roads traffic situations, analyzes them using analytical and numerical methods and presents the model of optimal traffic flow distribution, which considers different ways of lanes designation on isolated transportation networks. It was found that the modeling of designated lanes eliminates Braess’ paradox and optimizes the total traveling time. The solutions were shown on artificial networks and on the real-life example. A modeling algorithm for Braess network was proposed and its correctness was verified using the real-life example.

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

$$ \text{Argmin}_{x\in X}{\langle p,\,x \rangle} $$

для заданного вектора $p \in \mathbb{R}^n$. Существует целый ряд методов условного градиента, имеющих линейную скорость сходимости в сильно выпуклом случае. Однако во всех этих методах в оценку скорости сходимости входит размерность задачи, которая в современных приложениях может быть очень большой. В данной работе доказывается, что в сильно выпуклом случае скорость сходимости методов условного градиента в лучшем случае зависит от размерности задачи $n$ как $\widetilde{\Omega}\left(\!\sqrt{n}\right)$. Таким образом, методы условного градиента могут оказаться неэффективными для решения сильно выпуклых оптимизационных задач больших размерностей.

Отдельно рассматривается приложение методов условного градиента к задачам минимизации квадратичной формы. Уже была доказана эффективность метода Франк – Вульфа для решения задачи квадратичной оптимизации в выпуклом случае на симплексе (PageRank). Данная работа показывает, что использование методов условного градиента для минимизации квадратичной формы в сильно выпуклом случае малоэффективно из-за наличия размерности в оценке скорости сходимости этих методов. Поэтому рассматривается метод рестартов условного градиента (Shrinking Conditional Gradient). Его отличие от методов условного градиента заключается в том, что в нем используется модифицированный линейный минимизационный оракул, который для заданного вектора $p \in \mathbb{R}^n$ вычисляет решение задачи $$ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. $$ В оценку скорости сходимости такого алгоритма размерность уже не входит. С помощью рестартов метода условного градиента получена сложность (число арифметических операций) минимизации квадратичной формы на $\infty$-шаре. Полученная оценка работы метода сравнима со сложностью градиентного метода.

In this paper, we consider conditional gradient methods for optimizing strongly convex functions. These are methods that use a linear minimization oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem

\[ \text{Argmin}_{x\in X}{\langle p,\,x \rangle}. \]There are a variety of conditional gradient methods that have a linear convergence rate in a strongly convex case. However, in all these methods, the dimension of the problem is included in the rate of convergence, which in modern applications can be very large. In this paper, we prove that in the strongly convex case, the convergence rate of the conditional gradient methods in the best case depends on the dimension of the problem $ n $ as $ \widetilde {\Omega} \left(\!\sqrt {n}\right) $. Thus, the conditional gradient methods may turn out to be ineffective for solving strongly convex optimization problems of large dimensions.

Also, the application of conditional gradient methods to minimization problems of a quadratic form is considered. The effectiveness of the Frank – Wolfe method for solving the quadratic optimization problem in the convex case on a simplex (PageRank) has already been proved. This work shows that the use of conditional gradient methods to solve the minimization problem of a quadratic form in a strongly convex case is ineffective due to the presence of dimension in the convergence rate of these methods. Therefore, the Shrinking Conditional Gradient method is considered. Its difference from the conditional gradient methods is that it uses a modified linear minimization oracle. It's an oracle, which, for a given vector $p \in \mathbb{R}^n$, computes the solution of the subproblem \[ \text{Argmin}\{\langle p, \,x \rangle\colon x\in X, \;\|x-x_0^{}\| \leqslant R \}. \] The convergence rate of such an algorithm does not depend on dimension. Using the Shrinking Conditional Gradient method the complexity (the total number of arithmetic operations) of solving the minimization problem of quadratic form on a $ \infty $-ball is obtained. The resulting evaluation of the method is comparable to the complexity of the gradient method.

Модели многозначной классификации возникают в различных сферах современной жизни, что объясняется всё большим количеством информации, требующей оперативного анализа. Одним из математических методов решения этой задачи является модульный метод, на первом этапе которого для каждого класса строится некоторая ранжирующая функция, упорядочивающая некоторым образом все объекты, а на втором этапе для каждого класса выбирается оптимальное значение порога, объекты с одной стороны которого относят к текущему классу, а с другой — нет. Пороги подбираются так, чтобы максимизировать целевую метрику качества. Алгоритмы, свойства которых изучаются в настоящей статье, посвящены второму этапу модульного подхода — выбору оптимального вектора порогов. Этот этап становится нетривиальным в случае использования в качестве целевой метрики качества $F$-меры от средней точности и полноты, так как она не допускает независимую оптимизацию порога в каждом классе. В задачах экстремальной многозначной классификации число классов может достигать сотен тысяч, поэтому исходная оптимизационная задача сводится к задаче поиска неподвижной точки специальным образом введенного отображения $\boldsymbol V$, определенного на единичном квадрате на плоскости средней точности $P$ и полноты $R$. Используя это отображение, для оптимизации предлагаются два алгоритма: метод линеаризации $F$-меры и метод анализа области определения отображения $\boldsymbol V$. На наборах данных многозначной классификации разного размера и природы исследуются свойства алгоритмов, в частности зависимость погрешности от числа классов, от параметра $F$-меры и от внутренних параметров методов. Обнаружена особенность работы обоих алгоритмов для задач с областью определения отображения $\boldsymbol V$, содержащей протяженные линейные участки границ. В случае когда оптимальная точка расположена в окрестности этих участков, погрешности обоих методов не уменьшаются с увеличением количества классов. При этом метод линеаризации достаточно точно определяет аргумент оптимальной точки, а метод анализа области определения отображения $\boldsymbol V$ — полярный радиус.

Multi-label classification models arise in various areas of life, which is explained by an increasing amount of information that requires prompt analysis. One of the mathematical methods for solving this problem is a plug-in approach, at the first stage of which, for each class, a certain ranking function is built, ordering all objects in some way, and at the second stage, the optimal thresholds are selected, the objects on one side of which are assigned to the current class, and on the other — to the other. Thresholds are chosen to maximize the target quality measure. The algorithms which properties are investigated in this article are devoted to the second stage of the plug-in approach which is the choice of the optimal threshold vector. This step becomes non-trivial if the $F$-measure of average precision and recall is used as the target quality assessment since it does not allow independent threshold optimization in each class. In problems of extreme multi-label classification, the number of classes can reach hundreds of thousands, so the original optimization problem is reduced to the problem of searching a fixed point of a specially introduced transformation $\boldsymbol V$, defined on a unit square on the plane of average precision $P$ and recall $R$. Using this transformation, two algorithms are proposed for optimization: the $F$-measure linearization method and the method of $\boldsymbol V$ domain analysis. The properties of algorithms are studied when applied to multi-label classification data sets of various sizes and origin, in particular, the dependence of the error on the number of classes, on the $F$-measure parameter, and on the internal parameters of methods under study. The peculiarity of both algorithms work when used for problems with the domain of $\boldsymbol V$, containing large linear boundaries, was found. In case when the optimal point is located in the vicinity of these boundaries, the errors of both methods do not decrease with an increase in the number of classes. In this case, the linearization method quite accurately determines the argument of the optimal point, while the method of $\boldsymbol V$ domain analysis — the polar radius.

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

В данной работе этот алгоритм лежит в основе решения следующих задач.

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

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

Задача 3. Построение непрерывного аналога задачи минимизации вещественного квадратичного многочлена от булевых переменных и новой формы задания необходимых и достаточных условий оптимальности для разработки методов их решения за полиномиальное время. В результате исходная задача сводится к задаче поиска минимального расстояния между началом координат и угловой точкой выпуклого многогранника (полиэдра), который является возмущением $n$-мерного куба и описывается системой двойных линейных неравенств с верхней треугольной матрицей коэффициентов с единицами на главной диагонали. Исследованию подлежат только две грани, одна из которых или обе содержат вершины, ближайшие к началу координат. Для их вычисления достаточно решить $4n – 4$ систем линейных уравнений и выбрать среди них все ближайшие равноудаленные вершины за полиномиальное время. Задача минимизации квадратичного полинома является $NP$-трудной, поскольку к ней сводится $NP$-трудная задача о вершинном покрытии для произвольного графа. Отсюда следует вывод, что $P = NP$, в основе построения которого лежит выход за пределы целочисленных методов оптимизации.

We consider a numerically stable direct multiplicative algorithm of solving linear equations systems, which takes into account the sparseness of matrices presented in a packed form. The advantage of the algorithm is the ability to minimize the filling of the main rows of multipliers without losing the accuracy of the results. Moreover, changes in the position of the next processed row of the matrix are not made, what allows using static data storage formats. Linear system solving by a direct multiplicative algorithm is, like the solving with $LU$-decomposition, just another scheme of the Gaussian elimination method implementation.

In this paper, this algorithm is the basis for solving the following problems:

Problem 1. Setting the descent direction in Newtonian methods of unconditional optimization by integrating one of the known techniques of constructing an essentially positive definite matrix. This approach allows us to weaken or remove additional specific difficulties caused by the need to solve large equation systems with sparse matrices presented in a packed form.

Problem 2. Construction of a new mathematical formulation of the problem of quadratic programming and a new form of specifying necessary and sufficient optimality conditions. They are quite simple and can be used to construct mathematical programming methods, for example, to find the minimum of a quadratic function on a polyhedral set of constraints, based on solving linear equations systems, which dimension is not higher than the number of variables of the objective function.

Problem 3. Construction of a continuous analogue of the problem of minimizing a real quadratic polynomial in Boolean variables and a new form of defining necessary and sufficient conditions of optimality for the development of methods for solving them in polynomial time. As a result, the original problem is reduced to the problem of finding the minimum distance between the origin and the angular point of a convex polyhedron, which is a perturbation of the $n$-dimensional cube and is described by a system of double linear inequalities with an upper triangular matrix of coefficients with units on the main diagonal. Only two faces are subject to investigation, one of which or both contains the vertices closest to the origin. To calculate them, it is sufficient to solve $4n – 4$ linear equations systems and choose among them all the nearest equidistant vertices in polynomial time. The problem of minimizing a quadratic polynomial is $NP$-hard, since an $NP$-hard problem about a vertex covering for an arbitrary graph comes down to it. It follows therefrom that $P = NP$, which is based on the development beyond the limits of integer optimization methods.