Convergence de BFGS pour les problèmes sur-paramétrés convexes

Question

Il est "bien connu" que l'algorithme d'optimisation BFGS est convergent de façon superlinearly pour les problèmes strictement convexes, mais y a-t-il une analyse pour les problèmes qui ne sont pas strictement convexes. Par exemple, supposons que f (x) soit convexe pour un scalaire x. Supposons ensuite que nous optimisons sur g (x1, x2) = f (x1 + x2). Est-ce que ce sera toujours toujours super-linéaire?

Answer 1

Corrigez-moi si je me trompe, mais la «solution» dans ce cas ne sera-t-elle pas réellement une ligne, pas un seul point? Si x 'est un minimiseur pour f (x), alors le meilleur que vous pouvez espérer en appliquant n'importe quelle méthode à g (x1, x2) est qu'il converge vers la ligne x2 = x' - x1.

Answer 2

Si BFGS converge du tout sur des problèmes non-convexes est toujours un problème ouvert. En fait, en 1984, Powell a donné un contre-exemple qui montre que BFGS avec une recherche de ligne inexacte peut échouer à converger. Ce qui peut être fait sont des instructions locales, telles que: Étant donné un minimum local x *, si vous entrez finalement une région d'espace près de x * BFGS convergera de façon super-linéaire. La raison en est que près de x *, la fonction objectif peut être modélisée avec précision par un quadratique convexe. En ce qui concerne ce que l'on sait pour la fonction de composition que vous avez donnée, je ne suis pas sûr. Pour une explication détaillée des propriétés de BFGS, voir Dennis et Schnabel ou Nocedal et Wright.

Bonne chance.

Answer 3

En pratique, j'ai trouvé qu'un algorithme soigneusement écrit va converger, mais pas nécessairement de façon super-linéaire. L'erreur d'arrondi est le coupable. Les critères de convergence entrent en jeu. Il en est de même pour les fonctions qui sont "presque" non convexes, c'est-à-dire "rigides".

Il faut faire attention aux mises à jour BFGS pour s'assurer que le Hessien approximatif qui en résulte reste positif-défini "bien" même si le Hessian théorique ne l'est pas. Ce que je fais est de garder et mettre à jour une décomposition de Chesky du Hessian, plutôt que le Hessian en soi ou son inverse.