Maximaler Wert einer konvexen Kombination über einer konvexen Hülle realer Variablen

8

Ich habe das folgende lineare Programm: wobei x \ in \ mathbb {R} ^ n , \ mathbf {1} ^ T x die Summe der Einträge von x bezeichnet und a bekannt ist und hat deutlich streng positive Einträge.

MaximizeaTxSubject toxminxxmax1Tx=1
xRn1Txxa

Ich suche nach einer schnellen Möglichkeit, das oben genannte Problem zu lösen, ohne einen LP-Solver zu verwenden. Gibt es ein schnelles Verfahren? (neben Simplex).

Vielen Dank!

Mohammad Fawaz
quelle

Antworten:

5

Die optimale Lösung lautet wie folgt: Setzen Sie alle Variablen auf das Minimum. Setzen Sie dann vom größten bis zum kleinsten iterativ das entsprechende so groß wie möglich, bis Sie treffen . Wenn oder ist, ist das Problem nicht realisierbar. Ich glaube, dass dies die gleiche Lösung ist, die Geoffrey Irvings Algorithmus ausgibt.aixiixi=1ixi,min>1ixi,max<1

Der Grund dafür ist, dass Sie Ihr Problem über in die LP-Relaxation des 0-1-Rucksackproblems umwandeln können

yi=xixi,minxi,maxxi,min.

Im variablen Raum wird das Problem zu y

MaximizeiciyiSubject to0yi1, for each iibiyi=d,

wobei , und . Wenn das ursprüngliche Problem durchführbar ist, ist . Die und sind nicht negativ, also haben wir die LP-Relaxation von 0-1 Rucksack. (Der Ausdruck erscheint technisch auch im Ziel, aber da es sich um eine Konstante handelt, können wir ihn fallen lassen.)ci=ai(xi,maxxi,min)bi=(xi,maxxi,min)d=1ixi,mind0cibiiaixi,min

Unter der Annahme , die Variablen durch das Verhältnis sortiert vom größten zum kleinsten, die bekannten optimalen Lösung ist die gierige one: Set für so groß a wie möglich , setze und setze . Wenn Sie diese Lösung wieder in den variablen Problemraum umwandeln, erhalten Sie die gerade beschriebene Lösung.cibi=aiy1=y2==yk=1kyk+1=di=1kbiyk+2==yn=0x

Außerdem hat der 0-1-Rucksack eher eine Einschränkung als eine -Einschränkung. Wenn Sie alle Gegenstände im Rucksack mit noch freiem Platz unterbringen können, ist das ursprüngliche Problem mit der Variablen nicht realisierbar, da .=xixi,max<1

Mike Spivey
quelle
7

Der Greedy-Algorithmus funktioniert: Beginnen Sie mit einer Lösung, die Ihre Einschränkungen erfüllt, und erhöhen Sie dann iterativ das mit dem größten , das nicht bei und verkleinern Sie das mit dem kleinsten , das nicht bei so weit wie möglich. Stoppen Sie, wenn keine weiteren Paarbewegungen möglich sind. Dies dauert , um und Zeit für den Rest zu sortieren .xiaixmaxxjajxminO(nlogn)aO(n)

Wenn der Algorithmus abgeschlossen ist, wird eine Menge von bei (diejenigen mit großem ), eine Menge von bei (diejenigen mit kleinem ) und bei stecken die meisten mit und . Eine differenzielle Änderung von einer solchen Position zu kann das Ziel nicht erhöhen, da Gewinne aufgrund der Erhöhung von oder durch Verluste aufgrund der Verringerung von oder mehr als ausgeglichen würden .xixmaxaixjxminajxkxmin<xk<xmaxai>ak>ajxxjxkxixk

Geoffrey Irving
quelle
Bitte machen Sie dies genauer. Ihre aktuelle Methode ändert nur zwei Komponenten von , wenn sie wörtlich genommen wird, und ist daher nicht korrekt. Es wäre auch schön zu argumentieren, warum das Endergebnis optimal ist. x
Arnold Neumaier
Vielen Dank für Ihre Antwort. Der Ansatz scheint interessant zu sein, aber ich stimme der Bitte von @ArnoldNeumaier zu, ein Argument zu liefern.
Mohammad Fawaz
Es ändert zwei Komponenten pro Iteration, daher bin ich mir nicht sicher, was Sie unter nicht korrekt verstehen, wenn es wörtlich genommen wird. Ich werde eine kurze Erklärung hinzufügen.
Geoffrey Irving
Nun, das mit dem größten ist bei jeder Iteration usw. gleich. Sie versuchen also, dieselben zwei Komponenten wiederholt zu ändern. Ihre neue Version ist irritierend, da die in den beiden Absätzen anscheinend unterschiedliche Bedeutungen haben. xiiij
Arnold Neumaier
Ah, Sie haben bei jeder Iteration ungefähr das gleiche Recht. Sollte jetzt behoben sein.
Geoffrey Irving