Bibliothèque C ++ pour une minimisation contrainte non linéaire

J'essaie actuellement de résoudre le problème de minimisation contraint non linéaire tel qu'implémenté dans la fonction matlab "fmincon". Mes attentes sont, minimiser (fun1, x0, uB, lB, fun2) où x0 est l'état initial, fun1 est une fonction qui doit être minimisée, uB sont des limites supérieures, lB sont des limites inférieures et fun2 est une fonction qui fournit des vecteurs d'égalités non linéaires / inégalités comme décrit dans http://www.mathworks.com/help/optim/ug/fmincon.htmlcomme fonction nonlcon. Ces vecteurs évoluent également au cours des itérations (ils dépendent non linéairement de x_n, n-ième itération du vecteur solution). Dans l'implémentation de matlab, ils sont sous la forme c (x) <= 0. C'est le dernier morceau de code qui doit être porté de matlab vers c ++ et j'ai beaucoup de mal à essayer de trouver la bibliothèque c ++ appropriée contenant cet algorithme. C'est pourquoi je cherche de l'aide ici et j'apprécierais beaucoup si vous pouviez apporter votre expertise.

Un bon exemple de ce que je veux faire est le premier sur cette page http://www.mathworks.com/help/optim/ug/constrained-nonlinear-optimization-examples.html#f10960?s_tid=doc_12b La seule différence est que je besoin de limites aussi ...

Merci d'avance.

Peter

c++ nonlinear-programming Peter Kottas
la source

Il est possible d'utiliser NLOPT ab-initio.mit.edu/wiki/index.php/NLopt_C-plus-plus_Reference mais je devrais calculer des différences finies en utilisant plusieurs appels pour évaluer la fonction "minimisée" à partir de la fonction objectif et j'étais gentil d'espérer que cela serait pris en charge par l'algorithme lui-même afin d'améliorer les performances. Ma fonction minimisée est vraiment chère à calculer. Juste pour clarifier, la fonction minimisée est la probabilité logarithmique du modèle estimé avec les données originales dans l'estimation du modèle de commutation de Markov en série chronologique.

Peter Kottas

Avez-vous regardé les réponses à cette question ? Si vos exigences ne sont pas suffisamment prises en compte, vous devez modifier votre question pour les signaler afin d'obtenir des recommandations utiles.

Christian Clason

Merci, il y a là quelques informations utiles. Actuellement, je suis aux coudes dans la bibliothèque NLOPT depuis que j'ai découvert que cela pouvait aussi convenir à mon problème. Je garderai ce sujet affiché et je fournirai une solution lorsque j'en proposerai un. Toute aide qui pourrait accélérer le processus est toujours appréciée. Mise en œuvre réelle par exemple, etc.

Peter Kottas

Plusieurs questions: 1. Votre problème est-il convexe? 2. L'objectif et les contraintes sont-ils différenciables? Si oui, combien de fois? Une fois que? Deux fois? 3. Pouvez-vous calculer ces dérivés facilement, s'ils existent? Serait-il facile de calculer des approximations aux différences finies si ces dérivés n'étaient pas facilement disponibles? 4. Combien de variables de décision avez-vous? (c.-à-d. sur combien de variables essayez-vous de minimiser?) Une estimation approximative suffirait. 5. Les évaluations des fonctions sont-elles coûteuses? Il serait utile d'avoir toutes ces informations afin de vous donner une meilleure réponse.

Geoff Oxberry

Salut! Tout d'abord, merci pour la réponse. 1. Difficile à dire mais très probablement non, car la fonction minimisée est la probabilité logarithmique entre l'estimation du modèle de commutation de Markov des séries temporelles dans l'application financière et de la nature de celle-ci, je suppose une sorte de sortie bruyante. 2. non 3. n'utilisant que des différences finies 4. le vecteur de résolution se compose de n variables où n dépend des paramètres désirés du modèle, en général de 12 à 30 disons 5. la probabilité log entre le modèle et les données originales est coûteuse, des inégalités non linéaires supplémentaires sont à la recherche pour calculer

Peter Kottas

Réponses:

Si votre fonction n'est pas différenciable, vous devez faire attention à la façon dont vous utilisez les différences finies. Si vous souhaitez utiliser des informations dérivées, votre meilleur pari est probablement une sorte de méthode semi-lisse de type Newton. Un ensemble de notes décrivant ces méthodes peut être trouvé ici .

Douze à trente variables sont probablement à l'extrémité supérieure de ce qui est faisable avec les méthodes de recherche de modèle (également appelées recherche directe). Un article de synthèse récent de Rios et Sahinidis dans Journal of Global Optimization sur les méthodes d'optimisation sans dérivé (telles que les méthodes de recherche de modèle) peut être trouvé ici , ainsi qu'une page Web complémentaire . Un article de revue moins récent sur ces méthodes par Kolda, Lewis et Torczon dans SIAM Review peut être trouvé ici . Ces méthodes fonctionnent assez bien avec des évaluations de fonctions coûteuses et ne nécessitent pas nécessairement de différenciation ou d'informations dérivées.

Beaucoup de ces méthodes nécessitent une sorte de convexité pour garantir la convergence vers l'optimum global, donc si vous deviez résoudre votre problème de manière rigoureuse, vous devrez peut-être coupler ces méthodes ci-dessus avec une stratégie de branchement et de liaison. Cependant, si vous ne vous souciez pas de la rigueur, une approche comme MATLAB fminconpourrait fonctionner assez bien (il n'y a plus de garantie). Des différences finies vous donneront très probablement un membre de la sous-différence de votre fonction non différenciable, ce qui pourrait suffire à votre instance de problème et à des données d'entrée particulières pour retourner un résultat suffisamment précis pour vos besoins. Dans ce cas, vous devriez probablement consulter les bibliothèques mentionnées dans les réponses à la question liée à Christian dans son commentaire.

Geoff Oxberry
la source

Si vous n'avez besoin que d'une bibliothèque C ++ pour résoudre les problèmes d'optimisation non linéaire, vous pouvez utiliser RobOptim . Même si RobOptim a été initialement développé avec des problèmes d'optimisation robotique à l'esprit, il convient à tous les problèmes d'optimisation non linéaire. Il fournit une interface C ++ simple avec des plugins pour plusieurs solveurs non linéaires ( Ipopt , NAG , etc.). L'utilisation de ce type d'encapsuleurs facilite l'utilisation d'un autre solveur NLP. Si vous ne pouvez pas fournir de dégradés, le calcul des différences finies peut être effectué automatiquement.

C'est open source, vous pouvez donc consulter le code source sur GitHub: https://github.com/roboptim/

L'analyse effectuée par @Geoff Oxberry est essentielle pour le choix du solveur non linéaire qui sera appelé par RobOptim. Notez que lorsque vous traitez ce type de solveurs, le réglage des paramètres peut avoir un impact énorme sur les performances, et vous pouvez toujours rester coincé dans les minimas locaux (cela dépend vraiment du type de problème que vous traitez).

Remarque: je suis l'un des développeurs de ce projet.

BenC
la source