Ang SciPy (binibigkas na sai pie) ay isang mathematical application package batay sa extension ng Numpy Python. Sa SciPy, ang iyong interactive na session ng Python ay magiging kaparehong kumpletong data science at complex system prototyping environment gaya ng MATLAB, IDL, Octave, R-Lab, at SciLab. Ngayon gusto kong maikling pag-usapan kung paano gumamit ng ilang kilalang algorithm ng pag-optimize sa package ng scipy.optimize. Ang mas detalyado at up-to-date na tulong sa paggamit ng mga function ay palaging makukuha gamit ang help() command o gamit ang Shift+Tab.
Pagpapakilala
Upang mailigtas ang iyong sarili at ang mga mambabasa mula sa paghahanap at pagbabasa ng mga pangunahing mapagkukunan, ang mga link sa mga paglalarawan ng mga pamamaraan ay pangunahing nasa Wikipedia. Bilang isang tuntunin, ang impormasyong ito ay sapat na upang maunawaan ang mga pamamaraan sa mga pangkalahatang tuntunin at ang mga kondisyon para sa kanilang aplikasyon. Upang maunawaan ang kakanyahan ng mga pamamaraang pangmatematika, sundin ang mga link sa mga mas makapangyarihang publikasyon, na makikita sa dulo ng bawat artikulo o sa iyong paboritong search engine.
Kaya, kasama sa scipy.optimize module ang pagpapatupad ng mga sumusunod na pamamaraan:
- Kondisyon at walang kundisyon na pag-minimize ng scalar function ng ilang variable (minim) gamit ang iba't ibang algorithm (Nelder-Mead simplex, BFGS, Newton conjugate gradients, и )
- Global optimization (halimbawa: , )
- Pag-minimize ng mga nalalabi (least_squares) at curve fitting algorithm gamit ang nonlinear least squares (curve_fit)
- Pag-minimize ng mga function ng scalar ng isang variable (minim_scalar) at paghahanap ng mga ugat (root_scalar)
- Multidimensional solvers ng system of equation (root) gamit ang iba't ibang algorithm (hybrid Powell, o malalaking pamamaraan tulad ng ).
Sa artikulong ito ay isasaalang-alang lamang namin ang unang item mula sa buong listahang ito.
Walang kundisyong pag-minimize ng isang scalar function ng ilang variable
Ang minim function mula sa scipy.optimize package ay nagbibigay ng pangkalahatang interface para sa paglutas ng kondisyonal at walang kondisyong pag-minimize ng mga problema ng scalar function ng ilang variable. Upang ipakita kung paano ito gumagana, kakailanganin namin ang isang angkop na function ng ilang mga variable, na aming i-minimize sa iba't ibang paraan.
Para sa mga layuning ito, ang Rosenbrock function ng N variable ay perpekto, na may anyo:
Sa kabila ng katotohanan na ang Rosenbrock function at ang Jacobi at Hessian matrice nito (ang una at pangalawang derivatives, ayon sa pagkakabanggit) ay tinukoy na sa scipy.optimize package, kami mismo ang tutukuyin.
import numpy as np
def rosen(x):
"""The Rosenbrock function"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Para sa kalinawan, iguhit natin sa 3D ang mga halaga ng Rosenbrock function ng dalawang variable.
Code ng pagguhit
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# Настраиваем 3D график
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# Задаем угол обзора
ax.view_init(45, 30)
# Создаем данные для графика
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]))
# Рисуем поверхность
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Alam nang maaga na ang pinakamababa ay 0 sa 
, tingnan natin ang mga halimbawa kung paano matukoy ang pinakamababang halaga ng Rosenbrock function gamit ang iba't ibang pamamaraan ng scipy.optimize.
Nelder-Mead simplex na pamamaraan
Hayaang magkaroon ng paunang punto x0 sa 5-dimensional na espasyo. Hanapin natin ang pinakamababang punto ng Rosenbrock function na pinakamalapit dito gamit ang algorithm (ang algorithm ay tinukoy bilang ang halaga ng parameter ng pamamaraan):
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)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 339
Function evaluations: 571
[1. 1. 1. 1. 1.]Ang simplex na paraan ay ang pinakasimpleng paraan upang mabawasan ang isang malinaw na tinukoy at medyo maayos na function. Hindi ito nangangailangan ng pagkalkula ng mga derivatives ng isang function; ito ay sapat na upang tukuyin lamang ang mga halaga nito. Ang paraan ng Nelder-Mead ay isang mahusay na pagpipilian para sa mga simpleng problema sa pag-minimize. Gayunpaman, dahil hindi ito gumagamit ng mga pagtatantya ng gradient, maaaring mas matagal bago mahanap ang minimum.
Paraan ng Powell
Ang isa pang algorithm ng pag-optimize kung saan ang mga halaga ng function lamang ang kinakalkula ay . Para magamit ito, kailangan mong itakda ang method = 'powell' sa minim function.
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)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 1622
[1. 1. 1. 1. 1.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm
Upang makakuha ng mas mabilis na convergence sa isang solusyon, ang pamamaraan gumagamit ng gradient ng layunin function. Maaaring tukuyin ang gradient bilang isang function o kalkulahin gamit ang mga pagkakaiba sa unang pagkakasunud-sunod. Sa anumang kaso, ang paraan ng BFGS ay karaniwang nangangailangan ng mas kaunting mga function na tawag kaysa sa simplex na paraan.
Hanapin natin ang derivative ng Rosenbrock function sa analytical form:
Ang expression na ito ay wasto para sa mga derivatives ng lahat ng mga variable maliban sa una at huli, na tinukoy bilang:
Tingnan natin ang function ng Python na kinakalkula ang gradient na ito:
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 derAng gradient na pagkalkula function ay tinukoy bilang ang halaga ng jac parameter ng minim function, tulad ng ipinapakita sa ibaba.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 25
Function evaluations: 30
Gradient evaluations: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Conjugate gradient algorithm (Newton)
Algorithm ay isang binagong pamamaraan ni Newton.
Ang pamamaraan ni Newton ay batay sa pagtatantya ng isang function sa isang lokal na lugar sa pamamagitan ng isang polynomial ng pangalawang degree:
saan 
ay ang matrix ng pangalawang derivatives (Hessian matrix, Hessian).
Kung ang Hessian ay positive definite, kung gayon ang lokal na minimum ng function na ito ay makikita sa pamamagitan ng equating ang zero gradient ng quadratic form sa zero. Ang magiging resulta ay ang expression:
Ang inverse Hessian ay kinakalkula gamit ang conjugate gradient method. Ang isang halimbawa ng paggamit ng paraang ito upang mabawasan ang pagpapaandar ng Rosenbrock ay ibinigay sa ibaba. Upang magamit ang paraan ng Newton-CG, dapat mong tukuyin ang isang function na kinakalkula ang Hessian.
Ang Hessian ng Rosenbrock function sa analytical form ay katumbas ng:
saan 
и 
, tukuyin ang matrix 
.
Ang natitirang di-zero na elemento ng matrix ay katumbas ng:
Halimbawa, sa isang limang-dimensional na espasyo N = 5, ang Hessian matrix para sa Rosenbrock function ay may anyo ng isang banda:
Code na kinakalkula ang Hessian na ito kasama ng code para sa pagliit ng Rosenbrock function gamit ang conjugate gradient (Newton) na paraan:
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)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 24
[1. 1. 1. 0.99999999 0.99999999]Isang halimbawa na may kahulugan ng product function ng Hessian at isang arbitrary vector
Sa mga problema sa totoong mundo, ang pag-compute at pag-iimbak ng buong Hessian matrix ay maaaring mangailangan ng makabuluhang oras at mga mapagkukunan ng memorya. Sa kasong ito, talagang hindi na kailangang tukuyin ang Hessian matrix mismo, dahil ang pamamaraan ng minimization ay nangangailangan lamang ng isang vector na katumbas ng produkto ng Hessian na may isa pang arbitrary na vector. Kaya, mula sa isang computational point of view, mas mainam na agad na tukuyin ang isang function na nagbabalik ng resulta ng produkto ng Hessian na may isang di-makatwirang vector.
Isaalang-alang ang hess function, na kumukuha ng minimization vector bilang unang argumento, at isang arbitrary vector bilang pangalawang argumento (kasama ang iba pang argumento ng function na i-minimize). Sa aming kaso, ang pagkalkula ng produkto ng Hessian ng Rosenbrock function na may isang di-makatwirang vector ay hindi napakahirap. Kung p ay isang di-makatwirang vector, pagkatapos ay ang produkto 
parang:
Ang function na kinakalkula ang produkto ng Hessian at isang arbitrary vector ay ipinapasa bilang ang halaga ng hessp argument sa minimize function:
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})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 66Conjugate gradient trust region algorithm (Newton)
Ang mahinang pagkondisyon ng Hessian matrix at maling mga direksyon sa paghahanap ay maaaring maging sanhi ng hindi epektibong conjugate gradient algorithm ng Newton. Sa ganitong mga kaso, ang kagustuhan ay ibinibigay sa (trust-region) conjugate Newton gradients.
Halimbawa na may kahulugan ng Hessian matrix:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 19
[1. 1. 1. 1. 1.]Halimbawa sa product function ng Hessian at isang arbitrary vector:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 0
[1. 1. 1. 1. 1.]Mga pamamaraan ng uri ng Krylov
Tulad ng paraan ng trust-ncg, ang mga pamamaraang Krylov-type ay angkop para sa paglutas ng malalaking problema dahil gumagamit lamang sila ng mga produktong matrix-vector. Ang kanilang kakanyahan ay upang malutas ang isang problema sa isang rehiyon ng kumpiyansa na limitado ng isang pinutol na subspace ng Krylov. Para sa hindi tiyak na mga problema, mas mainam na gamitin ang pamamaraang ito, dahil gumagamit ito ng mas maliit na bilang ng mga nonlinear na pag-ulit dahil sa mas maliit na bilang ng mga produkto ng matrix-vector sa bawat subproblem, kumpara sa paraan ng trust-ncg. Bilang karagdagan, ang solusyon sa quadratic subproblem ay matatagpuan nang mas tumpak kaysa sa paggamit ng trust-ncg method.
Halimbawa na may kahulugan ng Hessian matrix:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 18
print(res.x)
[1. 1. 1. 1. 1.]
Halimbawa sa product function ng Hessian at isang arbitrary vector:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algorithm para sa tinatayang solusyon sa rehiyon ng kumpiyansa
Ang lahat ng mga pamamaraan (Newton-CG, trust-ncg at trust-krylov) ay angkop para sa paglutas ng mga malalaking problema (na may libu-libong mga variable). Ito ay dahil sa ang katunayan na ang pinagbabatayan na conjugate gradient algorithm ay nagpapahiwatig ng isang tinatayang pagpapasiya ng inverse Hessian matrix. Ang solusyon ay matatagpuan nang paulit-ulit, nang walang tahasang pagpapalawak ng Hessian. Dahil kailangan mo lang tukuyin ang isang function para sa produkto ng isang Hessian at isang arbitrary na vector, ang algorithm na ito ay lalong mabuti para sa pagtatrabaho sa mga kalat-kalat (band diagonal) na matrice. Nagbibigay ito ng mababang gastos sa memorya at makabuluhang pagtitipid sa oras.
Para sa mga katamtamang laki ng mga problema, ang halaga ng pag-iimbak at pag-factor ng Hessian ay hindi kritikal. Nangangahulugan ito na posibleng makakuha ng solusyon sa mas kaunting mga pag-ulit, na malulutas ang mga subproblema ng rehiyon ng pinagkakatiwalaan nang halos eksakto. Upang gawin ito, ang ilang mga nonlinear na equation ay inaayos nang paulit-ulit para sa bawat quadratic subproblem. Ang ganitong solusyon ay karaniwang nangangailangan ng 3 o 4 na Cholesky decompositions ng Hessian matrix. Bilang resulta, ang pamamaraan ay nagtatagpo sa mas kaunting mga pag-ulit at nangangailangan ng mas kaunting mga pagkalkula ng layunin ng function kaysa sa iba pang ipinatupad na mga pamamaraan ng rehiyon ng kumpiyansa. Ang algorithm na ito ay nagpapahiwatig lamang ng pagpapasiya ng kumpletong Hessian matrix at hindi sumusuporta sa kakayahang gamitin ang product function ng Hessian at isang arbitrary na vector.
Halimbawa sa pag-minimize ng Rosenbrock function:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization terminated successfully.
Current function value: 0.000000
Iterations: 13
Function evaluations: 14
Gradient evaluations: 13
Hessian evaluations: 14
array([1., 1., 1., 1., 1.])Malamang titigil na tayo diyan. Sa susunod na artikulo, susubukan kong sabihin ang mga pinaka-kagiliw-giliw na bagay tungkol sa conditional minimization, ang aplikasyon ng minimization sa paglutas ng mga problema sa approximation, pagliit ng function ng isang variable, arbitrary minimizers, at paghahanap ng mga ugat ng isang sistema ng mga equation gamit ang scipy.optimize. pakete.
Pinagmulan:
Pinagmulan: www.habr.com
