Séance Séminaire

Séminaire ACSIOM

Algorithmique en optimisation non-convexe et inégalité de Kurdyka-Lojasiewicz. Une application en compression de données

On présente des résultats récents définissant un cadre général pour l’algorithmique numérique en optimisation non-convexe. La convergence des algorithmes est basée sur une condition de descente suffisante, et le fait que les fonctions considérées vérifient l’inégalité de Kurdyka-Lojasiewicz. Cette propriété a été initialement dégagée par Lojasiewicz dans le cas des fonctions analytiques réelles. Nous l’étendons à un cadre non différentiable couvrant un vaste champ d’applications en optimisation (fonctions semi-algébriques sci., sous-analytiques). Les algorithmes considérés prennent en compte la résolution numérique approchée à chaque étape, avec la présence d’erreurs relatives. On montre la convergence de méthodes de gradient, proximales, forward-backward, et Gauss-Seidel relaxées, ces deux dernières assurant la convergence d’algorithmes de décomposition (respectivement parallèle et alterné) dans un cadre non convexe, ce qui constitue un des premiers résultats généraux de ce type. Une illustration est donnée en compression de données, avec prise en compte directe de la fonction de comptage.