Pourquoi la non-convexité devrait-elle être un problème d'optimisation?

J'ai été très surpris lorsque j'ai commencé à lire quelque chose sur l'optimisation non convexe en général et j'ai vu des déclarations comme celle-ci:

De nombreux problèmes pratiques importants ne sont pas convexes et la plupart des problèmes non convexes sont difficiles (sinon impossibles) à résoudre exactement dans un délai raisonnable. ( source )

En général, il est difficile de trouver un minimum local NP et de nombreux algorithmes peuvent rester bloqués à un point de selle. ( source )

Je fais une sorte d'optimisation non convexe tous les jours - à savoir la relaxation de la géométrie moléculaire. Je n'ai jamais considéré cela comme quelque chose de délicat, lent et susceptible de rester coincé. Dans ce contexte, nous avons clairement des surfaces non convexes à plusieurs dimensions (> 1000 degrés de liberté). Nous utilisons principalement des techniques de premier ordre dérivées de la descente la plus abrupte et de la trempe dynamique telles que FIRE , qui convergent en quelques centaines d'étapes vers un minimum local (moins que le nombre de DOF). Je pense qu'avec l'ajout de bruit stochastique, il doit être robuste comme l'enfer. (L'optimisation globale est une autre histoire)

Je ne peux pas en quelque sorte imaginer à quoi devrait ressembler la surface d'énergie potentielle , pour rendre ces méthodes d'optimisation bloquées ou lentement convergentes. Par exemple, un PES très pathologique (mais pas dû à la non-convexité) est cette spirale , mais ce n'est pas un si gros problème. Pouvez-vous donner un exemple illustratif de PSE non convexe pathologique?

Je ne veux donc pas contester les citations ci-dessus. J'ai plutôt l'impression de manquer quelque chose ici. Peut-être le contexte.

optimization nonconvex Prokop Hapala
la source

Le mot clé ici est "en général" - vous pouvez construire des fonctions fonctionnelles arbitrairement désagréables, en particulier dans des dimensions très élevées qui sont fondamentalement "toutes des pointes de selle". Les classes spécifiques de fonctionnelles non convexes, en revanche, peuvent se comporter très bien, surtout si vous utilisez des stratégies de mondialisation appropriées.

Christian Clason

Je pense que la théorie du contrôle optimal et les applications de recherche en ingénierie / opérations mettent un certain accent sur l'exactitude / la robustesse, alors que vous pensez qu'obtenir un «assez bon» est assez bon. Il peut y avoir des limites de performances (la convergence doit être garantie, afin que la trajectoire d'un robot soit calculée dans le temps), ou des limites de correction (si vous modifiez un peu les paramètres du problème, vous n'obtenez pas de manière inattendue un résultat totalement différent). Il ne suffit donc pas d'obtenir des points optimaux, il est également nécessaire qu'ils aient des propriétés prescrites.

Kirill

Réponses:

Le malentendu réside dans ce qui constitue la "résolution" d'un problème d'optimisation, par exemple . Pour les mathématiciens, le problème n'est considéré comme "résolu" que lorsque nous avons: $\arg\min f(x)$

Une solution candidate: un choix particulier de la variable de décision et de sa valeur objective correspondante , ET $x^\star$ $f(x^\star)$
Une preuve d'optimalité: Une preuve mathématique que le choix de est globalement optimal, c'est-à-dire que vaut pour chaque choix de . $x^\star$ $f(x) \ge f(x^\star)$ $x$

Lorsque est convexe, les deux ingrédients sont facilement obtenus. La descente en gradient localise une solution candidate qui fait disparaître le gradient . La preuve de l'optimalité découle d'un simple fait enseigné dans MATH101 que, si est convexe et que son gradient disparaît à , alors est une solution globale. $f$ $x^\star$ $\nabla f(x^\star)=0$ $f$ $\nabla f$ $x^\star$ $x^\star$

Lorsque est non convexe, une solution candidate peut toujours être facile à trouver, mais la preuve de l'optimalité devient extrêmement difficile. Par exemple, nous pouvons exécuter une descente de gradient et trouver un point . Mais lorsque n'est pas convexe, la condition est nécessaire mais n'est plus suffisante pour l'optimalité globale. En effet, il n'est même pas suffisant pour l' optimalité locale , c'est-à-dire que nous ne pouvons même pas garantir que est un minimum local basé uniquement sur ses informations de gradient. Une approche consiste à énumérer tous les points satisfaisant , et cela peut être une tâche formidable même sur une ou deux dimensions. $f$ $\nabla f(x^\star)=0$ $f$ $\nabla f(x)=0$ $x^\star$ $\nabla f(x)=0$

Quand les mathématiciens disent que la plupart des problèmes sont impossibles à résoudre, ils disent vraiment que la preuve de l'optimalité (même locale) est impossible à construire . Mais dans le monde réel, nous ne sommes souvent intéressés que par le calcul d'une solution «suffisamment bonne», et cela peut se trouver de nombreuses façons. Pour de nombreux problèmes très non convexes, notre intuition nous dit que les solutions "assez bonnes" sont en fait globalement optimales, même si nous sommes totalement incapables de le prouver!

Richard Zhang
la source

l'optimalité globale contre l'optimalité locale est un problème complètement différent. Mais le reste a du sens. Pouvez-vous en dire plus sur «ne peut même pas garantir que x est un minimum local basé uniquement sur ses informations de gradient» ou mieux illustrer cela?

Prokop Hapala

Supposons que nous ayons les fonctions et comme des cases noires (c'est-à-dire que nous ne pouvons qu'évaluer, mais nous ne voyons pas leur forme). Le point fait disparaître les deux gradients, c'est-à-dire et , mais le point n'est qu'un minimum local pour . En fait, leurs deuxièmes dérivées sont également nulles à ce stade, donc les deux scénarios sont identiques par rapport aux deux premiers dérivés seuls!

f (x) = x^{3}

$f(x)=x^3$

g (x) = x^{4}

$g(x)=x^4$

x = 0

$x=0$

f^{'} (x) = 0

$f'(x)=0$

g^{'} (x) = 0

$g'(x)=0$

g

$g$

Richard Zhang

aha, OK, je suppose toujours automatiquement l'inertie => que l'algorithme n'aurait pas tendance à converger vers le point en du tout. Mais bien sûr, nous utilisons ici des informations supplémentaires (l'inertie) des étapes précédentes, pas seulement un gradient en un point.

x = 0

$x=0$

g (x) = x^{3}

$g(x)=x^3$

Prokop Hapala

Je comprends votre point. Et c'est peut-être vraiment la raison pour laquelle l'optimisation non convexe rigoureuse au sens mathématique est considérée comme difficile. Mais, je suis toujours plus intéressé par une application pratique, où l'heuristique (que je suppose comme faisant naturellement partie de l'algorithme) échouerait lamentablement.

Prokop Hapala

Et la quasiconvexité? Selon cette logique (( est suffisant), les problèmes quasiconvexes ne seraient-ils pas aussi faciles à optimiser que les problèmes convexes?. Ma compréhension est que ce dernier n'est pas vrai (les problèmes convexes sont toujours plus faciles).

\nabla f (x) = 0

$\nabla f(x)=0$

Amelio Vazquez-Reina

Un exemple d'un problème délicat de faible dimension pourrait être:

Étant donné que vous avez atteint un minimum local, comment pouvez-vous être sûr que c'est quelque chose d'aussi proche que le minimum global? Comment savoir si votre résultat est une solution optimale unique, étant donné qu'il est globalement optimal? Comment pouvez-vous créer un algorithme robuste à toutes les collines et vallées afin qu'il ne reste pas coincé quelque part?

Un exemple comme celui-ci est celui où les choses peuvent devenir difficiles. Évidemment, tous les problèmes ne sont pas comme ça, mais certains le sont. Ce qui est pire, dans un environnement industriel, la fonction de coût peut être longue à calculer ET avoir une surface problématique comme celle ci-dessus.

Exemple de problème réel

Un exemple que je pourrais aborder au travail est l'optimisation d'un algorithme de guidage de missile qui pourrait être robuste dans de nombreuses conditions de lancement. En utilisant notre cluster, j'ai pu obtenir les mesures de performance dont j'ai besoin en environ 10 minutes pour une seule condition. Maintenant, pour juger adéquatement de la robustesse, nous voudrions au moins un échantillon de conditions à juger. Supposons donc que nous exécutons six conditions, ce qui fait qu'une évaluation de cette fonction de coût prend une heure.

La dynamique des missiles non linéaires, la dynamique atmosphérique, les processus temporels discrets, etc. entraînent une réaction assez non linéaire aux changements de l'algorithme de guidage, ce qui rend l'optimisation difficile à résoudre. Le fait que cette fonction de coût soit non convexe fait qu'il faut du temps pour évaluer un gros problème. Un exemple comme celui-ci est celui où nous nous efforcerons d'obtenir le meilleur possible dans le temps qui nous est imparti.

spektr
la source

OK, je pense que c'est un problème différent ... problème d'optimisation globale, qui est clairement difficile et insoluble dans la plupart des situations. Mais ce n'est pas ce à quoi les gens se réfèrent en ce qui concerne l'optimisation non convexe, où ils disent que NP-difficile de trouver un minimum local et de nombreux algorithmes peuvent rester bloqués à un point de selle.

Prokop Hapala

@ProkopHapala Mes commentaires faisaient plus référence à la citation De nombreux problèmes pratiques importants sont non convexes, et la plupart des problèmes non convexes sont difficiles (sinon impossibles) à résoudre exactement dans un délai raisonnable , d'autant plus que le PO parlait de la simplicité c'est à eux de s'attaquer aux problèmes non convexes de la recherche. Résoudre exactement , pour moi, c'est rechercher une solution globalement optimale (ou quelque chose de proche). J'ai donc voulu brosser un tableau des défis du monde réel liés à ces commentaires.

spektr

Je comprends. À vrai dire, vous avez raison, mais je pense quand même que cela ne répond pas à ce que je voulais dire ... j'aurais peut-être dû mieux le formuler.

Prokop Hapala

Le problème est celui des points de selle, discuté dans le post que vous avez lié. Extrait de l'un des articles liés :

Cependant, en général, il est difficile de garantir que de tels algorithmes convergent même vers un minimum local, en raison de l'existence de structures compliquées de point de selle dans des dimensions élevées. De nombreuses fonctions ont des points de selle dégénérés tels que les dérivées du premier et du second ordre ne peuvent pas les distinguer avec des optima locaux . Dans cet article, nous utilisons des dérivées d'ordre supérieur pour échapper à ces points de selle: nous concevons le premier algorithme efficace garanti pour converger vers un optimum local de troisième ordre (alors que les techniques existantes sont tout au plus de second ordre). Nous montrons également qu'il est NP-difficile d'étendre cela pour trouver des optima locaux du quatrième ordre.

Essentiellement, vous pouvez avoir des fonctions où vous avez des points de selle qui ne se distinguent pas des minima locaux lorsque vous regardez les dérivées 1ère, 2ème et 3ème. Vous pouvez résoudre ce problème en allant dans un optimiseur d'ordre supérieur, mais ils montrent que la fin d'un minimum local de 4e ordre est NP difficile.

Je recommande de lire l'article, car ils montrent également plusieurs exemples de telles fonctions. Par exemple, la fonction a un tel point à (0,0). $x^2y+y^2$

Vous pouvez utiliser plusieurs heuristiques pour échapper à ces points, qui peuvent travailler pour beaucoup ( la plupart?) Des exemples du monde réel, mais ne peut pas être prouvée à toujours du travail.
Dans le billet de blog que vous avez lié, ils discutent également des conditions dans lesquelles vous pouvez échapper à ces points de selle en temps polynomial.

LKlevin
la source

oui, il est clair que de la valeur et du gradient en un point, vous ne pouvez pas le distinguer. Mais je ne vois pas pourquoi les heuristiques courantes (comme la descente de gradient stochastique ou le FEU) devraient échouer dans une telle situation. Je suis sûr que cela fonctionnera très bien pour . J'essaie donc d'imaginer une fonction patologique si cela ne fonctionnait pas.

x^{2} y + y^{2}

$x^2y+y^2$

Prokop Hapala

Vous devez le regarder dans l'autre sens. Ce n'est pas que nous savons que la descente de gradient stochastique échouera, c'est que nous ne savons pas qu'elle réussira. Pour les problèmes de jouets, il est peu probable que cela se produise dans la pratique, mais cela peut se produire pour des problèmes de dimension supérieure. Je parie que pour vos problèmes de chimie, cela n'arrivera jamais, mais j'aurais du mal à le prouver.

LKlevin