Il termine chiave è enumerazione vertice di un politopo P. L'idea dell'algoritmo descritto di seguito è considerare il politopo P * dual. Quindi i vertici di P corrispondono alle facce di P *. Le sfaccettature di P * sono calcolate in modo efficiente con Qhull e quindi rimane da trovare i vertici risolvendo i corrispondenti sottosistemi di equazioni lineari.
L'algoritmo è implementato nel set di strumenti con licenza BSD Analyze N-dimensional Polyhedra in terms of Vertices or (In)Equalities per Matlab, creato da Matt J, in particolare, il suo componente lcon2vert. Tuttavia, al fine di leggere l'algoritmo e riutilizzarlo in un'altra lingua, è più facile lavorare con il più vecchio e semplice file con2vert di Michael Kleder, sul quale si basa il progetto di Matt J.
Spiegherò cosa fa passo dopo passo. I singoli comandi Matlab (ad es., convhulln) sono documentati sul sito di MathWorks, con riferimenti ad algoritmi sottostanti.
L'ingresso è costituito da un insieme di disuguaglianze lineari della forma Ax<=b, dove A è una matrice e b è un vettore colonna.
Passo 1. tenta di individuare un punto interno della polytope
primo tentativo è c = A\b, che è la soluzione dei minimi quadrati del sistema lineare sovradeterminato Ax=b. Se A*c<b tiene componentewise, questo è un punto interno. in caso contrario, viene eseguita una minimizzazione multivariata con la funzione obiettivo al massimo 0 e tutti i numeri A*c-b. Se questo non riesce a trovare un punto in cui detiene A*c-b<0, il programma si chiude con "Impossibile trovare un punto interno".
Fase 2. Tradurre il politopo in modo che l'origine è il suo punto interno
Questo viene fatto b = b - A*c in Matlab. Poiché 0 è ora un punto interno, tutte le voci di b sono positive.
Passo 3. Normalizza modo che il lato destro è 1
Questo è solo la divisione del esima riga di A da b (i), svolto da D = A ./ repmat(b,[1 size(A,2)]); in Matlab. D'ora in poi, viene utilizzata solo la matrice D. Si noti che le righe di D sono i vertici del doppio politopo P * menzionati all'inizio.
Passo 4. Verificare che il politopo P è delimitata
Il politopo P è illimitato se i vertici della sua duplice P * giacciono sullo stesso lato di alcuni iperpiano passante per l'origine. Questo viene rilevato utilizzando la funzione incorporata convhulln che calcola il volume dello scafo convesso di determinati punti.L'autore controlla se l'aggiunta della riga zero alla matrice D aumenta il volume dello scafo convesso; se lo fa, il programma si chiude con "Vincoli non rilegati rilevati".
Fase 5. Calcolo dei vertici
Questo è il ciclo
for ix = 1:size(k,1)
F = D(k(ix,:),:);
G(ix,:)=F\ones(size(F,1),1);
end
Qui, la matrice k codifica le sfaccettature della doppia politopo P *, con ogni riga elenca i vertici del sfaccettatura. La matrice F è la sottomatrice di D costituita dai vertici di un aspetto di P *. Backslash invoca la linear solver, e trova un vertice di P.
Fase 6: Pulizia
Poiché la polytope stato tradotto nella Fase 2, questa definizione viene annullata con V = G + repmat(c',[size(G,1),1]);. Le restanti due linee tentano di eliminare i vertici ripetuti (non sempre con successo).
Vuoi trovare * tutti * i punti estremi o solo alcuni sottoinsiemi? – templatetypedef
Se ho capito bene la teoria, per definire il set convesso ho bisogno di tutti i punti estremi. Dipende dalla definizione esatta dei punti estremi. Sto pensando ad un punto estremo come un punto che non può essere ottenuto da p = p0 * t + p1 * (1-t) per 0 <= t <= 1 e p0! = P1, entrambi nella forma convessa. In altre parole, voglio il set minimo di punti che generano il set convesso. –
Vedo, potrebbero esserci casi degenerati .... Modifica: pensando due volte, non vedo chiaramente, non immediatamente. –