Mi chiedevo se c'è un modo carino (preferibilmente utilizzando JuMP) per ottenere tutte le soluzioni ottimali di un programma lineare (nel caso ci siano più soluzioni ottimali).Programmazione lineare: trovare tutti i vertici ottimali
Un esempio
minimizzare la distanza statistica (Kolmogorov distanza) tra due distribuzioni di probabilità.
min sum_{i=1}^{4} |P[i] - Q[i]| over free variable Q
P = [0.25,0.25,0.25,0.25]
sum_i P[i] = 1
Q[1] + Q[4] = 1
sum_i Q[i] = 1 -> Q[2],Q[3] = 0
Nota possiamo frase l'ottimizzazione come un programma lineare, l'obiettivo diventa
min S >= sum_i S[i]
S[i] >= P[i]-Q[i]
S[i] >= Q[i]-P[i]
Non esiste una soluzione unica per questo problema, invece il sottospazio di soluzione ottimale è attraversato da
Q1 = [0.75,0,0,0.25]
Q2 = [0.25,0,0,0.75]
Entrambi hanno una distanza minima di 0,5, qualsiasi combinazione convessa di queste due soluzioni è ottimale.
Mi chiedevo se c'è un buon modo per trovare tutti questi punti estremi ottimali (punti che abbracciano il sottospazio ottimale)?
Perché sono interessato a questo; i punti che danno il massimo Bhattacharyya coefficient (funzione concava), si trovano da qualche parte nel mezzo del sottospazio ottimale della distanza statica.
Finora ho cercato di trovare le coppie P, Q ottimali (riferendosi all'esempio che ho dato) facendo l'algoritmo a favore di minimizzare la distanza tra P [i], Q [i], aggiungendo un peso di 1.001 a questo termine nella somma. Sembra funzionare in qualche modo, anche se non lo so per certo.
Probabilmente è possibile risolvere l'LP e quindi provare a massimizzare il coefficiente di Bhattacharyya dato il valore della funzione obiettivo del LP che hai risolto. Anche se disponi di tutte le soluzioni ottimali (vertici), non è chiaro come troverai i volti ottimali del poliedro sottostante e come eseguirai la ricerca (su queste facce) in modo da massimizzare il coefficiente di Bhattacharyya. Se la soluzione ottimale si trova "nel mezzo", che può accadere perché la funzione è concava, i vertici ottimali stessi sono di scarsa utilità. – Ioannis
Ho provato a modificare direttamente la domanda, ma apparentemente non posso; nel tuo programma lineare, il valore assoluto deve essere scomposto per ogni termine della funzione obiettivo, cioè 'min sum A [i]' soggetto a 'A [i]> = P [i] - Q [i]' e ' A [i]> = Q [i] - P [i] 'per ogni' 1 <= i <= 4' –
Ho corretto l'errore, grazie ;-) – balletpiraat