Mittelpunktlösungen für lineare Programme

Es gibt ein lineares Programm, für das ich nicht nur eine Lösung möchte, sondern eine Lösung, die auf der Vorderseite des Polytops so zentral wie möglich ist und den minimalen Wert annimmt.

A priori erwarten wir, dass die Minimierungsfläche aus verschiedenen Gründen hochdimensional sein sollte, einschließlich der Tatsache, dass die zu minimierende Zielfunktion das Maximum vieler der Einschränkungen ist:

Minimiere vorbehaltlich mit linear und für alle und . $\epsilon$ $f_i(\bar x) \leq \epsilon < 0$ $f_i$ $x_i > 0$ $i$ $\sum_i x_i = 1$

Wir würden natürlich niemals eine zentralitätsähnliche Eigenschaft des Simplex-Algorithmus erhalten. Weist einer der üblichen inneren Punktalgorithmen solche Eigenschaften auf? Garantieren Sie überhaupt, dass Scheitelpunkte oder Flächen mit niedrigeren Abmessungen nach Möglichkeit vermieden werden?

Tatsächlich bin ich wahrscheinlich mit einem einfachen quadratischen Programm zufrieden, das den Mittelpunkt des gesamten Polytops findet, da Zentralität mehr zählt als Minimalität, nur vage neugierig, ob andere lineare Programmieralgorithmen relevante Eigenschaften bieten.

Update: Ich habe das zugrunde liegende Problem auf ein einfaches Problem der eingeschränkten Minimierung reduziert, das mit Lagrange-Multiplikatoren lösbar ist, aber die obige Frage bleibt trotzdem interessant.

ds.algorithms linear-algebra linear-programming Jeff Burdges
quelle

nicht genau Ihre Frage, aber: Die Berechnung des Schwerpunkts ist # P-schwer; Ich bin nicht sicher, was die beste Annäherung ist, aber für einige Anwendungen reicht es aus, das Polytop in eine isotrope Position zu bringen und den Durchschnitt von polynomiell vielen einheitlichen Proben aus dem (transformierten) Polytop zu entnehmen. siehe diese Notiz, Lemma 15 zum Beispiel: cc.gatech.edu/~vempala/acg/notes.pdf

Sasho Nikolov

Ist das eher eine theoretische oder eher eine praktische Frage? Vielleicht wäre es möglich, alle Eckpunkte der optimalen Fläche zu erzeugen und dann eine geeignete konvexe Kombination davon zu verwenden.

anonym

Antworten:

Ich habe einige Beobachtungen, die für Kommentare zu lang sind. Hier ist eine Zusammenfassung.

Jeder Algorithmus zur exakten Lösung Ihres Problems kann verwendet werden, um lineare Programme genau zu lösen (dh "starke lineare Programmierung", die in Sariels Lösung verwendet wird und derzeit keinen Polynomzeitalgorithmus hat).
Das natürliche Follow-up ist, wenn Näherungslösungen (dh "schwache lineare Programmierung") eine Lösung liefern können. Während die Antwort ja ist, scheint es, dass die Stoppbedingung für dieses Verfahren Größen erfordert, die nach meinem besten Wissen nicht in Polynomzeit berechnet werden können. (Das heißt, der Algorithmus findet etwas Gutes, aber es ist schwierig, dies zu zertifizieren.) Mein Hauptvorschlag hier ist, eine aussagekräftige Definition einer " optimalen Lösung" für Ihr Problem zu erstellen. In diesem Fall ist dieser Ansatz nachvollziehbar. (Diese Strategie wirft effektiv winzige Flächen des Polyeders aus.) $\epsilon$

Während ich über Ihre derzeitige Aussage zu Ihrem Problem nachdachte, stieß ich im Allgemeinen immer wieder auf Effizienzüberlegungen. Aber das hat eine vernünftige Intuition: Die Objekte, die wir herumwerfen - Eckpunkte, Gesichter usw. - sind diskret und exponentiell reichlich vorhanden.

(1.) Angenommen, wir haben einen Algorithmus, der Ihr Problem genau löst. Beachten Sie, dass jeder belichtete Punkt einer Fläche, die den angegebenen Mittelpunkt enthält, eine exakte Lösung für das ursprüngliche lineare Programm darstellt. Gehen Sie also wie folgt vor. Fügen Sie eine neue lineare Einschränkung hinzu, die besagt, dass der ursprüngliche Zielwert gleich dem optimalen sein muss (den wir jetzt kennen), und legen Sie ein neues objektives Sprichwort fest, um die erste Koordinate der Lösung zu maximieren. Wiederholen Sie diesen Vorgang einmal für jede Dimension, fügen Sie jedes Mal eine Einschränkung hinzu und wählen Sie eine neue Koordinate aus, um sie zu maximieren. Dieser Prozess reduziert jedes Mal die Dimension der Lösung. Wenn der Prozess abgeschlossen ist, haben wir notwendigerweise eine 0-dimensionale affine Menge, was einen einzelnen Punkt bedeutet. Also mit $\mathcal O(d)$ Durch Iterationen Ihres Algorithmus zur Lösung des Mittelpunkts (und die Erhöhung der Problembeschreibung jedes Mal nur um einen Betragspolynom in ) wird eine starke lineare Programmierung gelöst. Dies zeigt, dass Sariels Lösung zwar eine starke lineare Programmierung erfordert, eine genaue Lösung Ihrer Frage dies jedoch nicht vermeiden kann. ( Bearbeiten : Beachten Sie, dass mein Beweis ein kompaktes Polyeder (ein Polytop) als Eingabe voraussetzt; andernfalls muss es etwas härter arbeiten, um Eckpunkte zu finden.) $d$

(2.) Hier ist ein iteratives Schema, bei dem in jeder Iteration ein ausgewachsener konvexer Löser verwendet wird, dessen Lösungen zu einem milden Begriff der Mittelpunktlösung konvergieren. Wählen Sie eine positive, aber abnehmende Folge von Strafparametern ; es ist vernünftig, diese geometrisch abfallen zu lassen, dh . Minimieren Sie nun für jedes ungefähr die konvexe Funktion $\{\lambda_i\}_{i=1}^\infty\downarrow 0$ $\lambda_i = 2^{-i}$ $i$

⟨ c, x ⟩ - - λ_{ich} \sum_{j = 1}^{m} \ln (⟨ {ein}_{j}, x ⟩ - - b),

$\langle c,x\rangle - \lambda_i\sum_{j=1}^m \ln(\langle a_j,x\rangle - b),$

wo Ihr ursprüngliches Ziel ist, und Bereiche über den ursprünglichen Beschränkungen, jetzt im Ziel über logarithmische Barrieren platziert (beachten Sie , das ist Standard). Wenn wir nun über die Minimierungsfläche (mit der größten Abmessung) Ihres Polyeders nachdenken, beachten Sie, dass für ein ausreichend kleines und eine Toleranz zu Ihrer konvexen opt Blackbox Ihr ungefähres Optimum nahe an dieser Fläche liegt, die Barrieren jedoch darauf drücken so weit wie möglich von den anderen Einschränkungen. Anders gesagt, als $\langle c,x\rangle$ $j$ $m$ $\lambda_i$ $\tau$ $\lambda_i$ Wenn das ursprüngliche lineare Ziel abnimmt, dominiert es schließlich einige heikle Barrieren, die Sie vom entsprechenden Gesicht fernhalten, wirkt sich jedoch nicht auf die Barrieren aus, die Sie von anderen Grenzen abhalten, insbesondere von denen des Zielgesichts.

In einer perfekten Welt würden wir uns hinsetzen und analytisch einen perfekten Wert oder zumindest eine Stoppzeit bestimmen , damit Sie nicht unendlich viele Probleme lösen müssen. Leider scheint dies schwierig. Eine Idee besteht beispielsweise darin, die kleinste Breite einer Fläche mit einer Abmessung größer als 0 zu bestimmen; Dies ist ein genau definiertes Minimierungsproblem mit positivem Optimum, da es endlich viele Flächen gibt (und die Breite relativ zu jeder berechnet wird). Damit können wir klein einstellen , dass der Einfluss der Barrieren in der Mitte jedes Gesichts winzig ist . Leider kann es exponentiell viele Gesichter geben, daher ist es Unsinn, diese Menge zu berechnen. $\lambda$ $\lambda$

Alle Stoppbedingungen, die ich mir vorstellen konnte, hatten diese Art von Rechenschwierigkeiten. (Darüber hinaus könnten viele wieder verwendet werden, um daraus einen starken linearen Programmierlöser zu machen.)

$\epsilon$ $\lambda$ $\tau$ $\epsilon$

(Einige abschließende Kommentare.) Es scheint, dass der Begriff "Mittelpunkt" entscheidend ist; Sashos Kommentar weist darauf hin, dass der Schwerpunkt (Schwerpunkt?) Ein äußerst schwieriges Problem ist, während es einfach ist, beispielsweise den größten eingeschriebenen Ball zu finden. Die logarithmischen Barrieren, die ich oben vorgeschlagen habe, stimmen im Allgemeinen nicht mit diesen beiden Mittelpunktsbegriffen überein. Auf der anderen Seite können Sie für die Barrieren und den Ball eine Untergrenze für den Abstand von Ihrem Schwerpunkt zur relativen Grenze des Gesichts ableiten. Vielleicht ist das für Sie nützlicher?

Schließlich glaube ich, dass Sie nach Ihrer Beschreibung gemeint haben, dass das "Zielgesicht" eine möglichst hohe Dimension hat? Dies ist gut definiert, es gibt jedoch auch Lösungsflächen für alle möglichen kleineren Abmessungen. Wie auch immer, sowohl Sariels Ansatz als auch der obige Barriereansatz funktionieren mit dem Gesicht der größten Dimension.

Matus
quelle

\sum_{i} f_{i} (x)^{2} + \sum_{j} x_{j}^{2}

$\sum_i f_i(x)^2 + \sum_j x_j^2$

\sum_{j} x_{j} = 1

$\sum_j x_j = 1$

x

$x$

ϵ

$\epsilon$

ϵ

$\epsilon$ minimiert, damit sich die Einschränkungen schneller entwickeln. Trotzdem danke! :)

Jeff Burdges

x

$x$

Ich verstehe den Punkt über "starke lineare Programmierung" nicht und habe diesen Ausdruck noch nie zuvor gehört. Es ist nicht bekannt, wie man eine LP in starker Polynomzeit löst. Das Lösen eines LP im Zeitpolynom in der Eingabebeschreibung (dh der schwachen Polynomzeit) ist natürlich bekannt. Wenn das OP möchte, dass ein Algorithmus in einer schwachen Polynomzeit ausgeführt wird, erledigt Sariels Lösung + ein mehrzeitiger Innenpunktalgorithmus die Aufgabe, nicht wahr?

Sasho Nikolov

τ

$\tau$

τ

$\tau$

@SashoNikolov, jetzt, wo ich darüber nachdenke, kann derselbe Optimalitätsbegriff (mit denselben Problemen) in Sariels Lösung eingearbeitet werden, indem beispielsweise Einschränkungen, die innerhalb einer winzigen Toleranz liegen, als tatsächlich eng behandelt und dieser Wert entsprechend angepasst werden. Ich werde meine Lösung heute Abend aktualisieren.

Matus

Finden Sie zuerst die optimale Lösung, fügen Sie dann die lineare Einschränkung hinzu, dass die Lösung einen Wert haben muss, der dem gewünschten Optimum entspricht, und wiederholen Sie Ihre LP als diejenige, die nach der größten Kugel innerhalb des realisierbaren Bereichs sucht. Löse diese modifizierte LP und du hast was du willst.

Warum das zweite Problem mit LP gelöst werden kann, ist ein normales Problem in der Computergeometrie ...

==============

$h \equiv cx = \alpha$ $\min c x$ $P$ $P \cap h$

$v$ $v$ $v$ $\alpha$

Um zu sommerisieren: (A) Löse LP, um den optimalen Wert zu ermitteln. (B) Berechnen Sie den kleinsten dimensionalen Unterraum, der die realisierbare Lösung enthält, mit dem optimalen Wert. (C) Schreiben Sie die Original-LP in diesem affinen Teilraum neu (dh lassen Sie alle irrelevanten Dimensionen fallen), fügen Sie eine Variable hinzu und verwandeln Sie sie in eine LP, um die größte Kugel in diesem Polytop zu finden.

Sariel Har-Peled
quelle

Was ist mit "größter Kugel" in einem Polyeder gemeint, das nicht die volle Dimension hat?

Kristoffer Arnsfelt Hansen

@KristofferArnsfeltHansen das Polyeder ist sicherlich eine konvexe Menge, die in einem affinen Unterraum irgendeiner Dimension liegt.

Sasho Nikolov

Damit dies funktioniert, müssen Sie eine Einschränkung angeben, die Sie auf die Gesichter beschränkt, die Sie im ersten Schritt gefunden haben. Sie müssten auch wissen, dass die Lösung auf diesem Gesicht konstant war (vermutlich würde eine komplementäre Schlaffheit dies offenbaren)

Suresh Venkat

Gibt es eine Möglichkeit, die Schritte nach der anfänglichen Optimierung in Polynomzeit auszuführen? Wie geschrieben, scheint es erforderlich zu sein, alle Eckpunkte in der Zielfläche zu berücksichtigen, von denen es exponentiell viele geben kann.

Matus

d

$d$

v

$v$