Les moteurs de recherche jouent un rôle essentiel sur le Web. Ils rassemblent des informations sur les pages web et pour chaque requête d'un internaute, ils donnent une liste ordonnée de pages pertinentes. Ils utilisent divers algorithmes pour classer les pages en fonction de leur contenu textuel ou de la structure d'hyperlien du Web. Ici, nous nous concentrons sur les algorithmes qui utilisent cette structure d'hyperliens, comme le PageRank, HITS, SALSA et HOTS. La notion fondamentale pour tous ces algorithmes est le graphe du web. C'est le graphe orienté qui a un noeud pour chaque page web et un arc entre les noeuds i et j si il y a un hyperlien entre les pages i et j. Le problème original considéré dans cette thèse est l'optimisation du référencement des pages d'un site web donné. Il consiste à trouver une stratégie optimale de liens qui maximise une fonction scalaire d'un classement donné sous des contraintes de design. Le PageRank, HITS et SALSA classent les pages par un vecteur de Perron, c'est-à-dire qu'ils correspondent au vecteur propre principal d'une matrice à coefficients positifs. Quand on optimise le référencement, on optimise donc une fonction scalaire du vecteur propre de Perron sur un ensemble de matrices positives irréductibles. La matrice est construite à partir du graphe du web, donc commander les hyperliens revient à commander la matrice elle-même. Nous étudions d'abord un problème général d'optimisation du PageRank avec une fonction d'utilité correspondant au revenu total du site et des contraintes de design. Ce cas est d'un intérêt particulier car pour de nombreux sites la valeur du PageRank est corrélée au chiffre d'affaires. Nous avons réduit le problème d'optimisation du PageRank à des problèmes de décision markoviens dont les ensembles d'action sont définis implicitement comme étant les points extrêmes de polytopes qui ont un oracle de séparation polynomial. Nous montrons que de tels problèmes de décision markoviens sont solubles en temps polynomial et nous donnons un algorithme qui passe à l'échelle pour la résolution effective du problème d'optimisation du PageRank sur de grandes bases de données. Ensuite, nous étudions le problème général de l'optimisation d'une fonction scalaire du vecteur propre de Perron sur un ensemble de matrices positives irréductibles. Cela couvre tous les classements par vecteur de Perron, HITS et SALSA compris. Nous montrons que la matrice des dérivées partielles de la fonction objectif a un petit rang et peut être calculée par un algorithme qui a les mêmes propriétés de convergence que la méthode de la puissance utilisée pour calculer le classement. Nous donnons un algorithme d'optimisation qui couple les itérations puissance et gradient et nous prouvons sa convergence vers un point stationnaire du problème d'optimisation. En considérant HOTS comme un vecteur de Perron non linéaire, nous montrons que l'algorithme HOTS converge géométriquement et nous résolvons l'optimisation locale de HOTS. Finalement, nous étendons le domaine d'application des méthodes d'optimisation du vecteur propre et de la valeur propre de Perron à l'optimisation de la chimiothérapie, sous l'hypothèse que les cellules se comportent différemment suivant l'heure de la journée. Nous voulons profiter de cette caractéristique pour minimiser le taux de croissance des cellules cancéreuses tout en maintenant le taux de croissance des cellules saines au dessus d'un seuil de toxicité donné. L'objectif et la contrainte peuvent s'écrire comme les valeurs propres de Floquet de modèles d'EDP structurés en âge avec des coefficients périodiques, qui sont approchés par des valeurs propres de Perron dans le problème discrétisé. Nous cherchons des stratégies d'injection de médicament localement optimales par une méthode des multiplicateurs où les minimisations sans contrainte sont faites en utilisant l'algorithme couplant les itérations puissance et gradient développé dans le cadre de l'optimisation du référencement.
| Identifer | oai:union.ndltd.org:CCSD/oai:pastel.archives-ouvertes.fr:pastel-00743187 |
| Date | 17 September 2012 |
| Creators | Fercoq, Olivier |
| Publisher | Ecole Polytechnique X |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | English |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0023 seconds