Verwenden sie in der Industrie semidefinite Programmierung?

10

Ich kann keine Erwähnung in Stellenangeboten sehen. Ich habe die erwähnte Ganzzahlprogrammierung, MIP, nichtlineare Programmierung mit gemischten Ganzzahlen, LP, dynamische Programmierung usw. gesehen, aber kein SDP. Ist es in der Akademie viel trendiger als in der Industrie?

Aufgrund meiner begrenzten Kontaktaufnahme mit Akademikern und Teilnehmern aus der Industrie an Stromversorgungssystemen besteht meiner Meinung nach eine gute Chance, dass SDP von unabhängigen Systembetreibern bei optimalen Stromflussproblemen angewendet wird, dies hängt jedoch davon ab, inwieweit sich die Eierköpfe skalieren lassen aktuelle Ansätze zur Bewältigung größerer Problemfälle.

GrayOnGray
quelle

Antworten:

8

Aufgrund meiner begrenzten Erfahrung in der Energiewirtschaft löst niemand SDPs in dieser Größenordnung. Ich habe nur begrenzte Kenntnisse darüber, was die New England ISO tut, und ich denke, sie sind mehr daran interessiert, Stochastizität in ihre bestehenden MILP-Modelle zu integrieren. Von Freunden, die in staatlichen Forschungslabors in den USA an Stromversorgungssystemen gearbeitet haben, denken sie auch über Stochastizität nach (stochastische Programmierung, Zufallsbeschränkungen, robuste Optimierung ...).

Aufgrund meiner Erfahrung im Bereich großer Technologieunternehmen lösen Menschen MILPs nach den kompliziertesten und normalerweise deterministischsten Modellen.

Aus chemisch-technischer Sicht scheinen sie an MINLP interessiert zu sein, insbesondere an nicht konvexen quadratisch beschränkten Optimierungen, die natürlich bei Mischungsproblemen auftreten. Es gibt auch Probleme mit PDE-Einschränkungen und all diese anderen lustigen Dinge, aber das liegt hauptsächlich an meinem Fachwissen.

Wenn ich spekulieren müsste, könnte SDP im Halbleiterdesign als Subroutine verwendet werden (z. B. für MAXCUT), aber angesichts des Mangels an Qualitätslösern gibt es (zumindest noch) keine große Nachfrage.

Ich würde sagen, im akademischen Bereich ist SDP als Beweiswerkzeug interessanter, dh "Schauen Sie, dieses Problem ist Polynomzeit!" wenn Sie herausfinden können, wie man als SDP kämpft. SDP-Löser sind so empfindlich (im Vergleich zu anderen konvexen Problemklassen), dass ich denke, die Leute sind nicht wirklich begeistert von der Idee, sie tatsächlich lösen zu müssen.

IainDunning
quelle
SDP ist nicht immer als Polynomzeit bekannt, denke ich. IIRC Sie benötigen zusätzliche Einschränkungen, um dies sicher zu wissen.
user541686
Sicher, aber wenn diese Einschränkungen nicht erfüllt wären, würden Sie es nicht als Beweis sehen, weil es nicht viel Sinn machen würde.
IainDunning
7

Semidefinite Programmierung und Kegelprogrammierung zweiter Ordnung wurden in der Praxis nicht so schnell übernommen, wie viele von uns gehofft hatten. Ich bin seit 20 Jahren daran beteiligt, und es war sehr enttäuschend, langsame Fortschritte zu sehen. Lassen Sie mich auf einige der Herausforderungen hinweisen:

  1. O(m2)mO(m2) Speicheranforderungen sind ein aktives Forschungsthema, aber im Bereich SDP haben sie sich einfach nicht als robust genug für die Verwendung in einem Allzwecklöser erwiesen.

  2. Die Anbieter von LP-Software haben es noch nicht für angebracht gehalten, SDP-Unterstützung in ihre Produkte aufzunehmen. Eine begrenzte Unterstützung für SOCP beginnt zu erscheinen.

  3. Das Wissen über semidefinite Programmierung hat sich langsam verbreitet. Das Lehrbuch von Boyd und Vandenberghe war in dieser Hinsicht äußerst hilfreich, aber es ist noch ein langer Weg, bis diese Technologie so bekannt wird wie ältere Optimierungstechniken.

  4. Modellierungssprachen und -systeme (wie GAMS, AMPL usw.) bieten noch keine gute Unterstützung für SOCP und SDP. Das CVX-Paket ist die interessanteste Arbeit in dieser Richtung, aber selbst es erfordert eine gewisse Raffinesse seitens des Benutzers.

SDP hat auf Forschungsebene in vielen Bereichen der Technik und Wissenschaft Anwendung gefunden. Es ist wahrscheinlich, dass diese letztendlich auch in der Industrie wichtig werden.

Brian Borchers
quelle
5
Nur um hinzuzufügen: Der einzige kommerzielle SDP-Löser afaik ist MOSEK und er ist sowieso ziemlich neu. Ich denke, dass Robustheit wichtiger ist als man denkt: In vielen Anwendungen können Sie mehr Zeit zuweisen, aber wenn ein Solver ausfällt, was sollte man dann tun?
AndreaCassioli
5

Die meiste Arbeit, die mir in Labors für Stromflussprobleme bekannt ist, befasst sich auch mit der stochastischen Optimierung, wobei der Schwerpunkt hauptsächlich auf MILPs liegt.

In der chemischen Technik interessieren sie sich für MINLPs, und das klassische Beispiel ist ein Mischungsproblem (insbesondere das prototypische Haverly-Pooling-Problem), sodass bilineare Begriffe häufig vorkommen. Abhängig von den verwendeten thermodynamischen Mischmodellen oder Reaktionsmodellen tauchen gelegentlich trilineare Terme auf. Es besteht auch ein begrenztes Interesse an ODE-beschränkter oder PDE-beschränkter Optimierung. Keine dieser Arbeiten verwendet SDPs.

Die meisten der PDE-beschränkten Optimierungsarbeiten, die ich gesehen habe (ich denke speziell an die Topologieoptimierung), verwenden keine SDPs. Die PDE-Einschränkungen könnten linear sein und theoretisch eine SDP-Formulierung zulassen, abhängig von den objektiven und verbleibenden Einschränkungen. In der Praxis sind technische Probleme in der Regel nichtlinear und führen zu nicht konvexen Problemen, die dann in lokalen Optima gelöst werden (möglicherweise auch mit Multistart). Manchmal werden Strafformulierungen verwendet, um bekannte suboptimale lokale Optima auszuschließen.

Ich konnte sehen, dass es vielleicht in der Steuerungstheorie verwendet wird. Die geringe Menge an Arbeit, die ich über "lineare Matrixungleichungen" gesehen habe, legt nahe, dass sie dort möglicherweise nützlich sein könnte, aber die Steuerungstheorie in der Industrie stützt sich eher auf bewährte Methoden als auf modernste mathematische Formulierungen, weshalb ich an SDPs zweifle wird für eine Weile verwendet, bis sie ihre Nützlichkeit beweisen können.

Es gibt einige SDP-Löser, die in Ordnung sind, und sie haben Probleme gelöst, die für die Wissenschaft ziemlich groß sind (zuletzt habe ich vor 3-4 Jahren überprüft, und sie haben Zehntausende bis Hunderttausende von Variablen gelöst), aber Leistungsflussszenarien Es gibt viel größere Probleme (zig Millionen bis Milliarden von Variablen), und ich glaube, die Löser sind noch nicht da. Ich denke, sie könnten dorthin gelangen - es gab in letzter Zeit eine ganze Reihe von Arbeiten zu matrixfreien Innenpunktmethoden, die darauf hindeuten, dass es möglich wäre, SDP-Löser mit diesen Techniken zu skalieren -, aber wahrscheinlich hat es noch niemand getan weil LPs, MILPs und konvexe NLPs viel häufiger auftreten und etablierte Technologien sind.

Geoff Oxberry
quelle
2
Ich habe jetzt sehr wenig darüber, aber das Lustige ist, dass es Anwendungen zur Steuerung der Theorie schon eine Weile gibt. Lineare Matrix-Ungleichungen in Systemen und Steuerung wurden 1994 veröffentlicht. Stephen Boyd macht den größten Teil seiner Forschung an der Schnittstelle von Optimierung und Steuerung, und das tut er auch seit mindestens 1996.
GrayOnGray
Das ist wahr. Das meiste, was ich über industrielle Kontrolle weiß, stammt aus einem kurzen Praktikum in der chemisch verarbeitenden Industrie, und dort war die modellprädiktive Kontrolle eine große neue Sache, und ich glaube, dass sie irgendwann zwischen Mitte der 80er und Anfang der 90er Jahre entwickelt wurde.
Geoff Oxberry