Python: wielowymiarowy nieliniowy solver z ograniczeniami

Question

Otrzymując funkcję f(x), która pobiera wektor wejściowy x i zwraca wektor o tej samej długości, w jaki sposób znaleźć źródła ograniczeń ustawień funkcji na x? (Np. Zakres dla każdego składnika x.)

Ku mojemu zdziwieniu nie mogłem znaleźć wielu przydatnych informacji na ten temat. Na liście scipy dla Optimization and Root finding algorithms wydają się być pewne opcje funkcji skalarnych, takich jak brentq. Nie mogę jednak znaleźć algorytmów obsługujących taką opcję w przypadku wielowymiarowej.

Oczywiście można wykonać obejście, jak wyrównywanie każdego komponentu zwróconego wektora, a następnie użyć jednego z minimalizatorów, takiego jak differential_evolution (jest to jedyny, który faktycznie myślę). Nie mogę sobie wyobrazić, że jest to dobra strategia, ponieważ zabija ona kwadratową zbieżność algorytmu Newtona. Również wydaje mi się zaskakujące, że nie wydaje się, że istnieje taka możliwość, ponieważ musi to być naprawdę powszechny problem. Czy coś przeoczyłem?

Answer 1

One (niezbyt ładne, ale mam nadzieję, że praca) możliwość obejścia tego problemu byłoby dać solver funkcję, która ma tylko korzenie w ograniczonej regionie, który jest kontynuowany w sposób zapewniający, że Solver jest odepchnięto w odpowiednim regionie (trochę jak here, ale w wielu wymiarach).

co można zrobić, aby osiągnąć to (przynajmniej dla prostokątnych ograniczeń) jest wdrożenie constrainedFunction że jest liniowo kontynuowane począwszy od wartości granicznej swojej funkcji:

import numpy as np 

def constrainedFunction(x, f, lower, upper, minIncr=0.001): 
    x = np.asarray(x) 
    lower = np.asarray(lower) 
    upper = np.asarray(upper) 
    xBorder = np.where(x<lower, lower, x) 
    xBorder = np.where(x>upper, upper, xBorder) 
    fBorder = f(xBorder) 
    distFromBorder = (np.sum(np.where(x<lower, lower-x, 0.)) 
         +np.sum(np.where(x>upper, x-upper, 0.))) 
    return (fBorder + (fBorder 
         +np.where(fBorder>0, minIncr, -minIncr))*distFromBorder) 

Możesz przekazać tę funkcję x wartość, funkcja f, którą chcesz kontynuować, a także dwie macierze lower i upper o takim samym kształcie, jak x, nadające dolny i górny margines we wszystkich wymiarach. Teraz możesz przekazać tę funkcję zamiast oryginalnej funkcji solverowi, aby znaleźć korzenie.

Stromość kontynuacji jest po prostu brana jako wartość graniczna, aby zapobiec skokom w górę przy zmianie znaku na granicy. Aby zapobiec korzeniom poza ograniczonym regionem, niektóre małe wartości są dodawane/odejmowane do dodatnich/ujemnych wartości granicznych. Zgadzam się, że nie jest to bardzo dobry sposób na poradzenie sobie z tym, ale wydaje się, że działa.

Oto dwa przykłady. Zarówno początkowe odgadnięcie znajduje się poza ograniczonym regionem, ale także znaleziony właściwy root w ograniczonym regionie.

Znalezienie korzeniami wielowymiarowy cosinus zamocowanym do [-2, -1] x [1, 2] otrzymujemy:

from scipy import optimize as opt 

opt.root(constrainedFunction, x0=np.zeros(2), 
     args=(np.cos, np.asarray([-2., 1.]), np.asarray([-1, 2.]))) 

otrzymujemy:

fjac: array([[ -9.99999975e-01, 2.22992740e-04], 
     [ 2.22992740e-04, 9.99999975e-01]]) 
    fun: array([ 6.12323400e-17, 6.12323400e-17]) 
message: 'The solution converged.' 
    nfev: 11 
    qtf: array([ -2.50050470e-10, -1.98160617e-11]) 
     r: array([-1.00281376, 0.03518108, -0.9971942 ]) 
    status: 1 
success: True 
     x: array([-1.57079633, 1.57079633]) 

ta działa także dla funkcji nie są przekątna:

def f(x): 
    return np.asarray([0., np.cos(x.sum())]) 

opt.root(constrainedFunction, x0=np.zeros(2), 
     args=(f, np.asarray([-2., 2.]), np.asarray([-1, 4.]))) 

daje:

fjac: array([[ 0.00254922, 0.99999675], 
     [-0.99999675, 0.00254922]]) 
    fun: array([ 0.00000000e+00, 6.12323400e-17]) 
message: 'The solution converged.' 
    nfev: 11 
    qtf: array([ 1.63189544e-11, 4.16007911e-14]) 
     r: array([-0.75738638, -0.99212138, -0.00246647]) 
    status: 1 
success: True 
     x: array([-1.65863336, 3.22942968]) 

Answer 2

Jeśli chcesz obsługiwać optymalizacji z ograniczeniami, można użyć łatwą lirbary, co jest o wiele łatwiejsze niż scipy.optimize

Oto link do paczki:

https://pypi.python.org/pypi/facile/1.2

Oto przykład korzystania z łatwej biblioteki dla twojego przykładu. Będziesz musiał sprecyzować to, co tutaj piszę, co jest tylko ogólne. Jeśli masz błędy, powiedz mi, które.

import facile 

# Your vector x 

x = [ facile.variable('name', min, max) for i in range(Size) ] 


# I give an example here of your vector being ordered and each component in a range 
# You could as well put in the range where declaring variables 

for i in range(len(x)-1): 
    facile.constraint(x[i] < x[i+1]) 
    facile.constraint(range[i,0] < x[i] < range[i,1]) #Supposed you have a 'range' array where you store the range for each variable 


def function(...) 
# Define here the function you want to find roots of 


# Add as constraint that you want the vector to be a root of function 
facile.constraint(function(x) == 0) 


# Use facile solver 
if facile.solve(x): 
    print [x[i].value() for i in range(len(x))] 
else: 
    print "Impossible to find roots" 

Answer 3

Jeśli istnieje ryzyko sugerowania czegoś, co może już się przekreśliło, uważam, że powinno to być możliwe przy użyciu tylko . Połów jest taki, że funkcja musi mieć tylko jeden argument, ale argument ten może być wektorem/listą.

Zatem f (x, y) staje się po prostu f (z) gdzie z = [x, y].

Dobrym przykładem, który może okazać się przydatny, jeśli nie spotkasz się, jest here.

Jeśli chcesz nałożyć granic, jak wspomniano, na wektorze 2x1, można użyć:

# Specify a (lower, upper) tuple for each component of the vector  
bnds = [(0., 1.) for i in len(x)] 

i wykorzystują to jako parametr bounds w minimize.