Optimisation non convexe

Ramufasa

Bonjour à tous
Je m'intéresse à un problème d'optimisation de la forme : $$
\text{min} ~ f(x) ~ \text{sous la contrainte } ||x - x_0|| = \alpha,
$$ où $f$ est une fonction convexe différentiable et $x_0$ est fixé.

La fonction $f$ étant continue et la sphère de centre $x_0$ et de rayon $\alpha$ étant compacte, ce problème admet une solution.
Je cherche maintenant à la déterminer numériquement.

Je voulais savoir si ce type de problèmes (fonction convexe, contrainte sphérique) pouvait bénéficier d'algorithmes particulièrement efficaces.
J'avais pensé à considérer le problème pénalisé par $\lambda ||x - x_0||^2$ pour me ramener à un problème convexe mais je ne sais pas s'il y a une meilleure idée.
Merci d'avance !

Barjovrille

Bonjour quel est l'espace de départ de $f$ ? Il y a des espaces où la sphère n'est pas compacte. Les algorithmes à mettre en place peuvent aussi dépendre de l'espace de départ.

Ramufasa

Bonjour
Je ne l'ai pas précisé effectivement mais $f$ est définie sur $\mathbb{R}^n$.

Barjovrille

Ok c'est bon pour la compacité. En fait ta question est compliqué je vais prendre le cas ou la norme est issus d'un produit scalaire et je remplace ta contrainte par $||x-x_0||^2=\alpha^2$ qui est équivalente, la stratégie en optimisation sous contrainte avec les hypothèses que tu as c'est d'introduir le lagrangien ($L : \mathbb{R}^n \times \mathbb{R}$) du problème qui permet de se ramener à un problème d'optimisation sans contraintes. Ensuite on essaye de chercher les points selles.

https://fr.wikipedia.org/wiki/Point_col (la première fois qu'on voit les points selles c'est en calcul différentiel, mais en fait ce type de point selle est un cas très particulier, la définition générale utilisé en optimisation est dans l'article wiki)

Parce qu'il y a une propriété qui dit que si on trouve un point selle $(x,\lambda)$ du Lagrangien alors $x$ est solution du problème initial. Et avec de bonnes propriétés sur la fonction à optimiser (comme c'est le cas ici) les points selles du lagrangien sont ses points critiques. Donc pour ce problème on peut aussi bien chercher algorithmiquement des points critiques que des points selles. Sauf que quand on calcul la différentielle du lagrangien il n'y a pas de point critique. Donc on jette à la poubelle toutes les méthodes de recherche de point selle, point critique...

Peut être qu'il est possible de faire une descente de gradient "circulaire"   (je veux dire en parcourant la sphère), c'est intéressant mais de ce que je vois le problème a l'air pas facile du tout (ou peut être que c'est moi qui ne sait pas faire) mais ça m'intéresse je vais essayer de chercher demain quand j'aurai un peu de temps. Ou peut être que d'ici là quelqu'un pourra nous sauver .

Bibix

Bonjour,
Sauf erreur, c'est le cadre parfait pour utiliser un algorithme newtonien du type SQP (tu peux voir la page wikipédia : https://fr.m.wikipedia.org/wiki/Optimisation_quadratique_successive). Si $f$ n'est différentiable qu'une seule fois, il existe des déclinaisons quasi-newtoniennes.

Ramufasa

Bonjour, 

Merci pour vos réponses ! Je vais regarder d'un peu plus près ces algorithmes SQP.