Marianne Akian

Olivier Fercoq, Marianne Akian, Mustapha Bouhtou et al.

We study a general class of PageRank optimization problems which consist in finding an optimal outlink strategy for a web site subject to design constraints. We consider both a continuous problem, in which one can choose the intensity of a link, and a discrete one, in which in each page, there are obligatory links, facultative links and forbidden links. We show that the continuous problem, as well as its discrete variant when there are no constraints coupling different pages, can both be modeled by constrained Markov decision processes with ergodic reward, in which the webmaster determines the transition probabilities of websurfers. Although the number of actions turns out to be exponential, we show that an associated polytope of transition measures has a concise representation, from which we deduce that the continuous problem is solvable in polynomial time, and that the same is true for the discrete problem when there are no coupling constraints. We also provide efficient algorithms, adapted to very large networks. Then, we investigate the qualitative features of optimal outlink strategies, and identify in particular assumptions under which there exists a "master" page to which all controlled pages should point. We report numerical results on fragments of the real web graph.

Marianne Akian, Stephane Gaubert, Meisam Sharify

We show that the sequence of moduli of the eigenvalues of a matrix polynomial is log-majorized, up to universal constants, by a sequence of "tropical roots" depending only on the norms of the matrix coefficients. These tropical roots are the non-differentiability points of an auxiliary tropical polynomial, or equivalently, the opposites of the slopes of its Newton polygon. This extends to the case of matrix polynomials some bounds obtained by Hadamard, Ostrowski and Pólya for the roots of scalar polynomials. We also obtain new bounds in the scalar case, which are accurate for "fewnomials" or when the tropical roots are well separated.

Marianne Akian, Sylvie Detournay

We present a fast numerical algorithm for large scale zero-sum stochastic games with perfect information, which combines policy iteration and algebraic multigrid methods. This algorithm can be applied either to a true finite state space zero-sum two player game or to the discretization of an Isaacs equation. We present numerical tests on discretizations of Isaacs equations or variational inequalities. We also present a full multi-level policy iteration, similar to FMG, which allows to improve substantially the computation time for solving some variational inequalities.

Marianne Akian, Stephane Gaubert, Asma Lakhoua

We introduce a max-plus analogue of the Petrov-Galerkin finite element method to solve finite horizon deterministic optimal control problems. The method relies on a max-plus variational formulation. We show that the error in the sup norm can be bounded from the difference between the value function and its projections on max-plus and min-plus semimodules, when the max-plus analogue of the stiffness matrix is exactly known. In general, the stiffness matrix must be approximated: this requires approximating the operation of the Lax-Oleinik semigroup on finite elements. We consider two approximations relying on the Hamiltonian. We derive a convergence result, in arbitrary dimension, showing that for a class of problems, the error estimate is of order $δ+Δx(δ)^{-1}$ or $\sqrtδ+Δx(δ)^{-1}$, depending on the choice of the approximation, where $δ$ and $Δx$ are respectively the time and space discretization steps. We compare our method with another max-plus based discretization method previously introduced by Fleming and McEneaney. We give numerical examples in dimension 1 and 2.

Marianne Akian, Stephane Gaubert, Asma Lakhoua

We develop the max-plus finite element method to solve finite horizon deterministic optimal control problems. This method, that we introduced in a previous work, relies on a max-plus variational formulation, and exploits the properties of projectors on max-plus semimodules. We prove here a convergence result, in arbitrary dimension, showing that for a subclass of problems, the error estimate is of order $δ+Δx(δ)^{-1}$, where $δ$ and $Δx$ are the time and space steps respectively. We also show how the max-plus analogues of the mass and stiffness matrices can be computed by convex optimization, even when the global problem is non convex. We illustrate the method by numerical examples in dimension 2.