Generalisation of Farkas' lemma beyond closedness: a constructive approach via Fenchel-Rockafellar duality

Each language version is independently generated for its own context, not a direct translation.

🗺️ Le Grand Défi : Trouver la Clé dans un Labyrinthe

Imaginez que vous êtes un explorateur (le mathématicien) face à un grand labyrinthe.

Le but (b) : C'est un trésor caché quelque part.
La carte (A) : C'est une machine magique qui transforme vos pas en coordonnées.
Le labyrinthe (P) : C'est une zone spécifique où vous avez le droit de marcher.

Le problème classique, appelé Lemme de Farkas, se résume à cette question simple :

"Est-ce que mon trésor (b) se trouve vraiment dans la zone que ma machine (A) peut atteindre en partant du labyrinthe (P) ?"

🚧 L'Obstacle Majeur : Le Mur Invisible

Pendant des décennies, les mathématiciens ont dit : "Pour être sûr de répondre, le labyrinthe doit être parfaitement fermé, sans trous, et l'image de la machine doit aussi être un mur solide."
En mathématiques, on appelle cela la fermeture (closedness). Si le labyrinthe a des portes qui s'ouvrent sur des abîmes ou si l'image de la machine est "floue" (des points manquants), les anciennes règles ne fonctionnaient plus. C'était comme essayer de construire un pont sur un ruisseau dont on ne connaît pas la largeur exacte.

🚀 La Nouvelle Solution : Une Approche "Constructive"

Les auteurs de ce papier (Camille, Emmanuel et Christophe) disent : "Oubliez le mur parfait ! Nous avons une nouvelle méthode."

Au lieu de chercher à savoir si le trésor est exactement là, ils proposent de :

Construire un pont provisoire (une approximation) : On accepte de s'approcher du trésor à une distance très petite (ε).
Utiliser un miroir magique (la dualité de Fenchel-Rockafellar) : Ils regardent le problème non pas de l'intérieur du labyrinthe, mais depuis l'extérieur, comme si on regardait le reflet du labyrinthe dans un lac.

L'analogie du Miroir :
Imaginez que vous ne pouvez pas voir le trésor directement. Mais si vous regardez dans le miroir (le problème dual), vous voyez une ombre. Si cette ombre a une certaine forme, vous savez que le trésor existe, même si le labyrinthe est un peu "fuyant" ou non fermé.

🛠️ Comment ça marche concrètement ?

Voici les trois étapes de leur méthode, expliquées simplement :

1. La Règle du "Générateur" (Le Kit de Construction)

Au lieu de demander que tout le labyrinthe soit parfait, ils demandent juste qu'il soit construit à partir d'un bloc de base solide et fini (un ensemble convexe borné).

Analogie : Imaginez que vous construisez une tour avec des briques. Même si la tour finie a une forme bizarre ou des trous, tant qu'elle est faite de briques solides et connues, on peut prédire comment elle va se comporter. Ils ne regardent plus la tour entière, mais les briques qui la composent.

2. Le Jeu de l'Optimisation (Trouver le Meilleur Chemin)

Ils transforment le problème "Est-ce que c'est possible ?" en un problème de "Course à pied".

Ils créent une course où l'objectif est de trouver le chemin le plus court pour atteindre le trésor.
Grâce à leur méthode, ils peuvent construire le chemin exact (la solution) en résolvant une équation simple, sans avoir besoin de deviner. C'est comme avoir un GPS qui vous donne non seulement la direction, mais aussi les coordonnées exactes de chaque virage.

3. La Révélation : Approximation vs Exactitude

Pour une approximation (ε > 0) : Ils peuvent toujours trouver un chemin qui passe très près du trésor. C'est comme dire : "Je ne peux pas toucher le trésor, mais je peux mettre mon doigt à 1 millimètre de lui." Et ils savent exactement comment faire.
Pour l'exactitude (ε = 0) : C'est plus difficile. Parfois, le trésor est là, mais le chemin idéal est "juste à côté" de la réalité (comme un point à l'infini). Ils expliquent quand on peut trouver ce chemin parfait et quand il faut se contenter de l'approximation.

💡 Pourquoi c'est génial ?

C'est plus flexible : Avant, il fallait que tout soit "parfaitement fermé". Maintenant, on peut travailler avec des formes plus libres, plus réalistes (comme des cônes qui s'ouvrent à l'infini).
C'est constructif : Ce n'est pas juste une théorie abstraite. Ils donnent une recette (un algorithme) pour fabriquer la solution. Si vous avez un ordinateur, vous pouvez utiliser leur méthode pour trouver la réponse.
C'est utile pour le monde réel : Cela aide à résoudre des problèmes complexes en ingénierie, en contrôle de robots, ou en économie, où les contraintes ne sont pas toujours parfaites.

🎯 En résumé

Ce papier dit : "Ne vous inquiétez pas si votre labyrinthe a des trous ou si la carte est floue. Nous avons un nouveau système de miroir et de GPS qui nous permet de trouver le trésor, ou du moins de s'en approcher à la perfection, en utilisant les briques de base du labyrinthe."

C'est une avancée majeure parce qu'elle rend la "magie" des mathématiques de l'optimisation utilisable dans des situations réelles, imparfaites et complexes.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique et Contexte

L'article s'intéresse à une variante du célèbre lemme de Farkas dans le cadre de l'optimisation en espaces de Hilbert. Le problème central est de déterminer si un vecteur $b \in Y$ appartient à l'image d'un cône $P \subset X$ par un opérateur linéaire continu $A : X \to Y$ , c'est-à-dire si l'équation contrainte $Ax = b$ avec $x \in P$ admet une solution.

Deux problèmes sont distingués :

Solvabilité approchée : Existe-t-il $x_\varepsilon \in P$ tel que $\|Ax_\varepsilon - b\| \le \varepsilon$ ? (Cela équivaut à vérifier si $b \in \overline{A(P)}$ ).
Solvabilité exacte : Existe-t-il $x \in P$ tel que $Ax = b$ ? (Cela équivaut à vérifier si $b \in A(P)$ ).

Limites des résultats existants :
La version classique du lemme de Farkas et ses généralisations (notamment dans les espaces de Banach réflexifs) reposent presque systématiquement sur l'hypothèse que l'image du cône, $A(P)$ , est fermée. Cette hypothèse est souvent difficile à vérifier et n'est pas toujours satisfaite. De plus, la plupart des généralisations supposent que le cône $P$ lui-même est fermé.

L'objectif de cet article est de surmonter ces restrictions en proposant une approche constructive qui ne nécessite pas que $A(P)$ (ni même $P$ ) soit fermé, mais qui repose sur des propriétés de génération du cône.

2. Méthodologie

Les auteurs développent une approche basée sur la dualité de Fenchel-Rockafellar et la formulation d'un problème d'optimisation auxiliaire.

A. Hypothèses sur le cône

Au lieu d'exiger que $P$ soit fermé, l'article suppose que le cône $P$ (noté $P_r$ dans le cas général) est généré par un ensemble convexe borné et fermé $K_r$ contenant l'origine :
$P_r = \text{cone}(K_r) = \{ \lambda v \mid \lambda \ge 0, v \in K_r \}$
Cette hypothèse est strictement plus faible que la fermeture de $P_r$ . Elle permet de traiter des cônes non fermés (par exemple, des cônes ouverts ou semi-ouverts dans des espaces de dimension infinie).

B. Problème d'optimisation primal

Pour un $\varepsilon \ge 0$ , les auteurs introduisent le problème primal $(P_\varepsilon)$ :
$\inf_{x \in X} F_\varepsilon(x) = \frac{1}{2} j_{K_r}^2(x) + \delta_{\{x \in X, \|Ax-b\|_Y \le \varepsilon\}}(x)$
où :

$j_{K_r}$ est la fonction de jauge de $K_r$ (définie par $j_{K_r}(x) = \inf \{ \alpha > 0 \mid x \in \alpha K_r \}$ ).
$\delta_C$ est la fonction indicatrice de l'ensemble $C$ .
Le terme $j_{K_r}^2$ pénalise la "taille" de $x$ par rapport au générateur $K_r$ .

La résolution de ce problème permet de trouver un $x$ satisfaisant la contrainte d'approximation ou d'exactitude.

C. Dualité et Problème Dual

En utilisant la théorie de Fenchel-Rockafellar, le problème dual $(D_\varepsilon)$ est dérivé. Il s'agit d'un problème de minimisation non contraint sur l'espace dual $Y$ :
$\inf_{y \in Y} J_\varepsilon(y) = \frac{1}{2} \sigma_{K_r}^2(A^*y) - \langle b, y \rangle_Y + \varepsilon \|y\|_Y$
où $\sigma_{K_r}$ est la fonction de support de $K_r$ ( $\sigma_{K_r}(z) = \sup_{v \in K_r} \langle z, v \rangle$ ).

Points clés de la méthodologie :

Dualité forte : Les auteurs établissent une égalité forte entre les valeurs infimales du primal et du dual.
Constructivité : La solution du problème primal (si elle existe) peut être reconstruite explicitement à partir de la solution du problème dual via les conditions d'optimalité (sous-différentiels).
Absence de contraintes dans le dual : Contrairement aux approches précédentes, le problème dual est non contraint, ce qui le rend plus facile à traiter numériquement.

3. Résultats Principaux

Les résultats sont présentés par ordre croissant de généralité.

A. Caractérisations de solvabilité (Théorèmes 1.2 et 1.3)

Les auteurs fournissent des conditions nécessaires et suffisantes pour la solvabilité approchée et exacte, sans supposer que $A(P)$ est fermé.

Cas d'un cône convexe fermé $P$ :
- $b \in A(P) \iff \forall y \in Y, (A^*y)_+ = 0 \implies \langle b, y \rangle \le 0$ .
- $b \in \overline{A(P)} \iff \exists C > 0, \forall y \in Y, \langle b, y \rangle \le C \|(A^*y)_+\|$ .
- Ici, $(z)_+$ désigne la projection de $z$ sur $P$ .
Cas d'un cône généré par un ensemble borné $K_r$ (Théorème 1.3) :
- $b \in A(P_r) \iff \forall y \in Y, \sigma_{K_r}(A^*y) = 0 \implies \langle b, y \rangle \le 0$ .
- $b \in \overline{A(P_r)} \iff \exists C > 0, \forall y \in Y, \langle b, y \rangle \le C \sigma_{K_r}(A^*y)$ .
- Ces conditions généralisent les résultats de Hernandez-Lerma et Lasserre (1997) avec une preuve plus simple et plus constructive.

B. Caractérisations Constructives (Théorèmes 1.4, 1.5, 1.6)

Si une solution existe, elle peut être reconstruite explicitement :

Pour la solvabilité approchée ( $\varepsilon > 0$ ) :
Le problème dual admet toujours un minimiseur unique $y_\varepsilon^*$ . La solution $x_\varepsilon^*$ est obtenue par :
$x_\varepsilon^* \in \sigma_{K_r}(A^*y_\varepsilon^*) \partial \sigma_{K_r}(A^*y_\varepsilon^*)$
où $\partial$ désigne le sous-différentiel. Sous certaines conditions de régularité (absence de vecteurs singuliers), cette inclusion devient une égalité unique.
Pour la solvabilité exacte ( $\varepsilon = 0$ ) :
L'existence d'un minimiseur pour le dual n'est pas garantie même si la solution primitive existe. Cependant, si un minimiseur $y^*$ existe, la solution $x^*$ est donnée par la même formule.
- Cas des cônes fermés : La solution est unique et donnée par $x^* = (A^*y^*)_+$ .
- Cas général (non convexe ou non fermé) : Les auteurs introduisent des hypothèses (H) et (E) pour garantir que la solution reconstruite appartient bien au cône original $P$ et non seulement à son enveloppe convexe fermée.

C. Interprétation Géométrique (Section 4)

L'article analyse la condition d'existence d'un minimiseur pour le dual. Cela revient à l'existence de vecteurs normaux partagés entre l'ensemble des solutions de l'équation affine $A^{-1}(b)$ et l'ensemble $K_r$ (ou son enveloppe).

En dimension finie, de tels vecteurs existent toujours.
En dimension infinie, des contre-exemples montrent que le dual peut ne pas atteindre son infimum même si le primal est soluble, ce qui limite la "constructivité forte" dans certains cas pathologiques.

4. Contributions Clés

Affaiblissement des hypothèses de fermeture : L'article ne nécessite pas que $A(P)$ soit fermé, ni même que $P$ soit fermé. Il suffit que $P$ soit généré par un ensemble convexe borné fermé.
Approche constructive : Contrairement aux preuves d'existence non constructives (souvent basées sur des arguments de séparation ou de compacité faible), cette méthode fournit un algorithme explicite : résoudre un problème de minimisation convexe non contraint (le dual) pour reconstruire la solution.
Unification : La méthode couvre à la fois les cônes fermés, les cônes non fermés, et peut être étendue à des cônes non convexes via une relaxation convexe (en utilisant l'enveloppe convexe fermée du générateur).
Pseudo-inverse conique : Pour les cônes fermés, la méthode définit naturellement une pseudo-inverse conique à norme minimale, généralisant la pseudo-inverse de Moore-Penrose.

5. Signification et Perspectives

Théorique : Ce travail comble un vide dans la théorie de l'optimisation convexe en fournissant des conditions de solvabilité précises pour des systèmes linéaires contraints sur des cônes non fermés, un cas fréquent en contrôle optimal et en analyse fonctionnelle.
Numérique : La nature non contrainte du problème dual et la convexité des fonctionnelles impliquées rendent cette approche très adaptée aux algorithmes modernes de point-selle (comme l'algorithme de Chambolle-Pock). Cela ouvre la voie à des méthodes numériques pour résoudre des problèmes de contrôle et d'inversion dans des espaces de dimension infinie (PDEs/ODEs).
Limites : La principale limitation réside dans la garantie d'existence d'un minimiseur pour le problème dual en dimension infinie pour le cas exact ( $\varepsilon=0$ ). Les auteurs identifient des conditions de régularité (liées aux vecteurs normaux partagés) nécessaires pour assurer cette existence.

En résumé, cet article propose une refonte constructive du lemme de Farkas, rendant la théorie applicable à une classe beaucoup plus large de problèmes d'optimisation et de contrôle, tout en offrant des outils pratiques pour la résolution numérique.