La descente de gradient peut-elle être appliquée à des fonctions non convexes?

J'apprends juste l'optimisation et j'ai du mal à comprendre la différence entre l'optimisation convexe et non convexe. D'après ma compréhension, une fonction convexe est une fonction où "le segment de ligne entre deux points quelconques sur le graphique de la fonction se trouve au-dessus ou sur le graphique". Dans ce cas, un algorithme de descente de gradient pourrait être utilisé, car il n'y a qu'un seul minimum et les gradients vous amèneront toujours à ce minimum.

Cependant, qu'en est-il de la fonction de cette figure:

Ici, le segment de ligne bleue passe sous la fonction rouge. Cependant, la fonction n'a toujours qu'un minimum, et donc la descente en pente vous mènerait toujours à ce minimum.

Mes questions sont donc:

1) La fonction de cette figure est-elle convexe ou non convexe?

2) S'il n'est pas convexe, des méthodes d'optimisation convexe (descente de gradient) peuvent-elles encore être appliquées?

La fonction que vous avez représentée n'est en effet pas convexe. Cependant, il est quasi - convexe .

$x_1, x_2, \ldots$$f(x_1) > f(x_2) > \ldots$ .

La descente en gradient finira par converger vers un point stationnaire de la fonction, quelle que soit la convexité. Si la fonction est convexe, ce sera un minimum global, mais sinon, ce pourrait être un minimum local ou même un point de selle.

$f(x) = x^3$

Paul a déjà mentionné un point important:

• si f est convexe, il n'y a pas de points de selle et tous les minima locaux sont également globaux. Ainsi, GD (avec une taille de pas appropriée) est garanti pour trouver un minimiseur global.

Ce qui rend difficile l'optimisation non convexe, c'est la présence de points de selle et de minima locaux, où le gradient est (0, ..., 0) et qui ont une valeur objective arbitrairement mauvaise.

Trouver le minimiseur global dans un tel paramètre est généralement difficile à NP et l'on s'installe à la place dans le but de trouver un minimiseur local.

Cependant, notez que:

• La probabilité que GD se bloque sur une selle est en fait de 0 ( voir ici ).
• Cependant, la présence de points de selle pourrait ralentir considérablement la progression des GD car les directions de faible courbure sont exploitées trop lentement ( voir ici )

En fonction de la dimensionnalité de votre problème, il peut donc être judicieux d'opter pour une routine d'optimisation de second ordre.