Der Schlüsselbegriff ist Vertex-Enumeration eines Polytop P. Die Idee des unten beschriebenen Algorithmus ist die dual Polytop P * zu betrachten. Dann entsprechen die Ecken von P den Facetten von P *. Die Facetten von P * werden effizient mit Qhull berechnet, und dann bleibt es, die Scheitelpunkte zu finden, indem die entsprechenden Untersysteme linearer Gleichungen gelöst werden.
Der Algorithmus wird durch Matt J in BSD-lizenzierten Toolset Analyze N-dimensional Polyhedra in terms of Vertices or (In)Equalities für Matlab, Autor implementiert, insbesondere seine Komponente lcon2vert. Um jedoch den Algorithmus zu lesen und eine andere Sprache wieder zu implementieren, ist es einfacher, mit der älteren und einfacheren Datei von Michael Kleder zu arbeiten, auf der Matt Js Projekt aufbaut.
Ich werde erklären, was es Schritt für Schritt macht. Die einzelnen Matlab-Befehle (z.B. convhulln) sind auf der MathWorks-Site mit Verweisen auf zugrundeliegende Algorithmen dokumentiert.
Die Eingabe besteht aus einem Satz von linearen Ungleichungen der Form Ax<=b, wobei A eine Matrix ist und b ein Spaltenvektor ist.
Schritt 1. Attempt einen inneren Punkt des Polytops
erster Versuch zu lokalisieren ist c = A\b, die die kleinsten Quadrate Lösung des überbestimmten linearen Gleichungssystemes Ax=b ist. Wenn A*c<b komponentenweise gilt, ist dies ein innerer Punkt. andernfalls wird eine multivariable Minimierung versucht, wobei die Zielfunktion das Maximum von 0 und alle Zahlen A*c-b ist. Wenn dies keinen Punkt findet, an dem A*c-b<0 gilt, wird das Programm mit der Meldung "Es kann keinen inneren Punkt finden" beendet.
Schritt 2. übersetzen Sie die Polytop so dass der Ursprung sein innerer Punkt ist
Dies wird durch b = b - A*c in Matlab durchgeführt wird. Da 0 jetzt ein innerer Punkt ist, sind alle Einträge von b positiv.
Schritt 3. normalisieren, so dass die rechte Seite 1
Diese nur die Teilung der i-ten Reihe von A sind durch b (i), durch D = A ./ repmat(b,[1 size(A,2)]); in Matlab getan. Von nun an wird nur die Matrix D verwendet. Beachten Sie, dass die Zeilen von D die Eckpunkte des zu Beginn erwähnten dualen Polytops P * sind.
Schritt 4. Überprüfen, ob die Polytop P
Das Polytop P unbeschränkten begrenzt wird, wenn die Scheitelpunkte ihrer doppelten P * auf der gleichen Seite einiger Hyperebene durch den Ursprung. Dies wird mithilfe der integrierten Funktion erkannt, die das Volumen der konvexen Hülle bestimmter Punkte berechnet.Der Autor überprüft, ob das Anhängen der Nullzeile an die Matrix D das Volumen der konvexen Hülle erhöht; Wenn dies der Fall ist, wird das Programm mit "Non-Bounding Constraints Detected" beendet.
Schritt 5. Berechnung von Vertices
Dies ist die Schleife
for ix = 1:size(k,1)
F = D(k(ix,:),:);
G(ix,:)=F\ones(size(F,1),1);
end
Hier kodiert die Matrix K, die Facetten des dualen Polytops P *, wobei jede Reihe die Scheitelpunkte der Auflistung Facette. Die Matrix F ist die Submatrix von D, bestehend aus den Eckpunkten einer Facette von P *. Backslash ruft die linear solver und findet eine Ecke von P.
Schritt 6: Clean-up
Da das Polytop in Schritt 2 übersetzt wurde, wird diese Übersetzung mit V = G + repmat(c',[size(G,1),1]); rückgängig gemacht. Die verbleibenden zwei Zeilen versuchen, wiederholte Scheitelpunkte zu eliminieren (nicht immer erfolgreich).
Möchten Sie * alle * die extremen Punkte finden, oder nur eine Teilmenge von ihnen? – templatetypedef
Wenn ich die Theorie richtig verstanden habe, brauche ich zur Definition der konvexen Menge alle Extrempunkte. Hängt von der genauen Definition von Extrempunkten ab. Ich denke an einen Extrempunkt als einen Punkt, der nicht durch p = p0 * t + p1 * (1-t) für 0 <= t <= 1 und p0! = P1, beide innerhalb der konvexen Form, erhalten werden kann. Mit anderen Worten, ich möchte die minimale Menge von Punkten, die die konvexe Menge erzeugen. –
Ich sehe, es könnte degenerierte Fälle sein .... Edit: Nachdenken, ich sehe nicht klar, nicht sofort. –