A SciPy (ejtsd: sájt páj) egy numpy alapú matematikai csomag, amely C és Fortran könyvtárakat is tartalmaz. A SciPy-val az interaktív Python munkamenet egy teljes értékű adatfeldolgozó környezetté alakul, mint például a MATLAB, IDL, Octave, R vagy SciLab.
Ebben a cikkben a matematikai programozás alapvető módszereit vizsgáljuk — a több változós skáláris függvények feltételes optimalizálási feladatait a scipy.optimize csomag segítségével. A feltétel nélküli optimalizálási algoritmusokat már tárgyaltuk önállóan. . A scipy funkcióinak részletes és aktuális áttekintését mindig elérhetjük a help() parancs, Shift+Tab vagy a .
Bevezetés
A feltételes és feltétel nélküli optimalizálási feladatok megoldásához az scipy.optimize csomagban közös interfészt biztosít a minimize(). Azonban tudvalevő, hogy nincs univerzális módszer minden feladat megoldására, ezért a megfelelő módszer kiválasztása mindig a kutató vállára nehezedik.
A megfelelő optimalizálási algoritmus a funkció minimize(..., method="").
argumentumával adható meg. A több változós feltételes optimalizáláshoz a következő módszerek megvalósítása érhető el:
trust-constr— lokális minimum keresés a bizalmi zónában. , ;SLSQP— korlátozásokkal rendelkező sorozatos kvadratikus programozás, Lagrange-rendszer megoldásának Newton-módszere. .TNC— Truncated Newton Constrained, korlátozott számú iteráció, jól alkalmazható nagy számú független változóval rendelkező nemlineáris függvényekhez. .L-BFGS-B— a Broyden-Fletcher-Goldfarb-Shanno négyes módszere, amely csökkentett memóriafogyasztással valósul meg a Hess-mátrix vektorainak részleges betöltésével. , .COBYLA— COBYLA Constrained Optimization By Linear Approximation, korlátozott optimalizálás lineáris közelítéssel (gradiens számítása nélkül). .
A választott módszertől függően különböző módon kell megadni a feladat megoldásának feltételeit és korlátait:
- a
Boundsosztály példányaként, a L-BFGS-B, TNC, SLSQP, trust-constr módszerekhez; - listaként
(min, max)a szintén L-BFGS-B, TNC, SLSQP, trust-constr módszerekhez; - példányokból vagy példányok listájaként
LinearConstraint,NonlinearConstrainta COBYLA, SLSQP, trust-constr módszerekhez; - szótárként vagy szótárak listájaként
{'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt}a COBYLA, SLSQP módszerekhez.
A cikk terve:
1) Vizsgáljuk meg a feltételes optimalizálási algoritmus alkalmazását a bizalmi térben (method=»trust-constr») olyan korlátokkal, amelyeket objektumokként adtunk meg. Bounds, LinearConstraint, NonlinearConstraint ;
2) Vizsgáljuk meg a legkisebb négyzetek módszerével (method=»SLSQP») történő soros programozást, amely a korlátozásokat szótár formájában adja meg. {'type', 'fun', 'jac', 'args'};
3) Elemezzünk egy példát a termelési optimalizálásra egy webstúdió esetén.
Feltételes optimalizálás method=»trust-constr»
A módszer megvalósítása trust-constr RabbitMQ-server egyenlőségi korlátokkal és továbbá olyan korlátozásokkal, amelyek nemegyenlőségeket tartalmaznak. Mindkét módszer a lokális minimum keresésének algoritmusával van megvalósítva a bizalmi térben, és jól alkalmazható nagy léptékű feladatokra.
A minimum keresésének matematikai megfogalmazása általános formában:
Szigorú egyenlőség esetén az alsó határ megegyezik a felső határral. 
.
Egységes korlátozás esetén a felső vagy az alsó határ megállapításra kerül. np.inf a megfelelő jellel.
Tegyük fel, hogy meg kell találni a Rosenbrock-függvény minimumát két változó esetén:
Ehhez a függvény értelmezési tartományán a következő korlátozások adottak:
A mi esetünkben egyetlen megoldás van az 
pontban, amely esetben csak az első és negyedik korlátozás érvényes.
Haladjunk a korlátozásokon alulról felfelé, és nézzük meg, hogyan rögzíthetjük ezeket a scipy-ban.
Korlátozások 
és 
határozzuk meg a Bounds objektum segítségével.
from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])Korlátozások 
és 
írjuk le lineáris formában:
Határozzuk meg ezeket a korlátozásokat LinearConstraint objektum formájában:
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 korlátozás mátrix formában:
Határozzuk meg a Jakobitáblát e korlátozás számára, és a Hess-mátrix lineáris kombinációját egy tetszőleges vektorral. 
:
Most a nemlineáris korlátozást definiálhatjuk, mint 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átrixokat ritkított formában is megadhatjuk:
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 mint objektum LinearOperator:
a 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)Amikor a Hesse-mátrix számítása 
nagy költségeket igényel, a következő osztályt használhatjuk: . A következő stratégiák állnak rendelkezésre: BFGS és SR1.
a scipy.optimize import BFGS
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())A Hesse-mátrix szintén kiszámítható végső eltérések segítségével:
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac='2-point', hess='2-point')A Jakobi-mátrix korlátozásokra is kiszámítható végső eltérések segítségével. Azonban ebben az esetben a Hesse-mátrix végső eltérésekkel már nem számítható ki. A Hesse-mátrixot funkcionalitásként vagy a HessianUpdateStrategy osztály segítségével kell definiálni.
nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac='2-point', hess=BFGS())Az optimalizálási feladat megoldása a következőképpen néz ki:
a scipy.optimize import minimize
a 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` leállítási feltétel teljesítve.
Iterációk száma: 12, funkciók értékelése: 8, CG iterációk: 7, optimális: 2.99e-09, korlátozások megsértése: 1.11e-16, végrehajtási idő: 0.033 s.
[0.41494531 0.17010937]Szükség esetén a Hesse-mátrix számító funkciót a LinearOperator osztály segítségével definiálhatja.
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 Hesse-mátrix és egy tetszőleges vektor szorzataként a 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ált függvény első és második deriváltját közelítőleg is kiszámíthatja. Például a Hesse-mátrix közelíthető a SR1 (kvázi-Newton közelítés) segítségével. A gradiens végső eltérések segítségével 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)Kondicionális optimalizálás method='SLSQP'
Az SLSQP módszer a funkció minimális értékének meghatározására szolgál a következő formában:
Ahol 
és 
– kifejezések indexeinek halmaza, amelyek korlátozásokat egyenlőségek vagy egyenlőtlenségek formájában írnak le. 
– alsó és felső határok halmaza a függvény értelmezési tartományára vonatkozóan.
A lineáris és nemlineáris korlátozások szótárformában vannak megadva, kulcsokkal type, . Új és 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ő módon 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)Az optimalizálás sikeresen befejeződött. (Kilépési mód: 0)
Jelenlegi függvényérték: 0.34271757499419825
Iterációk: 4
Függvénykiértékelések: 5
Gradienskiértékelések: 4
[0.41494475 0.1701105 ]Optimalizálási példa
Az ötödik technológiai rendszerre való átmenet kapcsán vegyük szemügyre a termelés optimalizálását egy olyan webstúdió példáján, amely kis, de stabil bevételt hoz számunkra. Képzeljük el, hogy a galéria igazgatói vagyunk, ahol háromféle terméket állítanak elő:
- x0 – értékesítő landing oldalak, 10 ezer ft-tól.
- x1 – vállalati weboldalak, 20 ezer ft-tól.
- x2 – internetes boltok, 30 ezer ft-tól.
Baráti munkacsoportunk négy juniorból, két midből és egy szeniorból áll. A havi munkaidő alapja:
- juniorok:
4 * 150 = 600 főóra, - midlek:
2 * 150 = 300 főóra, - szenior:
150 főóra.
Tételezzük fel, hogy egy (x0, x1, x2) típusú weboldal fejlesztésére és telepítésére az első szembe jövő juniornak (10, 20, 30) órát kell eltöltenie, a midnek – (7, 15, 20), a seniornak – (5, 10, 15) a legjobb éveiből.
Mint bármely normális igazgatónak, nekünk is maximalizálnunk kell a havi profitot. Az első lépés a siker felé: felírjuk a célfüggvényt érték mint a hónap során előállított termékekből származó bevételek összegét:
def value(x):
return - 10*x[0] - 20*x[1] - 30*x[2]Ez nem hiba, mivel a célfüggvény keresésekor a maximális értéket fordított előjellel minimalizáljuk.
A következő lépés: megtiltjuk dolgozóink számára a túlmunkát, és korlátozzuk a munkaidő keretet:
Ami ekvivalens:
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]])
}A formai korlátozás az, hogy a termék előállítása csak pozitív lehet:
bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])És végül a legkedvezőbb feltétel – a kedvező ár és a magas minőség miatt folyamatosan sorban állnak a boldog ügyfelek. Mi magunk is választhatjuk meg a havi termelési mennyiségeket, a feltételes optimalizáló feladat 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]Durván kerekítsük egész számra, és számoljuk ki a csónakosok havi terhelését az optimális termelési elrendezés mellett x = (8, 6, 3) :
- juniorok:
8 * 10 + 6 * 20 + 3 * 30 = 290 fő * óra; - midlek:
8 * 7 + 6 * 15 + 3 * 20 = 206 fő * óra; - szenior:
8 * 5 + 6 * 10 + 3 * 15 = 145 fő * óra.
Következtetés: hogy a direktor megkapja a megérdemelt maximumot, optimális havi 8 landing page, 6 közepes weboldal és 3 bolt készítése. A seniornak ebben az esetben folyamatosan dolgoznia kell, a middles terhelése körülbelül 2/3, a juniors ez alatt marad.
Zárás
A cikk bemutatja a csomaggal való munka főbb módszereit scipy.optimize, amelyeket a feltételes minimizálási feladatok megoldásához használunk. Személy szerint én használom scipy tisztán akadémiai célokra, ezért a bemutatott példa ilyen humoros jelleget ölt.
Sok elmélet és zip fájl példák található például I.L. Akulich könyvében "Matematikai programozás példákban és feladatokban". A hardcore alkalmazás scipy.optimize 3D struktúra létrehozására képekből () a .
Fő információforrás – , akik szeretnének hozzájárulni ennek és más szakaszok fordításához scipy üdvözöljük a .
Köszönöm a publikáció elkészítésében való részvételért.
Forrás: habr.com
