Utilisent-ils une programmation semi-définie dans l'industrie?

10

Je ne vois aucune mention de cela dans les listes d'emplois. J'ai vu mentionné la programmation entière, MIP, la programmation non linéaire à nombres mixtes, LP, la programmation dynamique, etc., mais pas de SDP. Est-ce beaucoup plus à la mode dans l'académie que dans l'industrie?

D'après mon exposition limitée aux universitaires et aux participants de l'industrie dans les systèmes d'alimentation électrique, je pense qu'il y a de fortes chances que le SDP soit appliqué dans les problèmes de flux de puissance optimale par des opérateurs de système indépendants, mais cela dépend de la mesure dans laquelle les têtes d'oeufs peuvent évoluer les approches actuelles pour faire face à des problèmes plus importants.

GrayOnGray
la source

Réponses:

8

D'après ma propre expérience limitée dans l'industrie de l'énergie, personne ne résout les SDP à ce genre d'échelle. J'ai une connaissance limitée de ce que fait l'ISO de la Nouvelle-Angleterre, et je pense qu'ils sont plus intéressés à intégrer la stochasticité dans leurs modèles MILP existants. Des amis qui ont travaillé sur les réseaux électriques dans des laboratoires de recherche gouvernementaux aux USA, ils pensent également à la stochasticité (programmation stochastique, contraintes de chance, optimisation robuste ...).

D'après mon expérience dans le secteur des grandes entreprises technologiques, les gens résolvent les MILP dans les modèles les plus compliqués et généralement déterministes.

Je crois comprendre que du côté de l'ingénierie chimique, ils semblent intéressés par le MINLP, en particulier l'optimisation non convexe à contraintes quadratiques, qui se pose naturellement dans les problèmes de mélange. Il y a aussi des problèmes contraints PDE et toutes ces autres choses amusantes, mais c'est principalement hors de mon expertise.

Si je devais spéculer, le SDP pourrait être utilisé dans la conception de semi-conducteurs comme sous-programme (par exemple pour MAXCUT), mais étant donné le manque de solveurs de qualité, je suppose qu'il n'y a pas une énorme demande (pour le moment du moins).

Je dirais que dans le monde universitaire, SDP est plus intéressant comme outil de preuve, c'est-à-dire "regardez, ce problème est le temps polynomial!" si vous pouvez comprendre comment se débattre en tant que SDP. Les solveurs SDP sont si délicats (par rapport aux autres classes de problèmes convexes) que je pense que les gens ne sont pas vraiment excités à l'idée de devoir les résoudre.

IainDunning
la source
SDP n'est pas connu pour être toujours polynomial, je pense. IIRC vous avez besoin de contraintes supplémentaires pour le savoir avec certitude.
user541686
Bien sûr, mais si ces contraintes n'étaient pas respectées, vous ne le verriez pas dans une preuve, car cela ne servirait à rien.
IainDunning
7

La programmation semi-définie et la programmation des cônes de second ordre n'ont pas été adoptées aussi rapidement dans la pratique que beaucoup d'entre nous l'espéraient. Je m'implique dans ce dossier depuis 20 ans et il est très décevant de voir des progrès lents. Permettez-moi de souligner certains des défis:

  1. O(m2)mO(m2) les besoins de stockage sont un sujet de recherche actif, mais dans le domaine du SDP, ils ne se sont tout simplement pas révélés suffisamment robustes pour être utilisés dans un solveur à usage général.

  2. Les fournisseurs de logiciels LP n'ont pas encore jugé bon d'inclure la prise en charge de SDP dans leurs produits. Un support limité pour SOCP commence à apparaître.

  3. Les connaissances sur la programmation semi-définie se sont lentement propagées. Le manuel de Boyd et Vandenberghe a été extrêmement utile à cet égard, mais il reste un long chemin à parcourir avant que cette technologie soit aussi largement connue que les anciennes techniques d'optimisation.

  4. Les langages et systèmes de modélisation (tels que GAMS, AMPL, etc.) ne fournissent pas encore un bon support pour SOCP et SDP. Le package CVX est le travail le plus intéressant dans ce sens, mais même il nécessite une certaine sophistication de la part de l'utilisateur.

SDP a trouvé des applications au niveau de la recherche dans de nombreux domaines de l'ingénierie et des sciences. Il semble probable que ceux-ci finiront également par devenir importants dans l'industrie.

Brian Borchers
la source
5
Juste pour ajouter: le seul solveur SDP commercial afaik est MOSEK et il est de toute façon assez récent. Je pense que la robustesse est plus importante qu'on ne le pense: dans de nombreuses applications, vous pouvez allouer plus de temps, mais si un solveur échoue, que faire?
AndreaCassioli
5

La plupart du travail que je connais dans les laboratoires pour les problèmes de flux de puissance concerne également l'optimisation stochastique, en se concentrant principalement sur les MILP.

En génie chimique, ils s'intéressent aux MINLPs, et l'exemple classique est un problème de mélange (en particulier, le problème de mise en commun prototypique de Haverly), donc les termes bilinéaires reviennent souvent. Des termes trilinéaires apparaissent parfois, selon les modèles de mélange thermodynamique ou les modèles de réaction utilisés. Il y a aussi un intérêt limité pour l'optimisation contrainte ODE ou contrainte PDE; aucun de ces travaux n'utilise de SDP.

La plupart des travaux d'optimisation contraints par PDE que j'ai vus (je pense spécifiquement à l'optimisation de la topologie) n'utilisent pas de SDP. Les contraintes PDE pourraient être linéaires et, en théorie, pourraient admettre une formulation SDP en fonction de l'objectif et des contraintes restantes. Dans la pratique, les problèmes d'ingénierie ont tendance à être non linéaires et à générer des problèmes non convexes qui sont ensuite résolus en optima locaux (éventuellement en utilisant également plusieurs démarrages). Parfois, des formulations de pénalités sont utilisées pour exclure les optima locaux sous-optimaux connus.

Je pouvais voir qu'il était peut-être utilisé dans la théorie du contrôle. Le peu de travail que j'ai vu sur les «inégalités matricielles linéaires» suggère qu'il pourrait être utile là-bas, mais la théorie du contrôle dans l'industrie a tendance à s'appuyer sur des méthodes éprouvées plutôt que sur des formulations mathématiques de pointe, donc je doute des SDP seront utilisés pendant un certain temps jusqu'à ce qu'ils puissent prouver leur utilité.

Il y a quelques solveurs SDP qui conviennent, et ils ont résolu des problèmes assez importants pour le monde universitaire (la dernière fois que j'ai vérifié, c'était il y a 3-4 ans, et ils résolvaient des dizaines à des centaines de milliers de variables), mais des scénarios de flux de puissance impliquent des problèmes beaucoup plus importants (des dizaines de millions à des milliards de variables), et je ne pense pas que les solveurs soient encore là. Je pense qu'ils pourraient y arriver - il y a eu pas mal de travaux récents sur les méthodes de point intérieur sans matrice qui suggèrent qu'il serait possible d'étendre les solveurs SDP en utilisant ces techniques - mais personne ne l'a encore fait, probablement parce que les LP, les MILP et les NLP convexes apparaissent beaucoup plus fréquemment et sont des technologies établies.

Geoff Oxberry
la source
2
J'en ai maintenant très peu à ce sujet, mais le plus drôle, c'est que les applications pour contrôler la théorie existent depuis un certain temps. Linear Matrix Inequality in Systems and Control a été publié en 1994. Stephen Boyd fait la plupart de ses recherches à l'intersection de l'optimisation et du contrôle, et il le fait également depuis au moins 1996.
GrayOnGray
C'est vrai. La plupart de mes connaissances sur le contrôle industriel proviennent d'un court stage dans l'industrie de la transformation chimique, et là, le contrôle prédictif des modèles était une grande nouveauté, et je pense qu'il a été développé entre le milieu des années 80 et le début des années 90.
Geoff Oxberry du