SciPy (izrunÄ kÄ 'sai pai') ir pielietoto matemÄtisko procedÅ«ru pakete, kas balstÄ«ta uz Numpy Python paplaÅ”inÄjuma. Ar SciPy mijiedarbÄ«bas sesija Python pÄrvÄrÅ”as pilnvÄrtÄ«gÄ datu apstrÄdes un sarežģītu sistÄmu prototipÄÅ”anas vidÄ, lÄ«dzÄ«gi kÄ MATLAB, IDL, Octave, R-Lab un SciLab. Å odien es vÄlos Ä«si pastÄstÄ«t par to, kÄ vajadzÄtu piemÄrot dažus pazÄ«stamus optimizÄcijas algoritmus paketÄ scipy.optimize. SÄ«kÄku un aktuÄlÄku informÄciju par funkciju izmantoÅ”anu var vienmÄr iegÅ«t, izmantojot komandu help() vai Shift+Tab.
Ievads
Lai atbrÄ«votos no veltÄ«gas laika tÄrÄÅ”anas sev un lasÄ«tÄjiem, saites uz metožu aprakstiem bÅ«s galvenokÄrt uz VikipÄdiju. Parasti Ŕīs informÄcijas pietiek, lai izprastu metodes vispÄrÄ«gÄs iezÄ«mes un to pielietoÅ”anas apstÄkļus. Lai saprastu matemÄtisko metožu bÅ«tÄ«bu, pÄrvietojamies uz saiknÄm uz autoritatÄ«vÄkÄm publikÄcijÄm, kuras var atrast katras raksta beigÄs vai savÄ iecienÄ«tajÄ meklÄtÄjÄ.
TÄtad, modulis scipy.optimize ietver Å”Ädu procedÅ«ru Ä«stenoÅ”anu:
- NosacÄ«tÄ un beznosacÄ«juma minimizÄcija skalarfunkcijÄm ar vairÄkiem mainÄ«gajiem (minim) dažÄdu algoritmu (Neldera-Mida simplex, BFGS, Å Å«tona konjugÄto gradientu) palÄ«dzÄ«bu, un )
- GlobÄlÄ optimizÄcija (piemÄram: , )
- MinimizÄcija atliekÄm (least_squares) un nelineÄro MNM (curve_fit) algoritmi
- MinimizÄcija skalarfunkcijÄm ar vienu mainÄ«go (minim_scalar) un sakÅu meklÄÅ”ana (root_scalar)
- DaudzdimensionÄlie vienÄdojumu risinÄtÄji (root), izmantojot dažÄdus algoritmus (hipbridais Pauels, vai masveida metodes, piemÄram, ).
Å ajÄ rakstÄ aplÅ«kosim tikai pirmo punktu no visa Ŕī saraksta.
BeznosacÄ«jumu minimizÄcija skalarfunkcijai ar vairÄkiem mainÄ«gajiem
Funkcija minim no paketes scipy.optimize nodroÅ”ina vispÄrÄju interfeisu skalarfunkciju ar vairÄkiem mainÄ«gajiem nosacÄ«tÄs un beznosacÄ«juma minimizÄcijas uzdevumu risinÄÅ”anai. Lai demonstrÄtu tÄs darbÄ«bu, mums bÅ«s nepiecieÅ”ama piemÄrota funkcija ar vairÄkiem mainÄ«gajiem, kuru mÄs dažÄdi minimizÄsim.
Å iem nolÅ«kiem lieliski derÄs Rozemberga funkcija no N mainÄ«gajiem, kas ir Å”Äda:
Neskatoties uz to, ka Rozebrokas funkcija un tÄs JÄkobi un Hess matriks (pirmÄ un otrÄ atvasinÄjums attiecÄ«gi) jau ir definÄti paketÄ scipy.optimize, noskaidrosim to paÅ”i.
import numpy as np
def rosen(x):
"""Rozebrokas funkcija"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Lai parÄdÄ«tu, attÄlosim 3D Rozebrokas funkcijas vÄrtÄ«bas no divÄm mainÄ«gajÄm.
Kods attÄloÅ”anai
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# IestatÄm 3D grafiku
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# NorÄdÄm skatÄ«juma leÅÄ·i
ax.view_init(45, 30)
# Izveidojam datus grafikam
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))
# ZÄ«mÄjam virsmu
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Zinot iepriekÅ”, ka minimums ir 0 pie 
, aplÅ«kosim piemÄrus, kÄ noteikt Rozebrokas funkcijas minimÄlo vÄrtÄ«bu, izmantojot dažÄdas procedÅ«ras scipy.optimize.
Nelder-Mead simpliksa metode
PieÅemot, ka ir sÄkumpunkts x0 5 dimensiju telpÄ. Atrast tuvÄko minimuma punktu Rozebrokas funkcijai, izmantojot algoritmu (algoritms norÄdÄ«ts kÄ parametra method vÄrtÄ«ba):
from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
options={'xtol': 1e-8, 'disp': True})
print(res.x)OptimizÄcija veiksmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 339
Funkciju novÄrtÄjumi: 571
[1. 1. 1. 1. 1.]Simpliksa metode ir visvienkÄrÅ”Äkais veids, kÄ minimizÄt skaidri definÄtu un diezgan gludu funkciju. TÄ neprasa funkcijas atvasinÄjumu aprÄÄ·inÄÅ”anu, pietiek tikai norÄdÄ«t tÄs vÄrtÄ«bas. Nelder-Mead metode ir laba izvÄle vienkÄrÅ”Äm minimizÄcijas uzdevumiem. TomÄr, jo tÄ neizmanto gradienta novÄrtÄjumus, minimuma atraÅ”anai var bÅ«t nepiecieÅ”ams vairÄk laika.
Pauela metode
Cits optimizÄcijas algoritms, kurÄ tiek aprÄÄ·inÄtas tikai funkciju vÄrtÄ«bas, ir Lai to izmantotu, nepiecieÅ”ams noregulÄt method = 'powell' funkcijÄ minim.
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
options={'xtol': 1e-8, 'disp': True})
print(res.x)OptimizÄcija veiksmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 19
Funkciju novÄrtÄjumi: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) algoritms
Lai sasniegtu ÄtrÄku konverÄ£enci uz risinÄjumu, procedÅ«ra izmanto mÄrÄ·a funkcijas gradientu. Gradientu var norÄdÄ«t kÄ funkciju vai aprÄÄ·inÄt, izmantojot pirmÄs kÄrtas atŔķirÄ«bas. JebkurÄ gadÄ«jumÄ BFGS metode parasti prasa mazÄk funkciju izsaukumu nekÄ simplex metode.
ApskatÄ«sim RÅzenbroka funkcijas atvasinÄjumu analÄ«tiskÄ veidÄ:
Å is izteikums ir spÄkÄ visÄm mainÄ«gajÄm atvasinÄjumiem, izÅemot pirmo un pÄdÄjo, kuras tiek noteiktas Å”Ädi:
PÄrbaudÄ«sim Python funkciju, kas aprÄÄ·ina Å”o gradientu:
def rosen_der (x):
xm = x [1: -1]
xm_m1 = x [: - 2]
xm_p1 = x [2:]
der = np.zeros_like (x)
der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
der [-1] = 200 * (x [-1] -x [-2] ** 2)
return derGradienta aprÄÄ·inÄÅ”anas funkcija tiek norÄdÄ«ta kÄ parametra jac vÄrtÄ«ba funkcijÄ minim, kÄ parÄdÄ«ts zemÄk.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)OptimizÄcija veiksmÄ«gi beigusies.
PaÅ”reizÄjÄ funkcionÄlÄ vÄrtÄ«ba: 0.000000
IterÄcijas: 25
Funkciju novÄrtÄjumi: 30
Gradienta novÄrtÄjumi: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]KopÄjo gradientu algoritms (Å Å«tona)
Algoritms ir modificÄtÄ Å
Å«tona metode.
Å
Å«tona metode balstÄs uz funkcijas apmÄram lokÄlÄ apgabalÄ ar otrÄ Å”Ä·irÄ«bas polinomu:
kur 
ir otro atvasinÄjumu matrica (Hesse matrica, hesians).
Ja hesians ir pozitÄ«vi noteikts, tad lokÄlo minimumu var atrast, pielÄgojot nulles gradienta kvadrÄtveida formu nullei. RezultÄtÄ iegÅ«sim izteikumu:
ApmainÄ«tais hesians tiek aprÄÄ·inÄts, izmantojot kopÄjo gradientu metodi. ZemÄk ir piemÄrs, kÄ izmantot Å”o metodi RÅzenbroka funkcijas minimizÄcijai. Lai izmantotu Newton-CG metodi, ir jÄnorÄda funkcija, kas aprÄÄ·ina hesianu.
RÅzenbroka funkcijas hesians analÄ«tiskÄ veidÄ ir:
kur 
un 
, nosaka matricu 
.
PÄrÄjie nenulles elementu matrica ir:
PiemÄram, piecu dimensiju telpÄ N = 5, Hesse matrica RÅzenbroka funkcijai ir joslas veidÄ:
Kods, kas aprÄÄ·ina Å”o hesianu kopÄ ar kodu RÅzenbroka funkcijas minimizÄcijai, izmantojot kopÄjo gradientu metodi (Å Å«tona):
def rosen_hess(x):
x = np.asarray(x)
H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
diagonal = np.zeros_like(x)
diagonal[0] = 1200*x[0]**2-400*x[1]+2
diagonal[-1] = 200
diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
H = H + np.diag(diagonal)
return H
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hess=rosen_hess,
options={'xtol': 1e-8, 'disp': True})
print(res.x)OptimizÄcija tika veiksmÄ«gi pabeigta.
EsoÅ”Ä funkcionÄlÄ vÄrtÄ«ba: 0.000000
IterÄcijas: 24
Funkciju novÄrtÄjumi: 33
Gradienta novÄrtÄjumi: 56
HesiÄna novÄrtÄjumi: 24
[1. 1. 1. 0.99999999 0.99999999]PiemÄrs ar HesiÄna funkcijas un jauka vektora noteikÅ”anu
ReÄlÄs problÄmÄs HesiÄna matricas aprÄÄ·ins un saglabÄÅ”ana var prasÄ«t ievÄrojamus laika un atmiÅas resursus. TÄdÄjÄdi faktiski nav nepiecieÅ”ams noteikt paÅ”u HesiÄna matricu, jo minimizÄÅ”anas procedÅ«rai nepiecieÅ”ams tikai vektors, kas ir HesiÄna reizinÄjums ar citu jauku vektoru. TÄdÄjÄdi, no aprÄÄ·inu viedokļa, daudz gaidÄmÄka ir tÅ«lÄ«tÄja funkcijas noteikÅ”ana, kas atgriež HesiÄna reizinÄjuma rezultÄtu ar jauku vektoru.
ApskatÄ«sim funkciju hess, kas pieÅem minimizÄÅ”anas vektoru kÄ pirmo argumentu un jauku vektoru kÄ otro argumentu (kopÄ ar citiem minimizÄjamÄs funkcijas argumentiem). MÅ«su gadÄ«jumÄ aprÄÄ·inÄt HesiÄna reizinÄjumu ar funkciju Rosenbrock nav pÄrÄk sarežģīti. Ja p ā jauks vektors, tad reizinÄjums 
ir Å”Äds:
Funkcija, kas aprÄÄ·ina HesiÄna un jauka vektora reizinÄjumu, tiek nodota kÄ argumenta hessp vÄrtÄ«ba funkcijai minimize:
def rosen_hess_p(x, p):
x = np.asarray(x)
Hp = np.zeros_like(x)
Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1]
-400*x[1:-1]*p[2:]
Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
return Hp
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hessp=rosen_hess_p,
options={'xtol': 1e-8, 'disp': True})
OptimizÄcija tika veiksmÄ«gi pabeigta.
EsoÅ”Ä funkcionÄlÄ vÄrtÄ«ba: 0.000000
IterÄcijas: 24
Funkciju novÄrtÄjumi: 33
Gradienta novÄrtÄjumi: 56
HesiÄna novÄrtÄjumi: 66UzticÄ«bas reÄ£iona (trust region) konjugÄto gradientu (Newton) algoritms
Slikta HesiÄna matricas nosegtÄ«ba un nepareizi meklÄÅ”anas virzieni var izraisÄ«t Newton konjugÄto gradientu algoritmu neefektÄ«vu. Å Ädos gadÄ«jumos priekÅ”roka tiek dota (trust-region) konjugÄto gradientu Newton algoritmam.
PiemÄrs ar HesiÄna matricas noteikÅ”anu:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)OptimizÄcija sekmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 20
Funkciju novÄrtÄjumi: 21
Gradientu novÄrtÄjumi: 20
Hesiena novÄrtÄjumi: 19
[1. 1. 1. 1. 1.]PiemÄrs ar hesiena funkcijas un nejauÅ”a vektora reizinÄjumu:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)OptimizÄcija sekmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 20
Funkciju novÄrtÄjumi: 21
Gradientu novÄrtÄjumi: 20
Hesiena novÄrtÄjumi: 0
[1. 1. 1. 1. 1.]Krylov tipu metodes
LÄ«dzÄ«gi kÄ trust-ncg metode, Krylov tipu metodes ir labi piemÄrotas lielo uzdevumu risinÄÅ”anai, jo tÄm tiek izmantotas tikai matricas-vektoru reizinÄjumi. TÄs bÅ«tÄ«ba ir uzdevuma risinÄÅ”ana uzticÄ«bas jomÄ, kas ierobežota ar Krylov trÄ«sdaļu apakÅ”telpu. NeizmantotÄm problÄmÄm Ŕī metode ir labÄkÄ izvÄle, jo tÄ izmanto mazÄk nelineÄru iterÄciju, pateicoties mazÄkam matricas-vektoru reizinÄjumu skaitam vienai apakÅ”uzdevumam, salÄ«dzinot ar trust-ncg metodi. TurklÄt kvadrÄtiskÄ apakÅ”uzdevuma risinÄjums tiek iegÅ«ts precÄ«zÄk nekÄ ar trust-ncg metodi.
PiemÄrs ar HesiÄna matricas noteikÅ”anu:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
OptimizÄcija sekmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 19
Funkciju novÄrtÄjumi: 20
Gradientu novÄrtÄjumi: 20
Hesiena novÄrtÄjumi: 18
print(res.x)
[1. 1. 1. 1. 1.]
PiemÄrs ar hesiena funkcijas un nejauÅ”a vektora reizinÄjumu:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
OptimizÄcija sekmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 19
Funkciju novÄrtÄjumi: 20
Gradientu novÄrtÄjumi: 20
Hesiena novÄrtÄjumi: 0
print(res.x)
[1. 1. 1. 1. 1.]
UzticÄ«bas jomÄ iegÅ«tÄ risinÄjuma algoritms
Visas metodes (Newton-CG, trust-ncg un trust-krylov) ir labi piemÄrotas lielo uzdevumu risinÄÅ”anai (ar tÅ«kstoÅ”iem mainÄ«go). Tas ir saistÄ«ts ar to, ka tÄs pamats ir otru gradientu algoritms, kas nozÄ«mÄ galÄ«go Hesiena apgriezto matricas meklÄÅ”anu. RisinÄjums nonÄk pakÄpeniski, neveicot skaidru hesiena sadalÄ«jumu. TÄ kÄ ir jÄnosaka tikai funkcija hesiena un nejauÅ”a vektora reizinÄÅ”anai, Å”is algoritms ir Ä«paÅ”i labs, strÄdÄjot ar retÄm (slÄÅveida diagonÄlÄm) matricÄm. Tas nodroÅ”ina zemu atmiÅas patÄriÅu un bÅ«tisku laika ietaupÄ«jumu.
VidÄja lieluma uzdevumos uzglabÄÅ”anas un Hessiana faktorizÄcijas izmaksas nav izŔķiroÅ”as. Tas nozÄ«mÄ, ka risinÄjumu var iegÅ«t mazÄkÄ iterÄciju skaitÄ, gandrÄ«z precÄ«zi atrisinot uzticÄ«bas reÄ£iona apakÅ”uzdevumus. TÄdÄjÄdi daži nelineÄrie vienÄdojumi tiek atrisinÄti iteratÄ«vi katram kvadrÄtiskajam apakÅ”uzdevumam. Å Äds risinÄjums parasti prasa 3 vai 4 Holeska matricas dekompozÄ«cijas. RezultÄtÄ metode konverÄ£Ä mazÄkÄ iterÄciju skaitÄ un prasa mazÄk mÄrÄ«jumu no mÄrÄ·a funkcijas, nekÄ citi Ä«stenotie uzticÄ«bas reÄ£iona algoritmi. Å is algoritms paredz tikai pilnas Hessiana matricas noteikÅ”anu un neatbalsta iespÄju izmantot Hessiana un nejauÅ”a vektora reizinÄjumu.
PiemÄrs ar Rozenbroka funkcijas minimizÄÅ”anu:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimizÄcija veiksmÄ«gi pabeigta.
PaÅ”reizÄjÄ funkcijas vÄrtÄ«ba: 0.000000
IterÄcijas: 13
Funkciju novÄrtÄjumi: 14
Gradienta novÄrtÄjumi: 13
Hessiana novÄrtÄjumi: 14
array([1., 1., 1., 1., 1.])Uz Å”o, domÄju, apstÄsimies. NÄkamajÄ rakstÄ centÄ«Å”os pastÄstÄ«t interesantÄko par nosacÄ«tu minimizÄciju, minimizÄcijas pielietojumu aptuvenoÅ”anu risinÄÅ”anÄ, vienas mainÄ«gÄs funkcijas minimizÄciju, dažÄdiem minimizatoriem un sistÄmas vienÄdojumu sakÅu meklÄÅ”anu, izmantojot scipy.optimize pakotni.
Avots:
Avots: habr.com
Russian
Italian
German
Polish
Estonian
Albanian
Bulgarian
Croatian
Czech
Danish
Dutch
English
French
Hungarian
Latvian
Norwegian
Portuguese
Romanian
Slovak
Slovenian
Spanish
Swedish