linprog(method=’interior-point’)

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)

Lineare Programmierung: Minimieren einer linearen Zielfunktion unter linearen Gleichheits- und Ungleichheitsnebenbedingungen mit der Interior-Point-Methode von [4].

Veraltet seit Version 1.9.0: method=’interior-point’ wird in SciPy 1.11.0 entfernt. Sie wird durch method=’highs’ ersetzt, da letztere schneller und robuster ist.

Lineare Programmierung löst Probleme der folgenden Form

\[\begin{split}\min_x \ & c^T x \\ \mbox{so dass} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

wobei \(x\) ein Vektor von Entscheidungsvariablen ist; \(c\), \(b_{ub}\), \(b_{eq}\), \(l\) und \(u\) Vektoren sind; und \(A_{ub}\) und \(A_{eq}\) Matrizen sind.

Alternativ, das heißt

minimieren

c @ x

so dass

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

Beachten Sie, dass standardmäßig lb = 0 und ub = None gilt, es sei denn, dies wird mit bounds angegeben.

Parameter:

c1-D-Array

Die Koeffizienten der linearen Zielfunktion, die minimiert werden soll.

A_ub2-D-Array, optional

Die Matrix der Ungleichheitsbedingungen. Jede Zeile von A_ub gibt die Koeffizienten einer linearen Ungleichheitsbedingung für x an.

b_ub1-D-Array, optional

Der Vektor der Ungleichheitsbedingungen. Jedes Element stellt eine Obergrenze für den entsprechenden Wert von A_ub @ x dar.

A_eq2-D-Array, optional

Die Matrix der Gleichheitsbedingungen. Jede Zeile von A_eq gibt die Koeffizienten einer linearen Gleichheitsbedingung für x an.

b_eq1-D-Array, optional

Der Vektor der Gleichheitsbedingungen. Jedes Element von A_eq @ x muss gleich dem entsprechenden Element von b_eq sein.

boundsSequenz, optional

Eine Sequenz von (min, max) -Paaren für jedes Element in x, die die minimale und maximale Wert dieser Entscheidungsvariablen definieren. Verwenden Sie None, um anzuzeigen, dass keine Grenze existiert. Standardmäßig sind die Grenzen (0, None) (alle Entscheidungsvariablen sind nicht-negativ). Wenn ein einzelnes Tupel (min, max) bereitgestellt wird, dienen min und max als Grenzen für alle Entscheidungsvariablen.

methodstr

Dies ist die methodenspezifische Dokumentation für ‘interior-point’. ‘highs’, ‘highs-ds’, ‘highs-ipm’, ‘revised simplex’ und ‘simplex’ (Legacy) sind ebenfalls verfügbar.

callbackcallable, optional

Callback-Funktion, die einmal pro Iteration ausgeführt werden soll.

Rückgabe:

resOptimizeResult

Ein scipy.optimize.OptimizeResult mit den Feldern

x1-D-Array

Die Werte der Entscheidungsvariablen, die die Zielfunktion minimieren und gleichzeitig die Bedingungen erfüllen.

funfloat

Der optimale Wert der Zielfunktion c @ x.

slack1-D-Array

Die (nominal positiven) Werte der Schlupfvariablen, b_ub - A_ub @ x.

con1-D-Array

Die (nominal nullen) Residuen der Gleichheitsbedingungen, b_eq - A_eq @ x.

successbool

True, wenn der Algorithmus erfolgreich eine optimale Lösung findet.

statusint

Eine Ganzzahl, die den Exit-Status des Algorithmus darstellt.

0 : Optimierung erfolgreich abgeschlossen.

1 : Iterationslimit erreicht.

2 : Problem scheint unzulässig zu sein.

3 : Problem scheint unbeschränkt zu sein.

4 : Numerische Schwierigkeiten aufgetreten.

messagestr

Eine Zeichenkette, die den Beendigungsstatus des Algorithmus beschreibt.

nitint

Die Gesamtzahl der Iterationen in allen Phasen.

Siehe auch

Die Dokumentation für die restlichen Parameter finden Sie unter scipy.optimize.linprog

Optionen:

——-

maxiterint (Standard: 1000)

Die maximale Anzahl von Iterationen des Algorithmus.

dispbool (Standard: False)

Auf True setzen, wenn Indikatoren des Optimierungsstatus bei jeder Iteration auf der Konsole ausgegeben werden sollen.

presolvebool (Standard: True)

Presolve versucht, triviale Unzulässigkeiten zu identifizieren, triviale Unbeschränktheit zu erkennen und das Problem zu vereinfachen, bevor es an den Hauptlöser übergeben wird. Es wird generell empfohlen, die Standardeinstellung True beizubehalten. Setzen Sie auf False, wenn Presolve deaktiviert werden soll.

tolfloat (Standard: 1e-8)

Abbruchtoleranz, die für alle Abbruchkriterien verwendet werden soll; siehe [4] Abschnitt 4.5.

autoscalebool (Standard: False)

Auf True setzen, um eine automatische Äquilibrierung durchzuführen. Erwägen Sie die Verwendung dieser Option, wenn die numerischen Werte in den Bedingungen um mehrere Größenordnungen voneinander abweichen.

rrbool (Standard: True)

Auf False setzen, um die automatische Entfernung redundanter Gleichungen zu deaktivieren.

alpha0float (Standard: 0.99995)

Die maximale Schrittgröße für die Vorhersage-Korrektur-Suchrichtung von Mehrota; siehe \(\beta_{3}\) in [4] Tabelle 8.1.

betafloat (Standard: 0.1)

Die gewünschte Reduzierung des Pfadparameters \(\mu\) (siehe [6]), wenn die Vorhersage-Korrektur von Mehrota nicht verwendet wird (unüblich).

sparsebool (Standard: False)

Auf True setzen, wenn das Problem nach der Voreingrenzung als dünn (sparse) behandelt werden soll. Wenn entweder A_eq oder A_ub dünn ist, wird diese Option automatisch auf True gesetzt, und das Problem wird auch während der Voreingrenzung als dünn behandelt. Wenn Ihre Nebenbedinungsmatrizen hauptsächlich Nullen enthalten und das Problem nicht sehr klein ist (weniger als etwa 100 Nebenbedingungen oder Variablen), sollten Sie erwägen, True zu setzen oder A_eq und A_ub als dünne Arrays bereitzustellen.

lstsqbool (Standard: False)

Auf True setzen, wenn das Problem als sehr schlecht konditioniert erwartet wird. Dies sollte immer auf False belassen werden, es sei denn, es treten schwere numerische Schwierigkeiten auf. Lassen Sie dies beim Standardwert, es sei denn, Sie erhalten eine Warnmeldung, die darauf hindeutet.

sym_posbool (Standard: True)

Auf True belassen, wenn die Normalgleichungsmatrix als gut konditionierte symmetrische positiv definite Matrix erwartet wird (fast immer). Lassen Sie dies beim Standardwert, es sei denn, Sie erhalten eine Warnmeldung, die darauf hindeutet.

choleskybool (Standard: True)

Auf True setzen, wenn die Normalgleichungen durch explizite Cholesky-Zerlegung gefolgt von expliziter Vorwärts-/Rückwärtssubstitution gelöst werden sollen. Dies ist typischerweise schneller für numerisch gutartige Probleme.

pcbool (Standard: True)

Auf True belassen, wenn die Vorhersage-Korrektur-Methode von Mehrota verwendet werden soll. Dies ist fast immer (wenn nicht immer) vorteilhaft.

ipbool (Standard: False)

Auf True setzen, wenn der verbesserte Startpunktvorschlag gemäß [4] Abschnitt 4.3 gewünscht ist. Ob dies vorteilhaft ist oder nicht, hängt vom Problem ab.

permc_specstr (Standard: ‘MMD_AT_PLUS_A’)

(Wirkt sich nur aus bei sparse = True, lstsq = False, sym_pos = True, und keine SuiteSparse.) Eine Matrix wird in jeder Iteration des Algorithmus faktorisiert. Diese Option gibt an, wie die Spalten der Matrix zur Erhaltung der Dünnheit permutiert werden sollen. Akzeptable Werte sind

• NATURAL: natürliche Reihenfolge.

• MMD_ATA: minimale Gradreihenfolge auf der Struktur von A^T A.

• MMD_AT_PLUS_A: minimale Gradreihenfolge auf der Struktur von A^T+A.

• COLAMD: ungefähre Minimalgrad-Spaltenordnung.

Diese Option kann die Konvergenz des Interior-Point-Algorithmus beeinflussen; testen Sie verschiedene Werte, um zu bestimmen, welcher für Ihr Problem am besten funktioniert. Weitere Informationen finden Sie unter scipy.sparse.linalg.splu.

unknown_optionsdict

Optionale Argumente, die von diesem speziellen Löser nicht verwendet werden. Wenn unknown_options nicht leer ist, wird eine Warnung ausgegeben, die alle ungenutzten Optionen auflistet.

Hinweise

Diese Methode implementiert den in [4] dargestellten Algorithmus mit Ideen aus [8] und einer Struktur, die von den einfacheren Methoden in [6] inspiriert ist.

Die primär-duale Pfadfolgemethode beginnt mit anfänglichen „Schätzungen“ der primären und dualen Variablen des Standardformularproblems und versucht iterativ, die (nichtlinearen) Karush-Kuhn-Tucker-Bedingungen für das Problem mit einem allmählich reduzierten logarithmischen Barrierebegriff, der zur Zielfunktion hinzugefügt wird, zu lösen. Diese spezielle Implementierung verwendet eine homogene selbstduale Formulierung, die bei Bedarf Zertifikate für Nichtlösbarkeit oder Unbeschränktheit liefert.

Der Standardstartpunkt für die primären und dualen Variablen ist der in [4] Abschnitt 4.4 Gleichung 8.22 definierte. Optional (durch Setzen der Startpunktoption ip=True) kann ein alternativer (potenziell verbesserter) Startpunkt gemäß den zusätzlichen Empfehlungen von [4] Abschnitt 4.4 berechnet werden.

Eine Suchrichtung wird mit der von Mehrota vorgeschlagenen und in [4] Abschnitt 4.1 beschriebenen Vorhersage-Korrektur-Methode berechnet. (Eine mögliche Verbesserung wäre die Implementierung der Methode der Mehrfachkorrekturen, die in [4] Abschnitt 4.2 beschrieben wird.) In der Praxis geschieht dies durch Lösen der Normalgleichungen, [4] Abschnitt 5.1 Gleichungen 8.31 und 8.32, abgeleitet aus den Newton-Gleichungen [4] Abschnitt 5 Gleichungen 8.25 (vergleiche mit [4] Abschnitt 4 Gleichungen 8.6-8.8). Der Vorteil des Lösens der Normalgleichungen anstelle von 8.25 direkt ist, dass die beteiligten Matrizen symmetrisch und positiv definit sind, so dass eine Cholesky-Zerlegung anstelle der teureren LU-Zerlegung verwendet werden kann.

Mit den Standardoptionen hängt der für die Zerlegung verwendete Löser von der Verfügbarkeit von Drittanbietersoftware und der Kondition des Problems ab.

Für dichte Probleme werden die Löser in folgender Reihenfolge versucht:

1. scipy.linalg.cho_factor

2. scipy.linalg.solve mit der Option sym_pos=True

3. scipy.linalg.solve mit der Option sym_pos=False

4. scipy.linalg.lstsq

Für dünne Probleme

1. sksparse.cholmod.cholesky (wenn scikit-sparse und SuiteSparse installiert sind)

2. scipy.sparse.linalg.factorized (wenn scikit-umfpack und SuiteSparse installiert sind)

3. scipy.sparse.linalg.splu (das SuperLU verwendet, das mit SciPy geliefert wird)

4. scipy.sparse.linalg.lsqr

Wenn der Löser aus irgendeinem Grund fehlschlägt, werden nacheinander robustere (aber langsamere) Löser in der angegebenen Reihenfolge versucht. Das Versuchen, Fehlen und Neustarten der Faktorisierung kann zeitaufwendig sein. Wenn das Problem numerisch herausfordernd ist, können Optionen gesetzt werden, um Lösungsversuche zu umgehen, die fehlschlagen. Das Setzen von cholesky=False überspringt zu Löser 2, sym_pos=False überspringt zu Löser 3 und lstsq=True überspringt zu Löser 4 für sowohl dünne als auch dichte Probleme.

Mögliche Verbesserungen zur Bekämpfung von Problemen mit dichten Spalten in ansonsten dünnen Problemen sind in [4] Abschnitt 5.3 und [10] Abschnitt 4.1-4.2 beschrieben; letzteres diskutiert auch die Linderung von Genauigkeitsproblemen im Zusammenhang mit der Substitutionsmethode für freie Variablen.

Nachdem die Suchrichtung berechnet wurde, wird die maximal mögliche Schrittgröße, die die Nicht-Negativitätsbeschränkungen nicht aktiviert, berechnet, und die kleinere dieser Schrittgröße und Eins wird angewendet (wie in [4] Abschnitt 4.1). [4] Abschnitt 4.3 schlägt Verbesserungen zur Auswahl der Schrittgröße vor.

Der neue Punkt wird gemäß den Abbruchbedingungen von [4] Abschnitt 4.5 getestet. Die gleiche Toleranz, die über die Option tol gesetzt werden kann, wird für alle Prüfungen verwendet. (Eine mögliche Verbesserung wäre, die verschiedenen Toleranzen unabhängig einstellbar zu machen.) Wenn Optimalität, Unbeschränktheit oder Nichtlösbarkeit erkannt wird, terminiert der Lösungsablauf; andernfalls wiederholt er sich.

Während das Top-Level-Modul linprog ein Problem der Form

Minimieren

c @ x

Unter den Nebenbedingungen

A_ub @ x <= b_ub
A_eq @ x == b_eq
 lb <= x <= ub

erwartet, wobei lb = 0 und ub = None ist, es sei denn, sie sind in bounds gesetzt. Das Problem wird automatisch in die Form

Minimieren

c @ x

Unter den Nebenbedingungen

A @ x == b
    x >= 0

zur Lösung konvertiert. Das heißt, das ursprüngliche Problem enthält Gleichheits-, Ober- und Variablenbeschränkungen, während der methodenspezifische Löser Gleichheitsbeschränkungen und Nicht-Negativität der Variablen erfordert. linprog konvertiert das ursprüngliche Problem in Standardform, indem es einfache Grenzen in Ungleichheitsbeschränkungen umwandelt, nicht-negative Schlupfvariablen für Ungleichheitsbeschränkungen einführt und unbeschränkte Variablen als Differenz zwischen zwei nicht-negativen Variablen ausdrückt. Das Problem wird vor der Berichterstattung der Ergebnisse wieder in die ursprüngliche Form zurückkonvertiert.

Referenzen

[4] (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16)

Andersen, Erling D., und Knud D. Andersen. „The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm.“ High performance optimization. Springer US, 2000. 197-232.

[6] (1,2)

Freund, Robert M. „Primal-Dual Interior-Point Methods for Linear Programming based on Newton’s Method.“ Unpublished Course Notes, March 2004. Verfügbar am 25.02.2017 unter https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec14_int_pt_mthd.pdf

[8]

Andersen, Erling D., und Knud D. Andersen. „Presolving in linear programming.“ Mathematical Programming 71.2 (1995): 221-245.

[9]

Bertsimas, Dimitris, und J. Tsitsiklis. „Introduction to linear programming.“ Athena Scientific 1 (1997): 997.

[10]

Andersen, Erling D., et al. Implementation of interior point methods for large scale linear programming. HEC/Universite de Geneve, 1996.