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

Dit artikel presenteert een constructieve generalisatie van het lemma van Farkas voor niet-perfect gesloten kegels, gebaseerd op Fenchel-Rockafellar-dualiteit, die noodzakelijke en voldoende voorwaarden biedt voor de bereikbaarheid van een vector en de constructie van benaderende oplossingen onder de zwakkere aanname dat de kegel wordt gegenereerd door een gesloten, begrensd convex verzameling.

De kern

Stel je voor dat je een grote, complexe puzzel probeert op te lossen. Je hebt een doos met stukjes (noem dit je P, een verzameling van mogelijke opties) en je wilt weten of je met die stukjes precies een bepaald plaatje kunt maken (noem dit b, je doel).

In de wiskunde heet dit het Farkas-lemma. Het is een oude, beroemde regel die zegt: "Als je een plaatje kunt maken, dan is er een specifieke manier om dat te bewijzen. En als je het plaatje niet kunt maken, dan is er een andere specifieke manier om dat te bewijzen."

Maar hier zit een addertje onder het gras. De oude regel werkt alleen als je puzzelstukjes in een strakke, gesloten doos zitten. Als de doos een klein gaatje heeft (wiskundig: als de verzameling niet "gesloten" is), dan faalt de oude regel. In de echte wereld (zoals bij het besturen van een raket of het oplossen van medische beeldvorming) zijn die "gaten" in de doos heel normaal.

De auteurs van dit paper (Camille, Emmanuel en Christophe) hebben een nieuwe, slimmere manier bedacht om dit probleem op te lossen. Hier is hoe het werkt, vertaald naar alledaags taal:

1. Het Probleem: De Gaten in de Doos

Stel je voor dat je een machine hebt (noem dit A) die je puzzelstukjes omzet in een ander plaatje. Je wilt weten: "Kan ik met mijn stukjes precies het plaatje b maken?"

De oude wiskundige regel zei: "Ja, als de doos met stukjes perfect gesloten is."
Maar wat als de doos een klein gat heeft? Dan kan het zijn dat je het plaatje bijna kunt maken, maar nooit 100% perfect. De oude regel zegt dan niets meer. Het is alsof je zegt: "Je mag alleen in de kamer als de deur dicht is." Maar als de deur op een kier staat, weet je niet of je binnen mag of niet.

2. De Oplossing: Een Nieuwe Strategie (De Spiegel)

De auteurs zeggen: "Laten we niet kijken naar de puzzelstukjes zelf, maar naar een spiegelbeeld ervan."

Ze gebruiken een wiskundige techniek genaamd Fenchel-Rockafellar-dualiteit.

• De Oude Manier: Kijk rechtstreeks naar de puzzelstukjes en probeer ze in elkaar te zetten. (Dit is lastig als de doos gaten heeft).
• De Nieuwe Manier: Kijk naar een "tegenpartij" (een spiegelbeeld). Als je in de spiegel ziet dat er een oplossing is, dan is er ook een oplossing in de echte wereld.

Het mooie van hun methode is dat ze niet alleen zeggen "ja" of "nee", maar ook hoe je het moet doen. Ze geven een recept (een algoritme) om de oplossing te bouwen.

3. De Creatieve Analogie: De Berg en de Vallei

Stel je voor dat je in een landschap loopt:

• Je hebt een berg (de verzameling van alle mogelijke oplossingen).
• Je wilt een piek vinden die precies op een bepaalde hoogte ligt (je doel b).

De oude regel zei: "Als de berg een gladde, gesloten helling heeft, kun je de top vinden."
Maar wat als de berg een afgrond heeft of een gat in de top? Dan kun je de top misschien niet bereiken, maar wel heel dichtbij komen.

De auteurs zeggen: "Laten we niet naar de berg kijken, maar naar de vallei eronder (het spiegelbeeld)."
Ze hebben een nieuwe kaart getekend van die vallei.

1. Als je de top kunt bereiken: Dan kun je in de vallei een punt vinden dat precies overeenkomt.
2. Als je de top niet kunt bereiken, maar wel heel dichtbij: Dan kun je in de vallei een punt vinden dat je vertelt hoe dichtbij je kunt komen.

En het allerbelangrijkste: De kaart is constructief. Dat betekent dat ze je niet alleen vertellen dat er een oplossing is, maar ze geven je de exacte coördinaten om erheen te lopen. Je hoeft niet te gissen; je kunt een computerprogramma draaien dat je precies de route geeft.

4. Waarom is dit zo belangrijk?

In de echte wereld zijn dingen zelden perfect "gesloten".

• In de luchtvaart: Je wilt een vliegtuig laten landen op een specifieke plek. De wind en de stuurinstructies vormen een verzameling met "gaten". De oude regels konden niet altijd zeggen of een landing mogelijk was. Deze nieuwe methode kan het wel.
• In de geneeskunde: Bij MRI-scans probeer je een beeld te reconstrueren. Soms ontbreken er data (gaten). Deze methode helpt om het beste mogelijke beeld te maken, zelfs als de data niet perfect is.

5. Samenvatting in één zin

De auteurs hebben een nieuwe, slimmere manier bedacht om te bewijzen of een complex probleem oplosbaar is, zelfs als de regels niet perfect zijn, en ze geven je bovendien een stap-voor-stap instructie om de oplossing te bouwen, net als een GPS die je niet alleen vertelt of je bestemming bereikbaar is, maar je ook de route uitzet.

Kortom: Ze hebben de oude, stijve regels van Farkas losgeknipt en vervangen door een flexibele, slimme tool die werkt in de "rommelige" echte wereld, en die je bovendien precies vertelt hoe je aan het doel komt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Generalisation of Farkas' lemma beyond closedness: a constructive approach via Fenchel-Rockafellar duality" in het Nederlands.

Probleemstelling

Het artikel adresseert een fundamenteel probleem in de optimalisatie en lineaire algebra: het bepalen van noodzakelijke en voldoende voorwaarden voor de oplosbaarheid van de vergelijking $Ax = b$ onder de restrictie dat $x$ behoort tot een kegel $P$.

• Gegeven: Twee Hilbertruimten $X$ en $Y$, een continue lineaire operator $A: X \to Y$, een vector $b \in Y$, en een kegel $P \subset X$ (die de oorsprong bevat).
• Doel: Bepalen of $b \in A(P)$ (exacte oplosbaarheid) of $b \in \overline{A(P)}$ (benaderende oplosbaarheid, d.w.z. bestaat er een $x$ zodat $\|Ax - b\| \leq \varepsilon$).
• De uitdaging: De klassieke stelling van Farkas vereist doorgaans dat de beeldkegel $A(P)$ gesloten is. Deze voorwaarde is echter vaak moeilijk te controleren en in veel praktische gevallen (zoals in oneindig-dimensionale ruimten) niet voldaan. Bestaande generalisaties die de geslotenheid van $A(P)$ laten varen, zijn vaak niet-constructief of vereisen nog steeds dat de kegel $P$ zelf gesloten is.

Methodologie

De auteurs ontwikkelen een nieuwe, constructieve aanpak gebaseerd op de Fenchel-Rockafellar-dualiteitstheorie. In plaats van direct te zoeken naar een oplossing, formuleren ze een hulpoptimalisatieprobleem en analyseren het duale probleem.

1. Hulpfuncties en Problemen:

   • Ze introduceren een gauge-functie $j_{K_r}(x)$ voor een begrensd, gesloten, convex verzameling $K_r$ die $0$bevat en de kegel$P$genereert (d.w.z.$P = \text{cone}(K_r)$).
   • Ze definiëren een primair optimalisatieprobleem $(P_\varepsilon)$ voor een tolerantie $\varepsilon \geq 0$:
     $$\inf_{x \in X} F_\varepsilon(x) = \inf_{x \in X} \left( \frac{1}{2} j_{K_r}^2(x) + \delta_{\{x : \|Ax-b\|_Y \leq \varepsilon\}}(x) \right)$$
     Hierbij is $\delta_C$ de indicatorfunctie van de verzameling $C$.
   • Het doel is om een $x$ te vinden die de norm minimaliseert (via de gauge) terwijl de vergelijking binnen de tolerantie $\varepsilon$ wordt opgelost.

2. Dualiteit:

   • Met behulp van Fenchel-Rockafellar-dualiteit wordt het duale probleem $(D_\varepsilon)$ afgeleid:
     $$\inf_{y \in Y} J_\varepsilon(y) = \inf_{y \in Y} \left( \frac{1}{2} \sigma_{K_r}^2(A^*y) - \langle b, y \rangle_Y + \varepsilon \|y\|_Y \right)$$
     Hierbij is $\sigma_{K_r}$ de steunfunctie (support function) van $K_r$.
   • Een cruciaal voordeel van deze formulering is dat het duale probleem ongebonden is (de kostenfunctie is overal eindig), in tegenstelling tot eerdere methoden die lineaire restricties in het duale probleem hadden.

3. Constructiviteit:

   • De auteurs tonen aan dat als het duale probleem een oplossing $y^*$ toelaat, de oplossing van het primaire probleem $x^*$ expliciet kan worden gereconstrueerd via optimaliteitsvoorwaarden (subdifferentiëren van de steunfunctie).

Belangrijkste Bijdragen

1. Verzwakking van Hypotheses:

   • De methode vereist niet dat $A(P)$ gesloten is (de standaard aanname in klassieke Farkas-lemma's).
   • Ze verzwakken ook de eis dat $P$ zelf gesloten is. Het enige vereiste is dat $P$ wordt gegenereerd door een begrensde, gesloten, convexe verzameling $K_r$ die $0$ bevat. Dit maakt de theorie toepasbaar op een bredere klasse van kegels, inclusief niet-gesloten kegels.

2. Constructieve Karakterisaties:

   • In tegenstelling tot eerdere generalisaties (zoals die van Hernandez-Lerma en Lasserre) die kwantitatieve maar niet-constructieve voorwaarden geven, biedt deze aanpak een praktisch algoritme.
   • Men lost het duale probleem op om $y^*$ te vinden en reconstructeert $x^*$ via projectie of subdifferentiëren.

3. Behandeling van Niet-Convexe Kegels:

   • De methode wordt uitgebreid naar niet-convexe kegels door deze te "relaxeren" naar hun gesloten convexe hull. Onder bepaalde voorwaarden (extreme punten van de generator liggen in de oorspronkelijke verzameling) garandeert de methode dat de oplossing ook in de oorspronkelijke (niet-convexe) kegel ligt.

Kernresultaten

Het artikel presenteert een reeks stellingen die noodzakelijke en voldoende voorwaarden geven voor oplosbaarheid, afhankelijk van de eigenschappen van de kegel:

• Voor gesloten convexe kegels:

  • $b \in A(P)$ dan en slechts dan als er een $C > 0$ bestaat zodat voor alle $y \in Y$: $\langle b, y \rangle \leq C \|(A^*y)_+\|$, waarbij $(\cdot)_+$ de projectie op $P$ is.
  • Voor $\varepsilon > 0$ is het duale probleem altijd goed gesteld en heeft het een unieke oplossing. De primaire oplossing is uniek en wordt gegeven door $x^* = (A^*y^*)_+$.

• Voor kegels gegenereerd door een begrensd gesloten convex verzameling ($P = \text{cone}(K_r)$):

  • De voorwaarden worden uitgedrukt in termen van de steunfunctie $\sigma_{K_r}$.
  • $b \in A(P)$ dan en slechts dan als er een $C > 0$ bestaat zodat $\langle b, y \rangle \leq C \sigma_{K_r}(A^*y)$.
  • De constructieve relatie is: $x^* \in \sigma_{K_r}(A^*y^*) \partial \sigma_{K_r}(A^*y^*)$.
  • Uniciteit: Als de steunfunctie differentieerbaar is op het bereik van $A^*$ (een niet-degeneratievoorwaarde), dan is de oplossing uniek en wordt deze volledig bepaald door de duale variabele.

• Exacte Oplosbaarheid ($\varepsilon = 0$):

  • Een belangrijke nuance is dat voor exacte oplosbaarheid het duale probleem niet altijd een minimum bereikt, zelfs als het infimum eindig is. De auteurs analyseren wanneer dit wel gebeurt (gerelateerd aan het bestaan van "gedeelde normaalvectoren" tussen de verzameling $A^{-1}(b)$ en de generator $K_r$).
  • In eindig-dimensionale ruimten wordt bewezen dat een duale oplossing altijd bestaat. In oneindig-dimensionale ruimten worden tegenvoorbeelden gegeven waar de duale oplossing niet bestaat, wat de constructiviteit beperkt tot "zwak constructief" (de oplossing bestaat, maar is niet altijd direct uit de duale variabele af te leiden).

Significantie en Toepassingen

• Theoretische Vooruitgang: Het artikel overbrugt de kloof tussen de klassieke, strikte Farkas-lemma's en de realiteit van niet-gesloten kegels in oneindig-dimensionale ruimten. Het biedt een unificerend kader voor zowel exacte als benaderende oplosbaarheid.
• Numerieke Toepasbaarheid: Omdat de methode leidt tot een ongebonden convex optimalisatieprobleem (het duale probleem), is deze zeer geschikt voor numerieke implementatie met moderne algoritmen zoals de Chambolle-Pock-algoritme (voor saddle-point problemen).
• Toepassingsgebieden: De resultaten zijn direct relevant voor:
  • Optimale besturing: Waar kegels vaak niet-gesloten zijn of waar "bang-bang" controles (extreme punten) nodig zijn.
  • Inverse problemen: Het oplossen van lineaire vergelijkingen met beperkingen in oneindig-dimensionale ruimten (bijv. PDE's).
  • Convex Analysis: Het biedt nieuwe inzichten in de relatie tussen primal-dual oplossingen en de geometrie van kegels en hun generatoren.

Samenvattend biedt dit werk een robuust, constructief raamwerk om de oplosbaarheid van lineaire vergelijkingen op kegels te analyseren, zelfs wanneer de gebruikelijke geslotenheidsvoorwaarden niet van toepassing zijn, en levert het concrete algoritmen voor het vinden van oplossingen.