A SciPy (ejtsd: sai pie) egy numpy alapú matematikai csomag, amely C és Fortran könyvtárakat is tartalmaz. A SciPy interaktív Python-munkamenetét egy teljes adattudományi környezetté alakítja, mint például a MATLAB, az IDL, az Octave, az R vagy a SciLab.
Ebben a cikkben a matematikai programozás alapvető technikáit tekintjük át – feltételes optimalizálási problémák megoldását több változó skalárfüggvényére a scipy.optimize csomag segítségével. A korlátlan optimalizálási algoritmusokról már volt szó . A scipy függvényekkel kapcsolatos részletesebb és naprakész súgó mindig elérhető a help() paranccsal, a Shift+Tab vagy a .
Bevezetés
A scipy.optimize csomag feltételes és korlátlan optimalizálási problémáinak megoldásához közös felületet biztosít a függvény minimize(). Köztudott azonban, hogy minden probléma megoldására nincs univerzális módszer, így a megfelelő módszer kiválasztása, mint mindig, a kutató vállára esik.
A megfelelő optimalizálási algoritmust a függvény argumentum segítségével adjuk meg minimize(..., method="").
Több változó függvényének feltételes optimalizálásához a következő módszerek megvalósításai állnak rendelkezésre:
trust-constr— helyi minimum keresése a bizalmi régióban. , ;SLSQP— szekvenciális másodfokú programozás megszorításokkal, Newtoni módszer a Lagrange-rendszer megoldására. .TNC- Csonka Newton Korlátozott, korlátozott számú iteráció, jó nemlineáris függvényekhez, nagyszámú független változóval. .L-BFGS-B— a Broyden–Fletcher–Goldfarb–Shanno csapat módszere, amelyet csökkentett memóriafelhasználással valósítottak meg a Hess-mátrixból származó vektorok részleges betöltése miatt. , .COBYLA— MARE kényszerített optimalizálás lineáris közelítéssel, kényszerített optimalizálás lineáris közelítéssel (gradiensszámítás nélkül). .
A választott módszertől függően a probléma megoldásának feltételei és korlátozásai eltérőek:
- osztályú objektum
Boundsmetódusokhoz L-BFGS-B, TNC, SLSQP, trust-constr; - a listát
(min, max)ugyanazokhoz a módszerekhez L-BFGS-B, TNC, SLSQP, trust-constr; - egy objektum vagy objektumok listája
LinearConstraint,NonlinearConstraintCOBYLA, SLSQP, trust-constr metódusokhoz; - szótár vagy szótárlista
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}COBYLA, SLSQP módszerekhez.
Cikk vázlata:
1) Fontolja meg egy feltételes optimalizálási algoritmus használatát a megbízhatósági régióban (method=”trust-constr”) objektumként megadott megszorításokkal Bounds, LinearConstraint, NonlinearConstraint ;
2) Fontolja meg a szekvenciális programozást a legkisebb négyzetek módszerével (method = "SLSQP") szótár formájában megadott korlátozásokkal {'type', 'fun', 'jac', 'args'};
3) Elemezzen egy példát a gyártott termékek optimalizálására egy webstúdió példáján.
Feltételes optimalizálási módszer="trust-constr"
A módszer megvalósítása trust-constr alapján az egyenlőség formájának korlátaival kapcsolatos problémákra és tovább az egyenlőtlenségek formájában jelentkező korlátokkal kapcsolatos problémákra. Mindkét módszert algoritmusok valósítják meg a megbízhatósági régióban lokális minimum meghatározására, és jól alkalmazhatók nagy léptékű problémák megoldására.
A minimum megtalálásának problémájának matematikai megfogalmazása általános formában:
Szigorú egyenlőségi megkötések esetén az alsó korlát egyenlő a felső korláttal .
Egyirányú kényszer esetén a felső vagy az alsó határ van beállítva np.inf a megfelelő jellel.
Legyen szükséges két változó ismert Rosenbrock-függvényének minimumát megtalálni:
Ebben az esetben a következő korlátozások vannak beállítva a definíciós tartományára vonatkozóan:
A mi esetünkben egyedi megoldás van a ponton , amelyre csak az első és a negyedik korlátozás érvényes.
Menjünk végig a korlátozásokon alulról felfelé, és nézzük meg, hogyan írhatjuk le őket scipy-ben.
Korlátozások и definiáljuk a Bounds objektum segítségével.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Korlátozások и Írjuk fel lineáris formában:
Határozzuk meg ezeket a megszorításokat LinearConstraint objektumként:
import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])És végül a nemlineáris kényszer mátrix formában:
Meghatározzuk a Jacobi mátrixot erre a megszorításra és a Hess-mátrix lineáris kombinációját egy tetszőleges vektorral :
Most egy nemlineáris kényszert definiálhatunk objektumként NonlinearConstraint:
from scipy.optimize import NonlinearConstraint
def cons_f(x):
return [x[0]**2 + x[1], x[0]**2 - x[1]]
def cons_J(x):
return [[2*x[0], 1], [2*x[0], -1]]
def cons_H(x, v):
return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H)Ha a méret nagy, a mátrixok ritka formában is megadhatók:
from scipy.sparse import csc_matrix
def cons_H_sparse(x, v):
return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]])
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_sparse)vagy tárgyként LinearOperator:
from scipy.sparse.linalg import LinearOperator
def cons_H_linear_operator(x, v):
def matvec(p):
return np.array([p[0]*2*(v[0]+v[1]), 0])
return LinearOperator((2, 2), matvec=matvec)
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
jac=cons_J, hess=cons_H_linear_operator)A Hess-mátrix kiszámításakor sok erőfeszítést igényel, használhat egy osztályt . A következő stratégiák állnak rendelkezésre: BFGS и SR1.
from scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())A Hessian kiszámítható véges különbségekkel is:
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')A kényszerek Jacobi-mátrixa véges különbségek felhasználásával is kiszámítható. Ebben az esetben azonban a Hess-mátrix nem számítható véges különbségekkel. A Hessian-t függvényként vagy a HessianUpdateStrategy osztály használatával kell meghatározni.
nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())Az optimalizálási probléma megoldása így néz ki:
from scipy.optimize import minimize
from scipy.optimize import rosen, rosen_der, rosen_hess, rosen_hess_prod
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)`gtol` termination condition is satisfied.
Number of iterations: 12, function evaluations: 8, CG iterations: 7, optimality: 2.99e-09, constraint violation: 1.11e-16, execution time: 0.033 s.
[0.41494531 0.17010937]Ha szükséges, a LinearOperator osztály segítségével definiálható a Hess-számítási függvény
def rosen_hess_linop(x):
def matvec(p):
return rosen_hess_prod(x, p)
return LinearOperator((2, 2), matvec=matvec)
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)vagy a Hess-féle és egy tetszőleges vektor szorzata a paraméteren keresztül hessp:
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod,
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Alternatív megoldásként az optimalizálandó függvény első és második deriváltja közelíthető. Például a Hessian a függvény segítségével közelíthető SR1 (kvázi-newtoni közelítés). A gradiens véges különbségekkel közelíthető.
from scipy.optimize import SR1
res = minimize(rosen, x0, method='trust-constr', jac="2-point", hess=SR1(),
constraints=[linear_constraint, nonlinear_constraint],
options={'verbose': 1}, bounds=bounds)
print(res.x)Feltételes optimalizálási módszer="SLSQP"
Az SLSQP módszert arra tervezték, hogy megoldja a függvény minimalizálásával kapcsolatos problémákat a következő formában:
ahol и — a korlátozásokat egyenlőségek vagy egyenlőtlenségek formájában leíró kifejezések indexei. — alsó és felső határok halmazai a függvény definíciós tartományához.
A lineáris és nemlineáris kényszerek leírása kulcsos szótárak formájában történik type, fun и jac.
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([1 - x [0] - 2 * x [1],
1 - x [0] ** 2 - x [1],
1 - x [0] ** 2 + x [1]]),
'jac': lambda x: np.array ([[- 1.0, -2.0],
[-2 * x [0], -1.0],
[-2 * x [0], 1.0]])
}
eq_cons = {'type': 'eq',
'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]),
'jac': lambda x: np.array ([2.0, 1.0])
}A minimum keresése a következőképpen történik:
x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='SLSQP', jac=rosen_der,
constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True},
bounds=bounds)
print(res.x)Optimization terminated successfully. (Exit mode 0)
Current function value: 0.34271757499419825
Iterations: 4
Function evaluations: 5
Gradient evaluations: 4
[0.41494475 0.1701105 ]Optimalizálási példa
Az ötödik technológiai struktúrára való átállás kapcsán nézzük meg a termelésoptimalizálást egy webstúdió példáján, ami csekély, de stabil bevételt hoz nekünk. Képzeljük el magunkat egy háromféle terméket előállító gálya igazgatójának:
- x0 - céloldalak értékesítése, 10 tr.
- x1 - céges weboldalak, 20 tr.
- x2 - webáruházak, 30 tr.
Barátságos csapatunkban négy junior, két középső és egy felső tagozatos. A havi munkaidő-alapjuk:
- június:
4 * 150 = 600 чел * час, - középső:
2 * 150 = 300 чел * час, - Senor:
150 чел * час.
Töltsön az első rendelkezésre álló junior (0, 1, 2) órát egy (x10, x20, x30), középső - (7, 15, 20), idősebb - (5, 10, 15) típusú helyszín fejlesztésére és telepítésére. ) órái élete legjobb időszakából.
Mint minden rendes igazgató, mi is maximalizálni akarjuk a havi nyereséget. A siker első lépése a célfüggvény feljegyzése value az előállított termékekből származó bevétel havi összegeként:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Ez nem hiba, a maximum keresésekor a célfüggvény az ellenkező előjellel minimalizálódik.
A következő lépés az, hogy megtiltjuk alkalmazottainknak a túlterheltséget, és korlátozzuk a munkaidőt:
Mi az egyenértékű:
ineq_cons = {'type': 'ineq',
'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2],
300 - 7 * x [0] - 15 * x [1] - 20 * x[2],
150 - 5 * x [0] - 10 * x [1] - 15 * x[2]])
}Formális megkötés, hogy a termékkibocsátás csak pozitív lehet:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])És végül a legrózsásabb feltevés, hogy az alacsony ár és a magas minőség miatt folyamatosan elégedett vásárlók sora áll felénk. A havi gyártási mennyiségeket magunk választhatjuk meg, a kényszerű optimalizálási probléma megoldása alapján scipy.optimize:
x0 = np.array([10, 10, 10])
res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds)
print(res.x)[7.85714286 5.71428571 3.57142857]Kerekítsünk lazán egész számokra, és számoljuk ki az evezősök havi terhelését optimális termékeloszlás mellett x = (8, 6, 3) :
- június:
8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час; - középső:
8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час; - Senor:
8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.
Következtetés: ahhoz, hogy a rendező megkapja a jól megérdemelt maximumát, optimális havonta 8 landing oldalt, 6 közepes méretű oldalt és 3 üzletet létrehozni. Ebben az esetben a szeniornak úgy kell szántania, hogy nem néz fel a gépről, a középsők terhelése megközelítőleg 2/3, a juniorok kevesebb mint fele.
Következtetés
A cikk felvázolja a csomaggal való munka alapvető technikáit scipy.optimize, feltételes minimalizálási problémák megoldására szolgál. Személy szerint én használom scipy pusztán akadémiai céllal, ezért is olyan komikus jellegű a felhozott példa.
Sok elmélet és virtuális példa található például I. L. Akulich „Matematikai programozás példákban és problémákban” című könyvében. Több hardcore alkalmazás scipy.optimize 3D-s struktúra felépítése képek halmazából () -ben megtekinthető .
A fő információforrás az azoknak, akik ennek és a többi résznek a fordításában kívánnak közreműködni scipy Isten hozott a .
Köszönöm a kiadvány elkészítésében való részvételért.
Forrás: will.com