Journée Programmation mathématique non linéaire (axe PMNL du GDR RO)

LIRMM (bâtiment 5), Montpellier, mercredi 26 octobre 2022

Inscription gratuite mais obligatoire

Informations pratiques

• Lieu : laboratoire LIRMM, 161 rue Ada, 34090 Montpellier.
• Salle : il y a deux bâtiments au LIRMM (éloignés de 100 m l'un l'autre), cela se passe au bâtiment 5, en salle Jean-Pierre Nougier (JPN ; 02.022).
• Comment venir : de la gare St Roch, vous pouvez prendre la ligne 1 de tramway et descendre à l'arrêt Château d'O (25 mn de la gare). C'est ensuite à 5 mn à pieds.
• Lien Zoom pour suivre en ligne : https://umontpellier-fr.zoom.us/j/obsolete

Programme

• 09:30-10:00 : Accueil des participants
• 10:00-10:45 : Les reformulations quadratiques convexes : théorie et application à l'OPF, présenté par Amélie Lambert (Cedric-Cnam)
• 10:45-11:20 : Convergent algorithms for a class of convex semi-infinite programs présenté par Antoine Oustry (LIX)
• 11:2O-11:35 : Pause
• 11:35-12:30 : Introduction to CD kernels and application in statistic, présenté par Edouard Pauwels (IRIT)
• 12:30-14:00 : Pause déjeuner
• 14:00-14:20 : Digestion technique pour récupérer des slides et faire refonctionner le vidéoprojecteur
• 14:00-14:45 : Résolution du TSP par flots de gradient sur variété et analogie des systèmes de Toda, présenté par Guillaume Bouleux (DISP)
• 14:45-15:00 : Pause
• 15:00-16:00 : Version tropicale du théorème de Putinar : dualité et résolution de problèmes linéaires en dimension infinie, présenté par Nicolas Delanoue (LARIS)

Exposés invités

Guillaume Bouleux (DISP) : Résolution du TSP par flots de gradient sur variété et analogie des systèmes de Toda

Le classique TSP et ses variantes n'ont peut-être pas encore livré tous leurs secrets. Il suffit pour s'en convaincre de ré-écrire le problème de minimisation sous sa forme matricielle. La solution de ce problème consiste finalement à chercher la matrice de permutation optimale des villes.

Or, chercher directement une matrice par des méthodes d'optimisation a reçu depuis quelques années maintenant un regain d'intérêt dû à une meilleure appropriation des outils de géométrie différentielle. En particulier, l'ensemble dans lequel vit la dite matrice recherchée possède une structure de variété différentielle (ou de sous-variété). Il s'agit donc d'opérer une optimisation sur cette variété en définissant naturellement des flots, qui dans notre cas seront des flots de gradient. La minimisation peut être alors traitée de manière continue. Plus « magique » encore, les flots qui définissent l'optimisation sont étroitement liés au système physique assez répandu qu'est le système de Toda. Cette analogie permet alors d'utiliser un certain nombre de résultats issus de cette approche pour caractériser des preuves de convergence des algorithmes vers les matrices optimales et d'entrevoir également de nouvelles méthodes.

Dans cet exposé, qui se veut néanmoins pédagogique, seront traités d'une part dans une première partie les notions et définitions essentielles de la géométrie différentielle pour la résolution du problème de TSP, puis dans un second temps l'analogie du problème avec le système de Toda.

Nicolas Delanoue (LARIS) : Version tropicale du théorème de Putinar : dualité et résolution de problèmes linéaires en dimension infinie

Résumé

Amélie Lambert (Cédric-Cnam) : Reformulations quadratiques convexes : théorie et application à l'OPF

Nous présentons les fondements des méthodes de résolution exacte de problèmes d'optimisation quadratiques généraux qui sont basées sur les relaxations/reformulations quadratiques convexes (QCRs). Ces méthodes permettent de calculer des relaxations quadratiques convexes qui capturent la qualité des bornes obtenues par relaxation semi-définie positive. Nous illustrons ces approches de résolution sur le problème du Flux de Puissance Optimal (OPF) qui consiste à déterminer la production de puissance à chaque bus d'un réseau électrique tout en minimisant le coût de production.

Antoine Oustry (LIX) : Convergent algorithms for a class of convex semi-infinite programs

We focus on convex semi-infinite programs with an infinite number of quadratically parametrized constraints. In our setting, the lower-level problem, i.e., the problem of finding the constraint that is the most violated by a given point, is not necessarily convex. First we derive a convergence rate in O(1/k) for the Cutting Plane algorithm in the case where the objective function is strongly convex, and under a strict feasibility assumption.

Second we propose a new approach to solve these semi-infinite programs, that generates a sequence of feasible solutions. Based on the Lagrangian dual of the lower-level problem, we derive a convex and tractable restriction of the semi-infinite program.

We state sufficient conditions for the optimality of this restriction. If these conditions are not met, the restriction is enlarged through an Inner-Outer Approximation Algorithm, and its value converges to the value of the original semi-infinite program.

This new algorithmic approach is tested on two applications (a constrained quadratic regression and a zero-sum game with cubic payoff) and compared with the classical Cutting Plane algorithm, the Mitsos algorithm and the KKT-based relaxation approach.

Edouard Pauwels (IRIT) Introduction to CD kernels and application in statistics

In a first step, I will introduce the Christoffel Darboux kernel (CD kernel) and its relation with the Christoffel function. We will focus on computational aspects and specificities related to its application to finite datasets in statistics. We will also illustrate favorable properties of the kernel by qualitatively describing its asymptotic properties known from approximation theory. In a second step, I will consider statistical properties of the empirical CD kernel when applied to IID data. In particular we will be interested in obtaining guarantees for statistical estimators based on the CD kernel.

Last modified: Thu Nov 3 15:34:46 CET 2022