Search

Necessary and sufficient conditions for the internal stability of formations whose dynamics are obtained is determined by linear differential equations., Comment: in Russian language Fixed an error in the English version of the title of the work

The paper presents various modifications of the Frank-Wolfe algorithm in the equilibrium traffic assignment problem. The Beckman model is used as a model for experiments. In this article, first of all, attention is paid to the choice of the direction of the basic step of the Frank-Wolfe algorithm. Algorithms will be presented: Conjugate Frank-Wolfe (CFW), Bi -conjugate Frank-Wolfe (BFW), Fukushima Frank-Wolfe (FFW). Each modification corresponds to different approaches to the choice of this direction. Some of these modifications are described in previous works of the authors. In this article, following algorithms will be proposed: N-conjugate Frank-Wolfe (NFW), Weighted Fukushima Frank-Wolfe (WFFW). These algorithms are some ideological continuation of the BFW and FFW algorithms. Thus, if the first algorithm used at each iteration the last two directions of the previous iterations to select the next direction conjugate to them, then the proposed algorithm NFW is using more than N previous directions. In the case of Fukushima Frank-Wolfe, the average of several previous directions is taken as the next direction. According to this algorithm, a modification WFFW is proposed, which uses a exponential smoothing from previous directions. Experiments with various modifications were carried out on several datasets representing urban structures and taken from publicly available sources. The relative gap value was taken as the quality metric. The experimental results showed the advantage of algorithms using the previous directions for step selection over the classic Frank-Wolfe algorithm. In addition, an improvement in efficiency was revealed when using more than two conjugate directions. For example, on various datasets, the modification 3FW showed the best convergence. In addition, the proposed modification WFFW often overtook FFW and CFW, although performed worse than NFW., Comment: 14 pages, in Russian language, 8 figures

We study a problem of damping a control system described by functional-differential equations of natural order $n$ and neutral type with non-smooth complex coefficients on an arbitrary tree with global delay. The latter means that the delay propagates through internal vertices of the tree. Minimization of the energy functional of the system leads to a variational problem. We establish its equivalence to a certain self-adjoint boundary value problem on the tree for equations of order $2n$ with nonlocal quasi-derivatives and multidirectional shifts of the argument, as well as Kirchhoff-type conditions emerging at the internal vertices. The unique solvability of both problems is proved., Comment: 21 pages, in Russian language, 2 figures

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 djustment procedure similar to that previously proposed by B.~T.~Polyak., Comment: in Russian language

In connection with the needs of solving optimization problems, the development of conditional minimization methods with convenient numerical implementation continues to attract the attention of mathematicians. In this monograph we propose methods for solving mathematical programming problems that belong to the class of cutting methods. The proposed methods are characterized, in particular, by the fact that they contain the possibility of periodically updating approximating sets by discarding accumulating cutting planes, which makes these methods convenient from a practical point of view. The monograph can be used by specialists in the field of mathematical programming, as well as by students studying in the specialties "Applied Mathematics", "Applied Mathematics and Computer Science", etc., Comment: 182 pages, in Russian

This work is devoted to the problem of synchronization of two Morris-Lecar neuron models. The Morris-Lecar model is a second-order system of differential equations, which describes an uneasy relationship between the membrane potential and the activation of ion channels inside the membrane. Synchronization, which is a state of a network when models begin to act similarly in some sense, of such models is interesting not only from a mathematical point of view, but also from a biological one, because synchronous activity plays a very important role in brain functioning. The speed gradient algorithm, which is a continuous version of gradient algorithms, was applied to solve this problem. The algorithm of coupling strength control was obtained. It ensures the achievement of the control goal. The MATLAB modelling demonstrated the correctness of the obtained result and fast convergence rate of corresponding models' variables to each other., Comment: 5 pages, 6 figures, in Russian, supported by grant SPbU ID 84912397

The article is devoted to some adaptive methods for variational inequalities with relatively smooth and relatively strongly monotone operators. Starting from the recently proposed proximal variant of the extragradient method for this class of problems, we investigate in detail the method with adaptively selected parameter values. An estimate of the convergence rate of this method is proved. The result is generalized to a class of variational inequalities with relatively strongly monotone generalized smooth variational inequality operators. Numerical experiments have been performed for the problem of ridge regression and variational inequality associated with box-simplex games., Comment: in Russian language

Some variant of the Frank-Wolfe method for convex optimization problems with adaptive selection of the step parameter corresponding to information about the smoothness of the objective function (the Lipschitz constant of the gradient). Theoretical estimates of the quality of the solution provided by the method are obtained in terms of adaptively selected parameters L_k. An important feature of the obtained result is the elaboration of a situation in which it is possible to guarantee, after the completion of the iteration, a reduction of the discrepancy in the function by at least 2 times. At the same time, using of adaptively selected parameters in theoretical estimates makes it possible to apply the method for both smooth and nonsmooth problems, provided that the exit criterion from the iteration is met. For smooth problems, this can be proved, and the theoretical estimates of the method are guaranteed to be optimal up to multiplication by a constant factor. Computational experiments were performed, and a comparison with two other algorithms was carried out, during which the efficiency of the algorithm was demonstrated for a number of both smooth and non-smooth problems., Comment: in Russian language

We consider minimization problems with the well-known Polya-Lojasievich condition and Lipshitz-continuous gradient. Such problem occurs in different places in machine learning and related fields. Furthermore, we assume that a gradient is available with some relative inexactness. We propose some adaptive gradient-type algorithm, where the adaptivity took place with respect to the smoothness parameter and the level of the gradient inexactness. The theoretical estimate of the the quality of the output point is obtained and backed up by experimental results., Comment: in Russian language

In this paper we study a generalization of distributed conditional gradient method to time-varying network architectures. We theoretically analyze convergence properties of the algorithm and provide numerical experiments. The time-varying network is modeled as a deterministic of a stochastic sequence of graphs., Comment: In Russian language

The paper considers approaches to saddle point problems with a two-sided variant of the Polyak-Lojasievich condition based on the gradient method with inexact information and proposes a stopping rule based on the smallness of the norm of the inexact gradient of the external subproblem. Achieving this rule in combination with a suitable accuracy of solving the auxiliary subproblem ensures that the quality of the original saddle point problem is acceptable. The results of numerical experiments for various saddle point problems are discussed to illustrate the effectiveness of the proposed method, including the comparison with proven convergence rate estimates., Comment: in Russian language

The search for equilibrium in a two-stage traffic flow model reduces to the solution of a special nonsmooth convex optimization problem with two groups of different variables. For numerical solution of this problem, the paper proposes to use the accelerated block-coordinate Nesterov-Stich method with a special choice of block probabilities at each iteration. Theoretical estimates of the complexity of this approach can markedly improve the estimates of previously used approaches. However, in the general case they do not guarantee faster convergence. Numerical experiments with the proposed algorithms are carried out in the paper., Comment: in Russian language

In this paper we consider multi-stages traffic assignment with several demand layers, user types and network types. We consider two stages: demand matrix calculation (Entropy Wilson's model) and traffic assignment models (Beckmann or Nesterov--de Palma). For the traffic assignment stage we use dual reformulation and combine these stages as a saddle-point problem (convex-concave). Then we discuss how one can solve this problem numerically., Comment: in Russian language. This research was supported by the annual income of the MIPT Foundation (Endowment No. 5 for the development of artificial intelligence and machine learning at MIPT)

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 non-smooth 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 quasi-convexity. 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., Comment: in Russian language

The application of combinatorial optimization problems to solving the problems of planning processes for industries based on a fund of reconfigurable production resources is considered. The results of their solution by mixed integer programming methods are presented., Comment: 12 pages, in Russian, 4 figures, for MMTT-35

This paper studies non-smooth problems of convex stochastic optimization. Using the smoothing technique based on the replacement of the function value at the considered point by the averaged function value over a ball (in $l_1$-norm or $l_2$-norm) of small radius with the center in this point, the original problem is reduced to a smooth problem (whose Lipschitz constant of the gradient is inversely proportional to the radius of the ball). An important property of the smoothing used is the possibility to calculate an unbiased estimation of the gradient of a smoothed function based only on realizations of the original function. The obtained smooth stochastic optimization problem is proposed to be solved in a distributed federated learning architecture (the problem is solved in parallel: nodes make local steps, e.g. stochastic gradient descent, then they communicate - all with all, then all this is repeated). The goal of this paper is to build on the current advances in gradient-free non-smooth optimization and in feild of federated learning, gradient-free methods for solving non-smooth stochastic optimization problems in federated learning architecture., Comment: In Russian language. Redesigned version for publication in the journal Computational Mathematics and Mathematical Physics

We deal with an isoperimetric problem on the Finsler hyperbolic plane. The space is defined as the Lie group of proper affine transformations of the line with a left-invariant Finsler structure. To state the problem, we use the left-invariant volume form. The optimal isoperimetric loops are found in terms of convex trigonometry functions. We also propose a generalization of the isoperimetric inequality in parametric form., Comment: 17 pages, 2 figures, in Russian

In this article we consider min-min type of problems or minimization by two groups of variables. 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., Comment: in Russian

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

In this paper, we consider convex stochastic optimization problems arising in machine learning applications (e.g., risk minimization) and mathematical statistics (e.g., maximum likelihood estimation). There are two main approaches to solve such kinds of problems, namely the Stochastic Approximation approach (online approach) and the Sample Average Approximation approach, also known as the Monte Carlo approach, (offline approach). In the offline approach, the problem is replaced by its empirical counterpart (the empirical risk minimization problem). The natural question is how to define the problem sample size, i.e., how many realizations should be sampled so that the quite accurate solution of the empirical problem be the solution of the original problem with the desired precision. This issue is one of the main issues in modern machine learning and optimization. In the last decade, a lot of significant advances were made in these areas to solve convex stochastic optimization problems on the Euclidean balls (or the whole space). In this work, we are based on these advances and study the case of arbitrary balls in the $\ell_p$-norms. We also explore the question of how the parameter $p$ affects the estimates of the required number of terms as a function of empirical risk., Comment: 14 pages, in Russian

In this paper, we present a unified analysis of methods for such a wide class of problems as variational inequalities, which includes minimization problems and saddle point problems. We develop our analysis on the modified Extra-Gradient method (the classic algorithm for variational inequalities) and consider the strongly monotone and monotone cases, which corresponds to strongly-convex-strongly-concave and convex-concave saddle point problems. The theoretical analysis is based on parametric assumptions about Extra-Gradient iterations. Therefore, it can serve as a strong basis for combining the already existing type methods and also for creating new algorithms. In particular, to show this we develop new robust methods, which include methods with quantization, coordinate methods, distributed randomized local methods, and others. Most of these approaches have never been considered in the generality of variational inequalities and have previously been used only for minimization problems. The robustness of the new methods is also confirmed by numerical experiments with GANs., Comment: in Russian, 57 pages, 3 figures, 1 table

This paper considers a general problem of convex stochastic optimization in a relatively low-dimensional space (e.g., 100 variables). It is known that for deterministic convex optimization problems of small dimensions, the fastest convergence is achieved by the center of gravity type methods (e.g., Vaidya's cutting plane method). For stochastic optimization problems, the question of whether Vaidya's method can be used comes down to the question of how it accumulates inaccuracy in the subgradient. The recent result of the authors states that the errors do not accumulate on iterations of Vaidya's method, which allows proposing its analog for stochastic optimization problems. The primary technique is to replace the subgradient in Vaidya's method with its probabilistic counterpart (the arithmetic mean of the stochastic subgradients). The present paper implements the described plan, which ultimately leads to an effective (if parallel computations for batching are possible) method for solving convex stochastic optimization problems in relatively low-dimensional spaces., Comment: 9 pages, in Russian

The paper investigates nonlinear control laws obtained from linear one by two types of substitutions using odd functions. The first substitution consists in passing each component of the state vector through a nonlinear function, the second substitution is in passing the entire linear control law through a nonlinear function. To study such systems, it is proposed to represent nonlinear functions as linear ones with a nonlinear slope. Such a representation will make it possible to use the linear matrix inequalities (LMIs) to study the stability of the closed-loop systems. The stability regions and the regions for the initial conditions are found, which are obtained as a result of a multistep procedure for finding solutions of LMIs. It is shown that the use of the proposed nonlinear control laws makes it possible to reduce the steady-state error in comparison with the linear ones., Comment: in Russian

The paper considers the generalization of the method proposed by I.B. Furtat, P.A. Gushchin in "Automation and Remote Control", 2021, No. 4 for systems with an arbitrary ratio of the number of input and output signals and with a guarantee of their being in a given set. To solve the problem, two coordinate changes are proposed. The first coordinate change reduces the output variable of the system to a new variable which dimension does not exceed the control dimension. The second coordinate change allows one to pass from a constrained control problem to an unconstrained one. In order to illustrate the efficiency of the method, the solution of two problems is considered. The first task is state feedback control of linear systems, taking into account the constraints on the control signal and phase variables. The second task is output feedback control of linear systems with a restriction on output and control. In both problems, checking the stability of the closed-loop system is formulated in terms of the solvability of linear matrix inequalities. The obtained results are accompanied by examples of modeling that illustrate the efficiency of the proposed method., Comment: in Russian

We introduce a notion of inexact model of a convex objective function, which allows for errors both in the function and in its gradient. For this situation, a gradient method with an adaptive adjustment of some parameters of the model is proposed and an estimate for the convergence rate is found. This estimate is optimal on a class of sufficiently smooth problems in the presence of errors. We consider a special class of convex nonsmooth optimization problems. In order to apply the proposed technique to this class, an artificial error should be introduced. We show that the method can be modified for such problems to guarantee a convergence in the function with a nearly optimal rate on the class of convex nonsmooth optimization problems. An adaptive gradient method is proposed for objective functions with some relaxation of the Lipschitz condition for the gradient that satisfy the Polyak--Lojasievicz gradient dominance condition. Here, the objective function and its gradient can be given inexactly. The adaptive choice of the parameters is performed during the operation of the method with respect to both the Lipschitz constant of the gradient and a value corresponding to the error of the gradient and the objective function. The linear convergence of the method is justified up to a value associated with the errors., Comment: in Russian

The article is devoted to the development of numerical methods for solving variational inequalities with relatively strongly monotone operators. We consider two classes of variational inequalities related to some analogs of the Lipschitz condition of the operator that appeared several years ago. One of these classes is associated with the relative boundedness of the operator, and the other one with the analog of the Lipschitz condition (namely, relative smoothness). For variational inequalities with relatively bounded and relatively strongly monotone operators, we introduce a modification of the Mirror Descent method, which optimizes the convergence rate. We also propose the adaptive Proximal Pirror algorithm and its restarted version with a linear convergence rate for problems with relatively smooth and relatively strongly monotone operators., Comment: in Russian

A deterministic method for synthesizing the interconnect topologies optimized for the required properties is proposed. The method is based on the original description of graphs by projections, on establishing the bijective correspondence of the required properties and the projection properties of the initial graph, on postulating the corresponding restrictions of modified projections and on iteratively applying these restrictions to them either until the projection system is solved and the projections of the desired graph are obtained, or until its incompatibility with the given initial conditions is revealed., Comment: In Russian

This textbook is based on lectures given by the authors at MIPT (Moscow), HSE (Moscow), FEFU (Vladivostok), V.I. Vernadsky KFU (Simferopol), ASU (Republic of Adygea), and the University of Grenoble-Alpes (Grenoble, France). First of all, the authors focused on the program of a two-semester course of lectures on convex optimization, which is given to students of MIPT. The first chapter of this book contains the materials of the first semester ("Fundamentals of convex analysis and optimization"), the second and third chapters contain the materials of the second semester ("Numerical methods of convex optimization"). The textbook has a number of features. First, in contrast to the classic manuals, this book does not provide proofs of all the theorems mentioned. This allowed, on one side, to describe more themes, but on the other side, made the presentation less self-sufficient. The second important point is that part of the material is advanced and is published in the Russian educational literature, apparently for the first time. Third, the accents that are given do not always coincide with the generally accepted accents in the textbooks that are now popular. First of all, we talk about a sufficiently advanced presentation of conic optimization, including robust optimization, as a vivid demonstration of the capabilities of modern convex analysis., Comment: 364 pages, in Russian

Left-invariant optimal control problems on Lie groups form an important class of problems with big symmetry group. They are interesting from the theoretical point of view since they often can be completely studied, and general features can be investigated on these model problems. In particular, problems on nilpotent Lie groups give a fundamental nilpotent approximation of general problems. Left-invariant problems also often arise in applications: in classical and quantum mechanics, geometry, robotics, models of vision and image processing. This work aims to review the main notions, methods and results for left-invariant optimal control problems on Lie groups. The main attention is paid to description of extremal trajectories and their optimality, cut time and cut locus, optimal synthesis. Bibliography: 238 titles., Comment: 130 pages, 46 figures. In Russian

We study a time minimization problem on the group of motions of a plane with admissible control in a half-disk. The considered control system describes a model of a car that can move forward on a plane and turn in place. Optimal trajectories of this system are used in image processing for the detection of salient lines. In particular, such trajectories are used in the analysis of medical images when searching for blood vessels in photos of the human retina. The problem is of interest in geometric control theory as a model example in which the set of admissible controls contains zero at the boundary. We prove complete controllability and the existence of optimal trajectories. By analyzing the Hamiltonian system of Pontryagin maximum principle we derive explicit formulas for extremal controls and trajectories. The optimality of extremals is partially investigated. The structure of optimal synthesis is described., Comment: 22 pages, 7 figures, (in Russian)

In this paper, we consider gradient-type methods for convex positively homogeneous optimization problems with relative accuracy. An analogue of the accelerated universal gradient-type method for positively homogeneous optimization problems with relative accuracy is investigated. The second approach is related to subgradient methods with B. T. Polyak stepsize. Result on the linear convergence rate for some methods of this type with adaptive step adjustment is obtained for some class of non-smooth problems. Some generalization to a special class of non-convex non-smooth problems is also considered., Comment: in Russian

This work presents a novel version of recently developed Gauss-Newton method for solving systems of nonlinear equations, based on upper bound of solution residual and quadratic regularization ideas. We obtained for such method global convergence bounds and under natural non-degeneracy assumptions we present local quadratic convergence results. We developed stochastic optimization algorithms for presented Gauss-Newton method and justified sub-linear and linear convergence rates for these algorithms using weak growth condition (WGC) and Polyak-Lojasiewicz (PL) inequality. We show that Gauss-Newton method in stochastic setting can effectively find solution under WGC and PL condition matching convergence rate of the deterministic optimization method. The suggested method unifies most practically used Gauss-Newton method modifications and can easily interpolate between them providing flexible and convenient method easily implementable using standard techniques of convex optimization., Comment: (in Russian, 105 pages)

This paper is devoted to some approaches for convex min-min problems with smoothness and strong convexity in only one of the two variable groups. It is shown that the proposed approaches, based on Vaidya's cutting plane method and Nesterov's fast gradient method, achieve the linear convergence. The outer minimization problem is solved using Vaidya's cutting plane method, and the inner problem (smooth and strongly convex) is solved using the fast gradient method. Due to the importance of machine learning applications, we also consider the case when the objective function is a sum of a large number of functions. In this case, the variance-reduced accelerated gradient algorithm is used instead of Nesterov's fast gradient method. The numerical experiments' results illustrate the advantages of the proposed procedures for logistic regression with the prior on one of the parameter groups., Comment: 15 pages, 2 figures, in Russian

This article is devoted to one particular case of using universal accelerated proximal envelopes to obtain computationally efficient accelerated versions of methods used to solve various optimization problem setups. In this paper, we propose a proximally accelerated coordinate descent method that achieves the efficient algorithmic complexity of iteration and allows one to take advantage of the problem sparseness. An example of applying the proposed approach to optimizing a SoftMax-like function considered, for which the described method allowing weaken the dependence of the computational complexity on the dimension of the problem $n$ in $\mathcal{O}(\sqrt{n})$ times, and in practice demonstrates a faster convergence in comparison with standard methods., Comment: 10 pages, 2 figures, in Russian

We describe homogeneous sub-Riemannian geodesics for the standard sub-Riemannian structure on the group of proper motions of the plane SE(2). We show that this structure is not geodesically orbital, although the cut time is invariant w.r.t. shift of the initial point along geodesic., Comment: 6 pages, 3 figures. In Russian

We propose some adaptive mirror descent dethods for convex programming problems with delta-subgradients and prove some theoretical results., Comment: in Russian

Authors describe a two-stage traffic assignment model. It contains of two blocks. The first block consists of model for calculating correspondence (demand) matrix, whereas the second block is a traffic assignment model. The first model calculates a matrix of correspondences using a matrix of transport costs. It characterizes the required volumes of movement from one area to another. The second model describes how exactly the needs for displacement, specified by the correspondence matrix, are distributed along the possible paths. It works on the basis of the Nash--Wardrop equilibrium (each driver chooses the shortest path). Knowing the ways of distribute flows along the paths, it is possible to calculate the cost matrix. Equilibrium in a two-stage model is a fixed point in the sequence of these two models. The article proposes a method of reducing the problem of finding the equilibrium to the problem of the convex non-smooth optimization. Also a numerical method for solving the obtained optimization problem is proposed. Numerical experiments were carried out for the small towns., Comment: in Russian

Robustness of linear systems with constant coefficients is considered. There exist methods and tools for analyzing the stability of systems with random or deterministic uncertainties. At the same time, there are no approaches for the analysis of systems containing both types of parametric uncertainty. The types of robustness are reviewed and new type of "mixed parametric robustness" is introduced. It includes several variations. The proposed formulations of mixed robustness problems can be considered as intermediate type between the classical deterministic and probabilistic approaches to robustness. Several cases are listed in which the tasks are easily solved. In general, tests of the stability of robust systems using the scenario approach are applicable, but these tests can be computationally complex. To calculate the desired stability probability, a simple graphical approach based on a robust D-partition is proposed. This method is suitable for the case of a small number of random parameters. The final estimate of the probability of stability is calculated in a deterministic way and can be found with arbitrary precision. Approximate ways of solving the assigned tasks are described. Examples and generalization of mixed robustness to other types of systems are given., Comment: text in Russian

The article considers minimization of the expectation of convex function. Problems of this type often arise in machine learning and a number of other applications. In practice, stochastic gradient descent (SGD) and similar procedures are often used to solve such problems. We propose to use the ellipsoid method with minibatching, which converges linearly and hence requires significantly less iterations than SGD. This is verified by our experiments, which are publicly available. The algorithm does not require neither smoothness nor strong convexity of target function to achieve linear convergence. We prove that the method arrives at approximate solution with given probability when using minibatches of size proportional to the desired precision to the power -2. This enables efficient parallel execution of the algorithm, whereas possibilities for batch parallelization of SGD are rather limited. Despite fast convergence, ellipsoid method can result in a greater total number of calls to oracle than SGD, which works decently with small batches. Complexity is quadratic in dimension of the problem, hence the method is suitable for relatively small dimensionalities., Comment: 8 pages, 1 figure, in Russian

In this paper we make a survey of modern parallel and distributed approaches to solve sum-type convex minimization problems come from ML applications., Comment: in Russian

The article is devoted to the development of algorithmic methods ensuring efficient complexity bounds for strongly convex-concave saddle point problems in the case when one of the groups of variables is high-dimensional, and the other is relatively low-dimensional (up to a hundred). The proposed technique is based on reducing problems of this type to a problem of minimizing a convex (maximizing a concave) functional in one of the variables, for which it is possible to find an approximate gradient at an arbitrary point with the required accuracy using an auxiliary optimization subproblem with another variable. In this case, the ellipsoid method is used for low-dimensional problems (if necessary, with an inexact $\delta$-subgradient), and accelerated gradient methods are used for high-dimensional problems. For the case of a very small dimension of one of the groups of variables (up to 5), an approach based on a new version of the multidimensional analog of the Yu. E. Nesterov's method on the square (multidimensional dichotomy) is proposed with the possibility of using inexact values of the gradient of the objective functional., Comment: 50 pages, 2 figures, 9 tables, in Russian. Several misprints corrected, proof of Theorem 1 revised

The work is devoted to the construction of efficient and applicable to real tasks first-order methods of convex optimization, that is, using only values of the target function and its derivatives. Construction uses OGM-G, fast gradient method which is optimal by complexity, but requires to know the Lipschitz constant for gradient and the strong convexity constant to determine the number of steps and step length. This requirement makes practical usage impossible. An adaptive on the constant for strong convexity algorithm ACGM is proposed, based on restarts of the OGM-G with update of the strong convexity constant estimate, and an adaptive on the Lipschitz constant for gradient ALGM, in which the use of OGM-G restarts is supplemented by the selection of the Lipschitz constant with verification of the convexity conditions used in the universal gradient descent method. This eliminates the disadvantages of the original method associated with the need to know these constants, which makes practical usage possible. Optimality of estimates for the complexity of the constructed algorithms is proved. To verify the results obtained, experiments on model functions and real tasks from machine learning are carried out., Comment: in Russian

We obtain universal affine type estimates for the location of the geometric medians of triangle perimeters and for the location of the geometric medians of triangular domains. At the end, some alternative implementations of the triangle space are discussed., Comment: in Russian, 13 pages, 11 figures

In the first part of the paper we consider accelerated first order optimization method for convex functions with $L$-Lipschitz-continuous gradient, that is able to automatically adapts to problems which satisfies Polyak-{\L}ojasiewicz condition or which is strongly convex with the value of parameter equal to $\mu$. In these cases method poses linear convergence with factor $\frac{\mu}{L}$, if $\mu$ is unknown. If the problem is strongly convex and $\mu$ is known, than the method possesses linear convergence with the factor $\sqrt{\frac{\mu}{L}}$. If that are not the cases, the method converges with a rate $O(1/k^2)$. The second part contains generalization of the method to the problems, that allows alternating minimization and proofs of the same asymptotic convergence rates. Also it is considered the approach called Adaptive Catalyst, which allows to increase convergence rate up to $O(1/k^2)$ and also it is provided an experimental comparison of the approach with AGM, Alternating AGM, APDAGD and Sinkhorn's algorithm for the dual problem to the discrete entropically regularized optimal transport problem. The result of the work is the attempt to explain the reason why Alternating AGM converge faster than AGM or Adaptive Catalyst despite of the asymptotic theoretical rate $O(1/k^2)$. The hypothesis relies on the fact that Alternating AGM adapts to strong convexity. The hypothesis was tested on quadratic functions, on that Alternating AGM also showed faster convergence., Comment: 15 pages, in Russian

In this paper, we consider the problem of restoring the correspondence matrix based on the observations of real correspondences in Moscow. Following the conventional approach, the transport network is considered as a directed graph whose edges correspond to road sections and the graph vertices correspond to areas that the traffic participants leave or enter. The number of city residents is considered constant. The problem of restoring the correspondence matrix is to calculate all the correspondence from the $i$ area to the $j$ area. To restore the matrix, we propose to use one of the most popular methods of calculating the correspondence matrix in urban studies -- the entropy model. In our work, we describe the evolutionary justification of the entropy model and the main idea of the transition to solving the problem of entropy-linear programming (ELP) in calculating the correspondence matrix. To solve the ELP problem, it is proposed to pass to the dual problem. In this paper, we describe several numerical optimization methods for solving this problem: the Sinkhorn method and the Accelerated Sinkhorn method. We provide numerical experiments for the following variants of cost functions: a linear cost function and a superposition of the power and logarithmic cost functions. In these functions, the cost is a combination of average time and distance between areas, which depends on the parameters. The correspondence matrix is calculated for multiple sets of parameters and then we calculate the quality of the restored matrix relative to the known correspondence matrix. We assume that the noise in the restored correspondence matrix is Gaussian, as a result, we use the standard deviation as a quality metric., Comment: In Russian

In this paper, we consider the conjugate gradient method for solving the problem of minimizing a quadratic function with additive noise in the gradient. Three concepts of noise were considered: antagonistic noise in the linear term, stochastic noise in the linear term, and noise in the quadratic term, as well as combinations of the first and second with the last. It was experimentally obtained that error accumulation is absent for any of the considered concepts, which differs from the folklore opinion that, as in accelerated methods, error accumulation must take place. The paper gives motivation for why the error may not accumulate. The dependence of the solution error both on the magnitude (scale) of the noise and on the size of the solution using the conjugate gradient method was also experimentally investigated. Hypotheses about the dependence of the error in the solution on the noise scale and the size (2-norm) of the solution are proposed and tested for all the concepts considered. It turned out that the error in the solution (by function) linearly depends on the noise scale. The work contains graphs illustrating each individual study, as well as a detailed description of numerical experiments, which includes an account of the methods of the noise of both the vector and the matrix., Comment: 14 pages, in Russian, 10 figures

We propose an accelerated meta-algorithm, which allows to obtain accelerated methods for convex unconstrained minimization in different settings. As an application of the general scheme we propose nearly optimal methods for minimizing smooth functions with Lipschitz derivatives of an arbitrary order, as well as for smooth minimax optimization problems. The proposed meta-algorithm is more general than the ones in the literature and allows to obtain better convergence rates and practical performance in several settings., Comment: 25 pages, in Russian

In this book we describe BMW traffic assignment model and Nesterov-dePalma model. We consider Entropy model for demand matrix. Based on this models we build multi-stage traffic assignment models. The equilibrium in such models can be found from convex-concave saddle-point problem. We show how to solve this problem by using special combination of universal gradient method and Sinkhorn's algorithm., Comment: in Russian, 204 pages. arXiv admin note: text overlap with arXiv:1607.03142, arXiv:1405.7630

In this paper, we consider conditional gradient methods. 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 $$\arg \min_{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} (\sqrt {n}) $. 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. The convergence rate of such an algorithm does not depend on dimension. Using the Shrinking Conditional Gradient method the complexity 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., Comment: in Russian

In this paper, we describe a new way to get convergence rates for optimal methods in smooth (strongly) convex optimization tasks. Our approach is based on results for tasks where gradients have nonrandom small noises. Unlike previous results, we obtain convergence rates with model conception., Comment: in Russian