Pourquoi les algorithmes d'optimisation sont-ils définis en fonction d'autres problèmes d'optimisation?

Je fais des recherches sur les techniques d'optimisation pour l'apprentissage automatique, mais je suis surpris de constater qu'un grand nombre d'algorithmes d'optimisation sont définis en fonction d'autres problèmes d'optimisation. J'illustre quelques exemples dans ce qui suit.

Par exemple https://arxiv.org/pdf/1511.05133v1.pdf

Tout semble beau et bon, mais il y a cet dans la mise à jour z k + 1 .... alors quel est l'algorithme qui résout l' argmin ? Nous ne savons pas, et cela ne dit pas. Donc, par magie, nous devons résoudre un autre problème d'optimisation qui est de trouver le vecteur de minimisation afin que le produit intérieur soit au minimum - comment cela peut-il être fait?$\text{argmin}_x$$z^{k+1}$$\text{argmin}$

Prenons un autre exemple: https://arxiv.org/pdf/1609.05713v1.pdf

Tout semble beau et bon jusqu'à ce que vous frappiez cet opérateur proximal au milieu de l'algorithme, et quelle est la définition de cet opérateur?

Boom:

$\text{argmin}_x$$f$

Quelqu'un peut-il m'éclairer sur:

1. Pourquoi tant d'algorithmes d'optimisation sont-ils définis en termes d'autres problèmes d'optimisation?

(Ne serait-ce pas une sorte de problème de poulet et d'oeuf: pour résoudre le problème 1, vous devez résoudre le problème 2, en utilisant la méthode de résolution du problème 3, qui repose sur la résolution du problème ....)

2. $x^{k+1} = \text{argmin}_x \text{really complicated loss function}$

3. $\text{argmin}_x$

(Bounty: quelqu'un peut-il faire référence à un article pour lequel les auteurs expliquent clairement l'algorithme du sous-problème intégré à l'algorithme d'optimisation de haut niveau?)

Vous recherchez des organigrammes d'algorithme de niveau supérieur. Certaines des étapes individuelles de l'organigramme peuvent mériter leurs propres organigrammes détaillés. Cependant, dans les articles publiés mettant l'accent sur la brièveté, de nombreux détails sont souvent omis. Les détails des problèmes d'optimisation interne standard, qui sont considérés comme des «vieux casquettes», peuvent ne pas être fournis du tout.

L'idée générale est que les algorithmes d'optimisation peuvent nécessiter la solution d'une série de problèmes d'optimisation généralement plus faciles. Il n'est pas rare d'avoir 3 ou même 4 niveaux d'algorithmes d'optimisation dans un algorithme de niveau supérieur, bien que certains d'entre eux soient internes aux optimiseurs standard.

Même décider quand mettre fin à un algorithme (à l'un des niveaux hiérarchiques) peut nécessiter la résolution d'un problème d'optimisation secondaire. Par exemple, un problème de moindres carrés linéaires non contraint négativement pourrait être résolu pour déterminer les multiplicateurs de Lagrange utilisés pour évaluer le score d'optimalité KKT utilisé pour décider quand déclarer l'optimalité.

Si le problème d'optimisation est stochastique ou dynamique, il peut y avoir encore des niveaux hiérarchiques supplémentaires d'optimisation.

Voici un exemple. Programmation quadratique séquentielle (SQP). Un premier problème d'optimisation est traité par la résolution itérative des conditions d'optimalité de Karush-Kuhn-Tucker, à partir d'un point initial avec un objectif qui est une approximation quadratique du lagrangien du problème, et une linéarisation des contraintes. Le programme quadratique (QP) résultant est résolu. Le QP qui a été résolu a soit des contraintes de région de confiance, soit une recherche de ligne est effectuée de l'itération actuelle à la solution du QP, qui est elle-même un problème d'optimisation, afin de trouver l'itération suivante. Si une méthode Quasi-Newton est utilisée, un problème d'optimisation doit être résolu pour déterminer la mise à jour Quasi-Newton du Hessien du Lagrangien - il s'agit généralement d'une optimisation de forme fermée utilisant des formules fermées telles que BFGS ou SR1, mais cela pourrait être une optimisation numérique. Ensuite, le nouveau QP est résolu, etc. Si le QP est irréalisable, y compris pour démarrer, un problème d'optimisation est résolu pour trouver un point réalisable. Pendant ce temps, il peut y avoir un ou deux niveaux de problèmes d'optimisation interne appelés à l'intérieur du solveur QP. À la fin de chaque itération, un problème de moindres carrés linéaires non négatifs peut être résolu pour déterminer le score d'optimalité. Etc.

S'il s'agit d'un problème d'entiers mixtes, alors tout ce shebang peut être effectué à chaque nœud de branchement, dans le cadre d'un algorithme de niveau supérieur. De même pour un optimiseur global - un problème d'optimisation local est utilisé pour produire une borne supérieure sur la solution globalement optimale, puis un relâchement de certaines contraintes est effectué pour produire un problème d'optimisation de borne inférieure. Des milliers voire des millions de problèmes d'optimisation «faciles» à partir de branches et de liaisons peuvent être résolus afin de résoudre un problème d'optimisation mixte entier ou global.

Cela devrait commencer à vous donner une idée.

Edit : En réponse à la question du poulet et des œufs qui a été ajoutée à la question après ma réponse: s'il y a un problème de poulet et d'œufs, ce n'est pas un algorithme pratique bien défini. Dans les exemples que j'ai donnés, il n'y a ni poulet ni œuf. Les étapes d'algorithme de niveau supérieur invoquent des solveurs d'optimisation, qui sont définis ou existent déjà. SQP appelle de manière itérative un solveur QP pour résoudre des sous-problèmes, mais le solveur QP résout un problème plus simple, QP, que le problème d'origine. S'il existe un algorithme d'optimisation globale de niveau encore plus élevé, il peut invoquer un solveur SQP pour résoudre des sous-problèmes d'optimisation non linéaire locaux, et le solveur SQP appelle à son tour un solveur QP pour résoudre les sous-problèmes QP. Pas de poulet ni d'oeuf.

Remarque: les opportunités d'optimisation sont "partout". Les experts en optimisation, tels que ceux qui développent des algorithmes d'optimisation, sont plus susceptibles de voir ces opportunités d'optimisation, et de les voir comme telles, que le Joe ou Jane moyen. Et étant inclinés algorithmiquement, ils voient tout naturellement des opportunités pour construire des algorithmes d'optimisation à partir d'algorithmes d'optimisation de niveau inférieur. La formulation et la solution des problèmes d'optimisation servent de blocs de construction pour d'autres algorithmes d'optimisation (de niveau supérieur).

Edit 2 : En réponse à une demande de prime qui vient d'être ajoutée par l'OP. Le document décrivant l'optimiseur non linéaire SQP SNOPT https://web.stanford.edu/group/SOL/reports/snopt.pdf mentionne spécifiquement le solveur QP SQOPT, qui est documenté séparément, comme étant utilisé pour résoudre les sous-problèmes QP dans SNOPT.

J'aime la réponse de Mark, mais je pensais que je mentionnerais le "recuit simulé", qui peut essentiellement fonctionner au-dessus de n'importe quel algorithme d'optimisation. À un niveau élevé, cela fonctionne comme ceci:

Il a un paramètre "température" qui démarre à chaud. Lorsqu'il est chaud, il s'éloigne fréquemment (et plus loin) de l'endroit où pointe l'algorithme d'optimisation subordonné. En refroidissant, il suit de plus près les conseils de l'algorithme subordonné et, à zéro, il le suit jusqu'à l'optimum local où il s'est retrouvé.

L'intuition est qu'il cherchera largement l'espace au début, à la recherche de «meilleurs endroits» pour rechercher des optimaux.

Nous savons qu'il n'y a pas de véritable solution générale au problème optimal local / global. Chaque algorithme aura ses angles morts, mais des hybrides comme celui-ci semblent donner de meilleurs résultats dans de nombreux cas.

Je pense qu'une référence qui peut satisfaire votre désir est ici . Allez à la section 4 - Optimisation dans le calcul bayésien moderne.

TL; DR - ils discutent des méthodes proximales. L'un des avantages de ces méthodes est le fractionnement - vous pouvez trouver une solution en optimisant les sous-problèmes plus faciles. Souvent (ou, du moins parfois), vous pouvez trouver dans la littérature un algorithme spécialisé pour évaluer une fonction proximale spécifique. Dans leur exemple, ils font du débruitage d'image. L'une des étapes est un algorithme très réussi et très cité par Chambolle.

C'est assez courant dans de nombreux articles d'optimisation et cela a à voir avec la généralité. Les auteurs écrivent généralement les algorithmes de cette manière pour montrer qu'ils fonctionnent techniquement pour n'importe quelle fonction f. Cependant, dans la pratique, ils ne sont utiles que pour des fonctions très spécifiques où ces sous-problèmes peuvent être résolus efficacement.

Par exemple, et maintenant je ne parle que du deuxième algorithme, chaque fois que vous voyez un opérateur proximal (qui, comme vous l'avez noté, est un autre problème d'optimisation qui peut être en effet très difficile à résoudre) est généralement implicite qu'il a une solution de forme fermée dans afin que l'algorithme soit efficace. Il en est ainsi pour de nombreuses fonctions d'intérêt dans l'apprentissage automatique telles que la norme l1, les normes de groupe, etc. Dans ces cas, vous remplaceriez les sous-problèmes pour la formule explicite de l'opérateur proximal, et il n'y a pas besoin d'un algorithme pour résoudre ce problème.

Quant à savoir pourquoi ils sont écrits de cette manière, notez simplement que si vous deviez proposer une autre fonction et que vous vouliez appliquer cet algorithme, vous vérifieriez, d'abord, si le proximal a une solution de forme fermée ou peut être calculé efficacement. Dans ce cas, il vous suffit de brancher la formule dans l'algorithme et vous êtes prêt à partir. Comme mentionné précédemment, cela garantit que l'algorithme est suffisamment général pour être appliqué à une fonction future qui pourrait apparaître après la première publication de l'algorithme, ainsi que leurs expressions proximales d'algorithmes efficaces pour les calculer.

Enfin, à titre d'exemple, prenez le papier original de l'algorithme FISTA classique. Ils dérivent l'algorithme pour deux fonctions très spécifiques, la perte au carré et la norme l1. Cependant, ils notent qu'il ne peut être appliqué aucune fonction tant qu'ils remplissent certaines conditions préalables, l'une d'entre elles étant que le proximal du régularisé peut être calculé efficacement. Il ne s'agit pas d'une exigence théorique mais pratique.

Cette compartimentation rend non seulement l'algorithme général mais aussi plus facile à analyser: tant qu'il existe des algorithmes pour les sous-problèmes qui ont ces propriétés, alors l'algorithme proposé aura ce taux de convergence ou autre.