Progiciel pour une optimisation contrainte?

21

Je cherche à résoudre un problème d'optimisation contraint où je connais les limites de certaines variables (en particulier une contrainte encadrée).

\arg min_{u} f (u, x)

$\arg \min_u f(u,x)$

sujet à

c (u, x) = 0

$c(u,x) = 0$

a \leq d (u, x) \leq b

$a \le d(u,x) \le b$

où $u$ est un vecteur de variables de conception, $x$ est un vecteur de variables d'état et $c(u,x)$ est une contrainte d'égalité (généralement un PDE). Les contraintes inférieures et supérieures $a$ et $b$ peuvent être spatialement variables.

Quels packages peuvent gérer les systèmes de cette forme?

pde optimization nonlinear-programming Sean Farley
la source

1

La version modifiée ne ressemble pas à un problème d'optimisation contraint par une boîte. Un problème d'optimisation contraint par une boîte aurait contrainte . Est-ce que est censé être une fonction de ? est-il linéaire en ? Si ce n'est pas le cas, est-il deux fois différentiable? Est

a \leq u \leq b

$a \leq u \leq b$

u

$u$

x

$x$

c

$c$

u

$u$

f

$f$ convexe en

? Est-il deux fois différentiable en

? Enfin,

désigne l'ensemble des points en

auxquels la valeur minimale de

est atteinte. Voulez-vous dire

place?

u

$u$

u

$u$

\arg min_{u}

$\arg \min_{u}$

u

$u$

f

$f$

min_{u}

$\min_{u}$

Geoff Oxberry

est un cas particulier, mais cette forme plus générale est en fait courante dans la pratique. Vous pouvez toujours introduire des variables supplémentaires si votre méthode ne peut traiter les contraintes que directement sur

. Nous sommes généralement plus intéressés par la valeur

à laquelle un minimum est atteint que par la valeur minimale de

. Sean a ajouté la balise [pde], vous pouvez donc en tirer une certaine régularité. Il n'a pas précisé si le système était hyperbolique ou non, alors ne supposons pas. Ne supposons pas que

est convexe, car il ne l'est souvent pas.

d (u, x) = u

$d(u,x) = u$

u

$u$

u

$u$

f

$f$

f

$f$

Jed Brown

Il est assez courant que

implique

ou

régularisation, nous ne devons donc pas supposer deux dérivées.

f

$f$

L^{1}

$L^1$

W^{1, 1}

$W^{1,1}$

Jed Brown

@JedBrown: Cela a du sens; il était déroutant de voir "contrainte de boîte" mentionnée sans, bien, une contrainte de boîte explicite. Pour les types de problèmes dont vous parlez (problèmes de conception, problèmes de contrôle),

est certainement plus intéressant, mais les problèmes d'optimisation sont généralement indiqués en utilisant la notation

, et leurs ensembles de solutions sont décrits en utilisant la notation

.

u

$u$

m i n

$min$

\arg min

$\arg \min$

Geoff Oxberry

Il peut être utile de spécifier dans quel langage / environnement vous modélisez les PDE. Cela peut restreindre le choix des optimiseurs.

Dominique

18

J'ai décidé de modifier radicalement ma réponse en fonction de certains des commentaires.

Je n'ai pas utilisé TAO. D'après la documentation, il semble que le seul moyen pour TAO de gérer les problèmes d'optimisation contraints (à l'exception du cas spécial des seules contraintes de boîte) est de convertir le problème en une inégalité variationnelle en utilisant les conditions de Karush-Kuhn-Tucker (KKT) , qui sont nécessaires sous qualification de contrainte (le type que je vois habituellement est la condition du point de Slater ), et suffisants sous convexité de l'objectif et des contraintes (plus généralement, l'invexité de type 1). Si $f$ est non convexe, la formulation de l'inégalité variationnelle utilisant les conditions KKT N'EST PAS équivalente au problème d'optimisation d'origine, donc à proprement parler, si vous voulez un optimum global pour le problème d'optimisation, vous ne devez pas l'exprimer comme une inégalité variationnelle. Il serait difficile de trouver de toute façon un optimum global pour l'optimisation contrainte par PDE (voir ci-dessous), donc ignorer ce détail est peut-être bien. Étant donné ce que Wolfgang a dit, je serais sceptique quant à l'utilisation de TAO; Je suis déjà sceptique car il n'implémente pas de méthodes pour résoudre des programmes non linéaires (PNL) en tant que PNL, plutôt que des inégalités variationnelles.

Je ne suis pas un expert en optimisation contrainte PDE; mes collègues et associés travaillent sur des problèmes d'optimisation sous contrainte ODE. Je sais que pour les formulations intrusives, Larry Biegler (et d'autres) utilisera des méthodes de collocation pour discrétiser la PDE et en faire une très grande PNL éparse, puis il la résoudra en utilisant des méthodes de point intérieur. Pour vraiment résoudre le problème de l'optimalité globale, vous devez également générer des relaxations convexes, mais pour autant que je sache, cette approche n'est pas adoptée car les problèmes d'optimisation contraints par PDE conduisent à des PNL si importants qu'il serait difficile de les résoudre. optimalité globale. Je mentionne ces détails uniquement parce que la formulation du problème influence fortement le choix du package de solveur. Pour les formulations non intrusives, les résolutions PDE répétées produisent des informations de gradient pour les algorithmes d'optimisation.

Certaines personnes qui étudient les problèmes d'optimisation sous contrainte ODE utilisent une approche similaire pour discrétiser le problème à l'aide de la collocation et d'une méthode numérique, puis assouplir la PNL résultante pour produire une formulation convexe utilisée dans un algorithme d'optimisation globale. Une autre approche de l'optimisation contrainte par ODE consiste à détendre le problème, puis à discrétiser l'ODE, qui est l'approche adoptée dans mon laboratoire. Il pourrait être possible de détendre certaines classes de problèmes d'optimisation contraints par PDE, mais je ne connais aucun travail existant sur ce problème. (C'était un projet potentiel dans mon laboratoire à un moment donné.)

En fin de compte, ce qui importe n'est pas la différentiabilité de l'EDP d'origine, mais la différentiabilité de la discrétisation par rapport aux variables de décision.

Si le problème discrétisé est deux fois différentiable par rapport aux variables de décision, les packages suivants calculent une solution locale:

IPOPT est un solveur de point intérieur open source développé par Andreas Wächter chez IBM. C'est un code de très haute qualité. En tant que solveur de point intérieur, il est préférable pour les fonctions objectives avec de grandes matrices jacobiennes clairsemées et serait utile pour l'optimisation contrainte par PDE
SNOPT est un solveur de programmation quadratique séquentiel commercial qui est un autre code de haute qualité. Il est préférable pour les fonctions objectives avec de petites matrices jacobiennes denses, donc je ne m'attendrais pas à ce qu'il soit utile pour l'optimisation contrainte par PDE, mais vous pouvez l'essayer.
NLopt est un petit code open source écrit par Steven Johnson au MIT qui contient des implémentations de base d'un certain nombre d'algorithmes d'optimisation non linéaires. Tous les algorithmes devraient être adéquats pour résoudre des problèmes à contraintes liées.
fmincon dans Matlab implémente un certain nombre d'algorithmes (y compris le point intérieur et la programmation quadratique séquentielle) pour l'optimisation non linéaire
GAMS et AMPL sont tous deux des langages de modélisation commerciaux utilisés pour formuler des problèmes d'optimisation et contiennent des interfaces avec un grand nombre de solveurs de programmation non linéaire. Je sais que GAMS a une version d'essai qui peut être utilisée pour des problèmes plus petits, et des instances de problème peuvent également être soumises au serveur NEOS pour une solution.

Cependant, il est possible que la discrétisation ne soit différenciable qu'une seule fois en ce qui concerne les variables de décision, auquel cas, vous devez utiliser la descente la plus abrupte projetée ou une autre méthode d'optimisation de premier ordre lors du calcul d'une solution locale. Étant donné que de nombreuses études se concentrent sur les problèmes où des méthodes de second ordre peuvent être utilisées (et lorsque vous pouvez les utiliser, leurs propriétés de convergence supérieures en font un meilleur choix), je n'ai pas pu trouver de nombreuses implémentations de descente la plus abrupte qui n'étaient pas des solutions aux problèmes de devoirs. La bibliothèque scientifique GNU a une implémentation, mais ce n'est qu'à des fins de démonstration. Vous auriez probablement besoin de coder votre propre implémentation.

Si le problème n'est que continu en ce qui concerne les variables de décision, vous pouvez utiliser des méthodes directes pour le résoudre localement. Il existe une excellente enquête sur les méthodes directes par Kolda, Lewis et Torczon . La plus connue de ces méthodes est l' algorithme simplex de Nelder-Mead . Il n'est pas garanti de converger vers un minimum local dans plusieurs dimensions, mais il a quand même trouvé une utilisation pratique considérable.

Le choix du package dépend vraiment de la langue que vous souhaitez utiliser pour résoudre le problème, si la résolution du problème lié à la limite n'est qu'une partie d'un algorithme que vous souhaitez implémenter (ou si c'est la seule étape de votre algorithme, auquel cas les langages de modélisation devenir plus viable pour le code de production), le type et la taille du problème, et si vous avez besoin de parallélisme.

Geoff Oxberry
la source

4

Nous avons essayé TAO, mais nous l'avons trouvé peu utile pour les problèmes liés aux inégalités. Il est également essentiellement en mode maintenance depuis au moins 2003, sans aucune nouvelle fonctionnalité en dehors des mises à jour pour suivre les changements dans PETSc sur lesquels il est construit.

Wolfgang Bangerth
la source

3

OPT ++ est une autre alternative . Il prend en charge les contraintes linéaires et non linéaires avec un solveur de point intérieur non linéaire efficace, permet de contrôler la précision des fonctions (si une différenciation numérique est requise), de contrôler les tailles de pas, etc. J'optimise généralement de grandes fonctions implicites (par exemple FEM) où ces types de les contrôles peuvent être utiles.

Barron
la source

Pourriez-vous expliquer pourquoi OPT ++ est un bon package à utiliser? Avez-vous (ou vos collègues) une expérience avec cela?

Geoff Oxberry

Pour être clair, je n'ai aucune raison de dire que OPT ++ est supérieur à ceux que vous avez énumérés précédemment parce que je n'ai aucune expérience avec ceux-ci (bien que j'en ai mis en signet quelques-uns à vérifier). Mais j'ai de l'expérience avec OPT ++ et je l'ai trouvé adapté à mes besoins. Il prend en charge les contraintes linéaires et non linéaires avec un solveur de point intérieur non linéaire efficace, permet de contrôler la précision des fonctions (si une différenciation numérique est requise), de contrôler les tailles de pas, etc. J'optimise généralement les grandes fonctions implicites (par exemple FEM) où ces types de les contrôles peuvent être utiles.

Barron

2

@Barron: vous auriez dû mettre cela dans votre réponse pour commencer. :)

JM

2

Si le problème est formulé comme un problème de complémentarité, vous pouvez utiliser TAO (Toolkit for Advanced Optimization). Certaines des méthodes de TAO, telles que la méthode de l'espace réduit (une variante de la méthode de l'ensemble actif), sont actuellement disponibles dans le cadre de SNES dans PETSc ( SNESVI ).

Jungho Lee
la source

1

$[-\infty,+\infty]$

Je ne pense pas que MINUTE fonctionnera bien pour vos besoins, mais la transformation peut si vous êtes obligé d'écrire une partie ou la totalité du code vous-même.

dmckee
la source

Cette transformation a l'air désagréable; pas étonnant qu'il soit accompagné de quelques paragraphes.

Geoff Oxberry

1

Comme l'a souligné @Geoff Oxberry, plusieurs packages vous permettent de trouver une solution locale. Si vous voulez pouvoir comparer ces différents solveurs NLP pour un même problème, 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 NLP (par exemple Ipopt, NAG). 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/

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

BenC
la source

1

Doit souligner que d'autres réponses décrivent des solveurs , pas des cadres. Il est plus facile de trouver un framework ( pilote ) acceptable qu'un bon solveur,

Deer Hunter

@DeerHunter Lorsque vous recherchez un solveur pour résoudre un problème donné, il est souvent difficile de savoir a priori quel solveur calculera la meilleure solution et / ou sera le plus rapide. Vous parlez d'un «bon solveur», mais cela dépend vraiment de ce que vous résolvez: il n'y a pas un «meilleur solveur global». De plus, les API de solveur sont généralement assez différentes, donc l'utilisation d'un bon framework qui vous permet de passer facilement d'un solveur à un autre peut être très utile. La question portait sur les "progiciels pour l'optimisation contrainte", et les cadres entrent également dans cette catégorie.

BenC

1

Voici une liste partielle des packages d'optimisation contraints par PDE.

Dolfin Adjoint fait partie de FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance font partie de Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

Exemple PYOMO pour l'optimisation contrainte par PDE:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

Le manuel TAO donne des exemples de résolution de problèmes d'optimisation contraints par PDE:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

denfromufa
la source

1

Bienvenue sur SciComp.SE! Le simple fait de fournir un lien (aussi utile soit-il) n'est pas vraiment une bonne réponse; voir meta.stackexchange.com/questions/8231 . Pourriez-vous développer un peu cela (langage informatique, quel type de contraintes peut-on traiter, quelles méthodes sont implémentées, etc.)?

Christian Clason

Je suis d'accord avec @ChristianClason. Il y a eu un développement substantiel dans les solveurs pour les logiciels d'optimisation contraints par PDE; cependant, cette réponse ne fournit essentiellement aucune information sur les algorithmes que ces packages implémentent réellement.

Geoff Oxberry

0

Les packages APM MATLAB et APM Python peuvent résoudre à grande échelle (plus de 100 000 variables) des systèmes d'équations algébriques différentielles à nombres mixtes entiers. Le logiciel est disponible en tant que service Web pour une utilisation commerciale ou académique. Si vous résolvez un système PDE, vous pouvez discrétiser une fois pour le mettre sous forme DAE ou ODE pour le mettre dans le langage de modélisation APMonitor. Le langage de modélisation utilise les solveurs APOPT , BPOPT, IPOPT, SNOPT et MINOS.

John Hedengren
la source

1

Veuillez indiquer votre affiliation en tant que développeur APMonitor dans cette réponse et les futures qui mentionnent votre logiciel. Consultez la FAQ pour plus de détails sur notre politique de divulgation.

Geoff Oxberry

Geoff, merci pour l'astuce. J'ai commencé à travailler sur la plateforme APMonitor en 2004 en tant qu'étudiant diplômé à l'Université du Texas à Austin. Nous l'utilisons maintenant dans notre groupe de recherche de l'Université Brigham Young pour le contrôle et l'optimisation des processus ( apm.byu.edu/prism ) des applications biologiques, chimiques, aérospatiales et autres. Je le rend disponible gratuitement pour les utilisateurs commerciaux ou académiques.

John Hedengren

Progiciel pour une optimisation contrainte?

Réponses: