scipy.optimize.

lsq_linear#

scipy.optimize.lsq_linear(A, b, bounds=(-inf, inf), method='trf', tol=1e-10, lsq_solver=None, lsmr_tol=None, max_iter=None, verbose=0, *, lsmr_maxiter=None)[Quelle]#

Löst ein lineares Kleinste-Quadrate-Problem mit Beschränkungen für die Variablen.

Gegeben eine m-mal-n-Designmatrix A und ein Zielvektor b mit m Elementen, löst lsq_linear das folgende Optimierungsproblem

minimize 0.5 * ||A x - b||**2
subject to lb <= x <= ub

Dieses Optimierungsproblem ist konvex, daher ist ein gefundenes Minimum (falls die Iterationen konvergiert sind) garantiert global.

Parameter:
Aarray_like, sparse array oder LinearOperator, Form (m, n)

Designmatrix. Kann ein scipy.sparse.linalg.LinearOperator sein.

barray_like, shape (m,)

Zielvektor.

bounds2-Tupel aus array_like oder Bounds, optional

Untere und obere Schranken für die Parameter. Standardmäßig keine Schranken. Es gibt zwei Möglichkeiten, die Schranken anzugeben

  • Instanz der Klasse Bounds.

  • 2-Tupel aus array_like: Jedes Element des Tupels muss entweder ein Array mit der Länge gleich der Anzahl der Parameter oder ein Skalar sein (in diesem Fall wird die Schranke für alle Parameter gleich angenommen). Verwenden Sie np.inf mit dem entsprechenden Vorzeichen, um Schranken für alle oder einige Parameter zu deaktivieren.

method‘trf’ oder ‘bvls’, optional

Methode zur Durchführung der Minimierung.

  • ‘trf’ : Trust Region Reflective-Algorithmus, angepasst für ein lineares Kleinste-Quadrate-Problem. Dies ist eine Methode vom Typ Interior-Point, und die benötigte Anzahl von Iterationen ist schwach mit der Anzahl der Variablen korreliert.

  • ‘bvls’ : Bounded-variable least-squares-Algorithmus. Dies ist eine Active-Set-Methode, die eine Anzahl von Iterationen benötigt, die mit der Anzahl der Variablen vergleichbar ist. Kann nicht verwendet werden, wenn A spärlich oder ein LinearOperator ist.

Standard ist ‘trf’.

tolfloat, optional

Toleranzparameter. Der Algorithmus endet, wenn die relative Änderung der Kostenfunktion in der letzten Iteration kleiner als tol ist. Zusätzlich wird das Maß der Erstordnung-Optimalität berücksichtigt

  • method='trf' endet, wenn die uniforme Norm des Gradienten, skaliert zur Berücksichtigung der Schranken, kleiner als tol ist.

  • method='bvls' endet, wenn die Karush-Kuhn-Tucker-Bedingungen innerhalb einer Toleranz von tol erfüllt sind.

lsq_solver{None, ‘exact’, ‘lsmr’}, optional

Methode zum Lösen von unbeschränkten Kleinste-Quadrate-Problemen während der Iterationen

  • ‘exact’ : Verwenden Sie eine dichte QR- oder SVD-Zerlegung. Kann nicht verwendet werden, wenn A spärlich oder ein LinearOperator ist.

  • ‘lsmr’ : Verwenden Sie das iterative Verfahren scipy.sparse.linalg.lsmr, das nur Matrix-Vektor-Produktauswertungen benötigt. Kann nicht mit method='bvls' verwendet werden.

Wenn None (Standard), wird der Solver basierend auf dem Typ von A ausgewählt.

lsmr_tolNone, float oder ‘auto’, optional

Toleranzparameter ‘atol’ und ‘btol’ für scipy.sparse.linalg.lsmr. Wenn None (Standard), wird er auf 1e-2 * tol gesetzt. Wenn ‘auto’, wird die Toleranz basierend auf der Optimalität des aktuellen Iteranden angepasst, was den Optimierungsprozess beschleunigen kann, aber nicht immer zuverlässig ist.

max_iterNone oder int, optional

Maximale Anzahl von Iterationen vor dem Abbruch. Wenn None (Standard), wird sie auf 100 für method='trf' oder auf die Anzahl der Variablen für method='bvls' gesetzt (ohne Iterationen für die 'bvls'-Initialisierung).

verbose{0, 1, 2}, optional

Level der Ausführlichkeit des Algorithmus

  • 0 : still arbeiten (Standard).

  • 1 : zeigt einen Beendigungsbericht an.

  • 2 : Fortschritt während der Iterationen anzeigen.

lsmr_maxiterNone oder int, optional

Maximale Anzahl von Iterationen für den lsmr-Kleinste-Quadrate-Solver, falls er verwendet wird (durch Setzen von lsq_solver='lsmr'). Wenn None (Standard), verwendet er den lsmr-Standard von min(m, n), wobei m und n die Anzahl der Zeilen und Spalten von A sind. Hat keine Auswirkung, wenn lsq_solver='exact'.

Rückgabe:
OptimizeResult mit den folgenden Feldern:
xndarray, Form (n,)

Gefundene Lösung.

costfloat

Wert der Kostenfunktion an der Lösung.

funndarray, Form (m,)

Vektor der Residuen an der Lösung.

optimalityfloat

Maß der Erstordnung-Optimalität. Die genaue Bedeutung hängt von method ab; siehe die Beschreibung des tol-Parameters.

active_maskndarray von int, Form (n,)

Jede Komponente zeigt an, ob eine entsprechende Einschränkung aktiv ist (d.h. ob eine Variable an der Grenze liegt)

  • 0 : eine Einschränkung ist nicht aktiv.

  • -1 : eine untere Schranke ist aktiv.

  • 1 : eine obere Schranke ist aktiv.

Kann für die Methode trf etwas willkürlich sein, da sie eine Folge von streng zulässigen Iterierten erzeugt und die active_mask innerhalb eines Toleranzschwellenwerts bestimmt wird.

unbounded_soltuple

Unbeschränkte Kleinste-Quadrate-Lösungs-Tupel, das vom Kleinste-Quadrate-Solver zurückgegeben wird (gesetzt mit der Option lsq_solver). Wenn lsq_solver nicht gesetzt oder auf 'exact' gesetzt ist, enthält das Tupel ein ndarray der Form (n,) mit der unbeschränkten Lösung, ein ndarray mit der Summe der quadrierten Residuen, ein int mit dem Rang von A und ein ndarray mit den singulären Werten von A (siehe NumPy's linalg.lstsq für weitere Informationen). Wenn lsq_solver auf 'lsmr' gesetzt ist, enthält das Tupel ein ndarray der Form (n,) mit der unbeschränkten Lösung, einen int mit dem Exit-Code, einen int mit der Anzahl der Iterationen und fünf Floats mit verschiedenen Normen und der Konditionszahl von A (siehe SciPy's sparse.linalg.lsmr für weitere Informationen). Diese Ausgabe kann nützlich sein, um die Konvergenz des Kleinste-Quadrate-Solvers zu bestimmen, insbesondere des iterativen 'lsmr'-Solvers. Das unbeschränkte Kleinste-Quadrate-Problem besteht darin, 0.5 * ||A x - b||**2 zu minimieren.

nitint

Anzahl der Iterationen. Null, wenn die unbeschränkte Lösung optimal ist.

statusint

Grund für die Beendigung des Algorithmus

  • -1 : der Algorithmus konnte in der letzten Iteration keinen Fortschritt erzielen.

  • 0 : die maximale Anzahl von Iterationen wurde überschritten.

  • 1 : das Maß der Erstordnung-Optimalität ist kleiner als tol.

  • 2 : die relative Änderung der Kostenfunktion ist kleiner als tol.

  • 3 : die unbeschränkte Lösung ist optimal.

messagestr

Verbale Beschreibung des Abbruchgrundes.

successbool

True, wenn eines der Konvergenzkriterien erfüllt ist (status > 0).

Siehe auch

nnls

Lineare Kleinste-Quadrate mit Nicht-Negativitäts-Einschränkung.

least_squares

Nichtlineare Kleinste-Quadrate mit Schranken für die Variablen.

Hinweise

Der Algorithmus berechnet zunächst die unbeschränkte Kleinste-Quadrate-Lösung mittels numpy.linalg.lstsq oder scipy.sparse.linalg.lsmr, abhängig von lsq_solver. Diese Lösung wird als optimal zurückgegeben, wenn sie innerhalb der Schranken liegt.

Die Methode 'trf' führt die Anpassung des Algorithmus aus, der in [STIR] für ein lineares Kleinste-Quadrate-Problem beschrieben ist. Die Iterationen sind im Wesentlichen die gleichen wie im Algorithmus für nichtlineare Kleinste-Quadrate, aber da das quadratische Funktionsmodell immer genau ist, müssen wir den Radius einer Vertrauensregion nicht verfolgen oder modifizieren. Die Liniensuche (Backtracking) wird als Sicherheitsnetz verwendet, wenn ein ausgewählter Schritt die Kostenfunktion nicht verringert. Eine detailliertere Beschreibung des Algorithmus finden Sie in scipy.optimize.least_squares.

Die Methode 'bvls' führt eine Python-Implementierung des Algorithmus aus, der in [BVLS] beschrieben ist. Der Algorithmus verwaltet aktive und freie Mengen von Variablen, wählt in jeder Iteration eine neue Variable aus, um von der aktiven zur freien Menge zu wechseln, und löst dann das unbeschränkte Kleinste-Quadrate-Problem für die freien Variablen. Dieser Algorithmus liefert garantiert irgendwann eine genaue Lösung, kann aber bis zu n Iterationen für ein Problem mit n Variablen benötigen. Zusätzlich ist ein Ad-hoc-Initialisierungsverfahren implementiert, das bestimmt, welche Variablen anfangs als frei oder aktiv gesetzt werden sollen. Es dauert einige Iterationen, bis BVLS tatsächlich beginnt, kann aber die Anzahl der weiteren Iterationen erheblich reduzieren.

Referenzen

[STIR]

M. A. Branch, T. F. Coleman, und Y. Li, „A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems,“ SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp 1-23, 1999.

[BVLS]

P. B. Start und R. L. Parker, „Bounded-Variable Least-Squares: an Algorithm and Applications“, Computational Statistics, 10, 129-141, 1995.

Beispiele

In diesem Beispiel wird ein Problem mit großen spärlichen Arrays und Schranken für die Variablen gelöst.

>>> import numpy as np
>>> from scipy.sparse import random_array
>>> from scipy.optimize import lsq_linear
>>> rng = np.random.default_rng()
...
>>> m = 2000
>>> n = 1000
...
>>> A = random_array((m, n), density=1e-4, random_state=rng)
>>> b = rng.standard_normal(m)
...
>>> lb = rng.standard_normal(n)
>>> ub = lb + 1
...
>>> res = lsq_linear(A, b, bounds=(lb, ub), lsmr_tol='auto', verbose=1)
The relative change of the cost function is less than `tol`.
Number of iterations 10, initial cost 1.0070e+03, final cost 9.6602e+02,
first-order optimality 2.21e-09.        # may vary
Auf dieser Seite