Projected Subgradient Ascent for Convex Maximization

Résumé Technique : Ascension par Sous-Gradient Projeté pour la Maximisation Convexe

1. Problématique

Les auteurs considèrent le problème de maximisation d'une fonction convexe $f$ sur un ensemble fermé et convexe $S$ dans un espace de Hilbert réel $H$.
Le cas particulier d'intérêt est l'optimisation linéaire :
$$\max_{x \in S} \langle c, x \rangle$$
Contrairement à la minimisation convexe (qui est un problème bien posé et largement résolu), la maximisation d'une fonction convexe est généralement un problème NP-difficile. L'objectif n'est donc pas de trouver un optimum global garanti, mais d'atteindre des points stationnaires du premier ordre (points où le gradient ou le sous-gradient pointe vers l'extérieur de l'ensemble admissible, ou est orthogonal à la frontière).

2. Méthodologie

Le papier explore deux régimes principaux basés sur l'ascension par sous-gradient projeté (Projected Subgradient Ascent - PGA) :

• Cas Linéaire (Une seule projection) :
  Pour maximiser une fonction linéaire, les auteurs montrent qu'une seule projection orthogonale suffit pour obtenir une solution approchée.
  Soit $x_0$ un point initial et $c$ le vecteur de coût. La méthode consiste à calculer :
  $$x_\eta = P_S(x_0 + \eta c)$$
  où $P_S$ est la projection orthogonale sur $S$ et $\eta$ est un paramètre d'échelle (pas). Les auteurs analysent le comportement lorsque $\eta \to \infty$.

• Cas Convexe Général (Ascension par sous-gradient avec grands pas) :
  Pour maximiser une fonction convexe continue $f$, les auteurs étudient l'itération suivante avec une séquence de pas $\{\eta_k\}$ :
  $$x_{k+1} = P_S(x_k + \eta_k g_k)$$
  où $g_k \in \partial f(x_k)$ est un sous-gradient.
  Innovation clé : Contrairement à la descente de gradient projeté (PGD) pour la minimisation qui nécessite des pas tendant vers zéro ($\eta_k \to 0$), cette approche utilise des pas arbitrairement grands (voire infinis).

3. Contributions Clés et Résultats

A. Optimisation Linéaire et Projection Unique

• Convergence Forte : Le papier démontre que lorsque $\eta \to \infty$, la séquence $x_\eta = P_S(x_0 + \eta c)$ converge fortement vers l'unique solution optimale $x^*$ de l'ensemble des maximiseurs $M(c)$ qui est la plus proche de $x_0$ (Théorème 2.7).
• Bornes d'Erreur : Des bornes explicites sont fournies sur la valeur de l'objectif. Pour un $\eta$ fini, l'erreur d'approximation est bornée par $\frac{\|x^* - x_0\|^2 - \|x_\eta - x_0\|^2}{2\eta}$. Si $S$ est borné, l'erreur est de l'ordre de $O(1/\eta)$.
• Monotonie : La valeur de l'objectif $\langle c, x_\eta \rangle$ est monotone croissante avec $\eta$.
• Réduction de Complexité : Cela établit une réduction de l'optimisation linéaire à la projection orthogonale. Bien que la projection puisse être coûteuse, cela suggère que l'optimisation linéaire n'est pas plus difficile que la projection sur le même ensemble.

B. Maximisation Convexe avec Grands Pas

• Convergence vers la Stationnarité : Pour des fonctions convexes continues dans des espaces de Hilbert (même de dimension infinie), l'ascension par sous-gradient projeté avec des pas $\eta_k$ non décroissants et bornés supérieurement converge vers un point stationnaire du premier ordre (Théorème 3.14).
• Hypothèses Minimales : Contrairement aux travaux antérieurs sur la maximisation non convexe qui nécessitent la différentiabilité, la continuité lipschitzienne du gradient et l'inégalité de Kurdyka-Lojasiewicz, ce résultat repose uniquement sur la convexité de la fonction et la compacité de l'ensemble $S$.
• Propriétés de la Séquence :
  • La suite des valeurs de la fonction $\{f(x_k)\}$ est non décroissante.
  • L'ensemble des points d'accumulation de la suite $\{x_k\}$ est connexe.
  • Si les pas sont bornés inférieurement ($\liminf \eta_k > 0$), tous les points d'accumulation sont stationnaires.

C. Lien avec les Méthodes Existantes (Limite $\eta \to \infty$)

• Variante Déterministe de Frank-Wolfe : Lorsque les pas $\eta_k$ tendent vers l'infini, la mise à jour PGA devient :
  $$x_{k+1} = P_{M(\nabla f(x_k))}(x_k)$$
  Cela correspond à sélectionner, parmi les solutions du problème linéaire $\max_{z \in S} \langle \nabla f(x_k), z \rangle$, celle qui est la plus proche de $x_k$. C'est une variante déterministe de l'algorithme du gradient conditionnel (Frank-Wolfe) avec un pas unitaire.
• Optimisation Linéaire Itérée : Ce cadre généralise la méthode d'optimisation linéaire itérée (introduite dans [13]), qui correspond au cas particulier où $f(x) = \frac{1}{2}\|x\|^2$.

4. Signification et Impact

• Paradigme Inversé : Le papier renverse l'intuition classique de l'optimisation convexe. Alors que la minimisation nécessite des pas décroissants pour la stabilité, la maximisation de fonctions convexes bénéficie de pas très grands, voire infinis, pour converger vers des points stationnaires.
• Généralité : Les résultats s'appliquent aux espaces de Hilbert de dimension infinie et à des ensembles convexes avec des frontières lisses (non nécessairement polyédriques), élargissant ainsi le champ d'application par rapport aux travaux antérieurs limités aux polytopes ou aux espaces finis.
• Algorithmique : La réduction de l'optimisation linéaire à une seule projection offre une nouvelle perspective pour concevoir des algorithmes. Si l'on dispose d'un algorithme efficace pour la projection sur un ensemble $S$ (par exemple, des boules de norme nucléaire ou des polytopes de flux), on peut en déduire un algorithme efficace pour l'optimisation linéaire sur cet ensemble.
• Robustesse : La méthode ne nécessite pas de régularité forte (différentiabilité) de la fonction objectif, ce qui la rend applicable à des problèmes où les sous-gradients existent mais où le gradient n'est pas défini partout.

En conclusion, ce travail fournit un cadre théorique rigoureux justifiant l'utilisation de pas de gradient très grands pour la maximisation convexe, reliant des concepts d'analyse convexe, de théorie des opérateurs monotones et d'algorithmes d'optimisation classiques.