Skip to Main content Skip to Navigation
Theses

Optimization of Perron eigenvectors and applications: from web ranking to chronotherapeutics

Olivier Fercoq 1
1 MAXPLUS - Max-plus algebras and mathematics of decision
Inria Saclay - Ile de France, CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
Abstract : Search engines play a key role in the World Wide Web. They gather information on the web pages and for each query of a web surfer they give a sorted list of relevant web pages. Internet search engines use a variety of algorithms to sort web pages based on their text content or on the hyperlink structure of the web. Here, we focus on algorithms that use the latter hyperlink structure, called link-based algorithms, and among them PageRank, HITS, SALSA and HOTS. The basic notion for all these algorithms is the web graph, which is a digraph with a node for each web page and an arc between nodes i and j if there is a hyperlink from page i to page j. The original problem considered in the present work is the optimization of the ranking of the pages of a given web site. It consists in finding an optimal outlink strategy maximizing a scalar function of a given ranking subject to design constraints. PageRank, HITS and SALSA are Perron vector rankings, which means that they correspond to the principal eigenvector of a (elementwise) nonnegative matrix. When optimizing the ranking, we thus optimize a scalar utility function of the Perron eigenvector over a set of nonnegative irreducible matrices. The matrix is constructed from the web graph, so controlling the hyperlinks corresponds to controlling the matrix itself. We first study general PageRank optimization problems with a "total income" utility function and design constraints. This case is of particular interest since the value of the PageRank is an acknowledged economic issue. We reduced the PageRank optimization problem to Markov decision problems such that the action sets are implicitly defined as the vertices of polytopes that have a polynomial time separation oracle. We show that such Markov decision problems are solvable in polynomial time and we provide a scalable algorithm for the effective resolution of the PageRank optimization problem on large dataset. Then, we study the general problem of optimizing a scalar utility function of the Perron eigenvector over a set of nonnegative irreducible matrices. This covers all Perron vector rankings, including HITS and SALSA. We show that the matrix of partial derivatives of the objective has a low rank and can be computed by an algorithm with the same convergence properties as the power algorithm used to compute the ranking and so the value of the objective. We give an optimization algorithm that couples power and gradient iterations and prove its convergence to a stationary point of the optimization problem. Considering HOTS as a nonlinear Perron vector, we show that the HOTS algorithm converges with a linear rate of convergence, that the objective of the HOTS optimization problem has a low rank and that the coupled power and gradient algorithm applies. Finally, we extend the domain of application of the Perron eigenvalue and eigenvector optimization methods to the optimization of chemotherapy under the McKendrick model of population dynamics. We consider here that the cells behave differently at an hour of the day or another. We want to take advantage of this feature to minimize the growth rate of cancer cell population while we maintain the growth rate of healthy cell population over a given toxicity threshold. The objective and the constraint can be written as the Floquet eigenvalues of age-structured PDE models with periodic coefficients, and they are approximated by Perron eigenvalues in the discretized problem. We search for locally optimal drug infusion strategies by a method of multipliers, where the unconstrained minimizations are performed using the coupled power and gradient algorithm that we have developed in the context of web ranking optimization.
Document type :
Theses
Complete list of metadatas

Cited literature [221 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00743187
Contributor : Olivier Fercoq <>
Submitted on : Thursday, October 18, 2012 - 1:34:09 PM
Last modification on : Monday, November 4, 2019 - 12:20:03 PM
Long-term archiving on: : Saturday, January 19, 2013 - 3:37:25 AM

Identifiers

  • HAL Id : pastel-00743187, version 1

Collections

Citation

Olivier Fercoq. Optimization of Perron eigenvectors and applications: from web ranking to chronotherapeutics. Optimization and Control [math.OC]. Ecole Polytechnique X, 2012. English. ⟨pastel-00743187⟩

Share

Metrics

Record views

2441

Files downloads

2298