Search

An universal primal-dual approach of description equilibriums in large class of hierarchical congestion population games is proposed. At the very core of the approach is hierarchy of enclosed to each other transport networks. In different time-scales corresponding logit dynamics on this networks is considered. This dynamics reflect restricted rationality of the agents. Searching of equilibrium configuration to the multi-level convex optimization problem is reduced (in other words variational principle for these class of the games/models is formulated). Then the dual problem is formulated. This problem has natural interpretation in turn and it is more computationally attractive then the primal one. So an effective primal-dual method for this problem is proposed. This method is based on the composite fast gradient method. Due to primal-duality the solution of the primal problem from the dual iterative process is recovered. To fulfil one iteration of this method the rather complex problem of calculation characteristic function on graph is solved. A special technique (smooth version of Bellman--Ford approach to the shortest path problem) is proposed (based on some ideas of Yu. Nesterov) that allows to do it in a cheap manner. It also should be mentioned that different tricks of small parameters methods are actively used., Comment: 13 pages, in Russian in TRUDY MIPT. 2015. V. 7. no 4

The admissible positional control problem for the canonical system with geometrical restrictions on the control is considered. The investigation is performed with the help of the controllability function method. We obtain controllability functions which are the time of motion from an arbitrary initial condition to the origin. We also reveal a set of controls which solves this problem., Comment: This is a translation of the paper: A.E. Choque Rivero, V.I. Korobov, V.O. Skoryk: Controllability function as time of motion I, (in Russian) Mat. Fiz. Anal. Geom., 11(2), (2004), 208-225

We show how one can obtain nonaccelerated randomized coordinate descent method (Yu. Nesterov, 2010) and nonaccelerated method of randomization of sum-type functional (Le Roux-Schmidt-Bach, 2012) from the optimal method for the stochastic optimization problem (SIGMA, Devolder-Glineur-Nesterov-Dvurechensky-Gasnikov, 2014). The main trick is a special restart technique. We considered this trick to be usefull in others contexts. We consider only strongly convex case. We show that accelerated variants of this methods seems to be nontrivial in this context. That is, it is hard (perhaps impossible) to obtain accelerated variants using the same trick. We also propose new approach for accelerated coordinate descent methods. This approach is based on the coupling technique (Allen-Zhu-Orrechia, 2015) and allows us: to generalize accelerated coordinate descent methods for conditional optimization problems, to obtain the dual solution due to the primal-dual nature, to extend Universal method (Yu. Nesterov, 2013) to accelerated coordinate descent methods etc., Comment: 41 pages, in Russian in TRUDY MIPT. 2016. V. 8. no. 2. P. 67-100

In the work two ways of evolutionary interpretation of entropy model for correspondence matrix calculation are proposed. Both approaches based on the stochastic chemical kinetic evolution under the detailed balance condition. The first approach is based on the binary reactions, and the second one is based on the population games theory. Both approaches allow one to understand better possible physical interpretations of the classic model and to obtain the answers for some open questions in neighborhoods branches. For example, one can propose a selection rule to the unique equilibrium among the set of equilibriums., Comment: 16 pages, In Russian

In this paper we propose a new efficient approach for numerical calculation of equillibriums in multistage transport problems. In the very core of our approach lies the proper combination of Universal Gradient Method proposed by Yu. Nesterov (2013) and conception of inexact oracle (Devolder--Glineur--Nesterov, 2011). In particular our technique allows us to calculate Wasserstein's Barycenter in a fast manner (this results generalized M. Cuturi et al. (2014))., Comment: 26 pages, in Russian, TRUDY MIPT. 2016. V. 8. no. 3

In this paper we propose and develop classical Frank--Wolf algorithm for Beckmann's type models. This is not new, but we investigate details that allows us to speed up. We also consider stable dynamic like models. First model of this type was proposed 15 years ago by Yu. Nesterov and A. DePalma. We propose randomized dual averaging method with special (sum-type) randomization. For both of the problems we obtain the rates of convergences. It seems that this estimations to be unimprovable without additional assumption about problem formulation., Comment: 32 pages, in Russian

We propose composite approache to the special sum-type convex optimization problem with affine restriction and special entropy type regularization. Since the fuctional has a penalty type form, we reformulate initial conditional optimization problem in a special unconstrained form that allows us to put the penalty type functional into the composite term. We also describe the characteristic functions on graphs technique (Yu. Nesterov, 2007) in application to the dual problem., Comment: 16 pages, in Russian

In the paper we generalize universal gradient method (Yu. Nesterov) to strongly convex case and to Intermediate gradient method (Devolder-Glineur-Nesterov). We also consider possible generalizations to stochastic and online context. We show how these results can be generalized to gradient-free method and method of random direction search. But the main ingridient of this paper is assumption about the oracle. We considered the oracle to be inexact., Comment: 9 pages, in Russian

We describe a competetive equillibrium in a railway cargo transportation model. We reduce the problem of finding this equillibrium to the solution of to mutually dual convex optimization problems. According to L.V. Kantorvich we interpret an optimal traffic policy for the model in terms of Lagrange multipliers., Comment: in Russian, Preprint of CCAS RAS, March 2014

In this paper, we consider an NP-hard problem of scheduling a set of jobs of equal processing time on two machines, given a partial precedence order on the set of jobs, with an objective to minimize the makespan. An approximation algorithm is proposed for this problem with a tight approximation bound. Polynomial solvability of the problem is proved in the case when each job on the first machine is in precedence relation with two jobs on the second machine., Comment: 10 pages, in Russian

In the paper we show that euclidian randomization in some situations (i.e. for gradient-free method on a simplex) can be as good as the randomization on the unit sphere in 1-norm. That is on the simplex example we show that for gradient-free methods the choise of the prox-structure and the choise of a way of randomization have to be connected to each other. We demonstrate how it can be done in an optimal way. It is important that we consider inexact oracle., Comment: 26 pages, in Russian, Avtomatika i Telemekhanika. 2016

In the article we lead a brief survey of contemporary gradient type methods (with inexact oracle) for stochastic optimization problems., Comment: 60 pages, in Russian

We propose an efficient dual algorithm for ELP based on Fast Gradient Method. The basic idea - to solve properly regularized dual problem., Comment: 19 pages, in Russian

In the paper we show that an important class of multistage traffic equillibrium models (including correspondence matrix calculation, traffic assignment problem etc) and their economic generalizations can be considered as proper population games with the minimax structure of equillibriums. This is not trivial because at the first sight we have to consider competetive (Valras) equilibrium and Nash-Vardroop equillibrium., Comment: 16 pages, in Russian

In the paper we compare well known numerical methods of finding PageRank vector. We propose Markov Chain Monte Carlo method and obtain a new estimation for this method. We also propose a new method for PageRank problem based on the reduction of this problem to the matrix game. We solve this (sparse) matrix game with randomized mirror descent. It should be mentioned that we used non-standard randomization (in KL-projection) goes back to Grigoriadis-Khachiayn (1995)., Comment: 31 pages, in Russian

In the paper we consider an application of mirror descent (dual averaging) to the stochastic online convex optimization problems. We compare classical mirror descent (Nemirovski-Yudin, 1979) with dual averaging (Nesterov, 2005) and Grigoriadis-Khachiyan algorithm (1995). Grigoriadis-Khachiyan algorithm has just proved to be a randomized mirror descent (dual averaging) with randomization in KL-projection of (sub)gradient to a unit simplex. We found out that this randomization is an optimal way of solving sparse matrix games and some other problems arising in convex optimization and experts weighting., Comment: 26 pages, in Russian

A problem of minimization of delivery and storage costs of a product is considered under constraints on volumes of delivery from each of the suppliers. It is required to determine optimal volumes and times of product shipments. The problem is NP-hard. In this paper, the problem is proved to be pseudo-polynomially solvable and an algorithm for its solution is proposed., Comment: in Russian

In the paper we consider the infinite horizon control problems on the interval with free right-hand endpoint. We obtain the necessary conditions of strict optimality. The method of the proof actually follows the classic paper by Halkin, and the boundary condition for infinity that we construct in our paper is a stronger variety of the Seierstad condition. The complete system of relations of the maximum principle that was obtained in the paper allows us to write the expression for the adjoint variable in the form of improper integral that depends only on the developing trajectory. S.M. Aseev, A.V. Kryazhimskii, and V.M. Veliov obtained the similar condition as a necessary condition for certain classes of control problems. As we note in our paper, the obtained conditions of strict optimality lead us to a redefined system of relations for sufficiently broad class of control problems. An example is considered., Comment: In Russian

We consider a problem of multi-product scheduling in production. Each product can be produced by a family of alternative multi-machine technologies. Multi-machine technologies require more than one machine at the same time. A sequence dependent setup time is needed between different technologies. We formulate a mixed integer linear programming model for the general case of the problem and for the case, when the setup times satisfy the triangle inequality. The proposed models are experimentally tested on randomly generated instances., Comment: 8 pages, in Russian

Necessary optimality conditions and numerical methods for solving an optimal control problem for a linear continuous-time dynanical system with controlled coefficients and quadratic goal functional are discussed., Comment: 18 pages, in Russian, uses a_t.cls