Méthodes basées sur Newton dans l'optimisation vs la résolution de systèmes d'équations non linéaires

J'ai demandé des éclaircissements sur une question récente à propos de minpack et j'ai obtenu le commentaire suivant:

Tout système d'équations équivaut à un problème d'optimisation, c'est pourquoi les méthodes basées sur Newton en optimisation ressemblent beaucoup aux méthodes basées sur Newton pour résoudre des systèmes d'équations non linéaires.

Ce qui m'embrouille à propos de ce commentaire (et des opinions négatives connexes sur les solveurs des moindres carrés non linéaires spécialisés comme minpack) pourrait être mieux expliqué sur l'exemple de la méthode du gradient conjugué . Cette méthode est applicable aux systèmes $Ax=b$ avec une matrice symétrique définie positive $A$ . Il pourrait également être utilisé pour résoudre le problème général des moindres carrés $\operatorname{min}_x||Ax-b||^2$ pour une matrice arbitraire $A$ , mais cela n'est pas recommandé. Une explication pour laquelle nous ne devrions pas faire cela est que le numéro de condition du système augmenterait considérablement.

Mais si la transformation d'un système d'équations en un problème d'optimisation est considérée comme problématique même pour le cas linéaire, pourquoi devrait-elle être moins problématique pour le cas général? Il semble être en quelque sorte lié à l'utilisation d'un algorithme d'optimisation de pointe, au lieu d'utiliser un solveur des moindres carrés non linéaire légèrement vieilli. Mais les problèmes liés à la suppression des informations et à l'augmentation du nombre de conditions du système ne sont-ils pas relativement indépendants de l'algorithme d'optimisation réellement utilisé?

optimization least-squares Thomas Klimpel
la source

Réponses:

Puisqu'une de mes réponses a été citée, je vais essayer de clarifier pourquoi j'ai suggéré d'utiliser IPOPT au lieu de MINPACK.

Mes objections à l'utilisation de MINPACK n'ont rien à voir avec les algorithmes que MINPACK utilise et tout à voir avec leur implémentation. Ma principale objection est que le logiciel remonte à 1980 et a été mis à jour pour la dernière fois en 1999. Jorge Moré est à la retraite; Je doute que lui ou l'un des autres auteurs du logiciel garde un œil dessus, et il n'y a pas d'équipe de personnes qui le soutiennent activement. La seule documentation que je peux trouver sur le logiciel est le rapport technique original d'Argonne de 1980 écrit par Jorge Moré et les autres auteurs de MINPACK. (Les chapitres 1-3 peuvent être trouvés ici , et le chapitre 4 peut être trouvé ici.) Après avoir recherché le code source de MINPACK et parcouru la documentation (les fichiers PDF sont des images numérisées et ne peuvent pas être recherchés), je ne vois aucune option pour s'adapter aux contraintes. Puisque l'affiche originale du problème des moindres carrés non linéaires voulait résoudre un problème des moindres carrés non linéaires contraint, MINPACK ne résoudra même pas ce problème.

Si vous regardez la liste de diffusion IPOPT, certains utilisateurs indiquent que les performances du package sur les problèmes des moindres carrés non linéaires (NLS) sont mitigées par rapport aux algorithmes de Levenberg-Marquardt et aux algorithmes NLS plus spécialisés (voir ici , ici et ici ). Les performances d'IPOPT par rapport aux algorithmes NLS dépendent bien sûr du problème. Étant donné les commentaires des utilisateurs, IPOPT semble être une recommandation raisonnable par rapport aux algorithmes NLS.

Cependant, vous faites valoir que les algorithmes NLS doivent être étudiés. Je suis d'accord. Je pense simplement qu'un package plus moderne que MINPACK devrait être utilisé car je pense qu'il fonctionnera mieux, sera plus utilisable et sera pris en charge. Ceres semble être un package candidat intéressant, mais il ne peut pas gérer les problèmes contraints pour le moment. TAOfonctionnerait sur les problèmes de moindres carrés contraints par des boîtes, bien qu'il n'implémente pas le Levenberg-Marquardt classique, mais implémente à la place un algorithme sans dérivé. Un algorithme sans dérivé fonctionnerait probablement bien pour des problèmes à grande échelle, mais je ne l'utiliserais pas pour des problèmes à petite échelle. Je n'ai trouvé aucun autre package qui ait inspiré une grande confiance dans leur génie logiciel. Par exemple, GALAHAD ne semble pas utiliser le contrôle de version ou tout test automatisé, à première vue. MINPACK ne semble pas faire ces choses non plus. Si vous avez de l'expérience avec MINPACK ou des recommandations concernant un meilleur logiciel, je suis à l'écoute.

Avec tout cela à l'esprit, revenons à la citation de mon commentaire:

Tout système d'équations équivaut à un problème d'optimisation, c'est pourquoi les méthodes basées sur Newton en optimisation ressemblent beaucoup aux méthodes basées sur Newton pour résoudre des systèmes d'équations non linéaires.

Un meilleur commentaire est probablement quelque chose à l'effet de:

$n$ $n$ $g(x) = 0$

Cette affirmation est valable même pour la résolution de systèmes d'équations sous contraintes. Je ne connais aucun algorithme considéré comme "résolveur d'équations" dans le cas où il y a des contraintes sur les variables. L'approche commune que je connais, peut-être jaunie par plusieurs semestres de cours d'optimisation et de recherche dans un laboratoire d'optimisation, est d'incorporer les contraintes sur le système d'équations dans une formulation d'optimisation. Si vous deviez essayer d'utiliser les contraintes dans un schéma de type Newton-Raphson pour la résolution d'équations, vous vous retrouveriez probablement avec un gradient projeté ou une méthode de région de confiance projetée, un peu comme les méthodes utilisées dans l'optimisation contrainte.

Geoff Oxberry
la source

J'ai de l'expérience avec MINPACK. C'est assez bon comme méthode locale. J'aime le fait que les critères d'arrêt fonctionnent bien sans peaufiner. Je sais que la chose avec les contraintes peut être ennuyeuse, d'autant plus que ce ne serait pas un changement majeur pour l'algorithme lui-même. Je connais même des implémentations LM qui offrent des limites sur les variables et les contraintes linéaires générales, mais ces implémentations ne sont pas beaucoup plus jeunes que MINPACK lui-même, et je n'ai pas pris la peine de les évaluer.

Thomas Klimpel

g (x) = 0

$g(x)=0$

‖ g (x) ‖^{2}

$\lVert g(x) \rVert^2$

g (x) = 0, x \in S, S \subset R^{n}, S \neq R^{n}

$g(x) = 0, x \in S, S \subset \mathbb{R}^{n}, S \neq \mathbb{R}^{n}$

Geoff Oxberry

@JedBrown: Une manière standard de résoudre ce problème est de résoudre . Il peut y avoir d'autres moyens, mais je n'en connais aucun. Je ne suggère pas que l'on rejette ; les minima avec des valeurs de fonction objective non nulles ne résolvent clairement pas le système d'équations à résoudre. Dans le cas non convexe, des méthodes d'optimisation globale sont nécessaires pour certifier l'existence ou l'inexistence de solutions. Je n'ai pas beaucoup d'expérience avec les inégalités variationnelles, donc je ne sais pas immédiatement où les VIs entrent en jeu ici, d'autant plus que n'est pas nécessairement un cône.

min_{x \in S} ‖ g (x) ‖^{2}

$\min_{x \in S} \|g(x)\|^2$

g (x) = 0

$g(x) = 0$

S

$S$

Geoff Oxberry

Donc , vous avez encore besoin d'être en mesure de définir précisément ce que vous entendez par une solution qui se trouve sur la frontière de . Les VIs, souvent écrits comme une formulation de complémentarité, font exactement cela. J'ai l'opinion contraire concernant les produits sans dérivés, surtout lorsque l'espace de conception est grand. Si l'objectif implique une résolution PDE coûteuse, je considère que c'est une exigence que nous ayons un adjoint afin que nous puissions utiliser des gradients pour explorer l'espace de conception. Un adjoint PDE ne coûte qu'un petit multiple d'une résolution directe indépendante de la dimension de l'espace. Cela impose des exigences supplémentaires sur la fluidité du modèle.

S

$S$

Jed Brown

Si un système non linéaire donné est la condition d'optimalité de premier ordre pour un problème d'optimisation, alors nous pouvons souvent produire un algorithme plus robuste en utilisant ces informations. Par exemple, considérons l'équation

f (x) = x^{2} - \exp (- 4 (x - 2)^{2}) [click for Wolfram Alpha]

$f(x) = x^2 - \exp\big(-4(x-2)^2 \big) \qquad \text{[click for Wolfram Alpha]}$

Parcelle d'objectif d'origine

Cela a clairement un minimum unique et nous nous attendons à ce que notre méthode d'optimisation le trouve quel que soit le point de départ. Mais si nous ne regardons que les conditions d'optimalité de premier ordre, nous recherchons une solution de [Wolfram Alpha] $x$ $\nabla f(x) = 0$

pente

qui a une solution unique, mais de nombreuses méthodes de rootfinding peuvent rester bloquées au minimum local.

Si nous reformulons un nouveau problème d'optimisation pour minimiser la norme du gradient au carré, nous recherchons un minimum global de [Wolfram Alpha] qui a plusieurs minima locaux. $x$ $\lVert\nabla f(x)\rVert^2$

entrez la description de l'image ici

Pour résumer, nous avons commencé avec un problème d'optimisation qui avait une solution unique que nous pouvions garantir qu'une méthode trouverait. Nous avons reformulé comme un problème de recherche de racine non linéaire qui avait une solution unique que nous pouvions identifier localement, mais une méthode de recherche de racine (comme Newton) pourrait stagner avant de l'atteindre. Nous avons ensuite reformulé le problème de recherche de racine comme un problème d'optimisation qui avait de multiples solutions locales (aucune mesure locale ne peut être utilisée pour identifier que nous ne sommes pas au minimum global).

En général, chaque fois que nous convertissons un problème de l'optimisation en rootfinding ou vice-versa, nous affaiblissons les méthodes disponibles et les garanties de convergence associées. La mécanique réelle des méthodes est souvent très similaire, il est donc possible de réutiliser beaucoup de code entre les solveurs non linéaires et l'optimisation.

Jed Brown
la source

Jed, ces liens WA ne vont pas tout à fait à ce que vous dites qu'ils font. Les parenthèses sont ignorées ou mal passées dans l'URL.

Bill Barth

Étrange, les liens fonctionnent pour moi. Cela pourrait-il dépendre du navigateur Web? Avez-vous des suggestions pour une autre façon de présenter cela?

Jed Brown

Pas certain. Couper et coller le lien reformaté d'un onglet à l'autre le fait visser WA pour le revisser tout seul!

Bill Barth

Quelqu'un d'autre a-t-il des problèmes avec les liens? J'ai essayé dans plusieurs navigateurs et cela fonctionne bien dans tous les cas.

Jed Brown

Ceci est une bonne réponse. Cependant, j'ai décidé d'accepter la réponse de Geoff Oxberry à la place, car une partie de ce que j'essayais de comprendre concerne les problèmes du "monde réel" liés à la question. Cela inclut que des gens comme moi utilisent et recommandent MINPACK, malgré leurs lacunes, et que d'autres personnes demandent des conseils sur la résolution de systèmes non linéaires "trivialement petits", mais ne parviennent pas à tester même un seul solveur sur une période de trois mois Plage de temps.

Thomas Klimpel