Moindres carrés non linéaires avec contraintes de boîte

10

Quelles sont les façons recommandées de faire des moindres carrés non linéaires, min , avec des contraintes de boîte ? Il me semble (les imbéciles se précipitent) que l'on pourrait rendre les contraintes de boîte quadratiques, et minimiser où est la "fonction tub" en forme de \ _ _ _ /, . Est-ce que cela fonctionne en théorie, fonctionne en pratique? (Il semble y avoir de nombreux articles théoriques sur NLS +, mais mon intérêt est pratique - des cas de test réels ou réalistes m'aideraient à choisir parmi les méthodes.) $\sum err_i(p)^2$ $lo_j <= p_j <= hi_j$

\sum_{i} e r r_{i} (p)^{2} + C * \sum_{j} t u b (p_{j}, l o_{j}, h i_{j})^{2}

$\sum_i err_i(p)^2 + C * \sum_j tub( p_j, lo_j, hi_j )^2$

t u b (x, l o, h i)

$tub( x, lo, hi )$

m a x (l o - x, 0, x - h i)

$max( lo - x, 0, x - hi )$

(Experts, veuillez ajouter des balises: "moindres carrés"?)

optimization constraints denis
la source

5

Le remplacement de contraintes strictes par des fonctions de pénalité est une technique courante en optimisation numérique. Il semble que ce que vous proposez soit une forme particulière de ce remplacement. Vous pouvez tout lire sur des techniques similaires, par exemple ici: stanford.edu/~boyd/cvxbook

David Ketcheson

Vous pouvez utiliser une paramétrisation appropriée de pour satisfaire les contraintes de la boîte (par exemple . En ce qui concerne les solveurs NLS, Levenberg-Marquardt est assez bon la plupart du temps , peut-être combiné avec un optimiseur stochastique global comme le recuit simulé. Certaines boîtes à outils commerciales semblent également proposer des méthodes de région de confiance basées sur des modèles de surface de réponse adaptative, ce qui me semble être une généralisation raisonnable de Levenberg-Marquardt.

p

$p$

p_{i} = min (max (l o_{j}, p_{j}^{'}), h i_{j})

$p_i=\min(\max(lo_j, p'_j),hi_j)$

Thomas Klimpel

11

L'ajout de termes de pénalité au carré pour se débarrasser des contraintes est une approche simple donnant une précision d'ordre 1 / facteur de pénalité uniquement. Par conséquent, il n'est pas recommandé pour une grande précision, sauf si vous laissez la pénalité aller à l'infini pendant le calcul. Mais un facteur de pénalité élevé rend la Hesse très mal conditionnée, ce qui limite la précision totale réalisable sans tenir compte explicitement des contraintes.

Notez que les contraintes liées sont beaucoup plus faciles à gérer que les contraintes générales, d'où elles ne sont pratiquement jamais converties en pénalités.

Le solveur L-BFGS-B (utilisé avec une histoire d'environ 5 dimensions) résout généralement les problèmes liés liés de manière très fiable et rapide dans les deux faibles dimensions élevées. Les exceptions sont la mauvaise convergence sur des problèmes qui peuvent devenir très plats loin des solutions, où il est facile de rester bloqué avec une méthode de descente.

Nous avons fait beaucoup d'expériences sur des fonctions très diverses dans de nombreuses dimensions différentes, avec de nombreux solveurs différents disponibles, car nous avions besoin d'un solveur contraint lié très robuste dans le cadre de notre logiciel d'optimisation globale. Le L-BFGS-B se démarque clairement comme une méthode à usage général, bien que, bien sûr, sur les problèmes de PME, les autres solveurs fonctionnent beaucoup mieux. Je recommanderais donc L-BFGS-B comme premier choix et j'essaierais des techniques alternatives au cas où L-BFGS-B traiterait mal votre classe particulière de problèmes.

Arnold Neumaier
la source

L-BFGS est disponible en IPOPT, j'ai révisé ma réponse.

Ali

5

J'utiliserais simplement le solveur polyvalent IPOPT . C'est le solveur le plus robuste parmi ceux que j'ai essayés.

Sauf si vous avez des exigences très particulières, il n'y a aucune raison pour que vous insistiez sur un solveur spécifique au problème qui ne fonctionne que pour NLS avec des contraintes de boîte.

Une modification des exigences (par exemple, l'ajout de contraintes non linéaires) entraînerait un casse-tête majeur avec un résolveur spécifique au problème. Vous n'aurez pas de tels problèmes si vous utilisez l'IPOPT à usage général.

MISE À JOUR: Vous pouvez essayer L-BFGS avec IPOPT , voir sous Quasi-Newton dans la documentation.

La procédure de solution peut devenir plus rapide au prix de gâcher la remarquable robustesse d'IPOPT. À mon avis , utilisez les dérivés exacts s'ils sont disponibles. Je commencerais à jouer avec des approximations (telles que L-BFGS) uniquement si j'avais des problèmes de performances éprouvés.

Ali
la source

Je ne sais pas si IPOPT fonctionne bien, mais votre suggestion me rappelle des déclarations similaires de défenseurs de la méthode du simplex de descente. Étant donné que les moindres carrés non linéaires sont une classe de problèmes courante, le rejet pur et simple de l'un des solveurs NLS existants me semble un peu suspect.

Thomas Klimpel

@ThomasKlimpel Eh bien, denis devrait nous donner plus de détails, alors nous pourrions l'aider à choisir le bon solveur. :) Ou il peut le vérifier par lui-même et trouver celui qui correspond le mieux à ses besoins. IPOPT semble être un bon solveur pour commencer.

Ali

@Ali, pouvez-vous indiquer des "cas de test réels ou réalistes" s'il vous plaît?

denis

@denis je pourrais mais je n'ai pas l'intention de le faire, cela vous éjecterait de la piste. La seule chose qui compte, c'est la façon dont IPOPT gère votre problème . Sauf si vous avez des exigences très particulières, cela devrait le résoudre correctement. IPOPT a des interfaces avec MATLAB, C ++, C, Fortran, R, AMPL, CUTEr. Choisissez une interface et testez ce qui se passe avec votre problème :) Tester un solveur spécifique au problème ne serait pas plus facile non plus.

Ali

@Thomas Klimpel, je suppose que je n'étais pas clair: je ne rejette pas, ne pose pas de questions sur les packages, mais demande des informations ou des cas de test: pourquoi cette méthode triviale ne fonctionnerait-elle pas bien?

denis

1

Le package CRAN R minpack.lm fournit une implémentation de Levenberg-Marquardt avec des contraintes de boîte.

En général, Levenberg-Marquardt est beaucoup mieux adapté que L-BFGS-B pour les problèmes de moindres carrés. Il convergera (beaucoup) mieux sur des problèmes difficiles. Il sera également beaucoup plus rapide que l'IPOPT à usage général, car il est adapté aux problèmes de moindres carrés non linéaires.

Le package R choisit une approche de projection très simple pour appliquer les contraintes (voir le code source ). Selon l'implémentation LM que vous utilisez, il peut être simple à inclure.

Maintenant, la suggestion dans les commentaires d'utiliser une transformation, (par exemple une transformation sinus comme dans scipy) est également une bonne alternative simple pour transformer votre algorithme LM non contraint en un algorithme contraint. Vous devrez également inclure la transformation dans le jacobien si le jacobien est analytique.

jherek
la source

0

(Des années plus tard) deux solveurs qui gèrent les contraintes de boîte:

Scipy less_squares a 3 méthodes, avec une documentation complète:
1. 'trf': Trust Region Reflective
2. 'dogbox'
3. 'lm': un wrapper hérité pour MINPACK, sans contraintes de boîte.
ceres

denis
la source

1

Celui de Scipy dit explicitement que l'algorithme de Levenberg-Marquardt ne peut pas gérer les contraintes de boîte.

tholy

Moindres carrés non linéaires avec contraintes de boîte

Réponses: