Wie zum ausführen von nicht-linearen Optimierung mit scipy/numpy oder sympy?

Ich bin auf der Suche nach der optimalen Lösung für das follow-system von Gleichungen in Python:

(x-x1)^2 + (y-y1)^2 - r1^2 = 0
(x-x2)^2 + (y-y2)^2 - r2^2 = 0
(x-x3)^2 + (y-y3)^2 - r3^2 = 0

Angesichts der Werte, die einen Punkt(x,y) und einem radius (r):

x1, y1, r1 = (0, 0, 0.88)
x2, y2, r2 = (2, 0, 1)
x3, y3, r3 = (0, 2, 0.75)

Was ist der beste Weg, die optimale Lösung für den Punkt (x,y)
Im obigen Beispiel wäre es:

~ (1, 1)

Sie haben Undefinierte Variablen (x und y) in die Funktion eqs. Können Sie den eigentlichen code, den Sie verwenden?
Ich versuche zur Optimierung der Werte von x und y das Gleichungssystem.
Ich war mit diesem Beispiel: stackoverflow.com/questions/8739227/...
fsolve ist für die numerische Stamm Erkenntnis, nicht die Optimierung, d.h. er wird versuchen zu finden, die Werte der input so, dass die Ausgabe der Funktion ist null. Das Beispiel, das Sie zeigen, ist hier nicht anwendbar. Auch glaube ich nicht verstehen, was die optimalen Werte x und y bedeuten im Kontext der drei Gleichungen. (Von dem, was dein code sagt, der computer auch nicht.) Klaren sein, auf was Sie versuchen zu erreichen.
Danke für die Kommentare und sorry für die unklare. Ich habe also die Frage, was ist jetzt hoffentlich klarer.

InformationsquelleAutor drbunsen | 2012-10-17

14

Wenn ich verstehe deine Frage richtig, ich denke das ist, was Sie nach:
```
from scipy.optimize import minimize
import numpy as np

def f(coord,x,y,r):
    return np.sum( ((coord[0] - x)**2) + ((coord[1] - y)**2) - (r**2) )

x = np.array([0,   2,  0])
y = np.array([0,   0,  2])
r = np.array([.88, 1, .75])

# initial (bad) guess at (x,y) values
initial_guess = np.array([100,100])

res = minimize(f,initial_guess,args = [x,y,r])
```
Welche ergibt:
```
>>> print res.x
[ 0.66666666  0.66666666]
```
Können Sie auch versuchen, die Methode der kleinsten Quadrate, die erwartet, dass eine Objektive Funktion, liefert einen Vektor. Es will zur Minimierung der Summe der Quadrate des Vektors. Mit Hilfe der Methode der kleinsten Quadrate, Ihr Ziel-Funktion würde wie folgt Aussehen:
```
def f2(coord,args):
    x,y,r = args
    # notice that we're returning a vector of dimension 3
    return ((coord[0]-x)**2) + ((coord[1] - y)**2) - (r**2)
```
Und Sie würden zu minimieren, etwa so:
```
from scipy.optimize import leastsq
res = leastsq(f2,initial_guess,args = [x,y,r])
```
Welche ergibt:
```
>>> print res[0]
>>> [ 0.77961518  0.85811473]
```
Dies ist im Grunde das gleiche wie mit minimize - und re-schreiben der ursprünglichen Zielfunktion als:
```
def f(coord,x,y,r):
    vec = ((coord[0]-x)**2) + ((coord[1] - y)**2) - (r**2)
    # return the sum of the squares of the vector
    return np.sum(vec**2)
```
Damit ergibt sich:
```
>>> print res.x
>>> [ 0.77958326  0.8580965 ]
```
Beachten Sie, dass args behandelt werden, ein bisschen anders mit leastsq ist, und dass die Daten-Strukturen zurückgegeben, indem die beiden Funktionen sind auch unterschiedlich. Finden Sie in der Dokumentation für scipy.optimieren.minimieren und scipy.optimieren.leastsq für mehr details.

Sehen die scipy.optimieren - Dokumentation für weitere Optimierungen.
- Das Ergebnis fand Sie nicht befriedigen jede der Gleichungen...
- Das ist genau das, was ich gesucht habe! Vielen Dank für Ihre Hilfe und Patienten, die versuchen zu verstehen, was ich versuche zu tun.
- Froh, es zu hören! Sie könnten auch spielen mit mit der l2-norm statt die Summe für die Kosten-Funktion, D. H., verwenden Sie np.linalg.norm im Ort np.sum, und sehen, wie das wirkt sich auf Ihre Ergebnisse.
- Könnte leastsq auch hier verwendet werden? Was ist der Unterschied zwischen minimieren() und leastsq()?
- Der Haupt-Unterschied, dass das hier relevant ist, dass minimize erwartet einen scalar-valued function, und leastsq erwartet eine vektorwertige Funktion. leastsq will Minimierung der Summe der Quadrate der Vektor zurückgegeben, indem die Zielfunktion, so ist es fast wie mit der l2-norm mit minimize. In der Tat, bekomme ich Antworten, die sind fast identisch mit leastsq - und der l2-norm mit minimize: ~[.78,.86]
- Ah, Super. Nochmals vielen Dank. Would you mind posting die leastsq-code, so dass ich versuchen könnte, und verstehen es als gut?
- Sichere Sache. Ich habe bearbeitet meine Antwort.
- Vielen, vielen Dank. Ich werde aufhören, nervt Sie jetzt!
InformationsquelleAutor John Vinyard

Bemerkte ich, dass der code in der angenommen Lösung nicht mehr funktioniert... ich denke, vielleicht scipy.optimize hat sich verändert seine Oberfläche, seit die Antwort wurde geschrieben. Ich könnte falsch sein. Egal, ich zweiten den Vorschlag, die algorithmen in scipy.optimize, und die akzeptierte Antwort wird zeigen, wie (oder hast zu einer Zeit, wenn die Schnittstelle geändert hat).

Ich bin durch das hinzufügen einer weiteren Antwort hier rein, eine alternative vorzuschlagen-Paket, das verwendet die scipy.optimize algorithmen auf den Kern, ist aber viel robuster für die eingeschränkte Optimierung. Das Paket ist mystic. Eine der großen Verbesserungen ist, dass mystic gibt eingeschränkte globalen Optimierung.

Erste, hier ist dein Beispiel sehr ähnlich zu der scipy.optimize.minimize Weg, aber mit einem globalen Optimierer.

from mystic import reduced

@reduced(lambda x,y: abs(x)+abs(y)) #choice changes answer
def objective(x, a, b, c):
  x,y = x
  eqns = (\
    (x - a[0])**2 + (y - b[0])**2 - c[0]**2,
    (x - a[1])**2 + (y - b[1])**2 - c[1]**2,
    (x - a[2])**2 + (y - b[2])**2 - c[2]**2)
  return eqns

bounds = [(None,None),(None,None)] #unnecessary

a = (0,2,0)
b = (0,0,2)
c = (.88,1,.75)
args = a,b,c

from mystic.solvers import diffev2
from mystic.monitors import VerboseMonitor
mon = VerboseMonitor(10)

result = diffev2(objective, args=args, x0=bounds, bounds=bounds, npop=40, \ 
                 ftol=1e-8, disp=False, full_output=True, itermon=mon)

print result[0]
print result[1]

Ergebnisse so Aussehen:

Generation 0 has Chi-Squared: 38868.949133
Generation 10 has Chi-Squared: 2777.470642
Generation 20 has Chi-Squared: 12.808055
Generation 30 has Chi-Squared: 3.764840
Generation 40 has Chi-Squared: 2.996441
Generation 50 has Chi-Squared: 2.996441
Generation 60 has Chi-Squared: 2.996440
Generation 70 has Chi-Squared: 2.996433
Generation 80 has Chi-Squared: 2.996433
Generation 90 has Chi-Squared: 2.996433
STOP("VTRChangeOverGeneration with {'gtol': 1e-06, 'target': 0.0, 'generations': 30, 'ftol': 1e-08}")
[ 0.66667151  0.66666422]
2.99643333334

Wie bereits erwähnt, die Wahl der lambda im reduced betrifft worauf der Optimierer findet, da es keine tatsächliche Lösung der Gleichungen.

mystic bietet auch die Möglichkeit zum konvertieren von symbolischen Gleichungen in eine Funktion, wo die resultierende Funktion kann verwendet werden, als Ziel oder als eine Strafe-Funktion. Hier ist das gleiche problem, aber mit Hilfe der Gleichungen als eine Strafe, anstatt das Ziel.

def objective(x):
    return 0.0

equations = """
(x0 - 0)**2 + (x1 - 0)**2 - .88**2 == 0
(x0 - 2)**2 + (x1 - 0)**2 - 1**2 == 0
(x0 - 0)**2 + (x1 - 2)**2 - .75**2 == 0
"""

bounds = [(None,None),(None,None)] #unnecessary

from mystic.symbolic import generate_penalty, generate_conditions
from mystic.solvers import diffev2

pf = generate_penalty(generate_conditions(equations), k=1e12)

result = diffev2(objective, x0=bounds, bounds=bounds, penalty=pf, \
                 npop=40, gtol=50, disp=False, full_output=True)

print result[0]
print result[1]

Ergebnisse:

[ 0.77958328  0.8580965 ]
3.6473132399e+12

Sind die Ergebnisse anders als vorher, weil die Strafe angewendet wird, anders als wir früher in reduced. In mystic können Sie auswählen, welche Strafe die Sie anwenden möchten.

Der Punkt war, dass die Gleichung keine Lösung hat. Sie können sehen, aus dem Ergebnis vor, dass das Ergebnis schwer bestraft, das ist also ein gutes Indiz dafür, dass es keine Lösung gibt. Allerdings mystic hat eine andere Weise, die Sie sehen können, gibt es keine Lösung. Anstelle der Anwendung einer mehr traditionellen penalty, die bestraft die Lösung, wo die constraints verletzt werden... mystic bietet eine constraint, die im wesentlichen eine kernel-transformation entfernt alle potenziellen Lösungen, die nicht erfüllen die Konstanten.

def objective(x):
    return 0.0

equations = """
(x0 - 0)**2 + (x1 - 0)**2 - .88**2 == 0
(x0 - 2)**2 + (x1 - 0)**2 - 1**2 == 0
(x0 - 0)**2 + (x1 - 2)**2 - .75**2 == 0
"""

bounds = [(None,None),(None,None)] #unnecessary

from mystic.symbolic import generate_constraint, generate_solvers, simplify
from mystic.symbolic import generate_penalty, generate_conditions    
from mystic.solvers import diffev2

cf = generate_constraint(generate_solvers(simplify(equations)))

result = diffev2(objective, x0=bounds, bounds=bounds, \
                 constraints=cf, \
                 npop=40, gtol=50, disp=False, full_output=True)

print result[0]
print result[1]

Ergebnisse:

[          nan  657.17740835]
0.0

Wo die nan im Grunde gibt es keine gültige Lösung.

Zur info, ich bin der Autor, so habe ich eine gewisse Tendenz. Allerdings mystic hat es schon fast so lange wie scipy.optimize, ist ausgereift und hat eine stabile Schnittstelle, die Länge der Zeit. Der Punkt ist, wenn Sie brauchen eine viel leistungsfähiger und flexibler eingeschränkte nichtlineare Optimierer, schlage ich vor mystic.

Weitere Beispiele mit nichtlinearen Nebenbedingungen hier: stackoverflow.com/a/42299338/2379433

InformationsquelleAutor Mike McKerns

1

Diesen Gleichungen kann gesehen werden, als eine Beschreibung aller Punkte auf der Kreislinie der drei Kreise im 2D-Raum. Die Lösung wäre, die Punkte, wo die Kreise abzufangen.

Die Summe Ihrer Radien der Kreise, die kleiner ist als die Abstände zwischen Ihren Zentren, so dass die Kreise nicht überlappen. Ich habe gezeichnet, die Kreise, um die Skala unten an:

Gibt es keine Punkte, die erfüllen das Gleichungssystem.
- Richtig, aber ich möchte die optimale Lösung, wenn eine exakte Lösung nicht vorhanden ist.
- Was meinst du mit, eine optimale Lösung, in diesem Fall, wo keine Lösung existiert?
- Ich meine, ich will eine Lösung, minimiert die Fehler.
InformationsquelleAutor Roland Smith

Habe ich ein Beispiel-Skript, indem Sie die folgenden. Beachten Sie, dass die Letzte Zeile findet sich eine optimale Lösung (a,b):

import numpy as np
import scipy as scp
import sympy as smp
from scipy.optimize import minimize

a,b = smp.symbols('a b')
x_ar, y_ar = np.random.random(3), np.random.random(3)
x = np.array(smp.symbols('x0:%d'%np.shape(x_ar)[0]))
y = np.array(smp.symbols('y0:%d'%np.shape(x_ar)[0]))
func = np.sum(a**2+b**2-x*(a+b)+2*y)
print func
my_func = smp.lambdify((x,y), func)
print 1.0/3*my_func(x_ar,y_ar)
ab = smp.lambdify((a,b),my_func(x_ar,x_ar))
print ab(1,2)

def ab_v(x):
   return ab(*tuple(x))

print ab_v((1,2))

minimize(ab_v,(0.1,0.1))

Ausgänge :

3*a**2 + 3*b**2 - x0*(a + b) - x1*(a + b) - x2*(a + b) + 2*y0 + 2*y1 + 2*y2
1.0*a**2 - 0.739792011558683*a + 1.0*b**2 - 0.739792011558683*b    +0.67394435712335


12.7806239653
12.7806239653
Out[33]:
  status: 0
 success: True
 njev: 3
 nfev: 12
 hess_inv: array([[1, 0],
   [0, 1]])
 fun: 3.6178137388030356
 x: array([ 0.36989601,  0.36989601])
 message: 'Optimization terminated successfully.'
 jac: array([  5.96046448e-08,   5.96046448e-08])

InformationsquelleAutor FlyFish

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.