On the role of semismoothness in nonsmooth numerical analysis: Theory

Cet article explore le rôle des dérivées semilisses dans l'analyse numérique non lisse en examinant leur interaction avec la propriété de semilissitude* pour les multifonctions, en particulier pour les applications de solutions d'inclusions paramétriques, et établit leur coïncidence presque partout avec les jacobiennes généralisées.

L'essentiel

Imaginez que vous essayez de trouver le point le plus bas d'un terrain très accidenté, rempli de rochers, de falaises et de pentes abruptes. C'est ce que les mathématiciens appellent un problème "non lisse" (nonsmooth). Pour descendre, vous avez besoin d'une boussole qui vous indique la direction la plus raide.

Dans un monde parfait (lisse), cette boussole est simple : c'est une flèche précise qui pointe vers le bas. Mais sur ce terrain accidenté, les pentes changent brusquement. Parfois, il n'y a pas de pente unique, mais plusieurs directions possibles, ou la boussole elle-même devient floue.

C'est là que cette recherche intervient. Elle propose une nouvelle façon de naviguer dans ce chaos.

1. Le problème de la boussole parfaite

Traditionnellement, pour résoudre ces problèmes, les mathématiciens cherchaient une "boussole parfaite" (un sous-gradient exact ou une matrice de Jacobian généralisée). C'est comme si vous exigiez que votre GPS vous donne la position exacte de chaque pierre sur le chemin.

• Le problème : Parfois, calculer cette position exacte est impossible ou trop long. C'est comme essayer de compter chaque grain de sable d'une plage pour savoir où marcher.

2. La solution : La "Boussole Approximative" (Semi-lisse)

Les auteurs, Helmut Gfrerer et Jiří V. Outrata, disent : "Attendez, nous n'avons pas besoin de la boussole parfaite. Nous avons juste besoin d'une boussole qui fonctionne 'à peu près' bien, tant qu'elle respecte certaines règles."

Ils introduisent le concept de dérivée semi-lisse.

• L'analogie : Imaginez que vous êtes un randonneur. Au lieu de connaître la géologie exacte de chaque rocher, vous avez une règle simple : "Si je marche dans cette direction, je descends, et plus je m'approche du but, plus ma boussole devient précise."
• Cette "boussole approximative" (appelée semismooth derivative) suffit pour que les algorithmes (les méthodes de calcul) convergent vers la solution, même si elle n'est pas mathématiquement parfaite à chaque instant.

3. Le casse-tête des "Solutions Cachées"

Le papier aborde un cas encore plus difficile : les problèmes où la solution elle-même est cachée derrière une équation complexe.

• L'image : Imaginez que vous cherchez le point le plus bas d'une vallée, mais la forme de la vallée change selon où vous vous trouvez, et cette forme est définie par une équation mystérieuse que vous ne pouvez pas résoudre explicitement.
• C'est ce qu'on appelle une inclusion ou un problème à deux niveaux (bilevel). Vous devez d'abord trouver la solution à l'équation intérieure, puis optimiser le résultat extérieur.

4. L'astuce des "Squelettes" (SCD)

Pour gérer ces équations mystérieuses, les auteurs utilisent un outil génial appelé dérivée SCD (Subspace Containing Derivative).

• L'analogie du squelette : Imaginez que la fonction complexe (l'équation mystérieuse) est un animal vivant, un peu flou et mou. Calculer sa forme exacte à chaque instant est impossible. Mais, cet animal a un squelette rigide à l'intérieur.
• Au lieu de mesurer la peau molle (la fonction complète), les auteurs disent : "Regardons juste le squelette !" Ce squelette (la dérivée SCD) est beaucoup plus simple à manipuler. Il capture l'essentiel de la géométrie du problème sans se perdre dans les détails inutiles.

5. Le résultat magique : La "Magie des Ensembles"

Le résultat principal du papier est une démonstration de pouvoir :

1. Si vous avez une fonction "semi-lisse" (une boussole approximative) et que vous l'appliquez à une équation mystérieuse dont vous avez le "squelette" (SCD), alors le résultat final est aussi une fonction semi-lisse.
2. Cela signifie que vous pouvez enchaîner les opérations complexes sans perdre votre boussole. Vous pouvez construire des algorithmes puissants qui trouvent les solutions optimales même dans des situations où les méthodes classiques échouent.

En résumé

Ce papier est comme un manuel de survie pour les navigateurs perdus dans des montagnes mathématiques.

• Il dit : "Oubliez la perfection absolue."
• Il propose : "Utilisez des approximations intelligentes (semi-lisses) qui respectent certaines règles."
• Il offre un outil : "Le squelette (SCD) pour simplifier les équations complexes."
• Il promet : "Même si le chemin est bizarre, vous arriverez au but (la solution optimale) plus vite et plus facilement."

C'est une avancée majeure pour l'informatique et l'optimisation, permettant de résoudre des problèmes réels (comme la gestion de réseaux électriques, l'économie ou l'ingénierie) qui étaient auparavant trop complexes pour les ordinateurs.

Résumé technique

Voici un résumé technique détaillé de l'article "On the role of semismoothness in nonsmooth numerical analysis: Theory" de Helmut Gfrerer et Jiří V. Outrata.

1. Problématique et Contexte

L'article s'intéresse à la résolution numérique de problèmes non lisses (nonsmooth), qui apparaissent fréquemment en optimisation, en résolution d'équations et d'inclusions. Le défi central réside dans le fait que, pour des algorithmes efficaces (comme les méthodes de type Newton ou les méthodes de faisceaux/bundle), il n'est pas toujours nécessaire ni possible de disposer d'un sous-gradient exact ou d'un Jacobien généralisé de Clarke.

Il suffit souvent d'avoir accès à une dérivée semilisse (semismooth derivative), c'est-à-dire une application satisfaisant une propriété de semilissité spécifique. L'auteur aborde trois classes de problèmes :

1. Optimisation non lisse : Minimisation d'une fonction localement lipschitzienne sous contraintes. Les méthodes de faisceaux (bundle methods) nécessitent un oracle retournant une valeur de fonction et un sous-gradient (ou un pseudo-gradient).
2. Équations non lisses : Résolution de $G(x)=0$. La méthode de Newton semilisse classique utilise le Jacobien généralisé de Clarke, mais peut être remplacée par d'autres applications semilisses, ce qui est crucial pour les espaces de dimension infinie.
3. Inclusions non lisses : Résolution de $0 \in F(x)$où$F$est une application multivoque. La méthode de Newton semilisse* ($ss^*$) utilise la coderivée limite.

Le problème spécifique traité ici est l'approche par programmation implicite (ImP) pour des problèmes de type :
$$\min \phi(x,y) \quad \text{sous } 0 \in F(x,y), \quad x \in U_{ad}$$
où l'on cherche à éliminer $y$ via une application de solution $\sigma(x)$. L'objectif est de construire un oracle pour la fonction réduite $\theta(x) = \phi(x, \sigma(x))$ en utilisant les propriétés de semilissité de $F$ et $\phi$, même lorsque $\sigma$ n'est pas unique ou globalement lipschitzienne.

2. Méthodologie et Outils Théoriques

Les auteurs développent une analyse théorique approfondie reliant plusieurs notions de différentiation généralisée :

• Semilissité $\Psi$-ss (pour les applications univoques) : Une application $F$ est dite semilisse par rapport à une application multivoque $\Psi$ si l'erreur de linéarisation tend vers zéro uniformément par rapport aux éléments de $\Psi$. Cela généralise la notion de G-semilissité (Gowda).
• Propriété SCD (Subspace Containing Derivative) : Une généralisation du Jacobien de Bouligand aux applications multivoques. Une application possède la propriété SCD si sa dérivée graphique limite contient des sous-espaces vectoriels. L'application $S^*F$ (dérivée adjointe SCD) joue le rôle d'un "squelette" pour la coderivée limite.
• Semilissité $\Gamma$-$ss^*$ et SCD-$ss^*$ : Une extension de la propriété semilisse* (définie via la coderivée limite) aux applications multivoques, en utilisant des ensembles de dérivées spécifiques ($\Gamma$ ou $S^*F$) plutôt que la coderivée complète.
• Applications graphiquement lipschitziennes : Des applications dont le graphe est localement le graphe d'une application lipschitzienne univoque après un changement de coordonnées.

La méthodologie consiste à établir des liens entre ces concepts, à prouver des règles de calcul (chaîne, somme) pour les dérivées semilisses, et à analyser la régularité des applications de solution $\sigma(x)$ issues d'inclusions paramétrées.

3. Contributions Clés et Résultats Principaux

A. Théorie des applications univoques semilisses

• Équivalence : Une application univoque possède une dérivée semilisse sur un ouvert $\Omega$ si et seulement si elle est G-semilisse sur $\Omega$.
• Différentiabilité stricte : Une telle application est strictement différentiable presque partout (au sens de Lebesgue).
• Coïncidence : La dérivée semilisse coïncide presque partout avec le Jacobien généralisé de Clarke. De plus, le Jacobien généralisé est contenu dans l'enveloppe convexe fermée de la dérivée semilisse.
• Application aux méthodes de faisceaux : L'article montre que pour l'algorithme BT (Bundle-Trust region), il suffit d'un oracle fournissant un élément d'une dérivée semilisse (et non nécessairement un sous-gradient de Clarke exact) pour garantir la convergence vers un point stationnaire.

B. Relation entre SCD-$ss^*$ et G-semilissité

• Pour une application graphiquement lipschitzienne, la propriété SCD-$ss^*$ est équivalente à la G-semilissité de l'application transformée.
• Conséquence majeure : Une application SCD-$ss^*$ est strictement proto-différentiable presque partout, et sa dérivée SCD est un singleton presque partout, ce qui simplifie considérablement son calcul numérique.

C. Applications de solution et Inclusions

• Théorème principal sur les applications de solution : Pour une inclusion $0 \in F(x,y)$, sous des conditions de qualification appropriées sur la coderivée, l'application de solution$\sigma(x)$hérite de la propriété de semilissité de$F$.
• Cas SCD : Si $F$ est une application SCD et SCD-$ss^*$, alors une sélection continue $\sigma$ de l'application de solution est semilisse par rapport à une application $\Psi$ construite explicitement à partir des sous-espaces adjoints $S^*F$.
• Formule de dérivation : L'article fournit une formule explicite pour construire une dérivée semilisse de la fonction composée $\theta(x) = \phi(x, \sigma(x))$ en combinant la dérivée de $\phi$ et les dérivées SCD de $F$.

D. Exemple Académique

Les auteurs illustrent leur théorie sur un problème de programmation bi-niveau avec contraintes d'équilibre (MPEC). Ils résolvent un problème où la fonction de niveau inférieur est non lisse et l'application de solution n'est pas univoque localement. En utilisant l'approche ImP avec les dérivées SCD, ils réussissent à appliquer l'algorithme BT avec succès, démontrant que les dérivées semilisses calculées via la théorie SCD remplacent efficacement les sous-gradients de Clarke exacts, qui seraient difficiles à obtenir.

4. Signification et Impact

Cet article apporte une contribution fondamentale à l'analyse non lisse numérique :

1. Unification des concepts : Il clarifie les relations entre la semilissité classique (Gowda), la semilissité* (Mordukhovich) et les dérivées SCD, montrant qu'elles sont souvent équivalentes ou interchangeables dans des contextes larges.
2. Extension de l'approche ImP : Il permet d'étendre l'approche par programmation implicite à une classe beaucoup plus large de problèmes, y compris ceux où l'application de solution n'est pas unique ou globalement lipschitzienne, à condition que les données sous-jacentes soient SCD-$ss^*$.
3. Efficacité algorithmique : En démontrant que les dérivées SCD (qui sont souvent plus faciles à calculer que les coderivées limites complètes) suffisent pour assurer la convergence des méthodes de faisceaux et de Newton, l'article ouvre la voie à des algorithmes plus robustes pour des problèmes complexes (optimisation hiérarchique, équilibres).
4. Rigueur théorique : Les résultats sur la différentiabilité stricte presque partout et la coïncidence avec le Jacobien de Clarke renforcent la justification mathématique de l'utilisation de ces approximations dans les algorithmes numériques.

En résumé, ce travail fournit le socle théorique nécessaire pour remplacer les sous-gradients exacts par des dérivées semilisses calculables dans des algorithmes d'optimisation non lisse, élargissant ainsi le champ d'application des méthodes numériques modernes aux problèmes avec contraintes d'équilibre complexes.